无所谓失败可言,等待你是明天。
Day 2022.11.27
Day 2022.11.25
写过一篇总结应该算是,没来得及发出,Site is here。
Day 2022.11.26
NOIP2022 如约而至
8:30
开考,T1 plant 30min切掉,心情不错,出去上完WC回来9:17,
T2 模拟游戏 喵了个喵 很抽象,觉得有点不可做,貌似只会无脑贪心胡乱操作
于是开T3,发现又是一道图论(CSPS2022不够哈),判断是无向图边双缩点为树 后 跑树形DP,因为边双内怎么断路都没用Obviously
缩点直接 \(Tarjan\) 判桥再合并,这段 \(Tarjan\) 缩点最开始写得很抽象:直接把有向图缩点的套路搬过来,拿一个stack
打包,甚至标了scc
。。。
至于DP,一开始想得复杂,诸如 \(u\) 子树内 \(u\) 本身选不选之类;
大概剩2h40min的时候干脆f[u][0/1]
表示子树内(包括根)选或者不选,\(kgkb\) 表示所有子节点可选可不选方案数,\(bg\) 表示所有子节点不选方案数;
f[u][0]
容易由bg
得到。对于f[u][1]
,根节点 \(u\) 内必选容易处理,结合一下 \(kgkb\) 即可;但根节点 \(u\) 不选有些麻烦:笔者最初准备枚举强制某个子树 \(v\) 必选统计方案数,发现需要容斥。于是精确地,对于 \(u\) 的第 \(i\) 个子节点 \(v_i\) ,钦定前 \(i-1\) 个不选, \(v_{i+1}\sim v_{cntson_u}\) 可选可不选,以此分类累加得到f[u][1]
;具体实现后x子节点可选可不选笔者是采取 \(kgkb\) +逆元得到 \(kgkb_{i\sim v_{cntson_u}}\)。
调完细节约11:15,过了前两个小样例,第三个WA,第四个RE。死活不理解RE,发现是Tarjan()后尝试输出RE前访问节点编号,每次都不一样。
然后Tarjan改成求完桥以后再缩点,barrack3.out同样WA,barrack4照旧RE
就是调,T4搁,T2搁,T3写了个check改成有向图Tarjan也RE,有点怀疑人生???
12:00
暂时放弃,写一波T2无脑乱搞不知道叫啥了。
有牌就配,有空就塞,没空塞最矮。12:25搞完,第一个样例一过就弃。
然后又在无脑check有向图,试图搞清楚为什么RE,甚至怀疑样例锅。12:50无功而返。
然后就检查文件输入输出了,T4完全弃,旁边热心监考提醒我要建4个文件夹我寻思文件都没写建什么Directory,建个Empty
13:00
门的出
起身听到“今年T2不可做” 还好不是CSPS2022“今年一等不得300分”
出门碰头,简短交流
Pi--ow切了T3,f-rT3过了也前两个样例(但据说只要2个桥就WA),何神好像T2 AC,rn----j挺沉闷的,后来说冲了个T4暴力
Pi--ow说T3 barrack4.in 不开无限栈会爆,所以半个虚空调错?———不过barrack3.in还是一样炸
还是笔者比较悬,人均T1+T3Unknown+乱搞T2
Night
出门进行一个酸的核,买了张FWC彩票
Luogu 100+0+15/ Infoj 100+0+20
T2 挂RE,T3靠上帝
Afterthought Day 2022.11.27
考完心理状态波动不大,比较正常。接下来需要面对文化课,以及对OI/ICPC的规划(近期/远期)。
To Myself: 无所谓失败可言,等待你是明天。
待补。
关于 FWC
POL vs KSA 2:0 1:1票木有了~~~
Argentina 2:0 Mexico Delighted? !