AT2304 Cleaning 题意 一个树上每个节点有一些石子，每次只能选取两个叶子节点并将路径间的所有点上的石子数量减1，问是否能将所有石子取完。 思路 设 \(f_x\) 表示从 \(x\) 节点向上的路径条数，\(s_x\) 为子节点的 \(f\) 值的和，则有： \[ a_x=\frac{s_x-f_x}{2}+f_x\\ f_x=2a_x-s_x \] 我们只需要保...

AT2390 Games on DAG 题意 \(n\) 个点 \(m\) 条边的 DAG，每条边 \((u,v)\) 有 \(u<v\)。\(1,2\) 号点各一个石头，Alice 和 Bob 轮流每次沿边移动一个石头，不能动者输。求所有连边子集中先手胜的情况。两个石头可以重合。\(n\leq 15\)。 思路 发现对于两个石头的 SG 函数是独立的，输者两个石头 SG 函...

CF1032G Chattering 思路 对于每一个位置，它转移的范围是确定的。 对于一段可以走到的区间，我们可以求出区间中所有点再能走到区间范围。 于是这个就可以倍增进行转移。 如何快速求出一段区间能走到的区间范围？也就是分别求出一段区间向左跳的位置的最小值和向右跳位置的最大值，发现这其实就是一个RMQ问题。但是因为还有倍增的时间复杂度，而且是没有修改的，那么我们可以利用ST...

CF175E Power Defence 题意 一个塔防游戏：给定一个无限长的数轴，一个无限血的敌人要从正无穷走到负无穷。你的任务是放置三种塔，包含两种攻击塔和一种寒冰塔，使得敌人受到的伤害最大。 其中，每种塔的攻击半径可能不同，每种攻击塔的攻击力也可能不同。而寒冰塔没有攻击力，它的作用是使范围内敌人的速度减速，即一段区间若有\(k\)个寒冰塔覆盖，敌人速度变为\(\frac{1}{k...

CF404D-DP 正经的东西 题意 给定一个字符串，只包含'0','1','2','*','?'五种字符，其中'?'可被替换为其他任何一种，求使序列符合扫雷地图定义的方案数。 一个数字字符大小表示与之临近的位置总共有多少个雷。 思路 DP。 和其他题解不太相同，我们每个点只记录三种状态：0,1,2，分别表示若此点的下一位不为雷、为雷和此点位就是雷的此位及以前的方案数。 ...

CF1166E The LCMs Must be Large 思维好题，结论好题。 题意 一个长度为 \(n\) 的未知长度的序列，有 \(m\) 个限制，每个限制形如给定一个集合 \(S\) ，使集合内元素的 \(lcm\) 严格大于其补集元素的 \(lcm\) 。问是否存在这一序列。 思路 要注意我们是要尽可能使序列有解。 先给出结论：若所有集合两两间有交，则有解...

CF437D The Child and Zoo 题意 给定一个无向图，求所有点对间所有简单路径上最小点权的最大值的平均值。 思路 首先，我们可以将点权转移到边权上，边权为两端点点权的较小值。正确性显然。 然后，对于任意两个点之间的贡献，只有路径上含最大点权的简单路径有贡献，于是就可以把无向图转变为最大生成树。任意两个点间的贡献显然是在最大生成树上路径的最大边权。 考虑对于一...

CF487E Tourists 前排膜拜T神 上面的话和这道题一点关系都没有 题意 给一个点带权的无向图，每次询问查询两点间所有简单路径上最小值的最小值，单点修改。 思路 一眼圆方树。 ——@gxy001 这种题只有在树上做才比较好处理这么多次询问。考虑广义圆方树，缩完点双连通分量后建立的方点和圆点。 因为我们找的是最小值，所以必须将代表整个点双的方点的权值设为与其...

CF494D Birthday 题意 一个1为根的带边权有根树，每次询问给定两个点 \(u,v\) 求 \(\sum_{x\in S(v)} d(u,x)^2-\sum_{x\not\in S(v)}d(u,x)^2\) 其中 \(d(u,v)\) 表示 \(u,v\) 简单路径长度， \(S(u)\) 表示 \(u\) 的子树内点的集合。 思路 考虑 \(u\) 在 \(v\)...

CF710F String Set Queries 题意 动态支持加入删除字符串和字符串匹配 思路 动态 AC自动机 先不考虑动态情况。对于加入一个字符串，直接插入到自动机即可。 考虑删除。发现对于答案具有可减性，意思是对于同一个匹配串，答案可以表示为在自动机中匹配的答案减去删去的所有串匹配的答案。那我们考虑给所有删除的串也开一个 AC 自动机，每次询问在两个自动机中匹配将答案...