zhangxixi的博客

二进制下传优化AND连边：UOJ176 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135106721 https://vj.imken.moe/contest/600665#problem/E 一个朴素思路是枚举 ppp ，然后再枚举 x&y=px\&y=px&y=p ，如果 x,yx,yx,y 不在一起，则连一条边。 考虑优化。如果 x,yx,yx,y 的交集更大，则不是 ppp 。所以一个思路是取出 ppp 所有0的位置，然后...

若竞赛图中有环，则一定构成三元环 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135099517 考虑一个 n(n≥4)n(n\ge 4)n(n≥4) 元环，肯定有弦。 我们就可以通过这个弦不断把环缩小即可。 同时竞赛图中不存在两个点的强连通分量。

竞赛图缩点后成链状（拓扑序唯一） 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132993089 一个常见结论 竞赛图缩点后必然成链状。 不是真正的链，只是类似链的偏序关系。

斐波那契的平方、立方问题——考虑几何立体意义（数形结合法）：P9510 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135094722 https://www.luogu.com.cn/problem/P9510 关于斐波那契和的平方，其实就是正方形的面积和： 也就是 f(i)∗f(i+1)f(i)*f(i+1)f(i)∗f(i+1) 我们现在要求立方，但我们可以可以发现红色部分的结果是一样的： 直接三条棱表示除了，就是 f(i)∗f(i−1)∗f(i...

势能相关难维护的用分块——分块过程维护跨块的：CF1491H / P7446 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135093792 https://www.luogu.com.cn/problem/P7446 https://www.luogu.com.cn/problem/CF1491H 看到题，发现只有减，就和势能有关。维护势能，像这种题，树形ds显然不好做，所以可以去考虑进行分块。 考虑分块。每个块记录一个 bib_ibi​ ， iii 的...

考虑全选然后删的代价转最小割+最小割同一类连inf的边：AT_arc107_f 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135093630 https://www.luogu.com.cn/problem/AT_arc107_f 理论上界为 ∑∣bi∣\sum |b_i|∑∣bi​∣ 。考虑现在减少会有什么情况： 不选。代价为 ai+∣bi∣a_i+|b_i|ai​+∣bi​∣ 原先为正，所在连通块取绝对值后变负。代价为 −2∣bi∣-2|b_...

数学方法转化限制条件（使大于小于等于号左右互为相反数，变成绝对值）+加减交错法构造博弈论下界推出最优解再用限制代入：AT_agc056_d 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135089890 https://vj.imken.moe/contest/600552#problem/G 考虑对题目进行转化 L≤Sa≤RL \le S_a \le RL≤Sa​≤R 2L≤2Sa≤2R2L\le 2S_a \le 2R2L≤2Sa​≤2R 2L+Sb≤...

阴阳反转——运用INF巧妙建网络流：P3980 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135080814 https://vj.imken.moe/contest/598718#problem/L 考虑一个奇妙的转化： 有很多 inf⁡\infinf 个人要走 nnn 扇门，第 iii 扇只能走 inf⁡a−i\inf_a-iinfa​−i 个人，有 mmm 个通道，可以把一个人从 sis_isi​ 运到 ti+1t_i+1ti​+1 ，但要给 c...

通过费用流中的贪心来保证计数正确性：P4249剪刀石头布 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135080431 https://vj.imken.moe/contest/598718#problem/K 三元环数量尽量多，也就是非三元环数量尽可能少。非三元环的充要条件是存在一个点度数为2，而每条边可以给一个点一个度数，然后就变成了经典网络流问题。 但是，对于一个点，我们还是无法求最少流。考虑转化为费用流。一个点向汇点连很多条边，分别代表着度数为1...

插入数计数类 / 转为换行类dp：AT_agc024_e 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135078944 https://www.luogu.com.cn/problem/AT_agc024_e 首先题目可以转化成每次插入一个数，满足字典序递增。 如果只考虑暴力dfs，先别上dp，想想怎么合法和不算重。 合法，也就是插入数有3种情况 插到末尾 插到比他小的前 插到和它相等的数，然后后面退了一位后刚好满足 前2种是好做的，但如...