题目链接：https://codeforces.com/contest/1038/
A - Equality
题意：给出一个长度为 (n) 的大写字母字符串，求最长的子序列，使得这其中的恰好前 (k) 种大写字母出现次数相等。
题解：子序列，随便拿。
char s[100005];
int cnt[26];
void test_case() {
int n, k;
scanf("%d%d%s", &n, &k, s + 1);
for(int i = 1; i <= n; ++i)
++cnt[s[i] - 'A'];
int minL = INF;
for(int i = 0; i < k; ++i)
minL = min(minL, cnt[i]);
printf("%d
", minL * k);
}
B - Non-Coprime Partition
题意：把 ([1,n]) 的整数分为非空的两组，使得第一组的和与第二组的和不互质。
题解：看起来前后相加就很不互质，总是会是中位数的两倍。所以总是会有中位数作为公因子。
void test_case() {
int n;
scanf("%d", &n);
if(n <= 2) {
puts("No");
return;
}
puts("Yes");
printf("%d", (n + 1) / 2);
for(int i = 1; i <= n; i += 2)
printf(" %d", i);
puts("");
printf("%d", n / 2);
for(int i = 2; i <= n; i += 2)
printf(" %d", i);
puts("");
}
C - Gambling
题意：有两个人，每个人一个长度为 (n) 的数字序列，每次操作A先动，可以取走自己的一个数字并获得其得分或者扔掉别人的一个数字。
题解：首先肯定拿自己还是扔别人都是选最大的。那么当别人的比自己大的时候，假如自己拿了别人也拿了，就亏了。自己扔掉别人的那个不会更差。所以可以归纳出贪心。
priority_queue<int> PQA, PQB;
void test_case() {
int n;
scanf("%d", &n);
for(int i = 1; i <= n; ++i) {
int x;
scanf("%d", &x);
PQA.push(x);
}
for(int i = 1; i <= n; ++i) {
int x;
scanf("%d", &x);
PQB.push(x);
}
ll sumA = 0, sumB = 0;
for(int i = 1; i <= n; ++i) {
if(PQA.empty())
PQB.pop();
else {
if(PQB.empty() || PQA.top() > PQB.top()) {
sumA += PQA.top();
PQA.pop();
} else
PQB.pop();
}
if(PQB.empty())
PQA.pop();
else {
if(PQA.empty() || PQB.top() > PQA.top()) {
sumB += PQB.top();
PQB.pop();
} else
PQA.pop();
}
}
printf("%lld
", sumA - sumB);
}
D - Slime
题意：有 (n) 个史莱姆，每个史莱姆会有一个分 (a_i(-10^9leq a_i leq 10^9)) 排成一行，每次会选择一个史莱姆吃掉相邻的一个史莱姆，直到只剩下最后一个，其中 (x) 吃掉 (y) 之后会剩下 (x-y) 。求最大能剩下的史莱姆。
题解：首先要特判只有一个史莱姆的情况，这种不能归纳到下面的规律，直接输出。
然后，假如史莱姆都是正数，那么显然至少有一个的贡献会被变成负数，选最小的变成负数。
假如史莱姆都是负数，那么至少有一个要保持负数，选最大的保持负数。
有0或者有正有负的话，就让负数吃掉几乎所有非负数，只剩下一个非负数，然后让非负数把所有的负数吃完。
void test_case() {
int n;
scanf("%d", &n);
if(n == 1) {
int x;
scanf("%d", &x);
printf("%d
", x);
return;
}
ll sumP = 0, sumN = 0;
int minP = INF, maxN = -INF;
for(int i = 1; i <= n; ++i) {
int x;
scanf("%d", &x);
if(x < 0) {
sumN += x;
maxN = max(maxN, x);
} else {
sumP += x;
minP = min(minP, x);
}
}
if(maxN == -INF) {
printf("%lld
", sumP - 2 * minP);
return;
}
if(minP == INF) {
printf("%lld
", 2 * maxN - sumN);
return;
}
printf("%lld
", sumP - sumN);
}