代码源总结

代码源模拟赛 · 合集

2024 CSP-S 模拟赛 Day 2

题目链接

好难好难！

赛时

T1

首先看见 \(a_i\oplus a_j < a_j\oplus a_k\)，第一反应是两边同时 \(\oplus a_j\)，得到 \(a_i<a_k\)，遂 BIT 之，然后样例过不了，发现这个结论假飞了。

然后考虑统计 \(i<j<k\)，第一反应枚举 \(j\)，然后计数。

于是写了个 \(O(n^2\log n)\) 的部分分：

for (int p = 1; p <= n; ++p) {
  vector<int> t; for (int i = 1; i < p; ++i) t.push_back(a[i] ^ a[p]); sort(t.begin(), t.end());
  for (int i = p + 1; i <= n; ++i) res += upper_bound(t.begin(), t.end(), (a[i] ^ a[p]) - 1) - t.begin();
} printf("%lld\n", res);

突然考虑到异或题直接上 0/1 Trie，于是考虑维护左右两个 Trie，然后每次同时遍历。

ll Calc(int p, int q, int dep, int s) { ll tmp = 0;
  if (L.siz[p] == 0 || R.siz[q] == 0 || !p || !q || dep < 0) return 0;
  tmp += L.siz[L.tr[p][((s >> dep) & 1)]] * R.siz[R.tr[q][!((s >> dep) & 1)]];
  tmp += Calc(L.tr[p][0], R.tr[q][0], dep - 1, s);
  tmp += Calc(L.tr[p][1], R.tr[q][1], dep - 1, s);
  return tmp; }

但是发现时间复杂度很高，但是最坏 \(O(2^pn)\) 能过 \(a_i\le2^6\) 的点。

然后就不会了，过。

T2

先写暴力，然后不会。

T3

暴力也不会。

想写 Gauss 但是不会取模版本，于是写了个树上 DP 的 \(5\text{ pts}\)。

T4

暴力模拟求 \(f(i,j)\)，然后暴力 \(\sum_{i=1}^{m_a}\sum_{j=1}^{m_b}f(i,j)\)。

完全不会优化。（）

赛后

T1 就是恶心暴力分，还好过了 \(a_i<2^6\)。

T2、T4 只会暴力，没啥说的。

T3 写挂了，哭哭！

@Sorato @liang @forgive 太强了，%%！

讲评后 & 总结

• T1 的思路假了，正解是枚举 \(k\)，但是这种枚举三元组的题只想到了枚举 \(j\)。
• T2 的状压很显然，但是不会。要多在赛时想状压了……

代码源 CSP 模拟赛 Day 6

题目链接

好难好难！

赛时

T1

显然是树上 DP。

于是先写了一个 \(O(n)\) 的树上 DP，然后没过样例，发现我的 \(f_i\) 是强制选 \(i\)，于是跑了 \(n\) 次 DP，发现可过样例。

于是尝试换根，但是因为一直在考虑删除 \(x\) 节点会造成对它 \(fa\) 那一层的其他点有影响，即删除 \(u\) 的影响不止其字树。考虑不仅仅会有一个 n - siz[x] 的影响，还可能有一个其他导致向上的边删除增加连通块的影响。所以想了半天。

赛后讲评是说“由于这是一个树”，才反应过来一个儿子只有一个父亲，所以对非子树的影响仅仅是 n - siz[x] >= k，并没有其他的。

服了，只能说赛时真的脑子抽了。

然后顺便把链的性质写了，然后去看 T2。

T2

写了暴力和询问最大的两个性质，然后想了一会 \(a_i = i\) 的性质，发现没什么规律。于是考虑先看一下求一个怎么求。

想到了二分和 Check() 的写法，但是要推推式子，就先跳了，去看后边的了。

T3

第一眼就是 错排，但是有两个限制，不太会啊。猜到答案是容斥，不太会推式子，于是写了个暴力走了。

T4

dmy 部分分最足的一集。

先考虑了区间 DP，记 \(f_{i,j}\) 表示区间 \([i,j]\) 可能获胜的人，可由 \(f_{i,k}\circ f_{k + 1, j}\) 转移。

然后发现这样是不对的，一个区间有多个答案。于是把 \(f\) 开成了 vector，于是复杂度飞升到 \(O(n^5)\)。

考虑转移可以再开一个 \(g_{i,j}\) 表示区间 \([i,j]\) 内可能获胜的手势，也许可以降到 \(O(n^4)\)，但是没有这个点就不写了。

写完 T4 回去想了一会儿 T1，但是由于离谱的多重影响死活想不出来。

然后看了一眼 T3 的 \(\lfloor \dfrac{a_i}{5}\rfloor = \lfloor \dfrac{b_i}{5}\rfloor\)，感觉可做。但是发现需要容斥，就回去看 T2 了。码了一会儿二分，发现预处理和计算好麻烦。

没时间了，寄。

赛后

发现 T1、T2 过了一车，听说 T1 有一个找重心算答案和 \(1\)（如果可以）取 \(\max\) 的做法。赛时毙掉了找重心的想法，这样一说感觉好对啊。

出分后，\(55+20+5+25=105,\text{rk 98}\)，太菜了。@Sorato @konglingzhao @changziliang 太强了，%%%。

@NineSuns AK 了，@ANIG \(350\)，太强了，%%%。@QY2002 / Ech0_7 / empty-space \(200\)，还在隐藏实力？

感觉 T1 比较亏，T2 在时间安排上有一点问题，赛时的正解是可做的。

讲评后

• T1 的思路，枚举节点当作 \(lca\) 比合并两条链的思路，比我想的找链端点更好处理，也不用换根了，很简洁。
• T2 细节上还是有一些问题，比如 \((l,r)\) 的计数赛时还没有想到，应该多练一些这样的推式子的题。
• T3 是大容斥，emmm，组合数学基本板子还好，但是用这玩意算题就比较困难了，还是推式子的能力不太够。状压的分也没写，亏亏亏。
• T4 好像是个性质，赛时真推不出来啊。
• 感觉 dmy 的题感觉好离谱，全是推式子/性质题……

代码源 CSP 模拟赛 Day 7

题目链接

最有前途的一场，但是 GG。

赛时

T1

第一眼肯定是 \(O(r^n)\) 暴力，但是显然没分拿。

于是考虑到枚举答案并记忆化搜索，这样时间复杂度就到了记忆化数组的 \(O(nr)\)。

于是写了个这样的 DFS：

void Dfs(int p, int mask) {
  if (p == n) return (mask <= r[n]) && (++ans), void();
  if (mem[p][mask] != -1) return (ans += mem[p][mask]) %= P, void();
  int &c = mem[p][mask];
  for (int tmask = mask; tmask; tmask = (tmask - 1) & mask)
    if (tmask <= r[p]) Dfs(p + 1, mask ^ tmask);
  Dfs(p + 1, mask);
}

然后造了个 \(\text{Subtask III}\) 的数据，发现 Timed Out。原来没有记忆化上。

加上有了 \(55\text{pts}\)，走了。

T2

发现暴力不会写，尝试推性质，发现退不出来。

于是考虑随机化，然后能过两个样例点，然后走了。

发现还有 \(K=0\) 的点，考虑之后再考虑。

T3

先写了 \(O(2^m)\) 状压。

然后发现树的性质有很多个点，考虑以后再考虑。

通知题面假了，但是之前过了样例。改了代码，然后输出，发现还是过样例？抽象。

T4

先写了暴力，然后写了子树的性质。

不是哥们，一个线段树你就给 \(10\text{pts}\)。

恶心。

然后回去写 T1 正解，但是他会 TLE？

Heldivis：至少应该比纯暴力好，交这个吧。

赛后

发现 T1 从暴力 \(55\) 挂了 \(30\)，然后学长讲了讲发现时间复杂度都是 \(O(2^n\cdot n\log r)\) 这几很疑惑。

然后发现记忆化没记忆上，return res 没写 return f[mask][t] = res 就逆天。

然后发现 WA，于是考虑优化错了，于是交了没优化的 \(O(2^n\cdot n^2\log r)\)，发现不仅过了甚至比有的 \(O(2^n\cdot n\log r)\) 还快？

这不亏死。

讲评后

• T1 的数位 DP 还是比较显然的。
• T2 是个打表 + 三分，比较神奇。
• T3 是从性质推正解的那种题，但是赛时没时间想树的性质了。
• T4 就很离谱，感觉 1,2 操作和 3 操作共存很难搞。

总结

• 注意代码版本，要保证其他版本的能过的点最后一版提交的都能过。
• 注意打表，有的题真的要打表。
• 注意时间，开题过每题暴力最好控制在 \(60\min\) 以内（今天竟然写了俩小时！）。
• 今天这场记忆化直接失忆了，要注意这个细节。

代码源 CSP 模拟赛 Day 8

题目链接

杜瑜皓能不能不要用评测机打原神了啊！

赛时

T1

先写了个暴力 DFS，然后考虑贪心，手玩以下样例发现很有前途，但是发现假掉了。

然后考虑 DP，从后往前 DP，\(f(t,sum,cnt)\) 表示第 \(t\) 个选项，后边所有选择攻击的点到当前决策点的距离是 \(sum\)，有 \(cnt\) 个选择攻击的点的最大值。

发现很难转移，于是走了。

T2

写了个 \(n^4\) 暴力，考虑优化，发现不会。

T3

不会，再见。

T4

不会，再见。

于是，Heldivis 开始了他和 T1 的战斗（）

T1

发现上边的那个 DP 很正确，，虽然状态数量是 \(O(n^4)\) 的，但是用笔记化递归可以省一点。

于是写了代码：

inline ll Fn(int t, int cnt, int poss) {
  if (t == 0) return 0;
  if (f[t][cnt][poss]) return f[t][cnt][poss];
  ll X = Fn(t - 1, cnt, poss + cnt), Y = Fn(t - 1, cnt + 1, poss + cnt + 1);
  rec[t].emplace_back(cnt, poss);
  return f[t][cnt][poss] = max(X + max(1ll * b[t] * poss, 1ll * c[t] * cnt), Y + a[t]);
}

发现本地 NOI Linux 2.0 环境 + CPH on VSCode 显示 TC 2 和 TC 4 都是 800ms \(\color{lightgreen}\texttt{Passed}\)，于是喜悦的提交，发现 \(\color{orange}\text{TLE}\)。于是卡常卡了两页半。

发现本地时间从 800ms 卡到了 600ms，但是还是 \(\color{orange}\text{TLE}\)。

顺便写了个 T4 的 \(5\) 分和 T2 的 \(30\) 分，然后再卡卡，还是卡不过。

气气气！

赛后

老刘 刘教练：你用学校评测机试试。我：我上午就是用的 Linux。

老刘 刘教练：（指 LemonLime）开 \(512\text{ MB}\) 够不够？我：应该够。（然而开了 \(10^8\) 个 ll）

结果显示 \(\color{pink}\text{RE}\)。

随后找到了 CF 原题，但是看见原题空间 \(256\text{ MB}\)，于是开始卡空间。

空间越卡，时间越快，本地从 600ms 卡到了 500ms，交上去 \(\textcolor{lightgreen}{\text{AC}}\)。

感觉应该是清空时数组没用的地方太多，导致清空时很浪费时间。

讲评后

• T1 很对，好像有递推做法，可能就不会被卡了。
• T2 正解是根号分治，赛时想到了做法了，但是不会啊啊。
• T3 感觉比较模拟，但是赛时没有太考虑。
• T4 感觉好神奇。

总结

• 注意实现上的常数 / 细节问题，可能不捆 Subtask 还好，要不然直接 GG。
• 时间分配还有点问题，感觉赛时不去卡 T1 去写 T3 会更好一点罢。

代码源 CSP 模拟赛 Day 9

题目链接

比较简单的一场。

赛时

T1

第一眼发现 \(\&_{i=1}^na_i\) 是没用的，可以全部删掉不管，但是发现没有用。

第二眼是一个一个 AND 起来，直到为是 \(0\)，但是被样例直接卡掉。

然后发现把这俩性质一结合就太对啦，于是直接过了。

T2

感觉之前见过，但是那个好像是任意一个方案就好。

但是还是一样的思路，从后往前找完整的行列。

但是发现没法求最少步数，所以只能回去搜索了。

写了个手写 hash 记忆化，过了特和水的样例。

T3

先想到了二维 DP，\(f(i,j)\) 表示第一个序列到 \(i\)，第二个序列到 \(j\) 的方案。转移是 \(O(n)\) 的。

然后发现只有 \(a_i = a_j\) 的转移才有用，进而发现对于一个 \(i\)，他的 \(j\) 是固定的，优化到了 \(O(n^2)\) 的总复杂度。

T4

已经没有多长时间了，写了个 \(O(n^2)\) 暴力就走了。

赛后

同机房大佬过了一车 T3，说是二维数点。

然后我去看我的二维 DP：

if (p[t][1] > i && p[t][0] > j) Add(f[p[t][1]][p[t][0]], f[i][j]);
if (p[t][0] > i && p[t][1] > j) Add(f[p[t][0]][p[t][1]], f[i][j]);

真的好像二维数点，可能 DP 方向导致不太明显。

@Hthntd 大佬过了 T2，是贪心，感觉比较神奇，膜拜。

讲评后

• T1 / T3 比较水，略过。
• T2 的贪心证明也是搞了搞，感觉很对。然后 bitset 压一下就过了。
• T4 的根分比较神奇，最后正解的倍增也比较神奇，回去再看看。

总结

• T3 这种 DP 题，优化方向不仅要考虑二维压一维，还要想根据方程特点优化，然后上数据结构。

代码源 CSP 模拟赛 Day 18

题目链接

比较简单的一场。

赛时

A

先看了一眼，感觉 \(D=0\) 可以做个连通块内部乘积，然后发现数据范围 \(N=5000\)，那不就是暴力吗。

然后写了个 DFS 发现不过大样例，发现应该跑最短路，于是写了 \(n\) 遍 Dijkstra。

最后不放心怕被卡 \(\log\)，改成 deque 的 0/1 BFS。

B

感觉按照 \(l\) 排序然后贪心选 \(b\) 中 \(l < r_{a_i}\) 最大的 \(r\) 就行了，但是不过大样例。

发现会有左端点覆盖不到的地方，把 \(a\) 按照 \(r\) 排序过了大样例，但是感觉不太对啊，有点慌。

C

写了个记忆化 \(O(|A|\sum |A_i| \cdot|A_{i+1}| )\) 的暴力，想优化一下但是复杂度改不了。

然后考虑容斥，发现不会容斥。

D

写了个 \(O(N^2)\) 的 DP，然后考虑 \(a_i=0\) 的性质发现上个线段树就好了。

讲评

A、B 就不说了。

C 是根分，但是赛时没想到选最小的作为起点跑感觉唐了。

D 是李超树，不会。

总结

• 出分前害怕 A 写挂、B 的贪心假了还是比较慌的。感觉应该对拍一下的。
• C 时间复杂度没分析准，要不然应该能看出来第一项越小越好的。

代码源 NOIP 模拟赛 Day 1

题目链接

锟斤拷，唐唐唐

赛时

A

第一眼看，没什么思路，先玩了一下样例，发现好像 5 00011 这个样例输出的 \(10=5\times2\)，大胆猜测：连续相同若干个字符形成的一个串互相独立。

然后不太敢写，玩了一下样例，发现不管怎么移动都是 123456 在前六位，剩下的在后边四位，感觉有一个性质就是他这个数字排序后只能在相同字符串内交换，否则一定不合法。

然后码了个暴力，跑了一下小数据发现确实是对的，然后发现显然 000 和 111 的贡献相同，于是打了个表发现这个贡献是 \(\{1,2,5,14,42,132\}\)，欸这不是 Catalan 数吗，然后就按照这样写，发现过了样例。

B

先打了个 \(sg\) 函数的表，发现对于一个 \(x\) 有 \(sg_x(i)=i\bmod(x+1)\)，所以直接 \(O(n^2)\) 模拟就有了 \(n\le5000\) 的 \(30\text{ pts}\)。

然后考虑一下这个取模的性质，感觉很可以根分 (?)。然后考虑了一下，对于小于根号的直接暴力，然后对于大于根号的好像可以枚举倍数然后用个数据结构什么维护一下，感觉很对，考虑权值线段树，但是发现它这个异或的运算不好同时减去一个偏移量（当时脑子抽掉了感觉 \({(x+d)\operatorname{xor}(y+d)\to x\operatorname{xor}y}\) 可以处理一下 \(\operatorname{xor}d\) 什么的算出来），所以寄掉了。

然后发现有一个 \(n\le50000\) 的点，欸这个数据范围非常暧昧啊，感觉是留给手法的，所以加了异或的去重和对于 \(a_i\lt x+1\) 提前处理的优化交了，但是本地造的极限数据跑了 \(2600^{+}\text{ms}\)，感觉不太可过。遂换题。

C

第一眼感觉第一问第二问没关系，因为没看见让“求出 \(p\) 在所有合法排列中字典序的排名”，以为直接康托展开^{@PinesppleSummer 大佬赛后告诉我了这个词，%%%}就可以了，然后很快会了第二问。

考虑对于 \(n\le20\) 状压，发现不会，考虑对于 \(n\le 10\) 枚举全排列，发现第二问寄了，然后睁开眼睛发现了合法二字，于是改了一下计数就好了。

然后考虑 \(f_i=1\)，发现对于 \(q_1=1\)，\(p=q\)；否则 \(p_i=\left\{\begin{align}&1&i=1\\&n-i&i\neq 1\end{align}\right.\)，然后所有方案都是合法的，按照上边那个算就好了。

因为 \(n\le5000\)，所以可以 \(O(n^2)\) 算排名，但是直接上树状数组了……

D

考虑 DP，\(f(i,j)\) 表示前 \(i\) 个数，操作 \(k\) 次的最小最大值。

发现这个最小最大值很难转移，样例都难过，于是 ban 掉。

考虑一个贪心，每次删去最大子序列的值就好了。

然后眼睛再次瞎掉，没看见要求子序列非空，\(mx\) 初值给的 \(0\)，导致样例还是过不去，改了就过样例了。

赛后

A 听说 @R_Lydic 和 @Sorato 等大佬从 DP 推了结论，好像还有格路计数推的，%%%。但是 @R_Lydic 分段假了导致爆零，菜 引以为戒。

D 发现没取模到正数，15 分啊！

讲评 / 总结

• A 是一个特殊图的拓扑数计数，就是这个结论。
• B 是按照倍数分开做不太会……
• C 是有个讨论，即：枚举前边相同的部分，对不同的第一位进行讨论，然后上数据结构。
• D 炸了，赛时要造一些边界数据卡一下自己。

代码源 NOIP 模拟赛 Day 2

题目链接

“我们普遍认为，@Sorato 有 IOI \(\color{yellow}\text{Au}\) 的实力。”

更唐了，挂的分比得的分多。

赛时

先看了 A 题，感觉不太会，胡了几个瞎构造，只能过小样例。不会了，写了个暴力走了。

然后看 B 题，还不会啊，一看暴力只有 \(10\) 分，先走了看 C 去了。

看见 @Sorato 已经过了两道题了，很慌。看 C 想了一个 DP，\(f(i,j)\) 表示两行走到 \(i,j\) 的方案，写了发现是 \(O(n^3)\) 的，先写了。然后发现所有正数一定是选的，考虑了一下负数的转移，发现没太大用。

去看 D 了，发现是个期望，胡了个暴力发现跑的飞快。看到 \(n=5000\)。欸这个数据范围非常暧昧啊，感觉是留给手法的。于是卡了卡常，交了一发固定 \(n=5000\) 发现跑了 \(500^{+}\text{ms}\)，高兴了。

回去看 C 了，想转化一下题意跑个其他的 DP，发现不会，看到有一个 \(n=3000\) 的点，考虑能不能优化现在的 DP。推了推式子发现是要求 \(O(n)\) 个序列的最大值，每次有一个 push back 的操作，因为看到有 \(nk\le1\times10^7\) 的一个点，感觉是单调队列什么的，所以先写了个 set 优化 DP，发现有点问题，所以直接上了个线段树，但是还是会超时，于是又开始卡常，卡到样例 \(600^{+}\text{ms}\)，于是结束了。

赛后

期望得分：\(20+10+25+50=105\)；

实际得分：\(0+0+10+30=40\)。

评完后，发现 A 有 \(20\text{ pts}\)，还有 \(0\text{ pts}\)，然鹅最后一发是 \(0\)。注意到 A 题的假做法可以过小测试点，然鹅暴力会 T 小测试点。？，我直接怒了啊。

然后注意到 B 题有一个 input: n；output: 1 的点但是我的输出 0？我直接怒了啊，怎么还带这样玩呢。

然后注意到 C 题没冲过去，当时考完就感觉可能 \(k\) 比较大冲不过去，但是突然发现 \(k\) 足够大的时候就是 \(a_1+b_1+a_n+b_n\sum\limits_{i=2}^{n-1}([a_i>0]\cdot a_i + [b_i>0]\cdot b_i)\) 了。

然后又注意到 D 没冲过去，发现是 WA 了，感觉是因为卡常导致取模取少了，改了真就过了。

总结

• 感觉 A 考点是 LIS 的理解，赛时想到了根据大小关系建图的想法，但是少考虑了一步贪心向最近的点连边的策略。
• B 是 manacher + KMP，思路是分两类讨论，赛时没有发现这两类的讨论，感觉分类后就挺好写了。
• C 是优化建图 / 模拟 Dijkstra，感觉赛时没有建图。
• D 是跑容斥，不会。
• 常数害人不浅，一定要注重自己的常数问题，卡常时候别卡少超时，也别卡太多把正确性搞没了。

代码源 NOIP 模拟赛 Day 4

题目链接

哗哗哗。

赛时

先看了 A，发现题目只说了随一个 \(x\)，没说干啥，傻了几分钟有 dalao 说看一眼题目（？）写了个记忆化搜索暴力，交了发现 输出没换行 过了样例，考虑先看 B，一会再来看 A。

发现只有 3.、4. 操作随便跑一个 Topsort 就可以了，考虑对于其他两个操作应该是建一个虚，然后连边，但是发现不是很会构造方案，就先跳了。

然后看了 C，发现暴力比较难写，去写 D。写了一个 \(O(n^3)\) 暴力。

这时候感觉暴力写差不多了，感觉 A 和整除分块有关系，推了推式子，写了一个枚举因子后查个数的，结果比原来跑的还慢。

恶心到了，想起来 B 比较可做，想了一会还是不太会构造，于是写了一下暴力再看看 D。

本地跑了一下大样例，发现大样例 WA 了，发现 !st.empty() 写成 st.empty() 了，改了发现本地带编译跑 \(4500^{+}\text{ms}\)，感觉很可以卡常啊。

于是卡了 \(20 \min\) 的常，最后样例 \(n=2000\) 跑了 \(2400\text{ms}\)，感觉寄了。

感觉 A、B 太可做，A 又写了几个方法发现还是不如暴力。

然后发现 D 一车人过了样例两个点，发现 \(k=1\) 是一个本质不同的子序列计数。码了，过了。

赛后

预估 \(40+30+10+10=90\)，实际 \(50+30+10+35=125\)。

A 多十分是因为测试点数错了，然后 D 的每个提交基本都卡过了……

发现机房一车 \(125\)。

讲评

• A 的整除分块是再套一个根号分治，步长大于根号暴力，小于的开前缀和。
• B 确实是建图，输出方案直接从大到小赋值就行了，因为好像有一个 \((x)\to (y)\) 的限制一定会在之前 \((y)\to(x)\) 满足的证明。
• C 是转化之后跑区间 DP，有点难。
• D 不会。

总结

• 不要再卡常了！！！！！！！老老实实想题去！！！！！！！
• 感觉赛时 B 的思路是对的，但是就是没太敢尝试构造，要不然感觉能过。

代码源 NOIP 模拟赛 Day 9

T1 赛时在想从 \(i\) 的答案转移到 \(i+1\) 想剪枝冲一下 5E4 的点，但是分段写假了爆零了。赛时没想到把分母乘出去。

T2 想到 DP 了，但是推式子没退出来，然后暴力也假了，于是改了改，本来数据水能冲过去结果 WA Sub1、TLE Sub3。

T3 看到最大化期望就不太会。

T4 写了个暴力，赛后想了想，想到一个方法，但是需要动态维护区间颜色数，感觉有点寄。

代码源 NOIP 模拟赛 Day 11

题目链接

＼线段树／ ＼线段树／ ＼线段树／

赛时

先看了 A，观察样例，发现每次都是向周围扩展一圈得到一个新数字，那么最终 \(k=d(s,t)\)。对大样例使用最短的，得到 \(d(s,t)=k\)，考虑构造方案，发现每次 \(x\to y\) 的边可以直接赋值为 \(d(s,y)\)，剩下的边因为不能超过 \(k\)，于是仅当 \(d(s,y)\le d(s,t)\) 时赋值，其余为 \(0\)，交了，第一发 RE，检查发现代码里有 const int M = N * N;，但是 int ans[N];，改了 int ans[M]; 过了。

看 B，发现暴力很好写，于是写了暴力。然后突然发现 A 题有 \(n\le 400\)，但是写了 \(O(n^2)\)，担心假了。于是交了若干发测试 SPJ 是否好的，发现全判掉了，于是交了一发正解走了。

继续看 B，发现这个 \(O(n^2)\) 暴力很没前途，考虑换个暴力。发现每一个的数对一个区间长度的答案仅与这种颜色位置的前驱后继有关系，于是改成了 \(O(n^3)\) 的暴力，过了样例，然后推式子，发现了贡献是三个等差数列求和 \(A-B-C\)，考虑使用线段树维护「区间加等差数列-单点求值」，发现这样很脑残，于是改成线段树维护答案的差分数组，就变成了「区间加-区间求和」。开始写，发现假了，开始调，【数据删除】，\(40\min\) 后发现对 \(\ell\sim r\) 做差分时没有在 \(r+1\) 处还原，啊啊，服了。过了样例，交了，过了大样例，爽了。看到 @Sorato @Hthntd 的跑的飞快，于是开始卡常，去了 #define int ll，特判了一点点情况，吸了口臭氧交了。

然后开始看 C & D，没看懂，考虑考虑一下 A，上了个厕所，发现他 SPJ 可能偷懒写的 \(O(n^3)\) 才开的 \(n\le400\)，感觉很有道理。

然后发现 C 没有 邮 油箱限制随便做，加上好像不太好做，又看见 \(W\le10^5\)，于是设 \(f(d,x,w)\)，发现不会 DP，于是用最短路的形式跑 DP。然后发现寄了一点，于是【数据删除】，半个小时后过了样例，发现跑 \(n=100\) 会 RE 3，不管了。

然后去写 D，写了个复杂度不明的暴力，但是过不了样例，发现没有保证是导出子图，于是开始改，改完了发现能过样例，就这样吧。

回去检查了一下 A & B，发现没太大问题，想了一会 C 发现不会，GG。

赛后

估分：\(100+100+30+[0,15]=[230,245]\)，

实际：\(100+100+20+15=235\)。

发现 C 的第一个 Subtask 寄了，发现这个点 \(W\) 的确跑不动，赛时没算好，多了个 \(n\log n\) 没没算进去。

讲评

• A 的 SPJ 好像可以写到很快，这个问题感觉可以想想。
• B 有一个两次差分的做法，感觉常数极小。
• C 发现只有卡满油到下一个点，和加满油两种情况，分开 DP 就好了。
• D 智慧题……

总结

• 感觉这场还行。
• A 猜的结论，挺对，但是有点不自信，耽误了一会。
• B & C 调试时间过长，细节问题没有很快找到。