正文

1.Drinks Choosing

題目鏈接
題目大意：
有n個(gè)學(xué)生，每個(gè)學(xué)生都有自己喜歡的飲料類(lèi)型，用整數(shù)??1,??2,…,???? (1≤????≤??)表示，一共有k種飲料的類(lèi)型。
現(xiàn)在老師要采購(gòu)飲料，飲料是兩瓶裝；
所以老師打算采購(gòu)(n/2)個(gè)單位，保證每個(gè)學(xué)生至少有一瓶。（n/2向上取整，如果5個(gè)人，老師會(huì)買(mǎi)3個(gè)單位）
老師希望盡可能多的學(xué)生能喝到喜歡的飲料類(lèi)型，問(wèn)最多能有幾個(gè)學(xué)生喝到自己喜歡的飲料？

輸入：
第一行，?? and ?? (1≤??,??≤1000)
接下來(lái)n行，分別表示 ??1,??2,…,???? (1≤????≤??)

輸出：
能夠喝到喜歡飲料的學(xué)生人數(shù)；

Examples
input
5 3
1
3
1
1
2
output
4

題目解析：
興趣相同的，兩兩成對(duì)拿出來(lái)，湊成一個(gè)單位；(ans += 2)
剩下的所有人(n - ans)，每個(gè)人的興趣都不相同，任意兩兩湊對(duì)一個(gè)單位；(n-ans+1)/2

    int n, k;
    cin >> n >> k;
    int a[1001] = {0}, ans = 0;
    for (int i = 0; i < n; ++i) {
        int t;
        cin >> t;
        ++a[t];
        if (a[t] % 2 == 0) {
            ans += 2;
        }
    }
    ans += (n - ans + 1) / 2;
    cout << ans << endl;

2.Sport Mafia

題目鏈接
題目大意：
小明有個(gè)糖果盒子，起始的時(shí)候是空的。
小明會(huì)進(jìn)行n次操作，每次可以選擇：
1、吃掉盒子里的一個(gè)糖果；（如果里面有糖果的話）
2、放進(jìn)去x個(gè)糖果，之后x=x+1；（比如這次是放5個(gè)，下次就是放6個(gè)）
最后盒子里會(huì)剩下k個(gè)糖果；

例如下面的9個(gè)操作：
put 1 candy,
put 2 candies,
eat a candy,
eat a candy,
put 3 candies,
eat a candy,
put 4 candies,
eat a candy,
put 5 candies.

最終會(huì)剩下11個(gè)糖果。（1+2?1?1+3?1+4?1+5=11）

現(xiàn)在給出操作次數(shù)n，還有最終剩下的k個(gè)糖果，問(wèn)小明會(huì)吃掉幾個(gè)糖果。

輸入：
第一行，?? and ?? (1≤??≤10^9; 0≤??≤10^9)

輸出：
小明吃掉的糖果數(shù)；（題目保證數(shù)據(jù)是有解的）

Examples
input
5 3
1
3
1
1
2
output
4

題目解析：
由題目知道，吃掉的糖果是1、2、3、4、、、，那么假設(shè)吃掉的是1~t的糖果。
那么剩下的(n-t)次糖果，肯定是吃糖果的操作。
如果題目有解，那么就有：
總共的放進(jìn)去糖果數(shù) = 吃糖果數(shù) + 剩下糖果數(shù)；
即是：(1+t)*t/2 = (n-t) + k；

可以從1開(kāi)始遍歷t，最多重復(fù)sqrt(10^9)次就會(huì)有解，復(fù)雜度可以接受。

    int n, k;
    cin >> n >> k;
    for (int i = 1; i < 100000; ++i) {
        lld sum = (1ll + i) * i / 2;
        if (sum == (k + (n - i))) {
            cout << sum - k << endl;
            return 0;
        }
    }

3.Basketball Exercise

題目鏈接
題目大意：
籃球教練有2 * n個(gè)學(xué)生，排成兩行，每行有n個(gè)人；

問(wèn)選擇出來(lái)的學(xué)生高度和最大值是多少；

輸入：
第一行，?? (1≤??≤10e5)
第二行，n個(gè)整數(shù)h，表示第一行學(xué)生高度 (1≤?≤10e9)
第三行，n個(gè)整數(shù)h，表示第二行學(xué)生高度 (1≤?≤10e9)

輸出：
選擇出來(lái)的學(xué)生高度總和最大值；

Examples
input
5
9 3 5 7 3
5 8 1 4 5
output
29

圖中灰色為選中學(xué)生

input
3
1 2 9
10 1 1
output
19

圖中灰色為選中學(xué)生

題目解析：
兩個(gè)數(shù)組，從左到右遍歷選擇數(shù)字，每個(gè)index只能選擇一個(gè)數(shù)字，并且兩個(gè)數(shù)組要交替選擇。

對(duì)于每個(gè)數(shù)字，只有兩種選擇：選中或者不選中；
對(duì)于每個(gè)index，則有三種狀態(tài)：選擇數(shù)組a的元素（狀態(tài)1）、選擇數(shù)組b的元素（狀態(tài)2）、都不選擇（狀態(tài)0）；
那么有dp[N][i]：
dp[i][0] = max(dp[i-1][0], dp[i-1][1], dp[i-1][2]);
dp[i][1] = max(dp[i-1][2], dp[i-1][0]) + a[i];
dp[i][2] = max(dp[i-1][1], dp[i-1][0]) + b[i];

然后選擇dp[N][i]中的最大值即可。

    int n;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    for (int i = 0; i < n; ++i) {
        cin >> b[i];
    }
    
    lld ans = max(a[0], b[0]);
    dp[0][0] = 0;
    dp[0][1] = a[0];
    dp[0][2] = b[0];
    
    for (int i = 1; i < n; ++i) {
        dp[i][0] = max(max(dp[i-1][0], dp[i-1][1]), dp[i-1][2]);
        dp[i][1] = max(dp[i-1][2], dp[i-1][0]) + a[i];
        dp[i][2] = max(dp[i-1][1], dp[i-1][0]) + b[i];
        for (int j = 0; j < 3; ++j) {
            ans = max(ans, dp[i][j]);
        }
    }
    
    cout << ans << endl;

4.Letters Shop

題目鏈接
題目大意：
有一個(gè)小寫(xiě)字母組成的字符串s，長(zhǎng)度為n；
有m個(gè)人，每個(gè)人有一個(gè)名字，假如是t[i]；
現(xiàn)在小明想知道，對(duì)于每個(gè)人，至少需要s的前面多少個(gè)字符，才能組成他的名字；

假如 ?? ="arrayhead"，??[??]="arya"，那么需要前面5個(gè)字符array，才能夠組成arya的名字；
假如 ?? ="arrayhead"，??[??]="areahydra"，那么需要前面9個(gè)字符arrayhead，才能組成areahydra的名字；

輸入：
第一行，整數(shù)??，表示字符串長(zhǎng)度 (1≤??≤2?10^5)
第二行，字符串s；
第三行，整數(shù)m，表示m個(gè)人； (1≤??≤5?10^4)
接下來(lái)m行，每行有一個(gè)字符串t[i]； (1≤|??[??]|≤2?10^5)
題目保證每個(gè)人的名字，都可以由字符串s組成，并且m個(gè)人的名字總長(zhǎng)度不會(huì)超過(guò)2?10^5。

輸出：
m行，每行有一個(gè)數(shù)字，表示需要的最少字符數(shù)量。

題目解析：
先不考慮復(fù)雜度，直接的做法是將每個(gè)人的名字拿出來(lái)匹配，一共匹配m次；
怎么匹配比較方便？
把名字統(tǒng)計(jì)下，得到b[26]，表示26個(gè)字符的數(shù)量；
然后遍歷整個(gè)字符串，直到26個(gè)字母的數(shù)量都滿足；
復(fù)雜度是O(N)，總的復(fù)雜度是O(NM)；

這個(gè)復(fù)雜度太高，需要優(yōu)化。
容易知道，如果前i個(gè)字符滿足要求，則前i+1個(gè)字符也滿足要求，那么就可以二分。
同時(shí)為了避免多次計(jì)算，可以直接換成a[i][j]表示前i個(gè)字符，第j個(gè)字母的數(shù)量。

    int n;
    cin >> n;
    string str;
    cin >> str;
    a[0][str[0] - 'a'] = 1;
    
    for (int i = 1; i < n; ++i) {
        for (int j = 0; j < 26; ++j) {
            a[i][j] = a[i - 1][j];
        }
        ++a[i][str[i] - 'a'];
    }
    
    int m;
    cin >> m;
    while (m--) {
        string t;
        cin >> t;
        int cnt[26] = {0};
        for (int i = 0; i < t.length(); ++i) {
            ++cnt[t[i] - 'a'];
        }
        
        int l = 0, r = n - 1, ans = n - 1;
        while (l <= r) {
            int mid = (l + r) / 2;
            
            int ok = 1;
            for (int i = 0; i < 26; ++i) {
                if (cnt[i] && a[mid][i] < cnt[i]) {
                    ok = 0;
                }
            }
            
            if (ok) {
                ans = mid;
                r = mid - 1;
            }
            else {
                l = mid + 1;
            }
        }
        
        cout << ans + 1 << endl;
    }

總結(jié)

題目1是貪心，也沒(méi)有特別的trick；
題目2提供的解法是暴力去枚舉，如果操作的次數(shù)比較多，比如說(shuō)n=10e18，此時(shí)放入糖果的操作次數(shù)會(huì)比較多，此時(shí)可以使用二分查找；（判斷條件是糖果有沒(méi)有剩余）
題目3是動(dòng)態(tài)規(guī)劃，狀態(tài)轉(zhuǎn)移比較簡(jiǎn)單；樣例的數(shù)據(jù)有點(diǎn)像LIS（最長(zhǎng)上升子序列），一開(kāi)始理解錯(cuò)題意，以為是要求選擇出來(lái)的人是要身高遞減，但是這個(gè)題目又不能按照LIS一樣做到O(NlogN)；
題目4就是典型的二分題目。