长期留坑

1.AC自动机多模式串匹配问题

对于要统计各个模式串在文本中的出现次数，对于每个当前节点不能直接暴力跳$fail$

复杂可以退化到$O(n^2)$

$aaaaaa……aaa$可以卡掉

要将$fail$指针反向建出来，明显这是棵树，然后统计其子树大小

 1 #include <bits/stdc++.h>

 2 using namespace std;

 3 const int N=2*1e5+100;

 4 int n,tot,wh[N],cnt[N];

 5 struct node

 6 {

 7     int son[26],fail;

 8 }sh[N];

 9 string s,t;

10 vector <int> e[N];

11 void build(int x)

12 {

13     int p=1;

14     for (int i=0;i<(int)t.size();i++)

15     {

16         if (!sh[p].son[t[i]-'a'])

17         {

18             tot++;

19             sh[p].son[t[i]-'a']=tot;

20         }

21         p=sh[p].son[t[i]-'a'];

22     }

23     wh[x]=p;

24 }

25 void build_fail()

26 {

27     queue <int> q;

28     q.push(1);

29     while (!q.empty())

30     {

31         int x=q.front();

32         q.pop();

33         for (int i=0;i<26;i++)

34         {

35             if (!sh[x].son[i])

36             {

37                 if (x==1)

38                   sh[x].son[i]=1;

39                 else

40                   sh[x].son[i]=sh[sh[x].fail].son[i];

41             }

42             else

43             {

44                 if (x==1)

45                   sh[sh[x].son[i]].fail=1;

46                 else

47                   sh[sh[x].son[i]].fail=sh[sh[x].fail].son[i];

48                 q.push(sh[x].son[i]);

49             }

50         }

51     }

52 }

53 void match()

54 {

55     int p=1;

56     for (int i=0;i<(int)s.size();i++)

57     {

58         p=sh[p].son[s[i]-'a'];

59         cnt[p]++;

60     }

61 }

62 void dfs(int x,int fa)

63 {

64     for (int i=0;i<(int)e[x].size();i++)

65     {

66         int u=e[x][i];

67         if (u!=fa)

68         {

69             dfs(u,x);

70             cnt[x]+=cnt[u];

71         }

72     }

73 }

74 int main()

75 {

76     tot=1;

77     scanf("%d",&n);

78     for (int i=1;i<=n;i++)

79     {

80         cin>>t;

81         build(i);

82     }

83     build_fail();

84     cin>>s;

85     match();

86     for (int i=2;i<=tot;i++)

87     {

88         e[i].push_back(sh[i].fail);

89         e[sh[i].fail].push_back(i);

90     }

91     dfs(1,1);

92     for (int i=1;i<=n;i++)

93       printf("%d\n",cnt[wh[i]]);

94 }

2.KMP询问字符串的最短循环节

如$abcabcabc$的最短循环节为$abc$

先处理出这个字符串的前缀函数

如果循环节的长度为$k$，字符串的长度为$n$

那么$nxt[n-1]=n-k$

移项可得$k=n-nxt[n-1]$

那么只要满足$n-nxt[n-1]\mid n$，$n-nxt[n-1]$就是最短循环节，否则就是$n$

 1 nxt[l]=0;

 2 for (int i=l+1;i<=r;i++)

 3 {

 4     int j=nxt[i-1];

 5     while (j>0 && ch[i]!=ch[j+l])

 6       j=nxt[j-1];

 7     if (ch[i]==ch[j+l])

 8       j++;

 9     nxt[i]=j;

10 }

11 int N,M;

12 N=r-l+1;

13 M=N-nxt[r];

14 if (N%M==0)

15   return M;

16 else

17   return N;

3.对于分段函数迭代

比如CF1271E

在画出函数转移树的时候，要注意不同对应法则的连边的两个数字是否满足该函数的不同的定义域

如CF1271E这道题，一定要注意$f(x)=x-1$是在偶数情况下满足，所以在二分时要分偶数奇数考虑

4.Splay的区间操作和权值操作

对于区间操作，在建树时就要将$1$和$n+1$建入平衡树中，避免进行区间操作时越界

对于权值操作，在建树时要将$inf$和$-inf$建入平衡树中，避免求前驱后继时越界

5.对于最小费用最大流的建图

在建图的时候一定要注意，建出来的图在满足题目限制条件的时候，跑费用流时，是不是满足最大流的情况

也就是说，要将题目中所有的限制条件建的边是要能跑出最大流的

否则不满足最大流，是谈不上最小费用的

6.高斯消元

在将把主对角线上的矩阵元素替换成非0元素时候，需要在对$i$行进行处理的时候之前才进行替换

不能先将所有的行替换好，在进行消元

如

1 1 2

3 3 6

就无法判断无穷解的情况

正确做法

错误做法

7.FFT的使用范围

FFT处理的是如同$c_i = \sum\limits_{j=0}^{i}a_jb_{i-j}$的卷积形式

FFT只是DFT的加速，处理出的是在$n+1$个单位元点下多项式的取值

FFT只能处理$2^{k}$次的卷积，对于不是$2$的幂次长度的卷积

对于两个长度为$n$的多项式，其卷积的长度应为$2n-1$，那么要找到$k$，使得$2^{k}>=2n-1$

然后进行循环卷积

8.主席树处理区间第k大

主席树相当于处理了一个前缀和，是满足可加、可减性的

所以也可以处理树上的问题

处理第k大的思想主要就是维护前缀和

9.树形背包

如果是在枚举子树的时候先累加$size$，那么复杂度为$O(n^3)$

需要先进行转移再累加$size$

这样相当于 $dp$ 的时候是当前子树大小乘上这个子树之前所有子树的大小之和，可以理解成该子树中每一个点与之前的所有子树里每一个点两两组成的点对被计算一次，这样的话每一对点都只会被计算一次（在它们的 $LCA$ 处），时间复杂度$O(n^2)$

并且注意要倒序转移

for (int p=first[x];p!=-1;p=nxt[p])

{

    int u=point[p];

    if (u==fa) continue;

    for (int i=sz[x];i>=0;i--)

    {

        for (int j=sz[u];j>=0;j--)

        {

            if (i+j>背包容量) continue;

            dp[x][i+j]=max(dp[x][i+j],dp[x][i]+dp[u][j]+价值函数);

        }

    }

    sz[x]+=sz[u];

}

10.斜率优化--二分凸包

在二分凸包上的斜率的时候要注意要特判凸包上第一个点是否就是直线所切到的最佳决策点

如维护下凸包的时候，判断凸包上第一条线段的斜率是否大于当前直线的斜率，若大于直接返回第一个点

11.整体二分

在分治过程要函数开头判断当前是否还有操作的答案在$l$,$r$之间，如果没有直接返回，可以极大地减少常数

void solve(int x,int y,int l,int r)

{

    if (x>y) return;//important!!

        if (l==r)

        {

            ……

        }

        ……

}

12.左偏树的$dis$

在合并的过程中一定要保持$dis[0]=-1$来保证复杂度的正确

可以在$pushup$中开头加一句，以免有复杂操作会改变$dis[0]$的值

并且在$pop$的时候$dis$,$son$要重置为$0$，在重复利用时若$dis$不为$0$会出现问题

巴特西

一些bug