zhangxixi的博客

打表找规律与分析判断：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...

一道求导题：1004T3 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133560750 需要知识: (xn)′=nxn−1(x^n)'=nx^{n-1}(xn)′=nxn−1 (sinx)′=cosx(sinx)'=cosx(sinx)′=cosx [f(g(x))]′=f′(g(x))×g′(x)[f(g(x))]'=f'(g(x))\times g'(x)[f(g(x))]′=f′(g(...

与值域有关的问题（非权值线段树）——运用分块：1004T1 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133560662 区间小于等于某值 区间加 显然同时涉及区间和值域，不能用log级ds来做，常见套路就是上分块 这题是个复合题，后面就是个组合数 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535...

组合数与莫队——组合数前缀和 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133559588 用莫队求组合数是一种常见套路 莫队求 S(n,m)=∑i=0m(ni)S(n,m)=\sum_{i=0}^m\binom n iS(n,m)=∑i=0m​(in​) S(n,m+1)S(n,m+1)S(n,m+1) 直接做个差，然后就相当于加上 (ni+1)\binom n {i+1}(i+1n​) 求 S(n+1,m)S(n+1,m)S(n+1,m) 会麻烦点，...

抓住普通情况变量猜结论：ARC136C 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133525236 假如不是环，我们求的就是上升的量。那么我们可以先大胆猜一波，环形结果就是上升的量。 然而我们在非环的情况是在前面补了0的，我们这里不能补0，我们就只能对最大值取max 1234n=read(); for(i=0; i<n; ++i) a[i]=read(), m=max(m, a[i]); for(i=0; i<n; ++i) k+=max(...

善于拆约束条件+合并相关项+DS维护：0928T2 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133521713 http://cplusoj.com/d/senior/p/SS230928B 老套路了 考虑枚举0和2 m+j+min(fam−gaj,fbm−gbj)\large m+j+min(fa_m-ga_j,fb_m-gb_j) m+j+min(fam​−gaj​,fbm​−gbj​) 然后拆一下min，再分情况讨论一下，移项合并相同的 以其中一...

贪心找性质+dp表示+矩阵表示+线段树维护：CF573D 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133437456 比较套路的题目 首先肯定贪心一波，两个都排序后尽量相连。我一开始猜最多跨1，但其实最多跨2，考虑3个人的情况： 我们发现第3个人没了，所以可以出现跨2的情况 然后直接上dp，由 i−1,i−2,i−3i-1,i-2,i-3i−1,i−2,i−3 转移过来。 然后这显然可以拿矩阵表示。 然后显然可以拿线段树维护。 后面三部分都是比较套路...

图论+博弈论上dp：CF536D 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133364509 此题其实比较板，只是我没看出来 首先肯定要跑个最短路，然后发现可以离散化把值域缩小 然后 nnn 很小，直接暴力列个 n2n^2n2 dp。 转移要注意的是必须从大往小dp。从小到大会产生后效性。 然后拿个双指针优化下转移就行。 123456789101112131415161718192021222324252627282930313233343536373...