20230114比赛题解
T1 算账
签到题，模拟即可。
std:
#include <bits/stdc++.h>
using namespace std;
vector<int> a;
int main()
{
int n;
cin >> n;
int ans = 0;
for (int i = 1; i <= n; i++) {
int tmp;
cin >> tmp;
ans += tmp;
a.emplace_back(tmp);
}
sort(a.begin(), a.end());
for (int i = 0; i < n / 2; i++) {
ans += a[n - i - 1] - a[i];
}
cout << ans << endl;
return 0;
}T2 大米老师
原题，摘自国际大学生程序设计竞赛亚洲区域赛杭州站 F 题
这一题也是个模拟题，不过得懂一点点 STL。
我们要做两件事情：一，判定是否有重复；二，判定是否含有目标串。
判断重复，有两种方法：一种是使用 Hash，不过这样子还要手写 Hash，所以我们采用unordered_map(就是 hashmap)。每次读入一个新信息，我们先在 unordered_map 中查询是否存在相同消息，如果没有就塞入 unordered_map 中，如果有当前消息忽略。
判断是否含有目标串，直接使用find()函数就可以了，毕竟find()函数内部使用的是 KMP 算法，速度能满足我们要求。
std:
#include<bits/stdc++.h>
using namespace std;
unordered_map<string,bool> grp;
int main()
{
// freopen("data/dami1.in","r",stdin);
int a;
cin >> a;
int n;
string str;
bool flag;
for (int i = 1; i <= a; i++)
{
flag = false;
cin >> n;
for (int j = 1; j <= n; j++)
{
cin >> str;
if (str.find("bie")!=string::npos&&!grp[str])
{
grp[str]=true;
flag = true;
cout<<str<<'\n';
}
}
if(!flag){
cout<<"Time to play Genshin Impact, Teacher Rice!\n";
}
}
return 0;
}T3 金钱游戏
原题，摘自国际大学生程序设计竞赛亚洲区域赛杭州站 D 题
首先，我们会发现这个轮数是非常的多，那么就说明这题肯定没法暴力或者其他什么办法，那么我们可以猜测，在一定的轮数过后，接下来继续进行操作是对原序列不会出现什么变化。
循着这个思路，很显然我们可以先去“蒙”答案，就是编写一个暴力程序进行模拟，对于小数据进行极大的次数的模拟（比如几千次甚至几万次），然后观察序列的变化。我们会发现，序列变化到最后一定是
暴力程序：
#include <cstdio>
#include <iostream>
using namespace std;
double a[100010];
int main()
{
// freopen("data/test.txt", "w", stdout);
freopen("data/data1.in", "r", stdin);
freopen("data/data1.ans", "w", stdout);
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
for (int i = 1; i <= 500000; i++) {
for (int j = 1; j <= n - 1; j++) {
a[j] /= 2;
a[j + 1] += a[j];
}
a[n] /= 2;
a[1] += a[n];
}
for (int j = 1; j <= n; j++) {
cout << a[j] << ' ';
}
cout << endl;
return 0;
}接下来我们来解释一下为什么这样是对的：
如果我们把题面改一下，改成每个人都给下一个人他的全部，那么这个问题就会变的非常简单：所有钱在第一轮会叠罗汉一般的传递到最后一个人，最后一个人把钱在传给第一个人，那么一轮过去第一个人就拥有了全部的存款，接下来不管怎么传递，一轮结束后一定第一个人拥有全部的存款，那么这个时候就进入了一个稳态。
那么回到这个问题，这个问题是否存在稳态呢？事实上是存在的（数学证明极为复杂，此处不列）。接下来我们来构造一下这个稳态。对于我刚刚举的这个例子，进入稳态后就有一部分（例子中是全部）的钱像传花球一样的不断向下传递。这个问题中每次是有一半的钱在向下传递，那么我们可以先给所有人相同一部分的钱
由于总钱数是保持不变的，所以只要算出总钱数
std:
#include <cstdio>
#include <iostream>
using namespace std;
double sum;
int main()
{
// freopen("data/test.txt", "w", stdout);
// freopen("data/data2.in", "r", stdin);
// freopen("data/data2.out", "w", stdout);
double n;
cin >> n;
double tmp;
for (int i = 1; i <= n; i++) {
cin >> tmp;
sum += tmp;
}
sum /= n + 1;
printf("%.2lf ", sum * 2);
for (int i = 1; i <= n - 1; i++) {
printf("%.2lf ", sum);
}
printf("\n");
return 0;
}最后提一点反思：看到题面中如果有诸如