分析 我们需要加几个字符在末尾将其变为回文串。那么我们可以很容易考虑到，回文中心一定在这个字符串上。那么当一个回文中心确定时，这个串其实也就确定了。那么添加的长度为 。所以我们就应该寻找最大的可行的 。那么当一个字符可以为回文中心时当且仅当，回文中心加上回文半径覆盖了第 个字符的。那么求出每个点的回文半径就做完了。 代码 #include<bits/stdc++.h> using namespace std; const int N = 3e7 + 100; char ch[N],S[N]; int n,cnt,p[N],ans; int main() { scanf...

分析 我们看出，这是一个匹配问题。左边的点只能匹配右边的节点。而一个节点可以匹配的数量为 。我们可以考虑用网络流来解决这个问题。 向左边节点 连接一条容量为 边。 右边节点 向 连接一条容量为 的边。 如果右侧节点 满足 ，那么左侧节点 向 连一条容量为 的边。最后 。 但是我们发现这样连边时间复杂度为 的，要考虑优化。因为连的边是一个连续的区间，我们其实可以考虑线段树优化建边。那么总边数为 。 那么用 的总复杂度为 。由于网络流好像基本跑不满，所以也就过了。 代码 #include<bits/stdc++.h> using namesp...

分析 对于这类问题，我们先观察是否有什么性质。由于我们要求 的所有数最后都可以到达 。而 在行动时候会经过 的所有节点。那么我们的问题就随之转换为， 到 最少要经过几个区间。那么我们可以先考虑 。令 为考虑到前 个机器，当前点为 的最小步数。那么我们就有两个转移 和 。那么这样我们的总复杂度为 。 但其实我们仔细思考一下，可以发现，我们是否可以从 走到 只与最大值，也就是区间的右端点 有关。所以我们改变一下方程 只在 时才转移。那么这样是不会失去最优答案的，因为对于每个区间，只有我尽量靠右，才可能成为最优值。那么这样我们的时间复杂度为 了。而且观察到 ...

分析 非常好的思维题。我们发现第一条件完全没有用，其实就是要求我们，使每个串的后缀必须先于该串出现。那么我们可以根据后缀来构成一个拓扑图。那么现在问题就是求，求出一个拓扑图的遍历顺序，要求 这个最小。我们发现最小代价的遍历顺序，那么一个点的贡献就是 。那么我们优先 的 来遍历一定是最优的。 如何构建新图。我们考虑把所有串反序插入。那么在 树上，节点 是 的父亲，那么就要连一条 的单向边。这个很好理解，因为反序插入之后如果一个节点是另一个节点父亲或者祖先。那么它一定是作为后缀出现的。这里我们可以考虑用并查集来维护所有 上的结束节点。 新图上的求解，先进行一次 ，将所有节...

分析 要求有一条可以无限长的串，满足所有字串没有出现过。那么我们可以考虑 自动机。我们用 表示，那个无限长的串不可以匹配的节点。那么我们就会有这个转移 ，因为 是我的一个后缀，那么后缀都不能到，更别说自己了。那么我们直接在 自动机上 就好了。 代码 #include<bits/stdc++.h> using namespace std; const int N = 3e4 + 100; int ch[N][2],fail[N],size,inq[N]; char S[N]; int n,vis[N]; void ins(char *s) { int len = ...

分析 比较简单的贪心题。我们考虑到二分一个答案 。那么存在 也是成立的。所以这个是具有单调性的。那么为了让所有的点都是合法的。那么肯定要拿出最近一个将要不合法的节点让他的电量 。那么当第 次充电时发现最近的节点没电的时间在 之前，则是个非法答案。那么我们算法就是如果快速找到第一个将要不合法的点。这里考虑用 来维护就好了。那么总的复杂度为 。 还有一些减枝的小技巧，就看代码了。 代码 #include<bits/stdc++.h> using namespace std; #define LL long long const LL N = 2e5 + 100; s...

分析 可以说是关于 自动机运用的较难题了。但是能用 坚决不用 自动机。我们考虑一个串作为字串出现在其它字符串中，那么就是看这个串的结束节点的 集合有多少这个区间的串。所以现在的思路就是，对所有串建一个广义后缀自动机，这里不能建那种 之后就不管的伪自动机。要使用 树建法，或者在线建法。然后对于所有等价类求出 集合，最后查询一个区间和。那么我们发现算法的瓶颈在于如何求出 集合和区间和。我们考虑线段树合并，这样总的复杂度为 。 其实这道题用 自动机来写是非常有意思的，可以试试啊。代码 #include<bits/stdc++.h> using namespace s...

分析 真的是好题。我们考虑并不是所有线段都是有用的，如果有两条线段相交，那么其实我们只需要切断第一个 就行了。所以我们可以形式化的表达当 则 时，这才是个合法图。而我们就是要求这个图转换为合法图之后的最小答案。我们考虑线性 。令 以 结尾的最小代价。那么我们的转移为 。我们发现其实后面的是一堆常数。那么这又是一个满足 的形式了。所以我们考虑李超线段树来维护这个凸壳。 代码 #include<bits/stdc++.h> using namespace std; #define LL long long LL read() { LL x = 0,f = 0;c...

分析 非常平凡的一道题，没太大意义。这里放松，敲了一个 。有区间覆盖的，如果保证随机，其实 还是不错的。 代码 #include<bits/stdc++.h> using namespace std; struct Node{ int l,r; mutable int c; bool operator <(const Node a) const { return l < a.l; } Node(int _l,int _r = 0,int _c = 0) {l=_l;r=_r;c=_c;} }; set<N...

分析 我们先把最初的 方程写出来。令 为 结尾的最小代价。那么转移为 。那么我们令 是 的决策点，那么用前缀和 那么化简后 ，那么我们把这个化为了 的形式。但是 并不单调，所以我们考虑使用 维护一个上凸壳。时间复杂度为 。 代码 #include<bits/stdc++.h> using namespace std; #define LL long long const LL N = 8e5 + 10,mod = 998244353,M = 6e8; const long long inf = 0x3f3f3f3f3f3f3f3f; LL read() {...