zhangxixi的博客

全局操作区间查询——转前缀和+主席树维护 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/134369593 https://www.luogu.com.cn/problem/P9388 场上疯狂想分块，降智了 发现全局修改，区间查询，可以考虑前缀和 现在考虑维护某个时间戳的前缀。 我们现在有初始前缀所有数和前 qqq 次操作的所有数，我们要删掉前 qqq 大的数。 发现有值域和操作顺序 / 位置两个限制，考虑可持久化 发现维护三个很难，我们就拆成两棵线段树...

需要思考才能转化缩点问题（用猜的结论验证结论）：Gym - 103427H 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/134366564 https://vjudge.net/contest/593228#problem/E 首先大胆猜结论，偶数条边全选，奇数条边有一条不选，那哪条呢？ 考虑找桥。如果一条边不是桥，那么删掉后恰好偶数条边，符合我们猜的结论。 如果是桥，那么必须满足分成的两个连通块的边数都是偶数，这样才能满足我们猜的第一个结论。 然后缩点后...

分治构造：P9384 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/134366235 https://www.luogu.com.cn/problem/P9384 分治构造是很常见的一种构造 不能有三元环和五元环，考虑推广出去，也就是不能有奇环 那如果我们让每种颜色都为二分图，那么必然满足 考虑 0-9 总共10个数字，数据范围1000，考虑 210>10002^{10}>1000210>1000 ，考虑 logloglog 级复杂度的做...

__builtin_clzll()：返回前导0个数 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132628959 常用于查找二进制最高位 用法： __builtin_clzll(x) 查找最高位： 63-__builtin_clzll(x) ，例如3（10）会返回1 最低位为 __builtin_ffs(x)

关于 括号序列与问号 问题的一类处理方法 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132548658 启发题： https://codeforces.com/gym/104531/problem/I 判断 str[l:r]str[l:r]str[l:r] 是否合法： 把所有 ? 替换成 ‘(’，然后前缀和记为 sss ，满足任意时刻 si≥sl−1s_i\ge s_{l-1}si​≥sl−1​ 把所有 ? 替换成 ‘)’，然后后缀和记为 ttt...

类直径树上贪心 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/134317828 http://cplusoj.com/d/senior/p/SS231109C 场上想到枚举点，然后最大值为高，然后可以求最大值。但是感觉计数会重 计数其实不会重，如图中，红色线段显然比蓝色线段优 所以我们枚举3叉点时没错的 123456789101112131415161718192021222324252627282930313233343536373839404142...

删边加边建虚点（图转树）+分类讨论贡献动态维护树：P9194 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/134312476 https://www.luogu.com.cn/problem/P9194 考虑边的数量很多，而且图很难维护，我们考虑边变成点，把图变成树（类似圆方树） 我们对每条边建虚点，那样我们就分成了黑白两种点。如果一堆黑点连向白点，说明他们之间有边直接相连。 我们发现这样子删点非常容易维护（拿个并查集把白点并起来即可） 然后分类讨论一下贡...

树上移动类贪心：1108T4 / CF1381D 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/134297045 http://47.92.197.167:5283/contest/428/problem/4 我们定义关键点为有3条路径大于 ≥L\ge L≥L 的点。 如果其中一个点可以到达关键点，那么就可行。这是一个充要条件。 我们以关键点为根，如果某个时刻两个点一个是另一个是父亲，那么一定可以开到关键点那里。 我们只需要两个端点轮流往他们子树最深处的地...

字符串数数——考虑循环节：1108T3 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/134295576 http://47.92.197.167:5283/contest/428/problem/3 一个字符串的最小表示法每个位置的概率只和其 最短 循环节有关。 假设循环节长为 ddd ，则前面每个位置是开头的概率为 1d\dfrac 1 d d1​ 我们可以先预处理一个 gig_igi​ ，表示长为 iii 的字符串没有循环节的方案数。 然后对于每个串，...

贪心转DP：AGC022E 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132152603 upd on 11.7 : 1的个数维护2个即可 https://www.luogu.com.cn/problem/AT_agc022_e 考虑如何选取是最优的，显然是000变0，110和010都是同时消掉01 观察此性质，可以发现0最多不会同时出现3个。对于第2种方法，在入0的时候我们不能确定是否还有连续0，但入1的时候可以确定前面没有连续0，所以在1的时候来维...