游记 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 我也不清楚。
标签:off,vars,S2,CSP2023,back,mpt,nowt,游记,typ From: https://www.cnblogs.com/caijianhong/p/travel-in-csp2023.html