lzm0107 的博客

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() 了（