- https://atcoder.jp/contests/arc128/tasks
- https://www.bilibili.com/read/cv13612020
- https://www.cnblogs.com/stinger/p/15416806.html
arc 好难。。。（虽然题面都很简单）
A Gold and Silver
著名的套利系列问题，但是这个题应该是里面最简单的一类，可以贪心，
扫一遍就行了。
B Balls of Three Colors
讨论一下最后保留哪个，然后就很容易了。
C Max Dot
先不考虑 𝑚 的限制。。。
考虑 n=2 的情况，如果 a1 < a2 的情况，显然资源全部都给 a2，否则只能对半分。
考虑 n 个数的情况，一定是 0 0 x x x x 这种 pattern，均分给一个后缀。
题解用的是调整法，也不难用归纳法证明，我们可以把后面的后缀合并起来看成是一个数，权值用平均值代替，
然后沿用 n=2 的方法即可。
我们枚举后缀，得到的 x 有可能不满足 m 的限制。
这个时候我们只要先把这些后缀填上 m，然后就可以递归到更短且 s 更小的问题。
这样直接做是 O(n2) 的，可以构造一个 a 递增的序列就可以弄出最坏复杂度。。
不过已经足够通过本题。。。然后题解最后还说仔细观察这个过程可以用凸包优化到 O(n)，
（。。我猜是斜率 DP？。。。没能写出来。。）
const int N = int(5e3) + 9;
int n,m,s;
int a[N];
DB gao(int n, DB m, DB s) {
vector<pair<DB,int>> avg; DB ss = 0;
DWN(i, n, 0) {
ss += a[i];
avg.PB({ss / (n-i), i});
}
int t = max_element(ALL(avg))->se;
DB x = s / (n-t);
if (x <= m) {
DB z = 0;
FOR(i, t, n) z += x * a[i];
return z;
} else {
DB z = 0;
FOR(i, t, n) z += m * a[i];
return z + gao(t, m, s-(n-t)*m);
}
}
int main(){
#ifndef ONLINE_JUDGE
//freopen("in.txt", "r", stdin);
//freopen("/Users/minakokojima/Documents/GitHub/ACM-Training/Workspace/out.txt", "w", stdout);
#endif
RD(n,m,s); REP(i,n)RD(a[i]);
OT(gao(n,m,s));
}
D Neq Neq
看起来有点像 spoj zuma 那个题。。。不过转移感觉不是很好想。。
首先如果是 x,y,x,y,x … 这样的交错序列，答案就是斐波那契数列，一旦合并之后状态就会被分割。
那么用类似 上次那个题 的方法，可以用 x,x 将状态分割成独立的子问题，最后答案用乘法原理乘起来即可。
考虑不存在相邻元素相等的子问题，考察某个区间能否把中间的元素全部合并掉，
判定的条件是，长度 <= 3 或者这个区间有 3 种不同的元素，因为相邻的元素不同，总是可以用第三种元素作为支点反复消，不难用归纳法证明。
设 f[i] 表示以 i 元素结尾的方案数，有了上面的结论，就可以得到转移方程，大概就是斐波那契关系之上再加点东西，
f[i] = f[i-1] + f[i-2] + pre，其中 pre 是所有符合上述判定的前缀和，注意别和长度 <= 3 的算重复了。
用类似 小z的袜子 里的方法维护区间不同元素的数目即可。
实现的时候，可以设置哨兵 f[0] = f[1], f[n+1] = f[n] 以简化代码。
const int N = int(2e5) + 9;
Int f[N]; int a[N], c[N], cn;
int n;
void add(int x) {
x = a[x];
if (!c[x]) ++cn;
c[x] += 1;
}
void dec(int x) {
x = a[x];
c[x] -= 1;
if (!c[x]) --cn;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
//freopen("/Users/minakokojima/Documents/GitHub/ACM-Training/Workspace/out.txt", "w", stdout);
#endif
RD(n); REP_1(i, n) RD(a[i]);
f[0] = 1; f[1] = 1; a[0] = a[1]; a[n+1] = a[n]; ++n;
Int z = 1, pre = 0;
int l = 1; REP_1(i, n) {
if (a[i] == a[i-1]) {
z *= f[i-1]; f[i-1] = 0; f[i] = 1;
while (l < i) dec(l++); add(i); pre = 0;
} else {
add(i); while (cn > 2 && l < i-2) pre += f[l], dec(l++);
f[i] = f[i-1] + f[i-2] + pre;
}
}
cout << z << endl;
}
E K Different Values
直接 dfs 显然不行，考虑构造。。。
(1 hour later … )
呃。。。好吧，我觉得这个题还是挺难的。囧。。完全没看懂 题解。。。
但是 标程 到是挺容易丽洁的。。。
我们先考虑 k|n 的情况，那么可以分成 n/k 组，我们尝试贪心构造，每次尽可能放最小的，但是放到后面有可能需要回溯。。。
看来我们需要想一种贪心构造，使得问题的规模不断减小，并且最好不会出现回溯。。
设 n = dk + r，(r > 0)，首先如果存在 Ai > (d+1) 或者有超过 r 组 == (d+1) 那么显然无解 (a)，
否则，如果恰好有超过 r 组 == d+1，那么从这 r 组里选最小的 (1)，否则选全局最小的 (2)，添加到队首，
当然选出的数要保证与上次出现的距离至少为 k，然后递归到 n-1 即可。
上面的过程显然保证字典序最小，我们只要证明这个算法一定能终止即可。。
考虑反证法 + 归纳法。。
首先如果第一轮没有出现无解的情况，那么后面的轮次也都不会出现。。否则前面轮次的 (1) 就已经取走了。
再考虑如果某个轮次没有取到数，那么前 k 轮次时也一定没有取到数，但是 <= k 轮次时一定可以取到数，
因此取不到数的情况也不存在。
F Game against Robot
非常赞的组合计数题。有早年 SRM Div1 1000 的感觉了。。。。
首先考虑静态的问题，然后类似 linearity of expectation，我们设法求出每个 Ai 在结果中出现的次数。
我们只关注排列中每个元素和 Ai 的大小关系，这样只需要考察 01 序列，最后对贡献乘以 i!(n-i)! 即可。
进一步考察静态过程，我们可以计数得到所有大于等于 Ai 的数在答案中的出现次数，类似那个证明 Catalan 数等于 \binom{2n,n} – \binom{2n, n+1} 的过程，最后预处理二项式系数的和即可。
具体得看 lyric 的代码。
