A、Problemsolving Log
跳转原题点击此：A题地址
1、题目大意
Monocarp在思考A~Z中26道题目，其中A题的思考时间是1分钟，Z题的思考时间是26分钟，以此类推。同时Monocarp即使在思考我该题目，可能也会多思考几分钟用来复盘。
题目给定 n -- 字符串长度， 和 字符串s -- 代表每分钟思考哪道题目，并输出Monocarp一共解决了几道题目。
2、题目解析
只要定义一个数组用来存储A~Z题所思考的总时间，只要期思考时间 大于等于 该题所用时间，就可以得到输出结果。
#include<bits/stdc++.h>
using namespace std;
int t;
int n;
int f[30];
void solve()
{
string s1;
memset(f, 0, sizeof f); // 记得每次都要初始化字符个数的数组
cin >> n >> s1;
for (int i = 0; i < s1.size(); i++)
{
int tmp = s1[i] - 'A' + 1;
f[tmp]++;
}
int ans = 0;
for (int i = 1; i <= 26; i++)
{
if (f[i] >= i)
ans++;
}
cout << ans << endl;
}
int main()
{
cin >> t;
while (t--)
{
solve();
}
return 0;
}
B、Problemsolving Log
跳转原题点击此：B题地址
1、题目大意
Monocarp在写n道问题，题目难度为1~n，其中如果后面的题目比前面的题目难，则Monocarp会获得1点兴奋值，要求你排列这n道问题，使得兴奋度 == 输入的k。
2、题目解析
因为要求是后面的题目难度大于前面的难度，则可以按照贪心的思想，将难度高的k道题目顺序放在最前面，难度低的题目倒序放在后面。这样就满足了所需的k点兴奋度。
例如案例一：最终排列就是：1、5、6、4、3、2
#include<bits/stdc++.h>
using namespace std;
int t;
int n, k;
void solve()
{
cin >> n >> k;
// 特判：当k为0时，则只需要倒序输出即可
if (k == 0)
{
for (int i = n; i >= 1; i--)
cout << i << " ";
cout << endl;
return;
}
int be = n - k + 1; // 找到需要几题难度高的题目，然后放在前面
cout << 1 << " ";
// 顺序在前面输出难度高的题目题目，满足所需兴奋度
for (int i = be; i <= n; i++)
cout << i << " ";
// 然后在后面倒序输出难度低的题目
for (int i = be - 1; i >=2; i--)
cout << i << " ";
cout << endl;
}
int main()
{
cin >> t;
while (t--)
{
solve();
}
return 0;
}
C、Quests
跳转原题点击此：C题地址
1、题目大意
Monocarp在打游戏，其中每个任务获得的经验分为首次经验和重复经验。并且在继续下一个任务时，必须通过至少一次该任务之前的所有任务。并且可以随时回到之前的任务刷经验。但是，题目给定了你最多能进行的任务数量，所以要求你选择合适的策略，以获得最大经验值。
2、题目解析
可以通过前缀和实现，由于每个任务都必须通过其前面的所有任务，所以每个任务的首次经验就为其前面的所有首次经验和。由于任务具有重复经验，所以找到重复经验的最大值乘以其剩余的最大次数。当然有些情况并不是重复经验最大就是答案，所以可以通过循环来max到最终答案。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5+10;
int t;
int n, k;
int a[N], b[N], cuma[N], maxb[N];
void solve()
{
// cuma[0] = maxb[0] = 0;
cin >> n >> k;
for(int i = 1; i <= n; i++)
{
cin >> a[i];
// 前缀和，因为要解锁下一个a[i]，就需要a[1~i-1]都要遍历一遍
cuma[i] = cuma[i - 1] + a[i];
}
for(int i = 1; i <= n; i++)
{
cin >> b[i];
// 注意，随时可以选择b[1~i-1]的值，所以选择已解锁的b的最大值
maxb[i] = max(maxb[i - 1], b[i]);
}
int ans = 0;
for(int i = 1; i <= n; i++)
{
// 如果遍历完n，则代表已经完成全部的分数检索，已经得到答案了
if(i > k)
break;
// 得到输出选择的累加 a分数 和 解锁的b分数最大值
int tmp = cuma[i] + maxb[i] * (k - i >= 0 ? k - i : 0);
ans = max(ans, tmp);
}
cout << ans << endl;
}
int main()
{
cin >> t;
while (t--)
{
solve();
}
return 0;
}
D、Three Activities
跳转原题点击此：D题地址
1、题目大意
Monocarp在n天的寒假里想要和朋友们一起去skiing、cinema、board games，但是每天最多只能进行一个活动，并且每天会有不同的三批朋友陪Monocarp分别进行这三个活动。请你给出这三个活动分别在哪一天选择使得一起玩的朋友最多。
2、题目解析
因为是三个活动，所以分别找出这三个活动的三个最大值，然后查看其是否重复（可以通过pair同时存入朋友个数和在哪天），如果不重复，则有A(3,3)=6种排列，找到最大的即可。
#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int>pii;
const int N = 1e5+10;
int t;
int n;
// 因为三个项目不能在一天重复，所以把天数也存入
pii a[N], b[N], c[N];
bool cmp(pii a, pii b)
{
return a._1 > b._1;
}
void solve()
{
cin >> n;
for(int i = 1; i <= n; i++)
{
int tmp = 0;
cin >> tmp;
a[i] = {tmp, i};
}
for(int i = 1; i <= n; i++)
{
int tmp = 0;
cin >> tmp;
b[i] = {tmp, i};
}
for(int i = 1; i <= n; i++)
{
int tmp = 0;
cin >> tmp;
c[i] = {tmp, i};
}
// 因为要找出三天的a、b、c的最大值，所以对其的朋友数作从大到小排序
sort(a + 1, a + 1 + n, cmp);
sort(b + 1, b + 1 + n, cmp);
sort(c + 1, c + 1 + n, cmp);
int ans = 0;
// 遍历3次是因为有三天，所以a、b、c的各三天最大值排列组合就能形成ans
for(int i = 1; i <= 3; i++)
for(int j = 1; j <= 3; j++)
for(int k = 1; k <= 3; k++)
// 如果这三天都没有重复，就输出ans
if(a[i]._2 != b[j]._2 && a[i]._2 != c[k]._2 && b[j]._2 != c[k]._2)
ans = max(ans, a[i]._1 + b[j]._1 + c[k]._1);
cout << ans << endl;
}
int main()
{
cin >> t;
while (t--)
{
solve();
}
return 0;
}