lzm0107 的博客

Day 0 (2.28)

试机，按照惯例试了一下 \(2000\) 的 ULL Floyd，8s。

Day 1

进场、发密码、看题。

怎么输入里有测试点编号，这么良心？

看完 T1 感觉可能的中位数应该是一段连续区间，这样两个二分就做完了，至于 check，可以 \(O(n)\) 计算最多有多少个 mid，比 mid 小的数和比 mid 大的数的个数差的最小值，简单判一下。

写写写，发现不对劲，这东西可能会把不存在的数算进答案里。

至少 check 的思路没问题，那就直接离散化把值域搞成 \(O(n)\) 个区间，每个数能不能成为中位数只和它所属的区间有关，check 可以用一个扫描线和一堆树状数组做到总共 \(O(n\log n)\)。

T2 先写了一个 \(O(nq)\) 暴力。

看一看，发现它时间 6s，空间 2G。算一算，发现 \(10^{10}\) 个 bit 比 2G 小。

那就 bitset 处理能否到达。然后怎么做呢？看一眼部分分，AB 性质可以分块做，赶紧写了，拼上 \(O(nq)\) 20pts，有测试点编号就是好写！

T3 根本不会！暴力只会 \(O(Tn!m^2)\)，算下来 \(n \le 10\) 卡满都 \(10^{10}\) 了，不太能过。

然后还是写上去了，发现样例跑得飞快，完全不像 \(10^{10}\)，不管了。

Day 499122178

出考场，听说 T2 是根号重构，太强啦！但我怎么不会？

Day 2

一看 T1 怎么这么熟悉？ABC 原题？线段树维护 \(pos_i-i\)，写几个线段树上二分和区间推平秒了。

第二个样例怎么错得离谱？哦原来还可以往前推的啊。往线段树里加了个区间最小值之后标记下传又错得离谱了，调了不知道多久后过样例了。

完全不拍！相信大样例！开 T2！

性质 A 纯暴力，先写了个 \(O(4^m)\) 枚举边的存活状态，然后爆改 prim 再乘个 \(O(n^2)\)，一看怎么样例二第一组数据没过？\(1280\rightarrow 1256\)，重写了两遍还是不对，合理怀疑 prim 没正确性，直接枚举外向生成树的 \(n-1\) 条边过了。

性质 B 生成树唯一，容斥枚举哪些点能够到达其他所有点，样例能过。

试图将性质 A 与性质 B 进行对拍，发现每棵树拍出来的答案都一样，猜测树的形态没有影响，不过容斥都写完了。

开 T3，暴搜启动！

Day 3

还原了一下自己的 D1T1 和 D2T1，过洛谷民间数据了。

Day 6

\(100+24+8+100+24+8=264\)。感觉还行。

D1T2 \(O(nq)\) 有 88pts？

Day 0 (1.13)

下午到达酒店，按理来说应该两个人一间房间的，但我们有九个人，所以喜提大床房一间。

晚上去吃地锅鸡。

“你跟他说我们是重庆的，给我们上特辣。”

“啊？”

玩狼人杀，抽到预言家，但查了一个好人和一个自刀狼就被女巫毒了（？

晚上电脑和手机被收了，于是开始研究酒店的语音助手和电话，给 @LZYAC 房间打了两个电话结果他们没接。

Day 499122177

本来应该是 7:40 起床，然后被 @LZYAC 6:40 敲醒了，经过交流才知道我昨晚打电话时他们已经睡觉了。

吃完早饭前往龙山书院，到了之后才发现我们九个好像就我没背着包出来……

然后一整个上午都面临非常非常非常严重的水资源短缺，直到 12:20 试机前才买到两瓶水。然后考场旁边就出现了几箱水并且可以自取？

注意到考场发纸但不发笔且我的笔袋在酒店里。不过没事反正我 CSP 的时候也没用过草稿纸。 但我 NOIP 草稿纸不是写满了？不是写满了？不是写满了？

Day 1

T1

注意到这题十分熟悉，但我没管，猜测策略只有两种：

1. 将当前的第一节电池与其他所有电池进行测试直到成功或可以证明第一节电池为坏电池为止。

2. 将当前的第一节电池与第二节电池测试，不成功直接丢掉。

于是考虑 DP，\(f_{i, j}\) 表示当前有 \(i\) 节好的与 \(j\) 节坏的，最坏情况最少猜测次数。复杂度为 \(O(ab)\)。

显然错误。但为什么这题这么熟悉呢？回忆一下，原来我在去年不知道啥时候做过这题的一组 \(a = b = 4\) 的数据啊，回忆一下当时怎么构造的。

1
2
3
4
5
6
7
8

7
1 2
1 3
2 3
4 5
5 6
4 6
7 8

观察一下

1
2
3

1 2
1 3
2 3

它的意思是使用 \(3\) 次机会确保前 \(3\) 节中至多 \(1\) 节为好电池，然后直接丢弃前 \(3\) 节电池。

再仔细思考一下，这意味着可以使用 \(k\choose 2\) 次机会确保前 \(k\) 节中至多 \(1\) 节为好电池，然后丢弃前 \(k\) 节电池。

因为是最坏情况，所以前 \(k\) 节中必定有 \(1\) 节是好电池。

将其加入到转移中，此时复杂度为 \(O(a^2b)\)，400ms 轻松通过。虽然我也不知道为什么是对的。

T2

排序去重 + 树剖求 \(k\) 级祖先有一个 24pts 的暴力，啥也不管直接写了。

感觉可以离线询问然后枚举 \(x\)，对于每个 \(x\) 的询问像 P1972 一样扫描线处理，时间复杂度为 \(O(n^2\log n+m\log n)\)，也是 24pts。

在扫描线中将树状数组换为 \(O(1)\) 修改的分块就可以 \(O(n^2+m\sqrt n)\) 了，看起来还是过不了 Subtask3，但观察到时限给了 4000ms，由于 A 题带给我的对于评测机的信心，我决定写一下这个东西。

TLE 24pts

加了个快读仍然 24pts，跑路去做 T3 了。

T3

\(O(n^2k)\) DP，加了个 bitset，20pts。

Day 499122178

出来发现大家好像都是 144，疑似大众分？

经过交流知道了 T3 tarjan 缩点可以做到 \(O(nk)\)。

Day 2

炸飞了写什么游记？炸飞了写什么游记？炸飞了写什么游记？

Day 0 (11.29)

上午复习了三个 tarjan。

下午试机，听洛谷讨论区说 CCF 评测机跑 \(2 \times 10^3\) 的 ULL 自然溢出 Floyd 需要 5s，在考场的电脑上试了一下，12s，另外还试了在 qingyu 博客看到的 -fsanitize=address,undefined 和 ulimit -v，本来还想试一下对拍的，但是没打完就回去了。

晚上完全不知道干啥。

Day 1

进考场，和 CSP 一样还是开着 Windows，等极域发了密码我就赶紧重启成 Linux 了。前十分钟先开 VSC 敲了个缺省源。

读 A，发现自己好像不太会，于是边写边想，第 70min 写完，结果调不出来。于是直接重写，第 90min 过大样例。

然后开 B，一眼看出 \(d_j\) 不影响答案，也就是如果 \(j\) 是 \(i\) 下一个赋值的，那么有两种情况。

1. 从 \(i\) 开始的限制最后传到了 \(j\)，显然有 \(v^{j-i}\) 种方案，其中 \(\frac{1}{v}\) 的方案（即 \(x_{j-1} = a_j\) 的方案）是合法的。

2. 从 \(i\) 开始的限制最后没传到 \(j\)，有 \(v^{2j-2i}-v^{j-i}\) 种，全部合法。

将每段的合法方案数相乘，再特殊处理首尾两端，需要注意 \(c_j\) 相同的情况。

在草稿纸上写完上面这些直接开写，140min 左右过大样例。

C 题先写了一个 \(k=1\) 的 24pts，大概就是在很多个完全子图里任选一条钦定了一端的链，方案数为 \(\prod\limits_{i=1}^n (deg_i - 1)!\)，第 174min 写完。

写完 C 的 24pts，决定先看看 D，发现求 LCA 是可重复贡献的，而且满足结合律，用两个 ST 表写了 \(n, q\le 5000\) 的部分。回去看 C，观察第九个样例（一条链）发现全是 1，第十个样例（菊花图）的式子也很好推，于是喜提 16pts。

再看看 D，感觉自己的双 ST 也可以做 \(k=r-l+1\)，花五分钟改了一下。链的 32pts 脑子过载，一眼没看出来就没想了。时间只剩半小时，开始检查，发现自己 D 没写 freopen，赶紧加上。最后十分钟切回 Windows，等待结束收代码。

此时估分应当为 \(100+100+40+32=272\)，但由于我看错了 C 部分分的测试点个数，所以以为自己是 \(100+100+44+32=276\)。

比赛结束，然后别的考场十分钟收完，我们考场收了半个小时（？

赛后才发现 D 链的 32pts 非常好拿，不过我也拼了个 32，感觉还行吧。

感受

感觉这场自己打得比较保守，比如最后半小时没去冲链的 32pts。但是再想想，就算写出来也可能忘记 freopen。

另外，-fsanitize=address,undefined 好用！

跟风。

查浏览器，但是……

初赛

Day 0 (2024/9/20)

有的人，明天早上就要 CSP 了，却还在打 CF（

五题 WA 了四发，有多菜不用说了吧。

Day 1

上午

还没开考就发卷子了，第五题一眼 1048576，每次算空间都用的，再一眼原来是 bit 啊（

但是第十题我真的很想选 B。

Linux 只是内核，GNU/Linux 才是操作系统！

改二叉树遍历顺序的选项已经成了 CCF 传统艺能了吗？

阅读程序 <=n 看成 <n 了，痛失 3 分。

感觉真的一年比一年简单了。

下午

因为考场没有钟所以监考老师用希沃白板搞了个计时器？还能看到秒数？

发卷子 为什么我上午倒数第二个发，下午就成第一个了。

第十题感觉是 \(O(n\alpha)\) 的，但没看到 所以 CCF 是把 \(\alpha\) 当成常数了吗？

第十五题一开始数漏了一组，后来改了。

第三十一题直接按 123456 的顺序算的，没中序遍历，寄了。

晚上

ABC，Perf 第一次上 2400。

但 AC-predictor 告诉我 1936 的 rating 呢？怎么变 1937 了？

复赛

Day 0 (2024/10/25)

上午

随便复习了下 Splay 虽然模板题都没调出来。

下午

去考点试机啦。

考点是双系统，试机时还没断网。先试了下 NOI Linux，拿 VSC 试了下代码片段，打了个最短路模板，因为没有洛谷大号密码所以交小号上去了。

然后试 Windows，给了 VSC，上面还装了中文插件和 C++ 插件，甚至还能用自动补全 /jy。

键盘也很好用，反斜杠和回车的位置很顺手（

Day 1

上午

一进考场就开着 Windows，反正我也不太想拿 Linux 下那个啥也没有的 VSC 写代码。

开考了，先用 VSC 的代码片段默写了一下我的缺省源。接着开 A，写了个 set<string>，非常弱智地没有使用 52 - st.size()，而是枚举每个字符串判 st.count()。

B 没啥好说的。

C 写了一个逆天 DP，大概就是让 \(f_j\) 表示在总共使用 \(j\) 根火柴棒，且可以全部拼成 \(0\) 的情况下的最优方案。让 \(g_j\) 表示至少有一个非 \(0\) 数位的最优方案。方案都指的是多重集，所以时间复杂度大概是 \(O(nD + T)\)，\(D\) 指有用的数位的个数？不知道有啥正确性，但我的直觉告诉我它就是对的。

写完 C 大概已经 10:10 了。

看 D，一眼出了一个 \(O(r{\sum l}^2)\) 的 DP，就是把一共 \(2 \times 10^5\) 个 \(S_{i, j}\) 拍到一个一维数组上，记作 \(a\)，然后 \(f_{i, j}\) 就表示有没有方案可以使第 \(i\) 轮结尾的数字为 \(a_j\)。显然这个东西把状态的定义从“有没有方案”换成“有几种方案”就可以差分优化，时间复杂度为 \(O(r\sum l)\)。

写完；发现大样例跑了九秒多；发现自己没开 O2；发现开了 O2 也才四秒多；猜测 Windows 下测试有误差；关机启动 Linux；发现 Linux 下也跑得一样慢；随后就进入了漫长的卡常时间。

然后我还惊奇地发现 Linux 下的 VSC 突然就变成了最新版带中文带补全，明明昨天试机的时候还是 1.54.3 的。

经过了一个半小时的不懈奋战，终于把大样例卡进了两秒。然后就发现大样例的前两组数据的 \(\sum l\) 是 \(2000\)……

12:00 比赛结束，然而还要核对源代码，每人发了张打印了收上去代码字节数的纸。而且核对源代码怎么只核对字节数啊，为什么不核对一下 SHA256 什么的。

12:20 出考场，发现别人 C 好像都是找规律做的，而且 D 并不像我想象的一样人均正解卡常。

估分：\(100+100+100+100=400\)。

下午

下午入场怎么多了个安检。

解压发现有道题目叫 "duel"？CCF 怎么知道我前几天在某个网站上 duel CF 直接从紫掉到青的（

开考发现原来这个是 A 题啊，赶紧切了。

看 B。CCF 怎么知道我国庆以来停 WHK 错过了我们班神奇的 WHK 进度（语文七下，英语八上，还有物理），在这放道物理题偷袭我（

还好给了公式，二分一下就写完了。

C 题一眼出了一个 \(O(n\min(n, V)^2)\) DP，然后再一眼优化成 \(O(n\min(n, V))\)，再一眼优化成 \(O(n + V)\)，赶紧开写。

写完 C 过了大样例的时候是 16:00，反应过来这场好像非常简单，感觉自己认识的都要人均 300+ 了。

此时我还有两个半小时的时间，感觉自己可以随便浪了，就硬想 D 想了两个小时，才反应过来时间不够了。赶紧写一下自己刚想出来的 \(O(Tn\log n)\)，结果 WA 在了样例 4，也没时间调了，按照前三个样例的数据范围看，应该能拿到 32pts。

估分：\(100+100+100+32=332\)。

闲话

在 Day 1 中，我一共写下了 \(14\) 个汉字，其中有 \(0\) 个写在了草稿纸上，剩下的 \(14\) 个分别是：\(2\) 个“代”，\(2\) 个“码”，\(2\) 个“一”，\(2\) 个“致”，\(2\) 个 [l]，\(2\) 个 [z]，\(2\) 个 [m]。

Day 10

CCF 的评测机是强的，给我 J 组的 D 题放过去了。

CCF 的数据也是强的，没给我 S 组的 D 题留下一分。

J: \(100+100+100+100=400\)

S: \(100+100+100+0=300\)

今天看到一个帖子求随机数用法，看到回复都在使用 rand()，就突发奇想来比较一下 rand() 与 mt19937 的性能。

测试环境

测试于虚拟机中进行。

• 虚拟机软件：VMware Workstation 17 Pro
• 操作系统：Ubuntu 24.04 LTS
• 编译器：GCC 13.2.0
• 编译命令：g++ ./Code.cpp -std=c++14 -O2 -static -o ./Code
• CPU：AMD Ryzen 7 6800HS Creator Edition × 2（核）
• 内存：4096 MB

测试方法

使用 rand() 和 mt19937 分别生成 \(10^7\) 个随机数、计算异或和并记录使用时间。另外还记录了计算 \(1\) 到 \(10^7\) 的异或和的程序所用时间。为避免误差，测试进行三次。

测试结果

注：每次测试结果的第一个数是计算出的异或和，第二个数是运行时间。

rand()

1
2
3
4
5
6
7
8
9
10
11

#include <bits/stdc++.h>
using namespace std;
int sttime, edtime, ans;
int main(){
	srand(time(NULL));
	sttime = chrono::system_clock::now().time_since_epoch().count();
	for(int i = 1; i <= 10000000; i ++ ) ans ^= rand();
	edtime = chrono::system_clock::now().time_since_epoch().count();
	cout << ans << ' ' << edtime - sttime << '\n';
	return 0;
}

第一次：69721856 166411749

第二次：1482914441 163781860

第三次：985165798 165527310

mt19937

1
2
3
4
5
6
7
8
9
10
11

#include <bits/stdc++.h>
using namespace std;
int sttime, edtime, ans;
mt19937 rnd(time(NULL));
int main(){
	sttime = chrono::system_clock::now().time_since_epoch().count();
	for(int i = 1; i <= 10000000; i ++ ) ans ^= rnd();
	edtime = chrono::system_clock::now().time_since_epoch().count();
	cout << ans << ' ' << edtime - sttime << '\n';
	return 0;
}

第一次：-1197154284 54221094

第二次：1446003541 51768240

第三次：-528284598 50928197

\(1\) 到 \(10^7\) 的异或和

1
2
3
4
5
6
7
8
9
10

#include <bits/stdc++.h>
using namespace std;
int sttime, edtime, ans;
int main(){
	sttime = chrono::system_clock::now().time_since_epoch().count();
	for(int i = 1; i <= 10000000; i ++ ) ans ^= i;
	edtime = chrono::system_clock::now().time_since_epoch().count();
	cout << ans << ' ' << edtime - sttime << '\n';
	return 0;
}

第一次：10000000 8881985

第二次：10000000 9048101

第三次：10000000 8922749

测试总结

总结：别用 rand() 了（