来说一下这次比赛为什么会高血压。
首先我打开了 A 和 B，感觉都是傻逼题然后就写了，于是 A 错了 1 次，B 错了 4 次。然后我回来发现我的 A 假了不少，改了改过了，此时时间是 35 分钟（嗯）。然后开了 D，想了想是傻逼题，于是花了 12 分钟写完一发过了。然后我随手画了画 B 的图，找到了一种巨强的构造方式，改了之后也过了。至此，我成为了错了总共五次的罚时超人，后面 D 也不是很会.jpg
A. Gold and Silver
我们想到交换一定是一次金的一次银的，那么对于两组交易 (a,b) 和 (c,d)，在 b 大于等于 c 的时候，这两组带来的收益是 ，那你还不如用 (a,d) 这一组获得更好的收益。
那么我们考虑贪心。对于一组交易 (a,b) 来说，我们肯定要让 a 更大，让 b 更小。可以知道取一段区间的最大值和最小值进行交易时最优的，前提是最小值在最大值之后。我们枚举左端点，然后看这个数字后面是不是一直都在减小，如果是的话找到减小的最小点然后匹配。根据前面一段的论述，这两个位置之间不可能还有其他的交易操作，贪心的正确性随之可以得到证明。
int N, A[200010];
int ans[200010];
int main(){
iocin >> N;
readI(1, N, A);
for(int i=1; i<=N; i++){
int j = i;
while(j < N && A[j] >= A[j+1])
++j;
if(j == N && A[j] > A[i])
++j;
if(j > N)
break;
if(i != j)
ans[i] = ans[j] = true;
i = j;
}
outA(1, N, ans, "%d ");
return 0;
}
B. Balls of Three Colors
我们考虑队对于一个操作（我们在此假设为取出 R 和 G 变成 B），那么有 R,G,B -> R-1,G-1,B+2。我们观察两种颜色球的数量差，发现这个数字模 3 的余数没有改变。那么我们知道，最后同时变成 0 的两种颜色在一开始的数量差一定是 3 的倍数。
随后我们枚举最后没有的两个颜色，为了叙述方便，此处我们假设这两个颜色使 R 和 G，并且 R > G。由于把 B 变成 R 和 G 是多余操作，所以我们尝试只用剩余两种方式达到目标。在这种情况下实际上答案也是一定的。
我们可以把 R 和 G 尽可能变成 B，方便后续的操作。在变换后 G = 0，而 R 是 3 的倍数。考虑循环以下三种操作：1 次把 B 和 R 变成 G，2 次把 R 和 G 变成 B。此时我们发现 R 少了 3，并且 B 多了 3，并且整个过程不会有小球缺失的现象。所以我们就可以构造出一组一定可行的方案了。
int R, G, B;
int main(){
multiCase(){
iocin >> R >> G >> B;
int u = 1e9;
if(abs(G-B) % 3 == 0){
int a = min(G, B), b = max(G, B);
int c = R;
int curr = 0;
curr += a;
b -= a, c += 2 * a; a = 0;
curr += b;
u = min(u, curr);
}
int t = R; R = G; G = B; B = t;
if(abs(G-B) % 3 == 0){
int a = min(G, B), b = max(G, B);
int c = R;
int curr = 0;
curr += a;
b -= a, c += 2 * a; a = 0;
curr += b;
u = min(u, curr);
}
t = R; R = G; G = B; B = t;
if(abs(G-B) % 3 == 0){
int a = min(G, B), b = max(G, B);
int c = R;
int curr = 0;
curr += a;
b -= a, c += 2 * a; a = 0;
curr += b;
u = min(u, curr);
}
if(u == 1e9)
u = -1;
printf("%d\n", u);
}
return 0;
}C. Max Dot
先来看一个问题。我们需要最大化一个式子 ，其中 a 和 b 是已知量，x 和 y 是未知量，满足
，并且
的值给定。请给出取到最大值的方法。
正确的答案是取 。我们假设
，那么我们可以把 x 加上一个极小量，把 y 减去一个极小量，由于
，此时原式子的值会更大。
于是我们运用在原题上，得到一个结论：对于 A 一个连续的非增子序列，这个子序列对应的 x 值应该都是相同的。于是我们可以把 x 相同的段进行分割。
然后我们把每个序列的长度和包含的 A 的和取出来作为这个段的信息，记为 (size, sum)，此时其他信息均为无用信息。我们考虑把最后的一些段变成一个比较大的值。具体而言，我们引入 性价比 的概念，表示的是一些线段的 sum 之和除以 size 之和。对于性价比更高的集合，显然 让这些段的 x 尽可能大 是最优的。于是我们每次求出没有确定值的线段中，性价比最高的后缀，然后尽可能分配到最大的值，也就是 。最后统计答案输出即可。
int N, M;
double S;
int A[5010];
struct Segment{
int siz;
long long sum;
};
vector<Segment> Segs;
int main(){
iocin >> N >> M >> S;
readI(1, N, A);
int s = 1;
long long ss = A[1];
for(int i=2; i<=N; i++){
if(A[i] <= A[i-1])
++s, ss += A[i];
else{
Segment ns;
ns.siz = s;
ns.sum = ss;
Segs.push_back(ns);
s = 1, ss = A[i];
}
}
Segment ns;
ns.siz = s;
ns.sum = ss;
Segs.push_back(ns);
int p = Segs.size();
double ans = 0.0;
while(p != 0 && S >= 1e-9){
s = Segs[p-1].siz, ss = Segs[p-1].sum;
double R = 1.0 * ss / s;
int u = p-1;
for(int i=p-2; i>=0; i--){
s += Segs[i].siz, ss += Segs[i].sum;
if(1.0 * ss / s > R)
u = i, R = 1.0 * ss / s;
}
s = 0, ss = 0;
for(int i=u; i<p; i++)
s += Segs[i].siz, ss += Segs[i].sum;
double r = min(1.0 * M, S / s);
ans += r * ss;
S -= s * r;
p = u;
}
printf("%.12f", ans);
return 0;
}
D 题实际上我也差不多想出来了。比赛的时候就定义了两个词：
双锁：连续两个一样的数字
互锁：交替出现的数字
然后我断定这道题和这两个东西有关系（实际上确实有很大关系，可以利用这两个东西得出最后的动态规划式子），然后就罚坐了一个小时，嗯。大家不妨可以试试看，推一下这个式子。最后的计算复杂度是线性的。
