Problem D. Letter Picking
区间博弈 dp，状态 f[][]，但是比一般的博弈 dp 要简单，转移 trivial。
首先我们可以两轮操作绑定在一起转移，只要考虑长度为偶数的状态，并且也不用记录上一轮选了什么字符。
进一步不难归纳出结果只有可能是先手胜或平局，进一步简化状态和转移。
#include <lastweapon/io>
using namespace lastweapon;
const int N = int(2e3) + 9;
char s[N]; bool f[N][N];
int n;
int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
#endif
Rush {
n = strlen(RS(s));
REP(i, n+1) f[i][i] = 0;
for(int l=2;l<=n;l+=2) {
REP(i, n-l+1) {
int j = i+l;
bool ll = f[i+2][j] || (s[i] > s[i+1]);
bool lr = f[i+1][j-1] || (s[i] > s[j-1]);
bool rl = f[i+1][j-1] || (s[j-1] > s[i]);
bool rr = f[i][j-2] || (s[j-1] > s[j-2]);
f[i][j] = (ll && lr) || (rl && rr);
}
}
puts(f[0][n] ? "Alice" : "Draw");
}
}
Problem E. Red-Black Pepper
调整法。先考虑判定性问题，用扩展欧几里得求丢番图方程 ax + by = n 特解，然后判断是否存在一组解使得 ax 在 [0, n] 范围内即可。
考虑最优化问题，根据输入，可以预处理出关于 ax 的，定义域为 [0, n] 之间整数的，非严格凸函数 f，所谓非严格就是可能中间存在一些相等的情况，比如最值可能会是一个区间，
不过稍后会看到，这问题并不大。。
每次询问的目标函数的定义域则是 f 函数的子集，以特解为中心，每次步长为 lcm(a, b)，这也是非严格凸函数，因为我们已经预处理出了它的导数，所以可以在导数上二分求极值。
不过我们能做的更好，只要检查最值附近的两个点的函数式值 f(xl), f(xr) 即可，具体来说，假设我们预处理阶段保留的是最值的右端点 x0，
那么就检查 xl < x0 <= xr，如果是左端点，
就检查 xl <= x0 < xr。。。
#include <lastweapon/io>
using namespace lastweapon;
const int N = int(3e5) + 9;
int a[N], b[N], x0; LL f[N];
int n;
LL exgcd(LL a, LL b, LL &x, LL &y){
if (!b){
x = 1, y = 0;
return a;
}
LL d = exgcd(b, a % b, y, x);
y -= a / b * x;
return d;
}
LL query() {
LL a, b, x, y; RD(a, b);
LL d = exgcd(a, b, x, y);
if (n % d) return -1;
x *= n/d*a; d = a/d*b;
x -= ceil(max(0ll, x-x0), d) * d;
x += max(0ll, x0-x) / d * d;
LL z = -1; if (x >= 0) checkMax(z, f[x]);
x += d; if (x <= n) checkMax(z, f[x]);
return z;
}
void init() {
RD(n); LL s = 0; REP(i, n) RD(a[i], b[i]), s += b[i];
REP(i, n) a[i] -= b[i]; sort(a, a+n, greater<int>());
f[0] = s; REP(i, n) f[i+1] = f[i] + a[i];
x0 = upper_bound(a, a+n, 0, greater<int>()) - a - 1;
}
int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
#endif
init(); Rush OT(query());
}
Problem F. Fishermen
。。。居然比赛时只有 <10 个人过，，，但是做法非常简单。。。
首先可以看出是个最优匹配模型。。然后，权值都在单侧的顶点上，于是可以 sort 之后直接跑 Kuhn’s 算法。。。这是个比较常见的套路。。
然后再加一个优化。。。“if you haven’t found an augmenting path, don’t reset the values representing which vertices were visited by the algorithm.”
就过了。。。囧。。
#include <lastweapon/io>
using namespace lastweapon;
const int N = int(1e3) + 9, N2 = N*N;
int a[N], b[N2], py[N]; bool vis[N2]; VI adj[N2];
int n, bn;
bool dfs(int x) {
if (vis[x]) return 0;
vis[x] = 1;
for (auto y: adj[x]) {
int xx = py[y];
if (xx == -1 || dfs(xx)) {
py[y] = x;
return 1;
}
}
return 0;
}
LL kuhn() {
LL z = 0; int c = 0;
fill(py, py+n, -1);
REP(i, bn) if (dfs(i)) {
z += b[i]; fill(vis, vis+bn, 0);
++c; if (c == n) break;
}
return z;
}
int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
#endif
RD(n); REP(i, n) {
RD(a[i]); REP(j, n) b[i*n+j] = a[i]*(j+1);
}
bn = n*n; sort(b, b+bn); bn = unique(b, b+bn) - b;
REP(i, n) {
int t = 0; REP(j, n) {
t = lower_bound(b+t, b+bn, a[i]*(j+1)) - b;
adj[t].PB(i);
}
}
OT(kuhn());
}
