正文
1.Drinks Choosing
题目链接
题目大意：
有n个学生，每个学生都有自己喜欢的饮料类型，用整数𝑎1,𝑎2,…,𝑎𝑛 (1≤𝑎𝑖≤𝑘)表示，一共有k种饮料的类型。
现在老师要采购饮料，饮料是两瓶装；
所以老师打算采购(n/2)个单位，保证每个学生至少有一瓶。（n/2向上取整，如果5个人，老师会买3个单位）
老师希望尽可能多的学生能喝到喜欢的饮料类型，问最多能有几个学生喝到自己喜欢的饮料？
输入：
第一行，𝑛 and 𝑘 (1≤𝑛,𝑘≤1000)
接下来n行，分别表示 𝑎1,𝑎2,…,𝑎𝑛 (1≤𝑎𝑖≤𝑘)
输出：
能够喝到喜欢饮料的学生人数；
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）
现在给出操作次数n，还有最终剩下的k个糖果，问小明会吃掉几个糖果。
输入：
第一行，𝑛 and 𝑘 (1≤𝑛≤10^9; 0≤𝑘≤10^9)
输出：
小明吃掉的糖果数；（题目保证数据是有解的）
Examples
input
5 3
1
3
1
1
2
output
4
题目解析：
由题目知道，吃掉的糖果是1、2、3、4、、、，那么假设吃掉的是1~t的糖果。
那么剩下的(n-t)次糖果，肯定是吃糖果的操作。
如果题目有解，那么就有：
总共的放进去糖果数 = 吃糖果数 + 剩下糖果数；
即是：(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)
现在教练需要选择若干个学生去参加篮球比赛，他决定从左到右选择学生，并且：
1、每列只选择一个学生；
2、不连续选择两个同一行的学生，如果这次选择了第一行的学生，则下次必然选择第二行的学生；
问选择出来的学生高度和最大值是多少；
输入：
第一行，𝑛 (1≤𝑛≤10e5)
第二行，n个整数h，表示第一行学生高度 (1≤ℎ≤10e9)
第三行，n个整数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
图中灰色为选中学生
题目解析：
两个数组，从左到右遍历选择数字，每个index只能选择一个数字，并且两个数组要交替选择。
对于每个数字，只有两种选择：选中或者不选中；
对于每个index，则有三种状态：选择数组a的元素（状态1）、选择数组b的元素（状态2）、都不选择（状态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]；
现在小明想知道，对于每个人，至少需要s的前面多少个字符，才能组成他的名字；
假如 𝑠 ="arrayhead"，𝑡[𝑖]="arya"，那么需要前面5个字符array，才能够组成arya的名字；
假如 𝑠 ="arrayhead"，𝑡[𝑖]="areahydra"，那么需要前面9个字符arrayhead，才能组成areahydra的名字；
输入：
第一行，整数𝑛，表示字符串长度 (1≤𝑛≤2⋅10^5)
第二行，字符串s；
第三行，整数m，表示m个人； (1≤𝑚≤5⋅10^4)
接下来m行，每行有一个字符串t[i]； (1≤|𝑡[𝑖]|≤2⋅10^5)
题目保证每个人的名字，都可以由字符串s组成，并且m个人的名字总长度不会超过2⋅10^5。
输出：
m行，每行有一个数字，表示需要的最少字符数量。
题目解析：
先不考虑复杂度，直接的做法是将每个人的名字拿出来匹配，一共匹配m次；
怎么匹配比较方便？
把名字统计下，得到b[26]，表示26个字符的数量；
然后遍历整个字符串，直到26个字母的数量都满足；
复杂度是O(N)，总的复杂度是O(NM)；
这个复杂度太高，需要优化。
容易知道，如果前i个字符满足要求，则前i+1个字符也满足要求，那么就可以二分。
同时为了避免多次计算，可以直接换成a[i][j]表示前i个字符，第j个字母的数量。
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提供的解法是暴力去枚举，如果操作的次数比较多，比如说n=10e18，此时放入糖果的操作次数会比较多，此时可以使用二分查找；（判断条件是糖果有没有剩余）
题目3是动态规划，状态转移比较简单；样例的数据有点像LIS（最长上升子序列），一开始理解错题意，以为是要求选择出来的人是要身高递减，但是这个题目又不能按照LIS一样做到O(NlogN)；
题目4就是典型的二分题目。
网友评论