Codeforces Round 916 (Div. 3)
比赛链接
完成度：4/7
又是脑子短路的一场比赛......
A题
刚睡醒就做这A题，脑子还有点懵，多花了几分钟
这题是让我们算完成的任务的个数，一共26个任务，任务花费时间依次递增。给了任务日志那么根据任务日志来对相应的值操作，记录完成任务的个数即可
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <map>
#include <string>
#define int long long
using namespace std;
const int N = 200010;
void solve()
{
int n, arr[27];
cin >> n;
for (int i = 0; i < 26; i++)
{
arr[i] = i + 1;
}
char c;
int ans = 0;
for (int i = 0; i < n; i++)
{
cin >> c;
arr[c - 'A']--;
if (arr[c - 'A'] == 0)
{
ans++;
}
}
cout << ans << endl;
}
signed main()
{
int tNum;
cin >> tNum;
for (int i = 0; i < tNum; i++)
{
solve();
}
return 0;
}
B题
这个我的做法是先将1-n个数按从小到大排，假如我们要n - 1个激励就将前0个数放在数组后面，同理，如果是k - 1个就是将n - k - 1个数放在后面，比如1 2 3 4 5 6，我们要3个激励，就是3 4 5 6 2 1。然后发现我们可以定义两个指针l和r，l向左输出数字，r向右输出数字，可以避免调换数组元素带来的时间，就是说1 2 3 4 5 6中l指向2，r指向3然后输出就是 3 4 5 6 2 1
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <map>
#include <string>
#define int long long
using namespace std;
const int N = 200010;
void solve()
{
int n, num;
cin >> n >> num;
vector<int> a(n + 2, 0);
for (int i = 1; i <= n; i++)
{
a[i] = i;
}
int l = n, r = n + 1, sum = 0;
if (num >= 1)
{
l -= 2, r -= 2;
sum = 1;
}
while (sum < num && l >= 0)
{
l--, r--;
sum++;
}
for (int i = r; i <= n; i++)
{
cout << a[i] << " ";
}
for (int i = l; i > 0; i--)
{
cout << a[i] << " ";
}
cout << endl;
}
signed main()
{
int tNum;
cin >> tNum;
for (int i = 0; i < tNum; i++)
{
solve();
}
return 0;
}
C题
这个类似于我们自己打的游戏，想要获取最大的经验值，首次通关和再次通关的奖励是不一样的。仔细想想就可以知道，这个最大的情况就是在首次打了某一个副本后停下，一直打那个再次通关奖励最多的副本，由于每个副本的再次奖励都不一样，有的多有的少，首次通关的奖励也可以打也可以小，没有比较好的停下打新副本的标准，我们只能考虑遍历所有副本，在遍历的同时计算在当前副本停下去一直打那个再次通关奖励最多的副本。这样就能算出最大的经验值是在首次通关哪个副本停下去打再次奖励最大的副本
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <map>
#include <string>
#define int long long
using namespace std;
const int N = 200010;
int a[N], b[N];
void solve()
{
int len, task;
cin >> len >> task;
for (int i = 0; i < len; i++)
{
cin >> a[i];
}
for (int i = 0; i < len; i++)
{
cin >> b[i];
}
int maxx = 0, ans = 0, sum = 0;
for (int i = 0; i < min(task, len); i++)
{
maxx = max(maxx, b[i]);
sum += a[i];
ans = max(ans, sum + (task - i - 1) * maxx);
}
cout << ans << endl;
}
signed main()
{
int tNum;
cin >> tNum;
for (int i = 0; i < tNum; i++)
{
solve();
}
return 0;
}
D题
这题直接暴力枚举肯定是超时的，立方的时间复杂度，数据稍微一多就哦嚯了。我们可以先排序，然后在前面最大的三个里面寻找，要的时间也就3的3次方
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <map>
#include <string>
#define int long long
using namespace std;
const int N = 200010;
bool cmp(pair<int, int> a, pair<int, int> b)//排序标准
{
return a.first > b.first;
}
void solve()
{
vector<pair<int, int>> a, b, c; //pair的作用是记下坐标，在后面循环时用来判断天数是否相同
int n, q;
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> q;
a.push_back({q, i});
}
sort(a.begin(), a.end(), cmp); //排序
for (int i = 0; i < n; i++)
{
cin >> q;
b.push_back({q, i});
}
sort(b.begin(), b.end(), cmp);
for (int i = 0; i < n; i++)
{
cin >> q;
c.push_back({q, i});
}
sort(c.begin(), c.end(), cmp);
int maxx = 0;
for (int i = 0; i < min(n,(long long)4);i ++) //其实在前3个里面寻找就行，当时写多了，不影响
{
for (int j = 0; j < min(n, (long long)4); j++)
{
for (int k = 0; k < min(n, (long long)4); k++)
{
if(a[i].second != b[j].second && a[i].second != c[k].second && b[j].second != c[k].second)
{
maxx = max(a[i].first + b[j].first + c[k].first,maxx);//满足条件就比较一下
}
}
}
}
cout << maxx << endl;
}
signed main()
{
int tNum;
cin >> tNum;
for (int i = 0; i < tNum; i++)
{
solve();
}
return 0;
}