头要炸了。
T1 题面很好懂，手玩了一下发现答案最小是 \((m-1)\times n\)。可能会多出来一个长度为 \(k\) 的部分，会发现如果多出来一个长度为 \(k\) 的部分且合法，那么单个串 \(1\sim k\) 位与 \(n-k+1\sim n\) 位一定相同，\(k+1\sim n\) 位与 \(1\sim n-k\) 一定相同。Hash 判一下即可。
写了个模数的 hash，发现过不去样例，改成自然溢出就过了，不懂，赌一把出题人不会卡自然溢出。（伏笔）
T2 怎么又是蛇形方阵，上一次出蛇形方阵头要炸了分数还不高，这一次打算冲一把。
\(O(n^3)\) 的就是暴力，\(O(n^2)\) 的应该需要写个函数，要 \(O(1)\) 计算 \((x,y)\) 位置的数字是多少。
然后疯狂打表。
发现对于
点击查看代码
for (int T = 1; T <= 20; ++T) {
n = T;
int x = 1, y = 1, tot = 0;
for (int i = n; i > 1; i -= 2) {
for (int j = 1; j < i; ++j) a[x++][y] = ++tot;
for (int j = 1; j < i; ++j) a[x][y++] = ++tot;
for (int j = 1; j < i; ++j) a[x--][y] = ++tot;
for (int j = 1; j < i; ++j) a[x][y--] = ++tot;
y ++, x ++;
}
if (n & 1) a[x][y] = ++tot;
x = 1, y = 1;
LL ans = 0, ans2 = 0;
while (x <= n && y <= n) {
if (x <= n / 2 && y <= n / 2)
ans2 += a[x][y];
ans += a[x][y];
++x, ++y;
}
cerr << n << ' ' << ans;
cout << ' ' << ans2 << ' ' << ans - ans2 << '\n';
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j)
cerr << setw(4) << a[i][j];
cerr << '\n';
}
for (int i = 1, lastans = 0, lastcha = 0; i <= n; ++i) {
int x = i, y = 1;
LL ans = 0;
while (x <= n && y <= n) {
ans += a[x][y];
++x, ++y;
}
cerr << i << ' ' << ans << ' ' << lastans - ans << ' ' << (lastcha - lastans + ans) << '\n';
lastcha = lastans - ans;
lastans = ans;
}
cerr << '\n';
for (int i = 1, lastans = 0, lastcha = 0; i <= n; ++i) {
int x = 1, y = i;
LL ans = 0;
while (x <= n && y <= n) {
ans += a[x][y];
++x, ++y;
}
cerr << i << ' ' << ans << ' ' << lastans - ans << ' ' << (lastcha - lastans + ans) << '\n';
lastcha = lastans - ans;
lastans = ans;
}