游记 CSP2023-S2
今年根本没有报名 J 组。
听说有人要开盒，感觉差不多得了，oierdb 搜 cjh 第一个就是我啊，怎么藏？感觉真的有有心人在查我，我早就被打回去了啊。
9.16
初赛过了就是过了，游记弃之，作文素材 +1。
10.20
在 S 校进行集训，打模拟赛，怎么突然这么会打了，能过两个题了，感觉很厉害，然后 xzzduang 马上给我打爆了。
今天是星期五。中午的时候，xzzduang 来了。他从周四模拟赛（他组题）讲起，说代码能力，说南京卷王怎么卷，然后大概后面的时候 Robin 过来聊起高考分数。令我惊奇的是，南京的卷王，他们除了每天 NOI 模拟赛的三个题都写完，还有 ARC 全部做完，CF div1 全部做完，俄罗斯有个训练营也全做，ucup 还有的时候也全做。
我问
10.21
8:00
和 S 校同学讨论虚拟机问题。算是知道了共享文件夹怎么用。
- zhangtx：为啥你们这群初中崽都没去考j啊
- caijianhong：因为去年AK了
- NobodyThere：是这样的
- NobodyThere：总之就是没必要考吧
- crxis：今年入门组新增1000人，但是ak人数却大大减少了，为什么呢？
- crxis：……所以早上可以参加入门组，顺便试机吧
13:40
OK 啊这边也是在石门中学打卡，还在下雨，好冷，怎么又是科学楼五楼，考 NOIP2022 的地方，完了怎么这么熟悉，完了怎么环境是完全一样的，求求了不要重现 NOIP2022（我的辉煌战绩之 NOIP2022 挂掉整整两个题获得整整 87 分）
14:05
怎么没人认出我？
为什么矿泉水瓶要将标签撕掉？那么水杯呢？我的铁打水杯和纯透明矿泉水瓶怎么都进去了？？？
14:27
密码下发了，具体忘了（因为今年游记是赛后写的）
键盘抬起！
但是下发文件在哪里？我看看快速访问，D:\ 没有，E:\ 没有，C:\ 没有，C:\user\admin_\Desktop 都没有？然后考生注意事项，怎么查看 pdf 的文件所在路径呢？但是桌面有个虚拟机，先来点虚拟机启动。暂时先不要管下发文件了，先玩玩虚拟机。
虚拟机开机。我还是第一次用 NOI Linux 虚拟机（真的），然后发现了 ~/桌面/ 下面的 share_dir 和 share.sh。想必是共享文件夹，但是怎么用？运行 ./share.sh，问我 admin_ 的密码？？？傻掉了
14:30
老师您能不能帮我看一下这个虚拟机怎么用共享文件夹？
（同一时刻终于发现文件在 F:\ 下，吓死了，好慌）
老师：我去找个人帮你解决一下。
开题，先看一遍题目。
T1 是个什么题？\(5^{10}=9765625\)（算错了应该是 \(10^5\)），直接暴力能过吧。
T2 首先有一个明显的栈做法，类似括号匹配，可以做一下。
T3 什么模拟能放 T3 的？
T4 是个什么题？连通块 DP？
在等待的过程中，我发现 windows 下有 gvim（梁老师诈骗我说只有 dev-c++ ？）。直接启动 powershell 在 windows 下完成了 T1 的代码。看上去很好写，有个溢出和相邻的问题，调一下就过了。那么现在是
14:59
也就是平常 8:00 开始模拟赛对应的 8:30，我怎么这么厉害秒 T1 了？
老师过来了。指导了一下，首先离开虚拟机环境，打开设备，共享文件夹，其它路径，挂载，自动挂载，然后就能传文件了。
我问老师，最终代码提交到那里？老师说是 windows。好的。
心中的一块巨石落地，今天可以纯用虚拟机完成代码。正片开始。
我把共享文件夹扔到 F:\，重新挂载，试了一下虚拟机关机。根本关不掉虚拟机，只能挂起。然后再次阅读 T3，发现 T3 就是纯纯的模拟，发现 T4 的起始点是 1 号点，好像能做了？
15:30
好像是这个时间吧，写了暴力。大致思路是，枚举左端点，扫过去，用一个栈。加入新字符时，如果与栈顶元素相同，弹栈，否则入栈。在所有使得栈空的右端点统计答案。这是一个 \(O(n^2)\) 暴力。
为了优化暴力，首先就是想能不能利用前面的匹配信息。若从右往左扫，可以搞一个 \(to_i\) 表示他第一次能弹空栈的地方是哪里，或者是 \(to_i=n+1\)，那么如果 \(to_i\leq n\) 则 \(f_i=f_{to_i+1}+1\)，其中 \(f_i\) 是以 \(i\) 为右端点的答案。
进一步的我们发现可以写一个暴力，就形如初始令 \(j=i+1\)，循环当 \(a_i\neq a_j\) 时，使得 \(j=to_{j}+1\)。当然 \(j\leq n\)，否则报告 \(to_i=n+1,f_i=0\)。
考虑这个过程，因为字符集太小了，考虑 \(nxt_{i,r}\) 表示当 \(j=i\)，\(a_i=r\) 时最终会跳到哪里。那么 \(to_i=nxt_{i+1,a_i}\)。如果合法，那么从 \(nxt_{to_i+1}\) 继承所有信息，同时 \(nxt_{i, a_i}=i\)。
复杂度 \(O(26n)\)。稍微调一下边界，过一下大样例，过了。这题的数据很难造强，不打算对拍。当我将代码提交到 windows 时已经是
16:00
也就是平常 9:30，一个小时过掉 T2。进度有点快了。因为 T4 暴力有点难写，不确定在树上贪心的想法是不是对的，打算写个 T3。
T3 分界线
T3 是个大模拟，C++ 是没有 eval 这种东西的，比较暴躁。这题的重点是怎么存储结构体和变量，以及计算 offset（偏移量）和 align（对齐）。
写一个 type_wrapper 表示一个结构体。
struct type_wrapper {
vector<pair<string, string>> vars;
LL Align, Size;
vector<LL> offset;
};
vars 就是结构体变量，使用 vector<pair<string, string>> 存，first 是类型，second 是名称。Align 就是对齐规则，Size 就是真实大小，offset 是每个变量的偏移。话说想起来小周老师写的，会出技术类大模拟，果真如此。
使用 map<string, type_wrapper> mp 存储所有结构体信息。
操作 1
int k;
string name;
cin >> name >> k;
type_wrapper typ;
typ.Align = 0;
typ.offset = vector<LL>(k);
for (int i = 0; i < k; i++) {
string t, v;
cin >> t >> v;
auto &&mpt = mp[t];
typ.Align = max(typ.Align, mpt.Align);
if (i != 0) {
LL tmp = typ.offset[i - 1] + mp[typ.vars.back().first].Size;
typ.offset[i] = calcoff(tmp, mpt.Align);
}
typ.vars.emplace_back(t, v);
}
typ.Size =
calcoff(typ.offset.back() + mp[typ.vars.back().first].Size, typ.Align);
mp[name] = typ;
cout << typ.Size << " " << typ.Align << "\n";
就摁建，摁算就是了。
calcoff 就是算对齐的，是一个向上取整再乘回去的东西。
操作 2
全局的变量，存储方法有一点不同，其实可以再新建一个 root 类型。但是因为我一开始没有看到全局变量也要对齐（？）所以还是开在外面，用 f 前缀标志全局（final，不对啊反了，不管）。
string t, v;
cin >> t >> v;
if (foffset.empty()) foffset.push_back(0);
else foffset.push_back(calcoff(foffset.back() + mp[fvars.back().first].Size, mp[t].Align));
fvars.emplace_back(t, v);
cout << foffset.back() << "\n";
操作 3
访问就直接访问就是了啊，暴力啊。记录当前访问到的类型，然后去找变量。
string name;
cin >> name;
vector<string> vec = split(name, '.');
LL off = 0;
string nowt;
for (size_t i = 0; i < fvars.size(); i++) {
if (fvars[i].second == vec[0]) {
off = foffset[i];
nowt = fvars[i].first;
break;
}
}
for (size_t d = 1; d < vec.size(); d++) {
auto &&mpt = mp[nowt];
for (int i = 0; i < mpt.vars.size(); i++) {
if (mpt.vars[i].second == vec[d]) {
off += mpt.offset[i];
nowt = mpt.vars[i].first;
break;
}
}
}
cout << off << "\n";
操作 4
主要是特判边界和溢出的情况。
LL off;
cin >> off;
if (fvars.empty() || off > foffset.back() + mp[fvars.back().first].Size) {
cout << "ERR" << endl;
continue;
}
vector<string> ret = {};
string nowt;
bool flag = 1;
for (size_t i = int(fvars.size()) - 1; i >= 0; i--) {
if (off >= foffset[i]) {
off -= foffset[i];
nowt = fvars[i].first;
ret.push_back(fvars[i].second);
break;
}
}
while (true) {
auto &&mpt = mp[nowt];
if (off >= mpt.Size) {
//overflowed
flag = 0;
break;
}
if (nowt == "byte" || nowt == "short" || nowt == "int" || nowt == "long")
break;
for (size_t i = int(mpt.vars.size()) - 1; i >= 0; i--) {
if (off >= mpt.offset[i]) {
off -= mpt.offset[i];
nowt = mpt.vars[i].first;
ret.push_back(mpt.vars[i].second);
break;
}
}
}
if (!flag) {
cout << "ERR" << "\n";
continue;
}
for (size_t i = 0; i < ret.size(); i++) {
cout << ret[i] << ".\n"[i + 1 == ret.size()];
}
感觉挺自然的，其中有几次段错误和除以零，随便调一下就出来了，原因是内层的循环没加 break 和其它一些全局内部不分的。属于是 gdb 一跑就能指出来。
过大样例
测样例二发现怎么第二个变量的 offset 错了，才看到原来全局变量也要对齐的？还以为不用。其实这个全局感觉有点麻烦了，我也不想重新写，就这样吧，后面样例都过了。
17:15
平常时间 10:45 什么幻想时间？
然后想象 T4。
首先菊花会不会？我们可以二分答案 \(lim\)，然后处理一个 \(t_i\) 表示这棵树必须要在 \(t_i\) 时刻前（包括 \(t_i\)）种掉，可以再写一个二分来点分段一次函数（\(\max(b_i+c_ix,1)\) 可以先求出相交点，然后分讨）。然后关于贪心的部分，有一个想法就是用一个优先队列存下当前可以种的树，然后选出 \(t_i\) 最小的那个种掉。例如第 \(i\) 天的决策是 \(u\)，如果 \(t_u<i\) 就寄了，\(t_u=i\) 就一定是你了，但是 \(t_u>i\) 怎么说？相同的怎么说？
因为种了以后要将自己的儿子加进去，自己的儿子的 \(t\) 比自己小是确实的，我们不仅关心自己还关心儿子。不妨使得 \(g_i=\min_{v\in subtree(i)}t_i\)，就是自己子树内的最小值，用这个作为比较关键字。然后就行了，\(O(n\log^2n)\)。
然后开始写，主要是 \(t_i\) 很难求，一直写错，拿暴力换掉二分就是对的，所以一定是我错了。发现有个乘法溢出问题，因为 \(b\leq 10^{18},|c|\leq 10^9\)，然后保证 \(10^9\) 内有解，真的抽象，算的时候要对 1e18 取 min，然后别前缀相减啊。
18:00
终于写对了。过了四题大样例了。胜利宣言：
//I'm in vim of the ternimal of noi linux. I cannot type Chinese charaters.
//The time is 2023/10/21 18:02,
//and I have passed all the samples.
// --caijianhong, GD-S01538, in Foshan Shimen School
但是 T4 大样例要跑 1.2s，一看时限怎么只有 1s，我复杂度假的？确实看上去是个 1log 题，但是我不是很会怎么 \(O(1)\) 求 \(t_i\)。考虑两个方向：
- 把优先队列换掉，换成一个指针就行。但是有清空问题，我没调出来，最后回档了。
- 把 \(g_i\) 从 dfs 换成 dfn 序倒推，要跑 0.8s，应该是过了。
18:13
由此我过了四题大样例，最后交到 windows 打包再测一次，写了一个脚本 test.sh 全部批量测大样例，但是发现不会用，./test.sh 没有权限，是说没有 sudo？sudo 也不行。不会了啊。于是只能复制出来测。
然后四个题的大样例都过得很顺利，user time 都在时限内。
监考真的我哭死，竟然问我有没有把文件放到 windows，他真的我哭死。
18:30
考完啦，估分直接 400 好吗？
18:45
好久不见彭老师了，我说我过了四题大样例。然后其他人好像都挺爆炸的，疯狂问做法。
天黑了，没有拍照。
黄队过了四题大样例，Mobius_127（我找不到一个合适的称呼。。。）过了四题大样例。
晚上
吃饭以后就在讨论自己怎么挂，云斗很快就有数据了，测出来 \(100+100+100+95\)？
然后黄队也挂 T4 了，\(t_i\) 求错，突然意识到 一次函数前缀和 的另一个说法是 不定积分，怎么想不到的，数学水平有点离谱。
然后发现 T4 的一次函数与 \(y=1\) 相交的点，写成了与 \(y=0\) 相交的点。草。
- LL pos = c[i] ? max(-b[i] / c[i], 1ll) : 1ll;
+ LL pos = c[i] ? max((1 - b[i]) / c[i], 1ll) : 1ll;
痛失 AK。然后其他人也很惨，运行时错误的好多，Mobius_127 挂没了？
Sunny郭 挂没了，怎么会是呢？
allenchoi 挂没了，怎么会是呢？
Lucky_Luo 怎么要起飞了，要提高一等了，膜拜。
10.22
洛谷 \(400\)
小图灵 \(400\)
云斗 \(395\)
计蒜客已经造了前三题，都过了。
就等吧，等就是了。
打的很开心，同时意味着下周不用回 HY 学校了。我到底是想去 HY 还是不想去 HY，我自己都说不好。上一句话到底应该是“去” go 还是”回“ return 我也不清楚。