zhangxixi的博客

博弈论：gym104065j 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133840922 https://vjudge.net/contest/587311#problem/J 我也不知道我在此题中学到了什么套路 结论：你选的数必须尽量接近 sum3\frac {sum} 3 3sum​ ，然后这个就是解 因为另外两人选的是和你的数相比不可能更接近，所以必然一个大一个小 唯一的套路只能必有解博弈/构造和假设法？（3个人，从三进制角度盲猜一波，然后发现完...

奇偶博弈 + 二分图博弈：Gym 102832H 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133840132 https://vjudge.net/contest/587311#problem/I 赛时想了好久，啥都没想到 博弈，在你啥都想不到时，就硬上套路。赛时想了好久假设法，但就是发了奇偶博弈。 从奇偶角度考虑。每转一位会使这一位的奇偶性改变，也会使和的奇偶性改变。 然后关键地方到了，发现Alice和Bob操作的奇偶性永远不变，也就是形成了一个 ...

二分图博弈 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133840227 一张二分图，Alice和Bob每人走一步，不能重复走，谁不能走谁输 结论：若存在最大匹配不包含初始点，则Bob赢，否则Alice赢 以上图为例，红色为最大匹配。 首先对于Alice第一步只能走黑边。而Alice无论走到哪个点，都有一条红边。（不然就不是最大匹配了 ） 那么Bob就走红边，此时回到左边，Alice就只能走黑边了。 实现上，我们先把初始点去掉跑一遍流，加上后在残...

序列中排列存在类dp问题+结合组合数学和拆贡献：1014T4 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133833513 http://47.92.197.167:5283/contest/412/problem/4 赛时就想到枚举开头来拆贡献。 先说一下，对于A我们不关心具体的值，我们只关心哪些位置相等，哪些位置不等，最后乘上一个系数就行 然后对于序列是否存在排列类问题有个常见的dp套路，而且我们可以观察特殊性质 dpi,jdp_{i,j}dpi...

奇偶+逆序对构造法：arc102d 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133825414 <https://atcoder.jp/contests/arc102/tasks/arc102_d<> 类似构造题，但不完全是，先从交换类构造题几个常见方面考虑一下： 差分：没关系 奇偶：发现奇数位一直在奇数位，偶数同理（我们得到判定1了） 逆序对 交换会使逆序对个数-3，所以总逆序对个数必然是3的倍数（判定2） ...

【1014T2】半假结论通过打表验证 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133824842 http://47.92.197.167:5283/contest/412/problem/3 场上猜结论，把上下界处理出来后，判断是否在范围内。 然后被样例hack掉了。 然后我就只能打暴力。 但打完暴力就不能顺手把表输出吗？ 发现 AAAAAA ， BBBBBB 的情况， L+1L+1L+1 取不到 ABABABAB 的情况 R−1R-1R−1 取不...

树上启发式合并：GYM102832F 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133802611 https://vjudge.net/contest/587311#problem/C 最近没打这个套路，场上忘了 发现和一堆lca什么的有关，然后又是lca下不同的儿子，考虑树上启发式合并。 对于 i⊕ji\oplus ji⊕j ，我们可以拆位枚举 然后常数大会被卡常。但树上启发式合并很多的dfs可以优化成遍历dfs序上一段连续的区间。 123456...

枚举gcd+启发式合并：GYM102832K 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133807724 https://codeforces.com/gym/102832/problem/K 首先从值域上预处理，对数不会很多。 场上想的是建树然后启发式合并。 但发现合并这个过程直接用类似并查集的启发式合并即可 预处理方面先枚举gcd， 再枚举x可以做到两个log

局限性贪心考虑分析贪心状态数：1012T2 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133793526 http://47.92.197.167:5283/contest/411/problem/3 场上当时认为是找出全局最大，全局最小，然后划分成不同类型的区间递归下去。 往前连肯定是尽量大的，往后连肯定是尽量小的 但发现这个过程会形成依赖。每个点不只连一条边，有些点不只连一次。但假如在每一次中，第一次选的必然是最优的。（和我当时的递归思路很像，区间...

巧妙设计状态+不断对拍寻找合适贪心策略：P8341 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133780272 https://www.luogu.com.cn/problem/P8341 场上看错题了… 考虑维护几个东西： a[x],b[x]a[x],b[x]a[x],b[x] 表示完整匹配，半完整匹配的数量。 p[x]p[x]p[x] 表示某条向上路径在 xxx 完成任务，可以变成 bbb 。 然后如果 xxx 位置有向上的话，我们贪心希望它和 ...