zhangxixi的博客

奇偶+逆序对构造法：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 位置有向上的话，我们贪心希望它和 ...

贪心+分类讨论完整性：ARC123C 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133772012 https://www.luogu.com.cn/problem/AT_arc123_c 场上就简单猜了个结论，[1,3]=>1, [4,6]=>2, [7,9]=>3，0=>4，若存在1则此时必须为1个数，否则为4。存在2则必须<=2，否则为4. 但我没对4进行完整讨论。如果4个数则不能凑3（此时可以判断是否进位，只有下一...

点向行列连边的网络流图优化成行列连边的二分图：CF1592F2 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133764633 https://www.luogu.com.cn/problem/CF1592F2 做完F1，然后用1的结论来思考。 场上推了几个性质。首先op4的操作行列必然两两不同，所以op4最多 max⁡(n,m)\max(n,m)max(n,m) 次。然后手玩发现只有除 (n,m)(n,m)(n,m) 的三个格子都为1，op4才有意义。 ...

区间dp之类似树形结构增加限制合并枚举状态：CF1107E 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133759674 https://www.luogu.com.cn/problem/CF1107E 场上想的思路是朴素 O(n5)O(n^5)O(n5) ，枚举区间和多少个0/1，转移则是枚举分界点和左边0/1数量 然后可以发现转移的 O(n2)O(n^2)O(n2) 似乎不那么必要（就是感觉上可以优化，但不知道怎么优化） 首先发现最后合并在一起的东...

归纳所猜半结论推出完整结论：CF1592F1 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133757947 https://www.luogu.com.cn/problem/CF1592F1 场上猜了个结论，感觉只会操作1。然后被样例1hack了。然后就猜如果 (n,m)(n,m)(n,m) 为1则翻转4操作，被#14hack了。然后就猜4操作只会进行一次，然后就不知道怎么做下去了。 上面猜的结论都正确，但是既然猜结论了，为什么不考虑先证明一波？ 考虑...