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

康托展开 什么是康托展开？ 就是关于全排列中某个排列的排名的问题  给出一个全排列，求出它是第几个全排列，这就叫康托展开 给出一个全排列的长度以及它的排名，让你求出这个全排列，这叫逆康托展开 （以上全排列都是从     1   −   N    1-N   1−N的排列，否则需要离散化一下，且排名指从小到大的排名）  康托展开的核心—变进制数 对于一个     N    N   N个数的排列  如果我们依次从左边到右边选择数字组成排列，那么每个位置可以选择的数字个数是确定的。比如第一个数有     N    N   N种选择，第二个数只有     N   −   1    N-1   N−1种...

Three arrays 赛场上想了半年都没有一点思路。。。看了题解发现原来是我学过的东东。。。（标题我瞎编的名字） 题意：给了一个大小为     1   e   5    1e5   1e5的     a    a   a数组和一个大小为     1   e   5    1e5   1e5的     b    b   b数组，请你对     a   ，   b    a，b   a，b数组元素任意排序，使得到的     c    c   c数组（      c   i    =    a   i     c_i=a_i   ci​=ai​      X   o   r    Xor   X...

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

Palindrome Mouse 题意：若把给定字符串的所有不同回文子串放到一个集合内，求集合内有多少对回文子串满足其中一个是另一个的子串。 思路：  建好回文自动机 若设     a   n    s   i     ans_i   ansi​为回文树上能到达     i    i   i节点的节点数（     0   ,   1    0,1   0,1除外），则题目要求的就是    <mstyle displaystyle="true" scriptlevel="0"> <munderover>  ∑    i   =   ...

Pair 考场上加了各种各样的优化也没能由T变AC。。。赛后题解“直接数位DP就行” 题意：给定     A   ,   B   ,   C    A,B,C   A,B,C求满足。。。还是看下面的题目描述吧。 思路：  直接数位DP就行，但需要注意的是！ 两个数的数位DP对于不保存的情况只有两个数都达到上限时，其余的都需要记忆化。比如一个数达到上限，另一个没有达到上限的情况。当然，也可以全部都保存下来，也不怎么费空间  题目描述： Given three integers , Count the number of pairs      <   x   ,   y   &amp...

K短路-魔法猪学院 题意：给定一个能量值     E    E   E，以及一些单向边权。求所拥有的能量能从     1    1   1走到     N    N   N多少次，并且每一次的走法不完全一样，即求最大的     K    K   K使得 前     K    K   K短路的和 不大于     E    E   E。 思路：  建边时将正反边都记录好 第一遍跑     d   i   j   s   t   r   a    dijstra   dijstra或     s   p   f   a    spfa   spfa将从     1    1   1到所有点最短路求出...

Just Jump 题意： 求从     0    0   0跳到     L    L   L处的方案数，条件限制为： —每次跳跃最少跳     d    d   d的长度 —有     m    m   m个     p   a   i   r   (   t   ,   p   )    pair(t,p)   pair(t,p)，每个表示不能在跳第     t    t   t次时跳到点     p    p   p处 思路：  利用容斥原理，先求出从     0    0   0跳到     L    L   L处的总方案，然后减去满足某个     p   a   i   r    ...

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

简洁的学习 更进一步的学习 小总结  优化目的：在依次计算     d   p   [   j   ]    dp[j]   dp[j]时能快速找到前方最优的     j    j   j使得从     j    j   j到     i    i   i的转移最优；若不优化，整体复杂度应为     O   (    n   2    )    O(n^2)   O(n2)，优化后为     O   (   n   l   o   g   n   )    O(nlogn)   O(nlogn)或     O   (   n   )    O(n)   O(n)（在于斜率     k    k...

Shortest Cycle 题意：给定     1   e   5    1e5   1e5个点的     a   [   i   ]    a[i]   a[i]，任意两个点     i   ,   j    i,j   i,j之间存在无向边当且仅当     a   [   i   ]    a[i]   a[i] &      a   [   j   ]   !   =   0    a[j]!=0   a[j]!=0，求周长最小的环 思路：  将所有的     a   [   i   ]    a[i]   a[i]看作二进制形式，则若两个点之间没有边，说明二者的二进制位没有公...

Wood Processing 题意：有     n    n   n块矩形，给出每块矩形底边长和高度，要将     n    n   n块矩形合并为     k    k   k块矩形，求最小花费（细节见题目描述） 思路：  先将矩形从高到低排序，然后处理出     d   p    dp   dp方程转化成的直线方程后所需要的变量 在做斜率优化DP时，依次枚举合并为     1    1   1块，     2    2   2块，…，     k    k   k块的     d   p    dp   dp值，复杂度为     O   (   k   ∗   n   )    O(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)<&...

最短母串问题 题意：给定     n    n   n个子串，求最短且字典序最小的母串（母串性质：这     n    n   n个子串都包含在母串里） 思路：  考虑把子串去重（不去重能不能A我不知道，但去重肯定没问题） 建好AC自动机 从     0    0   0节点开始用     b   f   s    bfs   bfs遍历自动机，并且总是从’A’遍历到’Z’以保证答案的字典序最下 每次取出头结点时检查其状态是否包含了所有的子串，状态检查：     n   o   w   .   s   t   a   t   e   =   =   (   1   <   &am...