双倍回文 刚刚用Manacher写了一遍这个题，现在换种写法，舒服！！！优美的half数组求法 （Manacher的简单写法请走这里) 题意：若一个回文串左半部分和右半部分分别为一个回文串，则这个回文串被称为双倍回文串(这名字有点傻呀！)。求：给定一个回文串，问最长的双倍回文串有多长。 思路： 由于双倍回文串是建立在回文串的基础上的，因此我们只需要对回文串动动手脚就行了 首先建好回文自动机 然后对每个节点跑一遍fail，若有一个len[fail]长度为len的一半，且len为4的倍数，那就更新答案咯 显然，这样会被卡，aaaaaaaa…aaa这组数据就a不过呀！ ...

康托展开 什么是康托展开？ 就是关于全排列中某个排列的排名的问题 给出一个全排列，求出它是第几个全排列，这就叫康托展开 给出一个全排列的长度以及它的排名，让你求出这个全排列，这叫逆康托展开 （以上全排列都是从 1 − N 1-N 1−N的排列，否则需要离散化一下，且排名指从小到大的排名） ...

Three arrays 赛场上想了半年都没有一点思路。。。看了题解发现原来是我学过的东东。。。（标题我瞎编的名字） 题意：给了一个大小为 1 e 5 1e5 1e5的 a a a...

Virus synthesis 回文自动机好题！ 题意：初始有一个空串，然后通过两种操作得到目的串t，求最少操作数。两种操作分别为： 在字符串前面或者后面任意加一个字符 在字符串前面或者后面加上当前字符串的镜像 思路： 思考一下，花费（操作数）要最小（少），那肯定操作2越多越好呀！ 同时，若过程中经过了操作2，那目的串一定是由某一次操作2以及在字符串前后使用操作1得来的，因此我们只需要求出这样的最优解就行了；否则输出初始化的答案—t的长度 由于操作2只能得到偶数长度的串，因此若我们建好回文自动机，那么只有0节点后面的节点才有用（思考一下） 同时，在由父...

Palindrome Mouse 题意：若把给定字符串的所有不同回文子串放到一个集合内，求集合内有多少对回文子串满足其中一个是另一个的子串。 思路： 建好回文自动机 若设 a n s i ans_i ...

Pair 考场上加了各种各样的优化也没能由T变AC。。。赛后题解“直接数位DP就行” 题意：给定 A , B , C A,B,C A,B,C求满足。。。还是看下面的题目描述吧。 思路： 直接数位DP就行，但需要注意的是！ 两个数的...

K短路-魔法猪学院 题意：给定一个能量值 E E E，以及一些单向边权。求所拥有的能量能从 1 1 1走到 N N N...

Just Jump 题意： 求从 0 0 0跳到 L L L处的方案数，条件限制为： —每次跳跃最少跳 d d ...

Ice_cream’s world II 题意：给定一个有向图，求最小生成树是否存在，若存在则求出根节点以及最小权值。 思路：利用朱刘算法，推荐博客 求最短弧集合E0 检查E0 收缩G中的有向环 展开收缩点 （以下代码节点下标从 0 0 0开始） //#pragma comment(linker, "/STACK:102400000,102400000") #include &quot...

简洁的学习 更进一步的学习 小总结 优化目的：在依次计算 d p [ j ] dp[j] dp[j]时能快速找到前方最优的 ...

Shortest Cycle 题意：给定 1 e 5 1e5 1e5个点的 a [ i ] ...

Wood Processing 题意：有 n n n块矩形，给出每块矩形底边长和高度，要将 n n n块矩形合并为 k k ...

主席树 小小总结： 1. 主席树静态区间第k小板子 //#pragma comment(linker, "/STACK:102400000,102400000") #include "bits/stdc++.h" #define pb push_back #define ls l,m,now<<1 #define rs m+1,r,now<<1|1 #define rt 1,n,1 #define hhh printf("hhh\n") #define see(x) (cerr<<(#x)&l...

最短母串问题 题意：给定 n n n个子串，求最短且字典序最小的母串（母串性质：这 n n n个子串都包含在母串里） 思路： 考虑把子串去重（不去重能不能A我不知道，但去重肯定没问题） 建好AC自动机 从 ...