题解：AT_agc066_a [AGC066A] Adjacent Difference
笑点解析：没有必要将总成本最小化。
我们将格子间隔的黑白染色（显然有两种染色方法），对于黑点我们要求它是奇数倍 \(d\)，对于白点我们要求它是偶数倍 \(d\)，这样一定满足相邻格子相差至少 \(d\)。
因为两种染色方法的代价和为 \(dN^2\)，所以两种方法中至少有一种满足代价小于 \(\frac{1}{2}dN^2\)，容易实现：
ll n, m, ans = 1e15, Case=1;
ll a[N][N], b[N][N], c[N][N];
void solve() {
input(n, m);
for(ll i = 1; i <= n; i++) {
for(ll j = 1; j <= n; j++) {
input(a[i][j]);
}
}
for(ll x = 0; x <= 1; x ++) {
ll sum = 0;
for(ll i = 1; i <= n; i ++) {
for(ll j = 1; j <= n; j ++) {
ll k = a[i][j] / m;
if((i + j + k + x) % 2 == 0) {
if(a[i][j] < 0) k --;
else k ++;
}
b[i][j] = k * m;
sum += abs(b[i][j] - a[i][j]);
}
}
if(sum < ans) {
for(ll i = 1; i <= n; i ++) {
for(ll j = 1; j <= n; j ++) {
c[i][j] = b[i][j];
}
}
ans = sum;
}
}
for(ll i = 1; i <= n; i ++) {
for(ll j = 1; j <= n; j ++) {
print(c[i][j]);
}
putchar('\n');
}
// print(ans);
}
题解：AT_agc066_b [AGC066B] Decreasing Digit Sums
题目大意：给定 \(n\)，求一个 \(x\)，使得对于任意的 \(1\le i\le n\)，满足 \(d(2^{i-1}x)>d(2^ix)\)。其中 \(d(x)\) 指 \(x\) 的数位和。
我们发现，答案是具有单调性的，也就是对于 \(n=50\) 的答案，同样适用于 \(n<50\) 的情况。
所以我们只用考虑 \(n=50\) 的答案即可。
按照直观的感受，给定任意的 \(x\) 与 \(y\)，已知 \(x>y\)，那么 \(d(x)\) 大于 \(d(y)\) 的概率会比较大。
但是随着 \(i\) 的增加，\(2^ix\) 也会随之增加，所以我们要考虑减小 \(d(2^ix)\)。
我们发现，如果某一个数位为 \(0\)，对于 \(d\) 函数就没有贡献。所以考虑构造一个 \(x\)，使得它乘上 \(2^i\) 可以产生若干个 \(0\)。所以设 \(x=5^{50}a\)，那么 \(d(2^ix)=d(2^i5^{50}a)=d(10^i5^{50-i}a)=d(5^{50-i}a)\)，此时随着 \(i\) 的增加，\(5^{50-i}a\) 也会随之减小，那么 \(d(5^{50-i}a)\) 肯定也会趋于减小。具体：
但是这样仍旧不是单调递减的，但是它是趋于单调递减的，所以我们可以考虑把它们拼接起来，这样平均下来，单调递减的概率就会大大上升。
我们随机得到 \(a_1,a_2,\cdots,a_k\)，然后将这 \(k\) 个系数组成的数用 \(0\) 连接起来，这样就可以保证它单调递减的概率比较大：
下面代码中的 bign 是高精度，check 是判断是否合法的函数：
ll n = 50, k = 100;
bign a = 1, ans;
int main() {
for(ll i = 1; i <= 50; i ++) a = a * 5;
while(true) {
ans = 0;
for(ll i = 1; i <= k; i ++) {
ll x = rnd() % 100 + 1;
bign tmp = a * x;
for(ll j = 1; j <= tmp.len + 50; j ++) ans = ans * 10;
ans = ans + tmp;
}
if(check(ans)) {
cout << ans << endl;
break;
}
}
return 0;
}
题解：AT_agc066_c [AGC066C] Delete AAB or BAA
这题评黑我觉得有点过了。其实还是比较好想的。
考虑一个区间怎么才能被消除掉：它满足可以分成若干个满足以下条件的子串：每个子串都满足 \(\tt A\) 的数量是 \(\tt B\) 的两倍，左端点或右端点是 \(\tt B\)。
证明可以让时间倒流，我们在这个字符串内不断添加 \(\tt AAB\) 或 \(\tt BAA\)。
如果一个字符串是空字符串，添加 \(\tt AAB\) 或 \(\tt BAA\) 明显符合。
如果一个字符串符合条件，那么在两端添加 \(\tt AAB\) 或 \(\tt BAA\) 相当于添加了一个新的符合条件的子串，如果在中间添加 \(\tt AAB\) 或 \(\tt BAA\)，字符串两端的字符仍旧不变，依旧符合。
所以通过归纳法可以证明。
所以我们设 \(x_i\) 表示 \(1\sim i\) 中 \(\tt B\) 的数量的两倍减去 \(\tt A\) 的数量。若 \(x_l=x_r\)，则 \([l+1,r]\) 明显是一个可以被消除掉的字符串。
所以我们容易设 \(f_i\) 表示处理到第 \(i\) 个字符，最少不删掉的字符的数量，明显我们需要最小化它。
那么有转移方程：
\[f_i=\begin{cases} f_{i-1}+1 \\ f_j & x_i=x_j,s_{j+1}={\tt B} \\ f_j & x_i=x_j,s_{i}={\tt B} \end{cases} \]对于第二、三种情况，我们可以用两个 map 来储存每种 \(x\) 下的最小 \(f\) 值。
这里不使用 \(f_i\) 表示最多不删除的字符数量的原因是因为不太好打。
void solve() {
map<ll, ll> ha, hb;
scanf("%s", s + 1);
n = strlen(s + 1);
for(ll i = 1; i <= n; i ++) {
a[i] = a[i - 1], b[i] = b[i - 1];
if(s[i] == 'A') {
a[i] ++;
}
else {
b[i] ++;
}
x[i] = a[i] - 2 * b[i];
ha[x[i]] = hb[x[i]] = inf;
}
ha[0] = hb[0] = inf;
for(ll i = 1; i <= n; i ++) {
f[i] = inf;
}
if(s[1] == 'A') {
ha[0] = 0;
} else {
hb[0] = 0;
}
for(ll i = 1; i <= n; i ++) {
f[i] = min(f[i], f[i - 1] + 1);
if(s[i] == 'A') {
f[i] = min(f[i], hb[x[i]]);
} else {
f[i] = min(f[i], ha[x[i]]);
f[i] = min(f[i], hb[x[i]]);
}
if(s[i + 1] == 'A') {
ha[x[i]] = min(ha[x[i]], f[i]);
} else {
hb[x[i]] = min(hb[x[i]], f[i]);
}
}
print((n - f[n]) / 3);
putchar('\n');
}