zhangxixi的博客

用欧拉路径判断图同构推出reverse合法性：1116T4 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/134444131 http://cplusoj.com/d/senior/p/SS231116D 假设我们要把 aaa 变成 bbb ，我们在 aia_iai​ 和 ai+1a_{i+1}ai+1​ 之间连边， bbb 同理，则 aaa 能变成 bbb 的充要条件是两图 A,BA,BA,B 同构。 必要性显然，因为无论如何reverse都不会改变图的形...

枚举连通块拆贡献+容斥：ABC321G 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133266690 https://atcoder.jp/contests/abc321/tasks/abc321_g 这种题都没看出来我要去退役了 看完题目，可以获得： 期望、连通块：显然拆贡献啊！ n≤17n\le 17n≤17 ：这不明显状压？结合前面连通块，就是枚举连通块啊！ 继续分析第2点，17这么小，显然枚举子集。为啥枚举？计数题只有容斥这个套路啊！...

缩点+图论路径网络流：1114T4 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/134407471 http://cplusoj.com/d/senior/p/SS231114D 重新梳理一下题目 我们先建图 x→yx\to yx→y ，然后对点分类：原串出现点，原串未出现点。 假如我们对一个原串出现点进行了操作，那么它剩余所有出边我们立刻去操作必然没有影响。所以我们只要所有原串出现点都操作一遍即可（如果有出边），那么我们就把边问题变成了点问题。 考虑一次...

曼哈顿距离与切比雪夫距离的相互转化 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133133274 假设已知原坐标中两点为 (x1,y1),(x2,y2)(x_1, y_1),(x_2,y_2)(x1​,y1​),(x2​,y2​) 求曼哈顿距离 →\to→ 转化为切比雪夫距离 令 (x,y)=(x+y,x−y)(x,y)=(x+y,x-y)(x,y)=(x+y,x−y) 求切比雪夫距离 →\to→ 转化为曼哈顿距离 令 (x,y)=(x+y2,x−y2)...

兔队线段树维护后缀非严格递增子序列的哈希值：CCPC2023深圳K 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/134372798 https://vjudge.net/contest/594134#problem/K 场上想到如果两个序列的后缀非严格递增子序列相同则平局，但不知道怎么维护 发现不用输出谁赢，只用判断是否平局，所以肯定是判断两个东西是否相等 然后如果单纯维护后缀非严格递增子序列，可以直接兔队线段树 O(nlog⁡2n)O(n\log^2n...

高精度预取模+哈希：CCPC2023深圳M 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/134371578 https://vjudge.net/problem/CSG-1249 对于取模操作，我们可以预处理，则三数之和只能是 0,M,2M0,M,2M0,M,2M 然后哈希一下即可 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484...

不可做题考虑最值来猜结论：CCPC2023深圳E 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/134369807 https://vjudge.net/contest/594105#problem/D 场上三个人死磕1.5个小时没磕出来，可以退役了 正常情况下区间或的max不可做，所以这题肯定是有什么特殊性质 根据对面队伍交流可得 ，此题为结论题。 我们考虑出现次数最多的次数分别是 mx1,mx2mx1,mx2mx1,mx2 ，则 mx1∣mx2mx1|...

全局操作区间查询——转前缀和+主席树维护 本文搬运自本人高中时期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 级复杂度的做...