专栏文章

NOIP2024游记

ZZYLZPP
生活·游记参与者 11已保存评论 10

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
10 条
当前快照
1 份
快照标识符
@mhze5cz5
此快照首次捕获于
2025/11/15 05:49
4 个月前
此快照最后确认于
2025/12/04 12:09
3 个月前
查看原文

Day -1145141(是个质数)

CSP 的 T4 调了 2h2h 多没有调出来，交了没调完的直接爆炸。

Day -2

看着编号特大的准考证，脑补 AFO 时光。

Day 0

吸取了之前坐大巴车晕车的教训，自驾前往杭州。

Day 1

7:30 起床 + KFC 早餐

8:00 左右进考场

8:30 开考

先配 vimrc，打快读。

开 T1

盲猜贪心，花 10min10min 打了一下，过大样例，直接跑路。

开 T2

计数？T2 就考计数？今年这么恐怖的吗？
再模了一遍，发现直接递推。
好吧，是我多虑了。
码量可能比 T1 还少。

开 T3

此时差不多 45min45min。
看见树边的遍历，新定义，计数，和K有关的数据点。
一眼不可做，直接跳 qwqqwq。

开 T4

区间 LCA，转换成相邻两个的 LCA 和区间 min⁡\min。
log2log^2 显然可做。
注意到 5e55e5 以及我的常数，还得优化。
发现将相邻 LCA 按深度降序排序后依次插入，会将左右两个区间合并。
这样产生的区间不超过 nn 个。
答案即查询满足条件的区间中 depdep 最大的。
按区间与询问是否包含分两类处理：
  • 不包含：按长度降序插入数据结构，询问是区间查询最大值。
  • 包含：转变为二维数点类问题，也可 O(nlog⁡n)O(n \log{n}) 解决。
开了 44 个线段树，大样例跑了 1s1s 多，有点慌。
改成 44 个双向树状数组，卡到了 0.7s0.7s，过。

回到 T3

此时大约还有 2h2h，总不能干坐着吧？
仔细模了下 K=1K=1 的样例，很快发现 ans=∏(degi−1)!ans = \prod {(deg_i - 1)!} ，24pt24pt 到手。
然后抱着能拿一点是一点的心态打了特殊性质 A、B，40pt40pt 到手。
开始磕 K=2K=2：
逐渐走向容斥，考虑减掉同时可为根的数目。
注意到只有两条边的路径上的边会影响是否可同时为根。
同时为根时路径上的边全被限制，每个点的贡献变为 (degi−2)!(deg_i - 2)! ，搞了个 LCA 求 dis，然后暴力跳算贡献，56pt56pt 到手。
此时大概还有 40min40min。
看着 K=8K=8 有点蒙，这难道是枚举子集容斥？感觉不太有性价比。
发现如果一子集内边之间的路径形成三岔，则没有可同时为根的方案。
于是想到了以每条关键边为根 DP 带容斥系数的方案数。
于是开码这个 O(n2)O(n^2) 做法，结果打着打着，写下了一句：
CPP
if (imp[v]) add(x, -x);
what? 这不是变成 00 了吗？
仔细一想，发现只有当一对边路径上的边都不关键（即相邻）的时候才有贡献，否则中间的边取或不取方案数一样，但系数变负，没有贡献。
赶紧改，调过小样例后直接测样例12。
我这是要 AK 了？
怎么可能！
这算法还是 O(n2)O(n^2) 的，直接 T 飞 qwqqwq。
想着是可以优化的，但没有时间了。
抄完字节数，就坐等结束了……

估分

100(贪心不挂的话)+100+76+100(不被卡常的话)100(贪心不挂的话) + 100 + 76 + 100(不被卡常的话)。

后记

高二了，最后一次真正的 NOIP 了，挂了就 AFO 了。
upd：出分了 376376 没挂。

评论

共 10 条评论，欢迎与作者交流。

正在加载评论...