Link-Cut-Trees

摘要： 首先二分，问题转换成每个被选中点可以标记距离祂 \(mid\) 以内的点，求最少需要选几个点。 考虑从深到浅贪心，对于每一个关键点，如果祂现在没被标记，最优的方案为选祂的 \(mid\) 级祖先，然后标记祂的 \(mid\) 级祖先的 \(mid\) 级邻域。标记直接暴力跑，记录一下每个点被标记时最 阅读全文

摘要： \(A,B,C,D\) 是简单题 \(E,F\) 都没场切，E题解，F题解 总结 对性质观察的不够透彻，博弈论掌握的不熟练。 阅读全文

摘要： 首先给个结论：反 nim 游戏（谁取到最后一个谁输）的游戏先手的必胜条件： 当所有数都是 \(1\) 时，数的个数为奇先手必败，否则必胜。 其他情况，所有数异或和为 \(0\) 先手必败，否则必胜。 设 \(f_{i,0/1}\) 表示前 \(i\) 个，先手取到 / 没取到最后一个的方案数。 考虑 阅读全文

摘要： 设对 \(i\)的操作次数为 \(v_i\) 则有 \(a_i+v_{i-1}+2\times v_i+v_{i+1}=a_{i+1}+v_i+2\times v_{i+1}+v_{i+2}\) 移项得 \((v_{i-1}+v_i)-(v_{i+1}+v_{i+2})=a_{i+1}+a_i\) 阅读全文

摘要： 设 \(u\) 子树内的权值和为 \(sum_u\)。 考虑枚举分成 \(x\) 几个联通块，每个联通块的权值和为 \(sum_1/x\)。 如果这个方案合法，那么满足 \(sum_u\) 是 \(sum_1/x\) 的 \(u\) 的个数应恰好为 \(x\)。（把满足条件的点和祂的父亲断开。） 那 阅读全文

摘要： \(A,B\) 是简单题。 \(C\) 枚举一下最后的 \(\gcd\)，然后调和级数复杂度算贡献。 \(D\) 在 \(n,m\) 较小的时候暴力跑网络流，否则输出 \(n\times m-(n\times m\&1)\)。 \(E\) 是黑题，场切不了一点。题解 阅读全文

摘要： \(A\) 是比较版的二维数点，由于时间不太够，没切出来，赛后还调了很久（被卡空间了）(╬￣皿￣)。 \(B\) 一眼圆方树，不会，就现场学了一下，题解。 \(D\) 有性质，森林的联通块数量=点数-边数，然后就很好做了。 \(C,F,H\) 是简单题。 剩下几道题没做。 总结 做题，调题能力要提升 阅读全文

摘要： 发现每个点双内两个点的距离为 \(1\)，考虑使用圆方树。 建出圆方树后，方点点权为 \(1\),圆点点权为 \(0\)，每次询问求路径上的点权和即可。 代码 #include<bits/stdc++.h> using namespace std; namespace IO{ template<ty 阅读全文

摘要： 将 \(1\) 的权值设为 \(1\),\(0\)的权值设为 \(-1\)。则一个子序列的分数为祂里面所有数的权值和除以 \(4\) 下取整。 把下取整去掉，变成 \(\frac{S_T^2-S_T\mod2}{4}\) 即 \(\frac{S_T^2-\lvert T\rvert\mod2}{4} 阅读全文

摘要： \(A,B,C\) 是简单题。 \(D\) 是简单贪心。 \(E\) 是神秘题目，询问的两个数的二进制分别为 \(10101010...\) 和 \(01010101...\) 即可。 \(F\) 是组合数学，没有切掉,题解 总结 做题速度要加快，\(F\) 题没时间想(想了也做不出来)。 阅读全文