zhangxixi的博客

对于复杂二进制数位dp问题考虑朴素思想：agc015d 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133643686 https://atcoder.jp/contests/agc015/tasks/agc015_d 我一开始考虑的是直接上二进制数位dp，但发现这很难做 然后其实可以从最朴素的二进制+分类讨论角度考虑 同样是那么几个套路，考虑最高位

充分理清限制与条件+构造二分图+最小割：ARC142E 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133623334 https://www.luogu.com.cn/problem/AT_arc142_e 他的充要条件是是什么： ai,aj≥min(bi,bj)a_i,a_j\ge min(b_i,b_j)ai​,aj​≥min(bi​,bj​) 存在 ai≥max(bi,bj)a_i\ge max(b_i,b_j)ai​≥max(bi​,b...

树上游走最优策略问题：Cf1725J 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133622359 https://codeforces.com/contest/1725/problem/J 首先要转化题目 发现题目本质是什么 不用回去 = 少走一条路径 传送 = 少走另一条路径 一开始猜的结论是这样 但这并不完整 传送本质是让我们把某些路径少走一遍 考虑这种情况，交于1点 12345678910111213141516171819202122232...

次方计数的拆贡献法（考虑组合意义）+限定类问题善用值域与位置进行ds：1006T3 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133621275 对于多次方的计数问题可以考虑拆贡献。 题目问 ∣S∣3|S|^3∣S∣3 ， ∣S∣|S|∣S∣ 表示选的点数。相当于在 ∣S∣|S|∣S∣ 中选了3次，也就是选了3个可相同的点。 先考虑3个不相同点的贡献，对应任意3个点，必然会对所有包含其矩形产生贡献。所以只需要统计对应的矩形数目。但是必须乘上全排列6，因为...

排列 -＞ 位置与值域相对应：1006T2 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133611553 http://47.92.197.167:5283/problem/5513 考场上转化后的是max（每个数的位置 - 其应该的位置） 但对于排列问题，此题可以直接转化为每个数之前有多少个数比他大

珂朵莉树维护并查集：CF1725K 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133607729 https://codeforces.com/problemset/problem/1725/K 发现题目涉及值域的区间覆盖，可以考虑对值域维护珂朵莉树（应该是类似珂朵莉树思想的东西）。 但要把值域对应回原位置，我们可以拿并查集维护。 12345678910111213141516171819202122232425262728293031323334353...

折半+dp之限制转状态+状压：CF1767E 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133607589 https://vjudge.net/problem/CodeForces-1767E/origin 首先40，必然折半。然后怎么做？ 分析性质。每次可以走1步or2步，等价什么？等价任意相邻2个必选一个！然后就可以建图 这个图是个限制图，我们折半后可以进行状压。dp的过程是限制转状态。 首先分别的，前后内部都必须满足。然后对于交织在两部分的限制，...

打表找规律与分析判断：ARC144C 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133607035 https://atcoder.jp/contests/arc144/tasks/arc144_c?lang=en 一开始我猜的结论是前后 kkk 个预处理，中间贪心。 通过打表： 可以发现是前面 2k2k2k 连续块直接暴配，最后一段再用我想的贪心。 究其原因，其实是我们本质上代表着只要大于 2k+12k+12k+1 就必然有解。所以这样构造必然是对的...

移动类匹配——固一枚一：ARC154C 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133606890 https://atcoder.jp/contests/arc154/tasks/arc154_c?lang=en 发现本质是两个环旋转的匹配。 题目支持 n2n^2n2 ，所以我们可以固定一个开头（B的），枚举A的开头再暴力匹配 此题中，能转的充要条件是由两个连续相同的。当发现这一点后，可以考虑特判，而不是归纳（理论上遇到应该先拓展，再看是归纳还是特判...

长剖与贪心+树上反悔贪心：1004T4 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133575747 长剖的本质是一种贪心。（启发式合并本质也是类似哈夫曼树的过程） 在此题中，首先肯定变直径，然后选端点为根。然后选叶子。而每个叶子为了不重复计算，可以只计算其长剖后所在链的贡献。（本题精髓，用长剖来贪心） 然后钦定某个点必选，就是一种反悔贪心。很显然的思路是删掉排名 2∗k−12*k-12∗k−1 的叶子，但考虑： 所以需要考虑离其最近被选的点 1234...