AC来自一个大佬的名字，并不是写了就可以自动AC的意思 XD AC自动机是建立在trie树上的一种优化手段。trie在每次查询一个字符串时，如果在一个子树查不到就会回溯再查，效率会很低。我们考虑在给每个节点加一个如果查不到就跳转的指针fail，那么如果找不到的话直接跳转到fail就可以了。fail代表的是拥有该点的最大后缀的点的位置。 那么怎么寻找这个fail呢？因为我们要寻找最大后缀，...

成品 B站链接 Wallpaper Engine 可用：搜索 Alice_StarCried 简述 参考了B站的两个自学教程，都是直接搜能搜到的。PS、AE 零基础。因为需要渲染所用电脑配置有一定需求，额外用了数位板。AE 使用了现成脚本。从学习到制作完成总用时不过四天。 所需技能为 PS 基本使用，包括抠图、补图等，以及 AE 基本使用和脚本使用，都很简单。最耗时的部分实际...

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 \] 我们只需要保...

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

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

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

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

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

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

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