青岛商网站建设,杭州建设网 执法人员名单,对网站的赏析,南宁seo排名收费时间安排
7:30–7:50 看题,T1可能是个数据结构之类的东西#xff0c;T2是 dp #xff0c;T3 构造。 7:50–8:20 T3,仿照样例的构造#xff0c;可以通过一部分测试点。 8:20–9:20 T1,发现题目实际上要求子树内各儿子的深度信息#xff0c;可以 dsu #xff0c;对于不能暴…时间安排
7:30–7:50 看题,T1可能是个数据结构之类的东西T2是 dp T3 构造。 7:50–8:20 T3,仿照样例的构造可以通过一部分测试点。 8:20–9:20 T1,发现题目实际上要求子树内各儿子的深度信息可以 dsu 对于不能暴力统计的部分可以打个懒标记维护。然后对拍。虽然带个 log 但是能过。 9:20–11:00 T2,发现必胜条件为存在某一长度大于一个下界的同一颜色的段于是可以对段做 dp 。对于 k50 的部分可以矩阵快速幂优化。思考 k^2n 的部分分发现可以容斥尝试去写发现答案不太对。 11:00–12:00 T3,尝试另一种构造在纸上乱试然后试出来一个貌似很对的测试点貌似都能通过。
回顾反思
10040100 T1 一部分时间花在了对拍上调整参数加强数据强度。 调试时遇到的一个问题是在划分轻重儿子的时候忘记把儿子的sz加到部分上来更新 sz ,导致所有点 sz 都是 1 这种错误决不能再犯。 考场上写的是 dsu 的做法考虑对重儿子最大深度与轻儿子最大深度之间差的部分打标记长剖的做法思想类似可以对 fi,j 记录其最后一次更新的结点离该链叶子的距离 len ,那么在根 x 时需要更新的便是 lenx-len 的这一段。
T2: 考试的时候准备冲 70 来着,然后容斥的档没冲出来拿了 40 。 想到了其中不需要多项式的容斥的部分分但是一直调不出来赛后发现是自己容斥的时候忘记乘上 (-1) 的系数。 需要注意的点是要仔细阅读数据范围该题中模数最大只有 1e7 级别于是能够暴力处理1e7 以内的阶乘和其逆元然后用lucas 快速计算极大数的组合数如果没有注意到这一点对极大数计算组合数就只能相对暴力求了复杂度会很高。 该题实际上是要求将 n 划分为若干长度不小于某个限制的方案数且划分有固定的权值求权值积。 对于限制 lim 对其数据范围分治若 lim 较大那么可以容斥钦定大于 lim 的段复杂度是 nlim\frac{n}{lim}limn 如果 lim 较小则可以用特征多项式快速幂求解暴力卷积是 lim2lognlim^2\log nlim2logn 的。 一个之前不太会的知识点是利用特征多项式求常系数线形齐次递推某一项的答案 例如有 fkfk−1fk−2...f0f_kf_{k-1}f_{k-2}...f_0fkfk−1fk−2...f0 那么有特征多项式 xk−xk−1−xk−2−...−1x^k-x^{k-1}-x^{k-2}-...-1xk−xk−1−xk−2−...−1 计算出头 k 项的值求解 xnmodxk−xk−1−xk−2−...−1x^n \mod {x^k-x^{k-1}-x^{k-2}-...-1}xnmodxk−xk−1−xk−2−...−1 即可得到第 n 项的解。 具体可参考博客
T3: 正解没有给出构造给了个随机调整法。 能放就随机放皇后不能放随机一个限制小的位置将控制它的皇后放到该位置。 然后随机跑上个 100 s能过 n5000 。
T2 的容斥是比较经典的。起码应该可以拿到 10070100270 分左右
