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

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

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

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

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

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

CF459E-DP 核心代码15行 思路 观察数据范围，我们建m层分层图跑最短路想到DP。 DP最大的特点就是无后效性。那么我们这一题哪个条件无后效性呢？ 发现DP值一定从边权小于当前点的位置转移而来。 这不就无后效性了？我们按边权将所有边排序即可。 然后，枚举边，将DP值记录到点上，每次用起始点的dp值加1更新到达点的dp值。最后输出dp值最大的即可。 然后，您会发现第一个...

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\)...

CF833B-线段树优化DP 题意 将一个长为\(n\)的序列分成\(k\)段，每段贡献为其中不同数字的个数，求最大贡献和。\(n\leq 35000,k\leq 50\)。 思路 此处感谢@gxy001 聚铑的精彩讲解 先考虑暴力DP，可以想到一个时空复杂度\(O(n^2k)\)的方法，即记录前i个数字分成了j段。我们现在来思考几个问题来优化这个操作： 对于一个数字，它对那...