zhangxixi的博客

分析性质题（集合类）：CF566E 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133870468 https://www.luogu.com.cn/problem/CF566E 感觉浪费了一道好题，没有好好分析性质 若非叶子节点有连边，则存在两个集合的交集为 {x,y}\{x,y\}{x,y} 然后就可以区分叶子和非叶子节点 对于叶子节点，包含它大小最小的集合就是对应的集合。 对于非叶只计算<=1距离的点，设为 GGG 显然在非叶>=3时...

对于从三个方向转移的期望dp式子移项方法 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133753059 fi=afi−1+bfi+cfi+1+vif_i=af_{i-1}+bf_i+cf_{i+1}+v_ifi​=afi−1​+bfi​+cfi+1​+vi​ ，其中 a+b+c=1a+b+c=1a+b+c=1 ，求 fff 考虑差分， gi=fi−fi+1g_i=f_i-f_{i+1}gi​=fi​−fi+1​ fi=a(fi−1+gi−1)+bfi...

去掉限制+让赢家保持局面不变：P4101 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133711268 假如没有限制，就和 n−1n-1n−1 的奇偶有关。 博弈论的构造我们做的是什么？无论对手做什么，我都可以通过一些操作使得某种形式的局面不变。 考虑一开始会怎样。第一步只能合并两个1。变成 2 1 1 1 1 ... 考虑现在有个人操作，他就有两种选择。合并两个1，或者合并1和2。分别变成 3 1 1 1 1... 或 2 2 1 1 1 1... ...

用欧拉路径判断图同构推出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|...