多校A层冲刺NOIP2024模拟赛16
T1 四舍五入
签到题
注意到一个数是否会入上去只和其剩余系有关，即满足 \(i\mod j<\frac{1}{2}j\)，会入上去，考虑枚举 j 的倍数，其贡献就成了一个区间，差分即可。
时间复杂度是调和级数的，为 \(O(n\ln n)\)。
T2 填算符
贪心，特殊性质
显然将所有 \(\&\) 放在最左端一定不劣（不管是考虑前多少），考虑在此基础上调整即可。
具体的可以贪心调整最右边一个，即将最右边的从最右端往左移，第一个合法的即使其所在位置，然后由于是 \(\&\) 操作，他的贡献会与前边的挂钩，找到它独一无二的贡献，作为下一个合法的判断即可。
时间复杂度为 \(O(n\log n)\)。
T3 道路修建
基环树，换根DP，树上问题，树链剖分，线段树，倍增
发现加边操作后的答案一定会包含原树的答案，而新加的答案为所有经过所加边的路径。
所以可以先 \(O(n)\) DP，算出原树的答案，然后考虑新增边的贡献。
考虑套路，计算路径长度的和转化为每一条边的贡献（经过的次数）。
由于是基环树，可以先考虑环上的边的贡献。
这一部分可以分为新加边和原树边。
-
新加边
显然经过其的次数为总路径的个数，考虑计算总路径的个数。路径只有两个端点，而现在又钦定了必须经过新加边，而且有路径点不交的限制，所以只要选出两个点则能对应唯一的路径。即就是 \(\binom{n}{2}\)，但此时算入了两个点都在同一个子树的贡献，减掉即可。
记为 \(tot=\binom{n}{2}-\sum_{v\in circle}\binom{siz_v}{2}\) -
原树边
显然能求出不经过的次数（相对于当前所加边而言），即边两边联通块的大小之积，记为 \(g_i\)，则经过的次数就为 \(tot-g_i\)
所以环上边的贡献为 \((dis_{u,v}+1)tot-\sum_{v\in circle}g_v\)
再考虑子树（环上的子树）的贡献
- 记 \(f_i=\sum_{v\in subtree_i}dis_{i,v}\)，则一个子树的贡献为 \(f_i(n-siz_i)\)
所以总贡献为 \((dis_{u,v}+1)tot-\sum_{v\in circle}g_v+\sum_{v\in circle}f_v(n-siz_v)\)
现在考虑怎么快速求出 \(\sum_{v\in circle}\binom{siz_v}{2},\sum_{v\in circle}g_v,\sum_{v\in circle}f_v(n-siz_v)\) 这三个部分，分别记为 \(res1,res2,res3\)。
-
\(res1\)
直接维护的难点在于 \(siz\) 在变（因为定义的是环上的子树），所以可以考虑树剖 \(siz\) 只维护所有的轻儿子的贡献，这样除了链底需要特殊处理，其他的能直接维护在线段树上。还需特殊处理 \(lca_{u,v}\)，记 \(tot_i=\sum_{j=1}^ndis_{i,j}\) （不同与前面的 \(tot\)），所以得换根 DP 求出 \(tot\) 数组。 -
\(res2\)
每个点套路维护其父向边的 \(g\) 数组，树剖即可。 -
\(res3\)
类似 \(res1\)
总时间复杂度为 \(O(n\log^2n)\)。
可以倍增，这样就能优化掉一支 \(\log\)
T4 逆序图
不会，但是可以讲讲结论
结论：逆序对的关联关系不会是嵌套状的，即关联关系会构成一段区间，并且这一段区间的值是连续的
证明考虑反证法，即尝试用 \(4\) 个值构造出一个嵌套状的关联关系，发现由于单调性显然是不行的。