lzm0107 的博客

发表于 更新于

初赛

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

Code

 
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

Code

 
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\) 的异或和

Code

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

0%