昨天狀態(tài)不是很好，沒做出幾個題，回到宿舍很早就睡了，今早4點半突然醒了,再也睡不著了，穿上衣服，簡單洗刷之后就來到了圖書館...
打開Chrome，進(jìn)入訓(xùn)練場，看到了這個：

梁延杰

馬鴻儒

我去，原來大家都這么努力，他倆一般是12點多剛打完球，然后平時1點還在補(bǔ)題...

不說了，肝！

今早，冷靜下來，思考了當(dāng)時沒做出來的題，原來其實都那么“水”
這里提幾個相對難一些的題目的題解，其它題可以私聊我QQ
只是相對難，其實還是蠻水的（逃...

問題 B：第N個智慧數(shù)

據(jù)說這個題，咱們隊不約而同的打表，怪我...
不知道中石油張老師，看到我們工大的代碼會怎么想...可怕...

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
int n;
int num[200] = {3, 5, 7, 8, 9, 11, 12, 13, 15, 16, 17, 19, 20, 21, 23, 24, 25, 27, 28, 29, 31, 32, 33, 35, 36, 37, 39, 40, 41, 43, 44, 45, 47, 48, 49, 51, 52, 53, 55, 56, 57, 59, 60, 61, 63, 64, 65, 67, 68, 69, 71, 72, 73, 75, 76, 77, 79, 80, 81, 83, 84, 85, 87, 88, 89, 91, 92, 93, 95, 96, 97, 99, 100, 101, 103, 104, 105, 107, 108, 109, 111, 112, 113, 115, 116, 117, 119, 120, 121, 123, 124, 125, 127, 128, 129, 131, 132, 133, 135, 136, 137};
int main()
{
    cin >> n;
    cout << num[n - 1];
    return 0;
}

問題 G：分割繩子

• 二分例題，套用我講的二分模板就行
• 注意，這里變換區(qū)間的時候不是Left = mid + 1；而是Left = mid + 0.001；精度問題
• 其他地方也沒得說，注意借用此題再鞏固一下自己腦海中的二分思想

#include <iostream>
#include <algorithm>
using namespace std;
double rope[1005];
int n, m;
double ans;
double mxn;
double l, r;
bool ansok(double k)
{
    int s = 0;
    for (int i = 0; i < n; i++)
    {
        s += rope[i] / k;
    }
    if (s >= m)
        return true;
    else
        return false;
}
int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i++)
    {
        cin >> rope[i];
        mxn = max(mxn, rope[i]);
    }
    l = 0;
    r = mxn;
    while (l <= r)
    {
        double mid = (l + r) / 2;
        if (ansok(mid))
        {
            l = mid + 0.001;
            ans = mid;
        }
        else
            r = mid - 0.001;
    }
    printf("%.2f", ans);
    return 0;
}

問題 K: 單純質(zhì)因數(shù)

• 這個題很多同學(xué)想打表，其實不用，看著數(shù)據(jù)，直接算應(yīng)該沒問題，我試了試，果然沒問題
• 把一個數(shù) num 分解質(zhì)因數(shù)，同時質(zhì)因數(shù)去重累乘得到 S 看 S 是否與sum相同，如果相同就表示這是一個單純質(zhì)因數(shù)

#include <iostream>
#include <cmath>
using namespace std;
bool isp(int num)
{
    if (num == 1)
        return 0;
    if (num < 4)
        return 1;
    for (int i = 2; i <= sqrt(num); i++)
        if (num % i == 0)
            return 0;
    return 1;
}
bool isok(int num)
{
    int ok = 0;
    int s = 1;
    if (num < 6)
        return false;
    for (int i = 2; i <= sqrt(num); i++)//將此數(shù)分解質(zhì)因數(shù)
    {
        if (num % i == 0)
        {
            ok = 1;
            if (isp(i))
                s *= i;
            if ((num / i != i) && isp(num / i))
                s *= (num / i);
        }
    }
    if (s == num)//s是累乘結(jié)果
        return 1;
    else
        return 0;
}
int main()
{
    int n;
    cin >> n;
    for (int i = 6; i <= n; i++)
        if (isok(i))
            printf("%d ", i);
    return 0;
}

問題 L: 安裝飲水機(jī)

• 這個題剛開始我想用二分...后來仔細(xì)一想大概不是，直接貪心就好，
• 貪心思想，每次安裝飲水機(jī)都安裝在當(dāng)前觀察員能到達(dá)的遠(yuǎn)的位置（向后），如果當(dāng)前觀察員能到達(dá)上一個飲水機(jī)，則這個觀察員就不必安裝飲水機(jī)，繼續(xù)往后枚舉
• 但這里有個問題，當(dāng)一個觀察員的覆蓋范圍在另一個觀察員覆蓋范圍之內(nèi)就會出問題

• 這時我想到要去重，把范圍大的觀察員全部踢掉，因為如果我們能滿足一個小范圍的觀察員的飲水需求，那么能到達(dá)這個小范圍觀察員的其它所有大范圍觀察員都能被滿足。想一想

  
  
  image.png

• 這里每個顏色各表示一個觀察員的覆蓋范圍，如果我們能滿足綠色觀察員的飲水需求，也就是我們在綠色范圍內(nèi)建一個飲水機(jī)的話，紅色和黑色我們還需要考慮嘛？
  當(dāng)然不用，因為他們兩個一定能到達(dá)綠色那里,當(dāng)然藍(lán)色就不一定了。
• 這個時候我們把飲水機(jī)盡量建在綠色最右邊，繼續(xù)枚舉下一個觀察員，如果下一個觀察員的范圍能與綠色相交，我們自然也不用考慮啊，如果不相交，那就在他的最右邊安裝飲水機(jī)就好了
• 關(guān)鍵步驟：排序，去重

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
int n;
int v[2000];
struct ss
{
    int k;
    int l;
    int r;
} s[1005];
bool cmp(ss a, ss b)
{
    if (a.r == b.r)
        return a.l < b.l;
    else
        return a.r < b.r;
}
int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        int p;
        cin >> s[i].k >> p; //k表示觀察員的坐標(biāo)，l是左邊界，r是右邊界
        s[i].l = s[i].k - p;
        s[i].r = s[i].k + p;
    }
    sort(s, s + n, cmp); //安裝我的規(guī)則排序，先安裝右邊界，再安裝左邊界
    for (int i = 0; i < n; i++)
    {
        for (int j = i + 1; j < n; j++)
        {
            if (s[j].l > s[i].l)
                break;
            if (s[j].r < s[i].r)
                continue;
            if (s[j].r >= s[i].r && s[j].l <= s[i].l)
                v[j] = 1; //去重我們就標(biāo)記一下就好了，到時候直接跳過就行
        }
    }
    int now = s[0].r;
    int ans = 1;
    for (int i = 1; i < n; i++)
    {
        if (v[i])
            continue;
        if (s[i].l <= now) //如果當(dāng)前觀察員能到達(dá)上一個飲水機(jī)，那就不用安裝新的飲水機(jī)
            continue;
        if (s[i].l > now) //如果當(dāng)前觀察員不能到達(dá)，那就安裝飲水機(jī)
        {
            ans++;
            now = s[i].r;
        }
    }
    cout << ans;
    return 0;
}

• 這個題數(shù)據(jù)真的水，不跳過大區(qū)間都能過...