正文
1.Drinks Choosing
題目鏈接
題目大意：
有n個學生，每個學生都有自己喜歡的飲料類型丢郊，用整數(shù)??1,??2,…,???? (1≤????≤??)表示，一共有k種飲料的類型。
現(xiàn)在老師要采購飲料，飲料是兩瓶裝拾徙；
所以老師打算采購(n/2)個單位，保證每個學生至少有一瓶感局。（n/2向上取整尼啡，如果5個人，老師會買3個單位）
老師希望盡可能多的學生能喝到喜歡的飲料類型询微，問最多能有幾個學生喝到自己喜歡的飲料崖瞭？
輸入：
第一行，?? and ?? (1≤??,??≤1000)
接下來n行撑毛，分別表示 ??1,??2,…,???? (1≤????≤??)
輸出：
能夠喝到喜歡飲料的學生人數(shù)书聚；
Examples
input
5 3
1
3
1
1
2
output
4
題目解析：
興趣相同的，兩兩成對拿出來，湊成一個單位雌续；(ans += 2)
剩下的所有人(n - ans)斩个，每個人的興趣都不相同，任意兩兩湊對一個單位西雀；(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
題目鏈接
題目大意：
小明有個糖果盒子萨驶，起始的時候是空的歉摧。
小明會進行n次操作艇肴，每次可以選擇：
1、吃掉盒子里的一個糖果叁温；（如果里面有糖果的話）
2再悼、放進去x個糖果，之后x=x+1膝但；（比如這次是放5個冲九，下次就是放6個）
最后盒子里會剩下k個糖果；
例如下面的9個操作：
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.
最終會剩下11個糖果跟束。（1+2?1?1+3?1+4?1+5=11）
現(xiàn)在給出操作次數(shù)n莺奸，還有最終剩下的k個糖果，問小明會吃掉幾個糖果冀宴。
輸入：
第一行灭贷，?? 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览妖、、揽祥、讽膏，那么假設吃掉的是1~t的糖果。
那么剩下的(n-t)次糖果拄丰，肯定是吃糖果的操作府树。
如果題目有解，那么就有：
總共的放進去糖果數(shù) = 吃糖果數(shù) + 剩下糖果數(shù)愈案；
即是：(1+t)*t/2 = (n-t) + k挺尾；
可以從1開始遍歷t，最多重復sqrt(10^9)次就會有解站绪，復雜度可以接受遭铺。
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個學生，排成兩行，每行有n個人魂挂；
每個學生都有一個高度h甫题；(1≤h≤10e9)
現(xiàn)在教練需要選擇若干個學生去參加籃球比賽，他決定從左到右選擇學生涂召，并且：
1坠非、每列只選擇一個學生；
2果正、不連續(xù)選擇兩個同一行的學生炎码，如果這次選擇了第一行的學生，則下次必然選擇第二行的學生秋泳；
問選擇出來的學生高度和最大值是多少潦闲；
輸入：
第一行，?? (1≤??≤10e5)
第二行迫皱，n個整數(shù)h歉闰，表示第一行學生高度 (1≤?≤10e9)
第三行，n個整數(shù)h卓起，表示第二行學生高度 (1≤?≤10e9)
輸出：
選擇出來的學生高度總和最大值和敬；
Examples
input
5
9 3 5 7 3
5 8 1 4 5
output
29
input
3
1 2 9
10 1 1
output
19
題目解析：
兩個數(shù)組，從左到右遍歷選擇數(shù)字戏阅，每個index只能選擇一個數(shù)字昼弟，并且兩個數(shù)組要交替選擇。
對于每個數(shù)字饲握，只有兩種選擇：選中或者不選中私杜；
對于每個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
題目鏈接
題目大意：
有一個小寫字母組成的字符串s铝耻，長度為n；
有m個人蹬刷，每個人有一個名字瓢捉，假如是t[i]；
現(xiàn)在小明想知道办成，對于每個人泡态，至少需要s的前面多少個字符，才能組成他的名字迂卢；
假如 ?? ="arrayhead"某弦，??[??]="arya"桐汤，那么需要前面5個字符array，才能夠組成arya的名字靶壮；
假如 ?? ="arrayhead"怔毛，??[??]="areahydra"，那么需要前面9個字符arrayhead腾降，才能組成areahydra的名字拣度；
輸入：
第一行，整數(shù)??螃壤，表示字符串長度 (1≤??≤2?10^5)
第二行抗果，字符串s；
第三行映穗，整數(shù)m窖张，表示m個人； (1≤??≤5?10^4)
接下來m行蚁滋，每行有一個字符串t[i]； (1≤|??[??]|≤2?10^5)
題目保證每個人的名字赘淮，都可以由字符串s組成辕录，并且m個人的名字總長度不會超過2?10^5。
輸出：
m行梢卸，每行有一個數(shù)字走诞，表示需要的最少字符數(shù)量。
題目解析：
先不考慮復雜度蛤高，直接的做法是將每個人的名字拿出來匹配蚣旱，一共匹配m次；
怎么匹配比較方便戴陡？
把名字統(tǒng)計下塞绿，得到b[26]，表示26個字符的數(shù)量恤批；
然后遍歷整個字符串异吻，直到26個字母的數(shù)量都滿足；
復雜度是O(N)喜庞，總的復雜度是O(NM)诀浪；
這個復雜度太高，需要優(yōu)化延都。
容易知道雷猪，如果前i個字符滿足要求，則前i+1個字符也滿足要求晰房，那么就可以二分求摇。
同時為了避免多次計算酵颁，可以直接換成a[i][j]表示前i個字符，第j個字母的數(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;
}
總結
題目1是貪心躏惋，也沒有特別的trick；
題目2提供的解法是暴力去枚舉嚷辅，如果操作的次數(shù)比較多簿姨，比如說n=10e18，此時放入糖果的操作次數(shù)會比較多簸搞，此時可以使用二分查找扁位；（判斷條件是糖果有沒有剩余）
題目3是動態(tài)規(guī)劃，狀態(tài)轉移比較簡單趁俊；樣例的數(shù)據(jù)有點像LIS（最長上升子序列）域仇，一開始理解錯題意，以為是要求選擇出來的人是要身高遞減寺擂，但是這個題目又不能按照LIS一樣做到O(NlogN)暇务；
題目4就是典型的二分題目。
