在这次周考中，你将见到包括但不限于：
- 1e6 的输出规模我跑了 1.1s！大力卡常！好耶！只跑了 0.997s！哇！单模哈希被卡啦！
- 6e7 的输出规模我跑了 32.7s！放弃卡常！好耶！交上去 A 啦！
这件事情告诉我们，如果本地跑大规模输出跑出来很寄，你要相信评测机的实力。
A. 午餐排队
http://222.180.160.110:1024/contest/4399/problem/1
题解说用逆向思维来倒推，很不幸我当时根本没往这块想。
我们整理需要维护的内容：
- 给定学生编号的单点移动操作
- 每个学生编号的实时位置
直接拿一个链表就能搞定，直接顺序模拟移动操作就行了。
#define int long long
namespace XSC062 {
using namespace fastIO;
const int maxn = 3e5 + 5;
int n, m, a, b, c, d, e, res;
int k[maxn], pre[maxn], nex[maxn];
int main() {
read(n), read(m);
read(a), read(b), read(c), read(d), read(e);
k[0] = a, k[1] = b;
for (int i = 0; i < n; ++i)
pre[i] = i - 1, nex[i] = i + 1;
pre[0] = n + 1, nex[n + 1] = 0;
pre[n] = n - 1;
pre[n + 1] = nex[n] = -1;
for (int i = 0; i < m; ++i) {
if (i >= 2) {
k[i] = (c * k[i - 1] +
d * k[i - 2] + e) % n;
}
if (nex[k[i]] != n) {
pre[nex[k[i]]] = pre[k[i]];
nex[pre[k[i]]] = nex[k[i]];
pre[k[i]] = pre[n];
nex[pre[n]] = k[i];
nex[k[i]] = n;
pre[n] = k[i];
}
}
for (int i = 0, x = n + 1; i < n; ++i)
x = nex[x], res += x * i;
print(res, '\n');
return 0;
}
} // namespace XSC062
#undef int
B. 字符串等级
http://222.180.160.110:1024/contest/4399/problem/2
反思与总结
这个需要反思。我当时打出的状态和题解完全一致，但是因为时间不充裕以及不想深入思考状态转移（这个转移不难想，但是想起来确实挺耗脑子，在人没有睡醒的情况下），最终直接跳了该题。
不过值得表扬的是状态想到了，以及懂得把这道题放在 T5 之后思考，还有发现时间不够暴力也不好打懂得赶紧跳。
C. 国王舞会
http://222.180.160.110:1024/contest/4399/problem/3
不难发现一个喜欢高的只能和喜欢矮的在一起。
于是我们给人分类，然后贪心地去配对（给喜欢高的分配尽可能矮的人；反之同理）。
拿个桶记录一下然后直接刷过去就行了。
namespace XSC062 {
using namespace fastIO;
const int maxn = 1e5 + 5;
int n, res, r, x;
int m0[maxn], m1[maxn], f0[maxn], f1[maxn];
int min(int x, int y) {
return x < y ? x : y;
}
int max(int x, int y) {
return x > y ? x : y;
}
int main() {
read(n);
for (int i = 1; i <= n; ++i) {
read(x);
if (x > 0) ++f1[x];
else ++f0[-x];
}
for (int i = 1; i <= n; ++i) {
read(x);
if (x > 0) ++m1[x];
else ++m0[-x];
}
for (int i = 1501; i <= 2500; ++i) {
x = min(f0[i], m1[i - 1] + r);
res += min(f0[i], x);
r += m1[i - 1] - x;
}
r = 0;
for (int i = 2499; i >= 1500; --i) {
x = min(f1[i], m0[i + 1] + r);
res += min(f1[i], x);
r += m0[i + 1] - x;
}
print(res, '\n');
return 0;
}
} // namespace XSC062
D. 翻转拼接串
http://222.180.160.110:1024/contest/4399/problem/4
我们给题目简单画个图：
ORIGINAL STRING: <-----+++++++>
SPLICED STRING: <-----<+++++++----->+++++++>
^ ^ ^ ^ ^
1 i N i+N 2*N
那么我们可以发现，只要 \([1,i]\) 和 \((N,i+N]\) 的反串相同，且 \((i, N]\) 的反串和 \((i+N,2\times N]\) 相同，那么 \(i\) 就可以成为答案。
于是我们从前向后枚举 \(i\)，用一正一反两个字符串哈希解决问题即可。
对于没有得满分的同学，恭喜你见到了单哈希（特别是自然溢出法）被卡掉的数据。为了在日后的比赛中不会懊恼，正式场合就麻烦你写一份双哈希吧。
恶意，满满的恶意。一看就是 LHY 出的。我甚至可以想象到他在屏幕后面猥笑的样子。
我们打一个双模哈希，用两个不同的模数分别存储两个哈希值。
打了过后还是没过，调了很久没有发现原因，后来发现题面上有一个 \(0\le i\le N\)，而我只讨论了 \(i\in [1, N]\) 的情况。需要警醒。
注意打其他模数的时候不能开无符号，不然在减法的时候就会减出问题。
namespace XSC062 {
const int base = 13331;
const int maxn = 2e6 + 5;
const int mod = 998244353;
using ll = long long;
using ull = unsigned long long;
int n;
char s[maxn];
ull p[maxn], h[maxn], g[maxn];
ll p1[maxn], h1[maxn], g1[maxn];
ll P(int l, int r) {
ll res = h1[r];
res -= h1[l - 1] * p1[r - l + 1] % mod;
res = (res % mod + mod) % mod;
return res;
}
ull H(int l, int r) {
return h[r] - h[l - 1] * p[r - l + 1];
}
ll Q(int l, int r) {
ll res = g1[l];
res -= g1[r + 1] * p1[r - l + 1] % mod;
res = (res % mod + mod) % mod;
return res;
}
ull R(int l, int r) {
return g[l] - g[r + 1] * p[r - l + 1];
}
int main() {
scanf("%d %s", &n, s + 1);
p[0] = p1[0] = 1;
for (int i = 1; i <= 2 * n; ++i) {
p[i] = p[i - 1] * base;
h[i] = h[i - 1] * base + s[i];
p1[i] = p1[i - 1] * base % mod;
h1[i] = (h1[i - 1] *
base + s[i]) % mod;
}
for (int i = 2 * n; i; --i) {
g[i] = g[i + 1] * base + s[i];
g1[i] = (g1[i + 1] *
base + s[i]) % mod;
}
for (int i = 0; i <= n; ++i) {
if (R(i + 1, n) == H(n + i + 1, 2 * n)
&& Q(i + 1, n) == P(n + i + 1, 2 * n)
&& H(1, i) == R(n + 1, n + i)
&& P(1, i) == Q(n + 1, n + i)) {
for (int j = 1; j <= i; ++j)
putchar(s[j]);
for (int j = n; j > i; --j)
putchar(s[j]);
printf("\n%d\n", i);
return 0;
}
}
puts("-1");
return 0;
}
} // namespace XSC062
E. 树上操作
http://222.180.160.110:1024/contest/4399/problem/5
这个比较板，数据范围都在明示你直接在 DFN 上跑差分就可以了。
我们以 1 为根，再拿一个数组记录一条边上谁是儿子（因为更改都是以儿子为基准才能直接连续差分），这个可以用链式前向星在 DFS 的时候搞定。
然后打一个小分讨就行。打完过后可以发现他们可以合并成一个更小的分讨。
只是我因为在本地输出 6e7 规模答案时因为跑了 32.7s 而慌张，卡了很久无用的常。
但需要意识到只要本地跑出来并且能 return 0 都应该能 A。
namespace XSC062 {
using namespace fastIO;
using ll = long long;
const int maxn = 2e6 + 5;
const int maxm = 4e6 + 5;
ll dif[maxn];
int dfn[maxn], rfn[maxn];
int n, tot, now, t, e, x;
int a[maxn], b[maxn], c[maxn];
int h[maxn], to[maxm], nxt[maxm];
void DFS(int x, int fa) {
dfn[x] = ++now;
for (int j = h[x]; j; j = nxt[j]) {
if (to[j] == fa) continue;
c[(j + 1) / 2] = to[j], DFS(to[j], x);
}
rfn[x] = now;
return;
}
void add(int x, int y) {
to[++tot] = y;
nxt[tot] = h[x], h[x] = tot;
return;
}
void upd(int l, int r, int x) {
dif[l] += x, dif[r + 1] -= x;
return;
}
int main() {
read(n);
for (int i = 1; i < n; ++i) {
read(a[i]), read(b[i]);
add(a[i], b[i]), add(b[i], a[i]);
}
DFS(1, -1), read(tot);
while (tot--) {
read(t), read(e), read(x);
if (((t == 1) ? a[e] : b[e]) == c[e])
upd(dfn[c[e]], rfn[c[e]], x);
else {
if (dfn[c[e]] > 1)
upd(1, dfn[c[e]] - 1, x);
if (rfn[c[e]] < n)
upd(rfn[c[e]] + 1, n, x);
}
}
for (int i = 1; i <= n; ++i)
dif[i] += dif[i - 1];
for (int i = 1; i <= n; ++i)
print(dif[dfn[i]], '\n');
return 0;
}
} // namespace XSC062
F. 道路建设
http://222.180.160.110:1024/contest/4399/problem/6
打了一个很耐人寻味的 10pts 的跑不满的暴力（本来还有一个理论得分更高的小贪心但是因为怕挂就删了），得到了耐人寻味的 50pts 的高分。