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，分别表示若此点的下一位不为雷、为雷和此点位就是雷的此位及以前的方案数。 ...

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

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

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

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

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段。我们现在来思考几个问题来优化这个操作： 对于一个数字，它对那...

CF896D Nephren Runs a Cinema 题意 售票员最开始没有纸币，每次来一个顾客可以给她一张、拿走她一张或不操作。求出不出现中途没钱给的情况 \(n\) 名顾客后剩余钱数在 \(l\sim r\) 的方案数。 思路 这是我们一道模拟赛题。 解法 1：套路组合计数。先不考虑不操作的顾客，那么就相当于是求二维平面不过一条直线到达一点的方案数。直接枚举操作顾客数，...