0103abc 的网站

前置知识：回文自动机 PAM。 一些定义： 回文串：定义一个长度为 $n$ 的串 $S$ 是回文的，当且仅当 $\forall i\in[1,n],Si=S{n-i+1}$。 Border：一个长度为 $m$ 的串 $T$ 是长度为 $n$ 的串 $S$ 的 Border，当且仅当...

十分经典的题（同样也是 PAM 的入门题之一），很多内容参考了 这篇文章。 先考虑这样的一个问题（P14185 回文子串划分计数）： 给定一个长度为 $n$ 的字符串 $S$。问有多少种划分该字符串的方法，使得划分的每一个子串都是回文串。 定义长度为 $n$ 的字符串 $S$...

直接做比较困难，考虑容斥。于是得到下面的式子： \def\sl{\sum\limits_{1\le i\le j\le n}} (\sl 1)-(\sl[\gcd(i,j)=1])-(\sl[\gcd(pi,pj)=1])+(\sl[\gcd(i,j)=1]\land[\gcd(pi,pj)=1])...

经典套路横纵坐标连边，对位于 $(x,y)$ 坐标的点，从 $x$ 向 $y$ 连一条双向边，得到一张图。容易发现此时连通块之间互相独立，因此这里只考虑一个连通块的情况。 发现此时答案和连通块的具体形态无关，只和连通块内点和边的数量有关。因此设点的数量为 $v$，边的数量为 $e$： 若...

经典套路考虑曼哈顿转切比雪夫，将两维坐标的约束分离讨论。设转切比雪夫后第 $i$ 个点的坐标为 $(xi,yi)$，则此时距离的定义变为：$\text{Dist}(i,j)=\max(|xi-xj|,|yi-yj|)$。 然后求第 $k$ 便宜的问题考虑二分求解，设当前二分到的第 $k$...

感觉比较典。题目给的条件是 $|i-j|=|ai-aj|$，所以考虑经典套路拆绝对值，条件变为 $i-ai=j-aj$ 或 $i+ai=j+aj$。于是容易想到点边互换，对每个 $i$ 满足 $1\le i\le n$，都在 $i-ai$ 和 $i+ai$...

先考虑不带修怎么做。容易想到设 $fi$ 表示当前考虑了前 $i$ 个位置，且第 $i$ 个位置放了支撑塔，最少所花费的代价是多少。容易想到 $O(n^2)$ 转移：枚举上一个设支撑塔的位置 $j$，转移为 $fi=(\min\limits{j}fj)+a_i$，其中 $j$ 需要满足...

这也太难了，，，好吧我真没见过这个套路（） 移动袋鼠是比较困难的，所以考虑移动边界和中间的坑。先考虑没有坑的情况，此时只需要记录上下左右四个边界的移动情况，具体来说：上边界最下移动到哪里，下边界最上移动到哪里，左边界最右移动到哪里，右边界最左移动到哪里。...

没想到官方题解的线性做法，所以这里提供一个比较困难的 ds 做法。直接做比较困难，考虑直接维护序列的平均攻击力。初始时平均攻击力为 $1$，这里将其写作非化简分数的形式即 $\frac 11$。 然后考虑每个操作对答案的贡献： 卡牌选择：可以看作是分子和分母同时加 $1$（后面简记为 $1$...

比较有趣的题。考虑到问题问的是“第 $k$ 大的值最大是多少”，于是容易想到二分这个最大值，问题在于怎么 check 是否合法。 注意到问题最多只会加一个等差数列，所以考虑对等差数列做一个滑动窗口，然后从左往右扫描整个数组，此时每一个位置的值的变化形如： 保持原来的值。 变为全过程的最大值。...