此次总结借鉴了Register_int，0x3ea，幻想家协会会长的题解。感谢大佬。
Recovering a Small String
题目大意：将字母a-z编号为1-26，给出一个整数，此整数为三个字母之和，求改字符串的最小字典序。
分析
可以暴力循环，或者分情况讨论.
我们只要尽力保持越前面的字母越小越好。
#include <iostream>
#include <algorithm>
typedef long long ll;
#define for(i,a,b) for(int i=a;i<=b;i++)
#define dfor(i,b,a) for(int i=b,i>=a;i--)
using namespace std;
int main() {
int T;
cin >> T;
while (T--) {
int n;
cin>>n;
for(i,1,26)
{
for(j,1,26)
{
for(k,1,26)
{
if(i+j+k==n)
{
printf("%c%c%c\n",'a'-1+i,'a'-1+j,'a'-1+k);
}
}
}
}
}
return 0;
}
Make Equal
题目大意：n个盛水容器，每个容器只能获得前面容器的水，求问每个容器的水是否可以相等。
分析
既然题干说了只能从前面的容器获取水源，那么我们就将计就计，将高于平均数的水倒入下一个容器中，以此类推。
如果下一个容器装了水之后还不能达到平均值，说明不可能达到了，因为前面的容器都已经达到平均值 ，已经分不出额外的水了。
还看到一种方法，利用前缀和，直接判断前i个水桶总和是否达到平均值的i倍即可。
//该方法为前缀和
#include <iostream>
#include <algorithm>
typedef long long ll;
#define for(i,a,b) for(int i=a;i<=b;i++)
#define dfor(i,b,a) for(int i=b,i>=a;i--)
using namespace std;
int a[200010], ans[200010];
int main() {
int T;
cin >> T;
while (T--) {
int n;
cin >> n;
for (i, 1, n) {
cin >> a[i];
ans[i] = a[i] + ans[i - 1];
}
int arg = ans[n] / n; //平均值
for (i, 1, n) {
if (ans[i] < arg * i) {
cout << "NO" << endl;
goto out;
}
}
cout << "YES" << endl;
out:
continue;
}
return 0;
}
/////////////////////////////////////////////
//该方法为从前往后倒水的方法
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
using namespace std;
int a[200010];
int main() {
int _;
cin >> _;
while (_--) {
int n;
cin >> n;
int sum = 0;
for (int i = 1; i <= n; i++) {
cin >> a[i];
sum += a[i];
}
if (n == 1) {
cout << "YES" << endl;
continue;
}
sum /= n;
if (a[1] < sum) {
cout << "NO" << endl;
goto out;
}
for (int i = 1; i <= n - 1; i++) {
a[i] -= sum;
a[i + 1] += a[i];
if (a[i + 1] < sum) {
cout << "NO" << endl;
goto out;
}
}
cout << "YES" << endl;
out:
continue;
}
return 0;
}
Make Equal Again
题目大意：一个数组里面有n个数字，只进行一次操作，将数组中下标 j——i 的部分变成一个数，其代价为（j-i+1），求让数组所有数字相同的最小代价。
分析
首先我们得明确操作只有一次，也就是说如果从前往后走，只要遇到一个数与前一个数不相同，就必须进行修改，并且这一次修改就必须使数组里面的数字相等。
当然，这是一道模拟，我们同意要考虑多种情况。
- 前面有相同的数，而后面数组结尾没有，比如 1，1，1，2 3，4；
- 前面没有相同的数，而结尾有，比如 1，2，3，4，4，4；
- 前面后面都有相同的数，比如 1，1，2，3，1，1；
- 前面后面都有相同的数字，但是数字不同，如 1，1，1，2，3，4，4；
严格来说，其实前两种情况也可以归为第四种情况，只是为了防止自己被绕晕，所以详细写出来了。
那么这题要求最小代价的话，应该很容易就能看出来，我们必须在数组前面或者后面，找到最长的连续相等的数列长度。
那么我们可以在代码中编写一个求最长长度的函数，简化代码。
#include <iostream>
using namespace std;
int a[200100];
int n;
int fff(int t) {
int I = 0, J = 0;
for (int i = 1; i <= n; i++) {
if (a[i] != t) {
I = i;
break;
}
}
for (int i = n; i >= 1; i--) {
if (a[i] != t) {
J = i;
break;
}
}
if (I == 0)
return 0;
return (J - I + 1);
}
int main() {
int _;
cin >> _;
while (_--) {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
int x = fff(a[1]);
int y = fff(a[n]);
int tt = min(x, y);
cout << tt << endl;
}
}
Divisible Pairs
题目大意：给定一个长度为n的数组a，再给定两个整数 x，y，在数列里面寻找下标为i，j（i<j）的数，使得ai+aj能被x整除，ai-aj能被y整除，求有多少组i，j。
分析
这其实是一题关于同模的逆运算的题目。
现在已知 (i%x+j%x)%x=0，(j-i)%y=0;
如果现在已知i，那么可以推出j要符合两个条件（x-j%x）%x=i%x，j%y=i%y
那么现在我们就知道如何将i和j进行配对了，
为了方便，我们在存数字的时候，可以直接存i%x和i%y，用两个数组分别存，
然后利用 map<PII,int>mp 直接遍历查询匹配的i和j
#include <iostream>
#include <algorithm>
#include <map>
typedef long long ll;
#define for(i,a,b) for(int i=a;i<=b;i++)
#define dfor(i,b,a) for(int i=b,i>=a;i--)
using namespace std;
typedef pair<int, int> PII;
int a[200010], b[200010];
map<PII, int>mp;
int main() {
int T;
cin >> T;
while (T--) {
int n, x, y;
cin >> n >> x >> y;
for (i, 1, n) {
int tmp = 0;
cin >> tmp;
a[i] = tmp % x;
b[i] = tmp % y;
}
mp.clear();
ll ans = 0;
for (i, 1, n) {
int t1 = (x-a[i]%x) % x;//得到j%x
int t2 = b[i] % y;
ans += mp[{t1, t2}];//加上能配对的数量（第一次配对的时候为0，是为了防止把自己也算进去）
mp[{a[i], b[i]}]++;//下标i能匹配的数量++
}
cout << ans << endl;
}
return 0;
}
Anna and the Valentine's Day Gift
题目大意：现有n个整数，Anna能对数字进行颠倒（能把末尾0变成前导0去掉），Sasha能合并两个数字，现在给出m，Anna先手，当数字只剩一个时结束游戏，
如果最后的数字 >=10^m ，Sasha获胜，否则Anna获胜。
分析
题目要求判断最后的数字与 10^m 的大小，10的幂有个特殊性质，就是位数为m+1，而Sasha又能拼接数字，所以在没有前导0的情况下，最后剩下的数的位数就是每个数位数之和。
但是现就就是有了前导0这种东西产生了变数，那么本题关键就是数组里面那些能被10整除的数字了。
现在，Anna能够消除0，让位数减少，从而让自己变得有利，而Sasha能保护一些0不被消除，让自己有利（如，10，10，变成1010，至少保护了一个0）
那么如果按最有利的情况来进行游戏，Anna先手，肯定把最多后导0的数倒过来，然后Sasha要把后导0数量仅次于Anna的数字保护起来，以此类推（这就是一种贪心）。
那么很容易根据后导0的数量进行排序，然后求出最后的位数即可。
#include <iostream>
#include <algorithm>
typedef long long ll;
using namespace std;
int f1(int x) { //求位数
int cnt = 0;
for (; x; x /= 10, cnt++);
return cnt;
}
int f2(int x) { //求后导0个数
int cnt = 0;
for (; x % 10 == 0; x /= 10, cnt++);
return cnt;
}
bool cmp(int a, int b) {
return a > b;
}
int a[200100];
int main() {
int T;
cin >> T;
while (T--) {
int n, m;
cin >> n >> m;
int tot = 0;
int sum = 0;
for (int i = 1; i <= n; i++) {
int x;
cin >> x;
tot += f1(x);
a[i] = f2(x);
}
sort(a + 1, a + n + 1, cmp);
for (int i = 1; i <= n; i += 2) { //Anna先手
sum += a[i];
}
if (tot - sum <= m) {
puts("Anna");
} else {
puts("Sasha");
}
}
return 0;
}
Chat Screenshots
题目大意：现在有n个人，每个人都能看到除自己外的其他数的顺序（自己永远在第一位），现在给出m个人的序列，检查是否有可能存在让所有人都合理的排序。
分析
观察“NO”的案例，发现如果不存在合理的序列的话，那么必有“环”的产生，比如
1，3，2；
2，1，3；
3，2，1；
由第一行可知3排在2前面，第二行知道3在1的后面，那么由前两个可知1，3，2才是合理的顺序，但是与第三个矛盾了，变成1，3，2，1，形成了一个环。
既然我们只要判断这个序列是否产生环了即可，那么不如利用这些序列建图，然后跑一遍拓扑排序，判断是否有环即可。（拓扑序列不是唯一的，而这一题合理的顺序有很多种，这一点也是相契合的）
所以我们只要进行建图即可，注意有效的序列是从每一个序列的第二个数字开始，第一个数字是不准的。
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
typedef long long ll;
using namespace std;
typedef pair<int, int> PII;
const int N = 200020;
vector<int>g[N];
int d[N], a[N], in[N];
int main() {
int T;
cin >> T;
while (T--) {
int n, k;
cin >> n >> k;
for (int i = 1; i <= n; i++) { //初始化
g[i].clear();
in[i] = 0;
}
while (k--) {
for (int i = 1; i <= n; i++) {
cin >> a[i];
if (i >= 3) {
g[a[i - 1]].push_back(a[i]); //在a_(i-1)后面接上a_i
in[a[i]]++;//入度
}
}
}
queue<int>q;
for (int i = 1; i <= n; i++) {
if (in[i] == 0)
q.push(i);//入度为0的点进队
}
int cnt = 0; //记录次数
while (q.size()) {
int u = q.front();
q.pop();
cnt++;
for (int v : g[u]) { //以u为起点遍历图
in[v]--;//入度--
if (in[v] == 0)
q.push(v);
}
}
puts(cnt == n ? "YES" : "NO");
}
return 0;
}
One-Dimensional Puzzle
我太蠢，脑袋不够用了，这题先放着吧，私密马赛/(ㄒoㄒ)/~~