Reinhart's algorithm template

,

Dijkstra

朴素 $O(N^2)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <vector>
#include <iostream>
#include <cstring>
using namespace std;
const int N = 510;
int n, m;
int g[N][N];//邻接矩阵存稠密图
int dis[N];//该点到起点的最短距离
bool st[N];//每个点的最短路是否已经确定
void dijkstra() {
    memset(dis, 0x3f, sizeof dis);
	  memset(st,false,sizeof st);
    dis[1] = 0;
    for (int i = 0; i < n - 1; ++i) {
        int t = -1;//将t设置为-1 因为Dijkstra算法适用于不存在负权边的图
        for (int j = 1; j <= n; ++j) {
            if (!st[j] && (t == -1 || dis[t] > dis[j]))t = j;//该步骤即寻找还未确定最短路的点中路径最短的点
        }
        st[t] = true;//第t个点的最短路径已经确定

        for (int j = 1; j <= n; ++j) {
            dis[j] = min(dis[j], dis[t] + g[t][j]); //用t去更新t能达到的点到起点的最短距离
        }


    }
}

int main() {
    cin >> n >> m;
    memset(g, 0x3f, sizeof g);
}

堆优化 $O(NlogN)$

链星版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include<iostream>
#include<cstring>
#include<queue>
#include<vector>
using namespace std;
const int N=150010;
int n,m;
typedef pair<int,int>PII;
int h[N],e[N],ne[N],idx=0,w[N];
void add(int a,int b,int c){
    w[idx]=c;
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;
}
int dis[N];
bool st[N];
void dijkstra(){
    memset(dis,0x3f,sizeof dis);
    memset(st,false,sizeof st);
    priority_queue<PII,vector<PII>,greater<PII>>heap;
    dis[1]=0;
    heap.push({0,1});
    while(heap.size()){
        auto t=heap.top();
        heap.pop();
        int ver=t.second,distance=t.first;
        if(st[ver])continue;
        st[ver]=true;

        for(int i=h[ver];~i;i=ne[i]){
            int j=e[i];
            if(dis[j]>distance+w[i]) {
                dis[j] = distance + w[i];
                heap.push({dis[j], j});
            }
        }
    }
}
int main(){
    memset(h,-1,sizeof h);

    cin>>n>>m;
    while(m--){
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);

    }
}

vector数组版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
vector<PII > g[N];
int dis[N];
bool st[N];

void dijkstra() {
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    memset(dis, 0x3f, sizeof dis);
    heap.push({0, T});
    dis[T]=0;
    while (!heap.empty()) {
        auto t = heap.top();
        heap.pop();
        int ver = t.se, distance = t.fi;
        if (st[ver])continue;
        st[ver] = true;
        for (int i = 0; i < g[ver].size(); i++) {
            auto j = g[ver][i];
            if (dis[j.fi] > distance + j.se) {
                dis[j.fi] = distance + j.se;
                heap.push({dis[j.fi], j.fi});

            }
        }
    }
}

快排

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void quick_sort(int q[], int l, int r)
{
    if (l >= r) return;
    int x = q[l + r >> 1];//确定分界点
    int i = l - 1, j = r + 1;//因为是先移动再交换
    while (i < j)
    {
        do i ++ ; while (q[i] < x);
        do j -- ; while (q[j] > x);
        if (i < j) swap(q[i], q[j]);
    }

    quick_sort(q, l, j);
    quick_sort(q, j + 1, r);

}

埃氏筛

1
2
3
4
5
6
7
8
9
10
11
12
13
const int N=1e6+5;
int prime[N];
bool st[N];
int cnt=0;
void Egypt_Prime(int n){
    for(int i=2;i<=n/i;i++){
        if(!st[i]){
            prime[cnt++]=i;
            for(int j=i+i;j<=n;j+=i)st[j]= true;
        }
x	
    }
}

线性筛

1
2
3
4
5
6
7
8
9
10
11
12
13
const int N=1e6+5;
int prime[N];
bool st[N];
int cnt=0;
void get_prime(int n){
    for(int i=2;i<=n;i++){
        if(!st[i])prime[cnt++]=i;
        for(int j=0;prime[j]<=n/i;j++){
            st[prime[j]*i]=true;
            if(i%prime[j]==0)break;//因为prime是从小到大枚举，所以如果i%prime[j]==0说明prime[j]是i的最小质因子
        }
    }
}

大数加

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <iostream>
#include <vector>

using namespace std;

vector<int> add(vector<int> &A, vector<int> &B)
{
    if (A.size() < B.size()) return add(B, A);

    vector<int> C;
    int t = 0;
    for (int i = 0; i < A.size(); i ++ )
    {
        t += A[i];
        if (i < B.size()) t += B[i];
        C.push_back(t % 10);
        t /= 10;
    }

    if (t) C.push_back(t);
    return C;
}

int main()
{
    string a, b;
    vector<int> A, B;
    cin >> a >> b;
    for (int i = a.size() - 1; i >= 0; i -- ) A.push_back(a[i] - '0');
    for (int i = b.size() - 1; i >= 0; i -- ) B.push_back(b[i] - '0');

    auto C = add(A, B);

    for (int i = C.size() - 1; i >= 0; i -- ) cout << C[i];
    cout << endl;

    return 0;
}

并查集

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int p[N]; //存储每个点的祖宗节点

// 返回x的祖宗节点
int find(int x)
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

// 初始化，假定节点编号是1~n
for (int i = 1; i <= n; i ++ ) p[i] = i;

// 合并a和b所在的两个集合：
p[find(a)] = find(b);

​

gcd

1
2
3
4
int gcd(int a, int b)
{
    return b ? gcd(b, a % b) : a;
}

扩展gcd

1
2
3
4
5
6
7
8
9
10
ll exgcd(ll a, ll b, ll &x, ll &y){
    if(b == 0){
        x = 1, y = 0;
        return a;
    }

    ll d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

快速幂

1
2
3
4
5
6
7
8
9
ll qmi(ll a,ll k,ll p){
    ll res=1;
    while(k){
        if(k&1)res=(res*a)%p;
        k=k>>1;
        a=(a*a)%p;
    }
    return res;
}

快速幂求逆元

根据费马小定理$b^{p-1}\equiv1\mod{p}\to b*b^{p-2}\equiv 1 \mod{p}$可得$b$的逆元为$b^{p-2}$

$(p是质数)$

矩阵快速幂

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
struct Mat
{
    ll m[101][101];
};//存储结构体
Mat a,e; //a是输入的矩阵，e是输出的矩阵
Mat Mul(Mat x,Mat y)
{
    Mat c;
    for(int i=1;i<=n;++i){
        for(int j=1;j<=n;++j){
            c.m[i][j] = 0;
        }
    }
    for(int i=1;i<=n;++i){
        for(int j=1;j<=n;++j){
            for(int k=1;k<=n;++k){
                c.m[i][j] = c.m[i][j]%mod + x.m[i][k]*y.m[k][j]%mod;
            }
        }
    }
    return c;
}
Mat pow(Mat x,ll y)//矩阵快速幂
{
    Mat ans = e;
    while(y){
        if(y&1) ans = Mul(ans,x);
        x = Mul(x,x);
        y>>=1;
    }
    return ans;
}

欧拉函数

1
2
3
4
5
6
7
8
9
10
ll a;
ll res = a;
        for (int i = 2; i <= a / i; ++i) {
            if (a % i == 0) {
                res = res * (i - 1) / i;//等价于(1-1/i)
                while (a % i == 0)a /= i;
            }
        }
        if (a > 1)res = res * (a - 1) / a;
        cout<<res<<'\n';

欧拉筛

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
const int N=1000005;
int euler[N];//存欧拉函数值
bool st[N];
int primes[N];
int cnt=0;
ll get_euler(int n){
    euler[1]=1;
    for (int i = 2; i <=n ; ++i) {
        if(!st[i]){
            primes[cnt++]=i;
            euler[i]=i-1;//质数n的前n-1个数字都与他互质
        }
        for (int j = 0; primes[j] <=n/i ; ++j) {
            st[primes[j]*i]=true;
            if(i%primes[j]==0){
                euler[i*primes[j]]=euler[i]*primes[j];
                break;
            }
            euler[i*primes[j]]=euler[i]*(primes[j]-1);
        }
    }
    ll res=0;
    for (int i = 1; i <=n ; ++i) res+=euler[i];

    return res;
}

快读

1
2
3
4
5
6
7
8
9
10
11
12
13
inline ll read() {
    char ch = getchar();
    ll p = 1, data = 0;
    while(ch < '0' || ch > '9') {
        if(ch == '-')p = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9') {
        data = data * 10 + (ch ^ 48);
        ch = getchar();
    }
    return p * data;
}

扩展中国剩余定理(模数不互质)

tips:

1.检查题目的a是否是正整数，若不是则需要预处理a（模数m一定是正整数） 

1
for(int i=0;i<n;i++) a[i]=mod(a[i],m[i]); //输入可能为负数

2.检查$\prod_{i=0}^{n-1}{b[i]}$是否会爆long long

  • int $[ -2147483648,2147483647]$
  • unsigned int $[ 0,4294967295]$
  • long $[-2147483648,2147483647]$
  • unsigned long $ [0,4294967295]$
  • long long $[-9223372036854775808,9223372036854775807]$
  • unsigned long long $[0,18446744073709551615]$
  • __int64 $[-9223372036854775808,9223372036854775807]$
  • unsigned __int64 $[0,18446744073709551615]$
  • float（32位）精确到小数点后6~7位
    • double（64位）精确到小数点后15~16位
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <cstdio>
#include <iostream>
using namespace std;
typedef long long ll;
int n;
const int N = 30;

ll exgcd(ll a, ll b, ll &x, ll &y) {
    if (b == 0) {
        x = 1, y = 0;
        return a;
    }

    ll d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

ll inline mod(ll a, ll b) {
    return ((a % b) + b) % b;//返回正余数的小技巧
}

ll a[N];
ll m[N];//模数
bool exCNRemainder() {
    for (int i = 0; i < n - 1; ++i) {
        ll k1, k2;
        ll d = exgcd(m[i], -m[i + 1], k1, k2);
        if ((a[i + 1] - a[i]) % d)return false;//无解
        k1 = mod(k1 * (a[i + 1] - a[i]) / d, abs(m[i + 1] / d));
        a[i+1] = k1 * m[i] + a[i];
        m[i+1] = abs(m[i] / d * m[i + 1]);//m1,m2的最大公约数
    }
    return true;
}

int main() {
    cin>>n;
    for (int i = 0; i <n ; ++i) {
        cin>>m[i]>>a[i];
    }
    if(exCNRemainder())cout<<a[n-1];
    else
        cout<<-1;
    return 0;
}
//https://www.acwing.com/solution/content/3539/

KMP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <iostream>
using namespace std;
const int N = 1000010, M = 100010;
int n, m;
int nxt[M];
char s[N];//主串
char p[M];//子串
void kmp(){
    //求nxt数组
    for (int i = 2, j = 0; i <= m; i ++ )//找以i结尾的P的相等的前缀与后缀最长长度
    {
        while (j && p[i] != p[j + 1]) j = nxt[j];
        if (p[i] == p[j + 1]) j ++ ;
        nxt[i] = j;
    }	
    //kmp匹配
    for (int i = 1, j = 0; i <= n; i ++ )
    {
        while (j && s[i] != p[j + 1]) j = nxt[j];//p还没退到起点并且不能匹配
        if (s[i] == p[j + 1]) j ++ ;
        if (j == m)//匹配成功
        {
            printf("%d ", i - m);//输出每次匹配成功的起始位置的下标
            j = nxt[j];
        }
    }
}
int main()
{
    cin >> m >> p + 1 >> n >> s + 1;

    kmp();
    return 0;
}
  • 求一个字符串的最小循环节的长度
1
int cir = n - nxt[n];

如果n可以被n - nxt[n]整除，则表明字符串S可以完全由循环节循环组成，循环周期T=n/cir。

如果不能，说明还需要再添加几个字母才能补全。需要补的个数是循环个数cir-n%cir=cir-(n-cir)%cir=cir-nxt[n]%cir

EXKMP

1664523306-5b8b351da943a_fix732

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
/*
https://segmentfault.com/a/1190000008663857
定义s，p，设s的长度为n，p的长度为m，求p与s的每一个后缀的最长公共前缀，也就是说，设extend数组,extend[i]表示p与s[i,n-1]的最长公共前缀，要求出所有extend[i](0<=i<n)。
注意到，如果有一个位置extend[i]=m,则表示T在S中出现，而且是在位置i出现，这就是标准的KMP问题，所以说拓展kmp是对KMP算法的扩展，所以一般将它称为扩展KMP算法。
 
 
注意！！！：此模版的nxt[i]是i-m-1的最长相同前缀，之前的kmp模版的nxt[i]是1-i
 */

// 从0开始
/* 求解 T 中 next[]，注释参考 GetExtend() */
char s[N];
char p[N];
int nxt[N];//p[i]...p[m - 1]与T的最长相同前缀长度
int extend[N];
int n;//s的长
int m;//p的长
void GetNext()
{
    int a = 0, pos = 0;
    nxt[0] = m;

    for (int i = 1; i < m; i++)
    {
        if (i >= pos || i + nxt[i - a] >= pos)
        {
            if (i >= pos)
                pos = i;

            while (pos < m && p[pos] == p[pos - i])
                pos++;

            nxt[i] = pos - i;
            a = i;
        }
        else
            nxt[i] = nxt[i - a];
    }
}

/* 求解 extend[] */
void GetExtend()
{
    int a = 0, pos = 0;
    GetNext();

    for (int i = 0; i < n; i++)
    {
        if (i >= pos || i + nxt[i - a] >= pos) // i >= p 的作用：举个典型例子，s 和 p 无一字符相同
        {
            if (i >= pos)
                pos = i;

            while (pos < n && pos - i < m && s[pos] == p[pos - i])
                pos++;

            extend[i] = pos - i;
            a = i;
        }
        else
            extend[i] = nxt[i - a];
    }
}

最小表示法

  • 找一个循环字符串的字典序最小的表示方法

对于两个循环的字符串如果能表示同一个字符串输出Yes否则输出No

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
int get_min(string s) {
    int i = 0, j = 1;

    while (i < n && j < n) {
        int k = 0;
        while (k < n && s[i + k] == s[j + k])k++;
        if (k >= n)break;
        if (s[i + k] > s[j + k])i += k + 1;
        else {
            j += k + 1;
        }
        if (i == j)j++;
    }
    int idx = min(i, j);//i和j又一个越界了才会退出上面的循环 所以这里取没有越界的那个肯定是最小的;
    //cout << idx<< '\n';//返回最小表示的起始点
    return idx ;
}


void solve() {
    string a, b;
    cin >> a >> b;
    n = a.length();
    a += a, b += b;

    int sta = get_min(a), stb = get_min(b);
    //cout<<a.substr(sta,n/2)<<' '<<b.substr(stb,n/2)<<'\n';
    if (a.substr(sta, n) == b.substr(stb, n)) {
        cout << "Yes" << '\n';
        cout << a.substr(sta,n);
    }
    else {
        cout << "No" << '\n';
    }

}

Manacher

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
const int N = 1e7 + 5;
char a[N];//原串
char s[N * 2];//处理过的串
int p[N * 2];//p[i]是以i为中心的最长回文串半径
//因为p[i]是相较于处理过的串而言的，所以p[i]-1即为以i为中心的最长回文串的长度
int n;

void init() {
    int idx = 0;
    s[idx++] = '$';
    s[idx++] = '#';
    for (int i = 0; i < n; i++) {
        s[idx++] = a[i], s[idx++] = '#';
    }
    s[idx++] = '^';
    n = idx;
}

void manacher() {
    int mr = 0;//最长回文的最右边界
    int mid;
    for (int i = 1; i < n; i++) {
        if (i < mr)p[i] = min(p[i - (i - mid) * 2], mr - i);
        else {
            p[i] = 1;
        }
        while (s[i - p[i]] == s[i + p[i]]) {
            p[i]++;
        }
        if (i + p[i] > mr) {
            mr = i + p[i];
            mid = i;
        }
    }
}

字典树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
const int N = 100010;
int son[N][26];//下标是0的点既是根节点又是空节点
int cnt[N];//以当前这个点结尾的单词有多少个
int idx;//当前用到了哪个下标
char str[N];

void insert()
{
    int p = 0;
    for (int i = 0; str[i]; i ++ )
    {
        int u = str[i] - 'a';//字母映射成数字
        if (!son[p][u]) son[p][u] = ++ idx;//如果不存在就把它创建出来
        p = son[p][u];
    }
    cnt[p] ++ ;
}

int query()
{
    int p = 0;
    for (int i = 0; str[i]; i ++ )
    {
        int u = str[i] - 'a';
        if (!son[p][u]) return 0;
        p = son[p][u];
    }
    return cnt[p];
}

AC自动机

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<unordered_map>
#include<set>
//#pragma GCC optimize(2)
//#pragma GCC optimize("inline")
//#pragma GCC optimize("-fgcse")
//#pragma GCC target("avx","sse2")
//#pragma GCC optimize("-fgcse-lm")
//#pragma GCC optimize("-fipa-sra")
//#pragma GCC optimize("-ftree-pre")
//#pragma GCC optimize("-ftree-vrp")
//#pragma GCC optimize("-fpeephole2")
//#pragma GCC optimize("-ffast-math")
//#pragma GCC optimize("-fsched-spec")
//#pragma GCC optimize("unroll-loops")
using namespace std;
#define ll long long
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define PIII pair<int,PII>
#define PLLL pair<ll,PLL>
#define fi first
#define se second
#define pb push_back
#define debug(a) cout << #a << " " << a << '\n';

const ll INF = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;

inline ll read();

const int N = 10010, S = 55, M = 1000010;
int n, m;
char s[M];
int tr[N * S][26], cnt[N * S], idx;
int ne[N * S];

void insert() {//trie树插入模版
    int p = 0;
    for (int i = 0; s[i]; i++) {
        int t = s[i] - 'a';
        if (!tr[p][t])tr[p][t] = ++idx;
        p = tr[p][t];
    }
    cnt[p]++;//p位置上的字符串多了一个
}

void build() {//构建ac自动机（bfs）
    queue<int> q;
    for (int i = 0; i < 26; i++) {
        //因为第一层也是全部连到根节点的，所以把第一层先全部入队
        if (tr[0][i])q.push(tr[0][i]);
    }
    //宽搜
    while (!q.empty()) {
        int t = q.front();
        q.pop();
        //遍历t的所有儿子
        for (int i = 0; i < 26; i++) {
            int p = tr[t][i];
            // if(p)
            // {
            //     int j = ne[t];
            //     while(j && !tr[j][i]) j = ne[j];
            //     if(tr[j][i]) j = tr[j][i];
            //     ne[p] = j;
            //     q[++tt] = p;
            // }

            // 优化思路 在没有匹配时 把while循环多次跳 优化为 直接跳到ne指针最终跳到的位置
            // 如果不存在儿子tr[t][i]的话就让当前节点的这个子节点指向当前节点指针的子节点
            if (!p) tr[t][i] = tr[ne[t]][i];
                // 如果存在儿子节点 让这个节点的指针指向(((他父亲节点)的失败指针所指向的那个节点)的下一个节点)
            else {
                ne[p] = tr[ne[t]][i];
                q.push(p);
            }

        }
    }
}

void solve() {
    memset(tr, 0, sizeof tr);
    memset(cnt, 0, sizeof cnt);
    memset(ne, 0, sizeof ne);
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> s;
        insert();
    }
    build();
    cin >> s;
    int res = 0;
    for (int i = 0, j = 0; s[i]; i++) {
        int t = s[i] - 'a';
        /*
        while(j && !tr[j][t]) j = ne[j];
        if(tr[j][t]) j=tr[j][t];
        int p = j;
         // she 和 he 的 e结点都有cnt[e]=1
            遍历到she的后缀he的时候 her的相同前缀he肯定是逐层遍历到了的 len(he)<len(she) 逐层遍历
            把所有ne 指针全部加一遍  比如当前p到了she的e  把cnt[p]+进res后
            把p通过ne[p]跳到he的e 再加上此时指向he中e的p的cnt[p]
        while(p)
        {
            res += cnt[p];
            cnt[p] = 0;
            p = ne[p];
        }
        */
        j = tr[j][t];

        int p = j;
        while (p) {
            res += cnt[p];
            cnt[p] = 0;//she he 把cnt[e]的用过了之后 res=2 此时再进来一个her 就不能再+he的cnt了,所以cnt[e]用过之后要置0
            p = ne[p];
        }
    }

    cout<<res<<'\n';
}


int main() {
    ios::sync_with_stdio(false);
#ifdef LOCAL
    int begin_time = clock();
    freopen("../input.txt", "r", stdin);
//    freopen("../output.txt", "w", stdout);
#endif
    int T = 1;
    cin >> T;
    for (int cas = 1; cas <= T; cas++) {
#ifdef LOCAL
        printf("Case #%d: ", cas);
#endif
        solve();
    }

#ifdef LOCAL
    int end_time = clock();
    printf("\nRun time: %.2lf ms", (double) (end_time - begin_time) / CLOCKS_PER_SEC * 1000);
#endif

    return 0;
}


inline ll read() {
    char ch = getchar();
    ll p = 1, data = 0;
    while (ch < '0' || ch > '9') {
        if (ch == '-')p = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        data = data * 10 + (ch ^ 48);
        ch = getchar();
    }
    return p * data;
}

后缀数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
const int N = 1000010;

int n, m;
char s[N];
int sa[N], x[N], y[N], c[N], rk[N], height[N];
/*
后缀数组sa[i]就表示排名为i的后缀的起始位置的下标
而它的映射数组rak[i]就表示起始位置的下标为i的后缀的排名
Height[i]表示LCP(i,i-1)
LCP(i,j)表示suff(sa[i])与suff(sa[j])的最长公共前缀
LCP(i,j)=LCP(j,i);
LCP(i,i)=len(sa[i])=n-sa[i]+1;

ababca
后缀按照字典序排序如下：
a
ababca
abca
babca
bca
ca
Height数组
0 1 2 0 1 0
Sa数组
6 1 3 2 4 5
Rak数组
2 4 3 5 6 1
 */
void get_sa()
{
    for (int i = 1; i <= n; i ++ ) c[x[i] = s[i]] ++ ;
    for (int i = 2; i <= m; i ++ ) c[i] += c[i - 1];
    for (int i = n; i; i -- ) sa[c[x[i]] -- ] = i;
    for (int k = 1; k <= n; k <<= 1)
    {
        int num = 0;
        for (int i = n - k + 1; i <= n; i ++ ) y[ ++ num] = i;
        for (int i = 1; i <= n; i ++ )
            if (sa[i] > k)
                y[ ++ num] = sa[i] - k;
        for (int i = 1; i <= m; i ++ ) c[i] = 0;
        for (int i = 1; i <= n; i ++ ) c[x[i]] ++ ;
        for (int i = 2; i <= m; i ++ ) c[i] += c[i - 1];
        for (int i = n; i; i -- ) sa[c[x[y[i]]] -- ] = y[i], y[i] = 0;
        swap(x, y);
        x[sa[1]] = 1, num = 1;
        for (int i = 2; i <= n; i ++ )
            x[sa[i]] = (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k]) ? num : ++ num;
        if (num == n) break;
        m = num;
    }
}

void get_height()
{
    for (int i = 1; i <= n; i ++ ) rk[sa[i]] = i;
    for (int i = 1, k = 0; i <= n; i ++ )
    {
        if (rk[i] == 1) continue;
        if (k) k -- ;
        int j = sa[rk[i] - 1];
        while (i + k <= n && j + k <= n && s[i + k] == s[j + k]) k ++ ;
        height[rk[i]] = k;
    }
}

int main()
{
    scanf("%s", s + 1);
    n = strlen(s + 1), m = 'z';
    get_sa();
    get_height();

    for (int i = 1; i <= n; i ++ ) printf("%d ", sa[i]);
    puts("");
    for (int i = 1; i <= n; i ++ ) printf("%d ", height[i]);
    puts("");
    return 0;
}

  • 求排名i和排名j的字符串的lcs

    $lcs(i,j)=min(height[i],height[i+1],…,height[j])$

后缀自动机

  • Node的大小要开字符串长度的两倍
  • 存fail树的大小要开字符串长度的三倍
  • 多组初始化
1
2
3
4
5
idx=ans=0;
        tot=1,last=1;
        memset(h, -1, sizeof h);
        memset(node,0,sizeof node);
        memset(f,0,sizeof f);//！

  • 求每个子串出现的次数

  • 对于所有 S 的出现次数不为 1 的子串，设其 value值为该子串出现的次数*该子串的长度。请计算,value 的最大值是多少。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;
const int N = 2000010;
int tot = 1, last = 1;
struct Node
{
    int len, fa;
    int ch[26];
}node[N];
char str[N];
LL f[N], ans;
int h[N], e[N], ne[N], idx;
//对于节点u的子串集合 最长的是node[u].len ,最短的是node[node[u].fa].len+1
void extend(int c)
{
    //fa：fail数组 ch：trie树 len:这个节点集合中字符串最长长度
    int p = last, np = last = ++ tot;//np：初步建立的后缀自动机
    f[tot] = 1;//记录每个子串出现的次数
    node[np].len = node[p].len + 1;
    for (; p && !node[p].ch[c]; p = node[p].fa) node[p].ch[c] = np;
    if (!p) node[np].fa = 1;
    else
    {
        int q = node[p].ch[c];
        if (node[q].len == node[p].len + 1) node[np].fa = q;
        else
        {
            int nq = ++ tot;//nq：当某节点没有合适的点做Fail的父亲时，需要的添加公共节点
            node[nq] = node[q], node[nq].len = node[p].len + 1;
            node[q].fa = node[np].fa = nq;
            for (; p && node[p].ch[c] == q; p = node[p].fa) node[p].ch[c] = nq;
        }
    }
}

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

void dfs(int u)
{
    for (int i = h[u]; ~i; i = ne[i])
    {
        dfs(e[i]);
        f[u] += f[e[i]];//根据fail树的性质可以直接递归求出现次数
    }
    if (f[u] > 1) ans = max(ans, f[u] * node[u].len);//出现次数大于1的记录一下
}

int main() {
    scanf("%s", str);
    for (int i = 0; str[i]; i++) extend(str[i] - 'a');
    memset(h, -1, sizeof h);
    for (int i = 2; i <= tot; i++) add(node[i].fa, i);//构建fail树
    dfs(1);
    printf("%lld\n", ans);

    return 0;
}

  • 给一个文本串s和多个模式串t ，我们要检查字符串t是否作为s的一个子串出现。也可以求模式串t在文本串中出现的最大前缀长度

  • 给一个主串s和m个子串t,求每一个t在s中出现的最大前缀长度 s和t都是由ESWN这几个字符构成.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
#include<bits/stdc++.h>
//#pragma GCC optimize(2)
//#pragma GCC optimize("inline")
//#pragma GCC optimize("-fgcse")
//#pragma GCC target("avx","sse2")
//#pragma GCC optimize("-fgcse-lm")
//#pragma GCC optimize("-fipa-sra")
//#pragma GCC optimize("-ftree-pre")
//#pragma GCC optimize("-ftree-vrp")
//#pragma GCC optimize("-fpeephole2")
//#pragma GCC optimize("-ffast-math")
//#pragma GCC optimize("-fsched-spec")
//#pragma GCC optimize("unroll-loops")
using namespace std;
#define ll long long
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define fi first
#define se second
#define pb push_back
#define debug(a) cout << #a << " " << a << '\n';
const int INF = 0x3f3f3f3f;
const ll LLINF =0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
inline ll read();
const int N = 2e7+5;
int tot = 1, last = 1;
struct Node
{
    int len, fa;
    int ch[4];
}node[N];
int change(char c){
    if(c=='E')return 0;
    if(c=='S')return 1;
    if(c=='W')return 2;
    if(c=='N')return 3;
}
string s;
string t;
void extend(int c)
{
    //fa：fail数组 ch：trie树 len:这个节点集合中字符串最长长度
    int p = last, np = last = ++ tot;//np：初步建立的后缀自动机
    node[np].len = node[p].len + 1;
    for (; p && !node[p].ch[c]; p = node[p].fa) node[p].ch[c] = np;
    if (!p) node[np].fa = 1;
    else
    {
        int q = node[p].ch[c];
        if (node[q].len == node[p].len + 1) node[np].fa = q;
        else
        {
            int nq = ++ tot;//nq：当某节点没有合适的点做Fail的父亲时，需要的添加公共节点
            node[nq] = node[q], node[nq].len = node[p].len + 1;
            node[q].fa = node[np].fa = nq;
            for (; p && node[p].ch[c] == q; p = node[p].fa) node[p].ch[c] = nq;
        }
    }
}
int query(){
    int p=1;
    int cnt=0;
    for(int i=0;i<t.length();i++){
        int u=change(t[i]);
        if(!node[p].ch[u])return cnt;
        else{
            p=node[p].ch[u];
            cnt++;
        }
    }
    return cnt;
}
int n,m;

void solve() {
    cin>>n>>m;
    cin>>s;
    for(int i=0;i<n;i++)extend(change(s[i]));
    while(m--){
        cin>>t;
        cout<<query()<<'\n';
    }
}
int main() {
    //ios::sync_with_stdio(false);
#ifdef LOCAL
    int begin_time = clock();
    freopen("../input.txt", "r", stdin);
//    freopen("../output.txt", "w", stdout);
#endif
    int T = 1;
    //T = read();
    for (int cas = 1; cas <= T; cas++) {
#ifdef LOCAL
        printf("Case #%d: ", cas);
#endif
        solve();
    }

#ifdef LOCAL
    int end_time = clock();
    printf("\nRun time: %.2lf ms", (double) (end_time - begin_time) / CLOCKS_PER_SEC * 1000);
#endif

    return 0;
}


inline ll read() {
    char ch = getchar();
    ll p = 1, data = 0;
    while (ch < '0' || ch > '9') {
        if (ch == '-')p = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        data = data * 10 + (ch ^ 48);
        ch = getchar();
    }
    return p * data;
}
  • 给一个数字串, 每加入一个字符,求当前所有子串个数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
#include<bits/stdc++.h>
//#pragma GCC optimize(2)
//#pragma GCC optimize("inline")
//#pragma GCC optimize("-fgcse")
//#pragma GCC target("avx","sse2")
//#pragma GCC optimize("-fgcse-lm")
//#pragma GCC optimize("-fipa-sra")
//#pragma GCC optimize("-ftree-pre")
//#pragma GCC optimize("-ftree-vrp")
//#pragma GCC optimize("-fpeephole2")
//#pragma GCC optimize("-ffast-math")
//#pragma GCC optimize("-fsched-spec")
//#pragma GCC optimize("unroll-loops")
using namespace std;
#define ll long long
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define fi first
#define se second
#define pb push_back
#define debug(a) cout << #a << " " << a << '\n';
const int INF = 0x3f3f3f3f;
const ll LLINF =0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
inline ll read();
const int N = 2e5+5;
int tot = 1, last = 1;
struct Node
{
    int len, fa;
    unordered_map<int,int>ch;
}node[N];

ll ans=0;
void extend(int c)
{
    //fa：fail数组 ch：trie树 len:这个节点集合中字符串最长长度
    int p = last, np = last = ++ tot;//np：初步建立的后缀自动机
    node[np].len = node[p].len + 1;
    for (; p && !node[p].ch[c]; p = node[p].fa) node[p].ch[c] = np;
    if (!p) node[np].fa = 1;
    else
    {
        int q = node[p].ch[c];
        if (node[q].len == node[p].len + 1) node[np].fa = q;
        else
        {
            int nq = ++ tot;//nq：当某节点没有合适的点做Fail的父亲时，需要的添加公共节点
            node[nq] = node[q], node[nq].len = node[p].len + 1;
            node[q].fa = node[np].fa = nq;
            for (; p && node[p].ch[c] == q; p = node[p].fa) node[p].ch[c] = nq;
        }
    }
    //debug(last)
    //debug(tot)
    ans+=node[last].len-node[node[last].fa].len;//last是加的这个c的位置
}
int n;

void solve() {
    cin>>n;
    for(int i=0;i<n;i++){
          int x;
        cin>>x;
        extend(x);
        cout<<ans<<'\n';
    }

}
int main() {
    //ios::sync_with_stdio(false);
#ifdef LOCAL
    int begin_time = clock();
    freopen("../input.txt", "r", stdin);
//    freopen("../output.txt", "w", stdout);
#endif
    int T = 1;
    //T = read();
    for (int cas = 1; cas <= T; cas++) {
#ifdef LOCAL
        printf("Case #%d: ", cas);
#endif
        solve();
    }

#ifdef LOCAL
    int end_time = clock();
    printf("\nRun time: %.2lf ms", (double) (end_time - begin_time) / CLOCKS_PER_SEC * 1000);
#endif

    return 0;
}


inline ll read() {
    char ch = getchar();
    ll p = 1, data = 0;
    while (ch < '0' || ch > '9') {
        if (ch == '-')p = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        data = data * 10 + (ch ^ 48);
        ch = getchar();
    }
    return p * data;
}

救急大板子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <string>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <unordered_map>

#define  pi    acos(-1.0)
#define  eps   1e-9
#define  fi    first
#define  se    second
#define  rtl   rt<<1
#define  rtr   rt<<1|1
#define  bug                printf("******\n")
#define  mem(a, b)          memset(a,b,sizeof(a))
#define  name2str(x)        #x
#define  fuck(x)            cout<<#x" = "<<x<<endl
#define  sfi(a)             scanf("%d", &a)
#define  sffi(a, b)         scanf("%d %d", &a, &b)
#define  sfffi(a, b, c)     scanf("%d %d %d", &a, &b, &c)
#define  sffffi(a, b, c, d) scanf("%d %d %d %d", &a, &b, &c, &d)
#define  sfL(a)             scanf("%lld", &a)
#define  sffL(a, b)         scanf("%lld %lld", &a, &b)
#define  sfffL(a, b, c)     scanf("%lld %lld %lld", &a, &b, &c)
#define  sffffL(a, b, c, d) scanf("%lld %lld %lld %lld", &a, &b, &c, &d)
#define  sfs(a)             scanf("%s", a)
#define  sffs(a, b)         scanf("%s %s", a, b)
#define  sfffs(a, b, c)     scanf("%s %s %s", a, b, c)
#define  sffffs(a, b, c, d) scanf("%s %s %s %s", a, b,c, d)
#define  FIN                freopen("../in.txt","r",stdin)
#define  gcd(a, b)          __gcd(a,b)
#define  lowbit(x)          x&-x
#define  IO                 iOS::sync_with_stdio(false)


using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
const ULL seed = 13331;
const LL INFLL = 0x3f3f3f3f3f3f3f3fLL;
const int maxm = 8e6 + 10;
const int INF = 0x3f3f3f3f;
const int mod = 2012;
const int maxn = 1e6 + 7;

struct Suffix_Automaton {
    int last, tot, nxt[maxn << 1][26], fail[maxn << 1];//last是未加入此字符前最长的前缀（整个串）所属的节点的编号
    int len[maxn << 1];// 最长子串的长度 (该节点子串数量 = len[x] - len[fa[x]])
    int sz[maxn << 1];// 被后缀链接的个数，方便求节点字符串的个数
    LL num[maxn << 1];// 该状态子串的数量
    LL maxx[maxn << 1];// 长度为x的子串出现次数最多的子串的数目
    LL sum[maxn << 1];// 该节点后面所形成的自字符串的总数
    LL subnum, sublen;// subnum表示不同字符串数目,sublen表示不同字符串总长度
    int X[maxn << 1], Y[maxn << 1]; // Y表示排名为x的节点，X表示该长度前面还有多少个
    int minn[maxn << 1], mx[maxn << 1];//minn[i]表示多个串在后缀自动机i节点最长公共子串，mx[i]表示单个串的最长公共子串
    int L[maxn << 1];

    void init() {
        tot = last = 1;
        fail[1] = len[1] = 0;
        for (int i = 0; i < 26; i++) nxt[1][i] = 0;
    }

    void extend(int c) {
        int u = ++tot, v = last;
        for (int i = 0; i <= 25; i++) nxt[u][i] = 0;
        fail[u] = 0;
        L[u] = len[u] = len[v] + 1;
        num[u] = 1;
        for (; v && !nxt[v][c]; v = fail[v]) nxt[v][c] = u;
        if (!v) fail[u] = 1, sz[1]++;
        else if (len[nxt[v][c]] == len[v] + 1) fail[u] = nxt[v][c], sz[nxt[v][c]]++;
        else {
            int now = ++tot, cur = nxt[v][c];
            len[now] = len[v] + 1;
            L[now] = L[cur];
            memcpy(nxt[now], nxt[cur], sizeof(nxt[cur]));
            fail[now] = fail[cur];
            fail[cur] = fail[u] = now;
            for (; v && nxt[v][c] == cur; v = fail[v]) nxt[v][c] = now;
        }
        last = u;
        //return len[last] - len[fail[last]];//多添加一个子串所产生不同子串的个数
    }

    void get_num() {// 每个节点子串出现的次数
        for (int i = 1; i <= tot; i++) X[i] = 0;
        for (int i = 1; i <= tot; i++) X[len[i]]++;
        for (int i = 1; i <= tot; i++) X[i] += X[i - 1];
        for (int i = 1; i <= tot; i++) Y[X[len[i]]--] = i;
        for (int i = tot; i >= 1; i--) num[fail[Y[i]]] += num[Y[i]];
    }

    void get_maxx(int n) {// 长度为x的子串出现次数最多的子串的数目
        get_num();
        for (int i = 1; i <= tot; i++) maxx[len[i]] = max(maxx[len[i]], num[i]);
    }

    void get_sum() {// 该节点后面所形成的自字符串的总数
        get_num();
        for (int i = tot; i >= 1; i--) {
            sum[Y[i]] = 1;
            for (int j = 0; j <= 25; j++)
                sum[Y[i]] += sum[nxt[Y[i]][j]];
        }
    }

    void get_subnum() {//本质不同的子串的个数
        subnum = 0;
        for (int i = 1; i <= tot; i++) subnum += len[i] - len[fail[i]];
    }

    void get_sublen() {//本质不同的子串的总长度
        sublen = 0;
        for (int i = 1; i <= tot; i++) sublen += 1LL * (len[i] + len[fail[i]] + 1) * (len[i] - len[fail[i]]) / 2;
    }

    void get_sa() { // Y表示排名为x的节点，X表示该长度前面还有多少个
        for (int i = 0; i <= tot; i++) X[i] = 0;
        for (int i = 1; i <= tot; i++) X[len[i]]++;
        for (int i = 1; i <= tot; i++) X[i] += X[i - 1];
        for (int i = 1; i <= tot; i++) Y[X[len[i]]--] = i;
    }

    void match(char s[]) {//多个串的最长公共子串
        mem(mx, 0);
        int n = strlen(s), p = 1, maxlen = 0;
        for (int i = 0; i < n; i++) {
            int c = s[i] - 'a';
            if (nxt[p][c]) p = nxt[p][c], maxlen++;
            else {
                for (; p && !nxt[p][c]; p = fail[p]);
                if (!p) p = 1, maxlen = 0;
                else maxlen = len[p] + 1, p = nxt[p][c];
            }
            mx[p] = max(mx[p], maxlen);
        }
        for (int i = tot; i; i--)
            mx[fail[i]] = max(mx[fail[i]], min(len[fail[i]], mx[i]));
        for (int i = tot; i; i--)
            if (minn[i] == -1 || minn[i] > maxx[i]) minn[i] = mx[i];
    }

    void get_kth(int k) {//求出字典序第K的子串
        int pos = 1, cnt;
        string s = "";
        while (k) {
            for (int i = 0; i <= 25; i++) {
                if (nxt[pos][i] && k) {
                    cnt = nxt[pos][i];
                    if (sum[cnt] < k) k -= sum[cnt];
                    else {
                        k--;
                        pos = cnt;
                        s += (char) (i + 'a');
                        break;
                    }
                }
            }
        }
        cout << s << endl;
    }

} sam;

int T, cas = 1;
char s[maxn];

int main() {
    sfi(T);
    while (T--) {
        sfs(s);
        int len = strlen(s);
        sam.init();
        printf("Case #%d:\n", cas++);
        for (int i = 0; i < len;) {
            int p, maxlen;
            for (p = 1, maxlen = 0; i < len;) {
                int c = s[i] - 'a';
                if (!sam.nxt[p][c]) break;
                else {
                    p = sam.nxt[p][c];
                    sam.extend((s[i] - 'a'));
                    i++, maxlen++;
                }
            }
            if (maxlen) printf("%d %d\n", maxlen, sam.L[p] - maxlen);
            else printf("-1 %d\n", s[i]), sam.extend((s[i] - 'a')), i++;
        }
    }

    return 0;
}

单调栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>

using namespace std;

const int N = 100010;

int stk[N], tt;

int main()
{
    int n;
    cin >> n;
    while (n -- )
    {
        int x;
        scanf("%d", &x);
        while (tt && stk[tt] >= x) tt -- ;
        if (!tt) printf("-1 ");
        else printf("%d ", stk[tt]);
        stk[ ++ tt] = x;
    }

    return 0;
}

单调队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <iostream>

using namespace std;

const int N = 1000010;

int a[N], q[N];
//队列存a的下标
int main()
{
    int n, k;
    scanf("%d%d", &n, &k);
    for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);
    //求窗口最小值
    int hh = 0, tt = -1;
    for (int i = 0; i < n; i ++ )
    {
        if (hh <= tt && i - k + 1 > q[hh]) hh ++ ;// 当前队头不在窗口内部，将其删掉（当前窗口[i-k+1,i]）

        while (hh <= tt && a[q[tt]] >= a[i]) tt -- ;//若当前队尾比该数还大说明是没用的，所以把它出队
        q[ ++ tt] = i;

        if (i >= k - 1) printf("%d ", a[q[hh]]);
    }

    puts("");
    //求窗口最大值
    hh = 0, tt = -1;
    for (int i = 0; i < n; i ++ )
    {
        if (hh <= tt && i - k + 1 > q[hh]) hh ++ ; 

        while (hh <= tt && a[q[tt]] <= a[i]) tt -- ;
        q[ ++ tt] = i;

        if (i >= k - 1) printf("%d ", a[q[hh]]);
    }

    puts("");

    return 0;
}

求组合数

多次询问

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 2010, mod = 1e9 + 7;


int c[N][N];


void init()
{
    for (int i = 0; i < N; i ++ )
        for (int j = 0; j <= i; j ++ )
            if (!j) c[i][j] = 1;
            else c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
}


int main()
{
    int n;

    init();

    scanf("%d", &n);

    while (n -- )
    {
        int a, b;
        scanf("%d%d", &a, &b);

        printf("%d\n", c[a][b]);
    }

    return 0;
}

询问稍少 a,b稍大

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 100010, mod = 1e9 + 7;


int fact[N], infact[N];


int qmi(int a, int k, int p)
{
    int res = 1;
    while (k)
    {
        if (k & 1) res = (LL)res * a % p;
        a = (LL)a * a % p;
        k >>= 1;
    }
    return res;
}


int main()
{
    fact[0] = infact[0] = 1;
    for (int i = 1; i < N; i ++ )
    {
        fact[i] = (LL)fact[i - 1] * i % mod;
        infact[i] = (LL)infact[i - 1] * qmi(i, mod - 2, mod) % mod;//求逆元
    }


    int n;
    scanf("%d", &n);
    while (n -- )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        printf("%d\n", (LL)fact[a] * infact[b] % mod * infact[a - b] % mod);
    }

    return 0;
}

询问很少 a,b很大(lucas定理)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;


int qmi(int a, int k, int p)
{
    int res = 1;
    while (k)
    {
        if (k & 1) res = (LL)res * a % p;
        a = (LL)a * a % p;
        k >>= 1;
    }
    return res;
}


int C(int a, int b, int p)
{
    if (b > a) return 0;

    int res = 1;
    for (int i = 1, j = a; i <= b; i ++, j -- )
    {
        res = (LL)res * j % p;
        res = (LL)res * qmi(i, p - 2, p) % p;
    }
    return res;
}


int lucas(LL a, LL b, int p)
{
    if (a < p && b < p) return C(a, b, p);
    return (LL)C(a % p, b % p, p) * lucas(a / p, b / p, p) % p;
}


int main()
{
    int n;
    cin >> n;

    while (n -- )
    {
        LL a, b;
        int p;
        cin >> a >> b >> p;
        cout << lucas(a, b, p) << endl;
    }

    return 0;
}

答案很大但不能求模

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;


const int N = 5010;

int primes[N], cnt;
int sum[N];
bool st[N];

//线性筛模版
void get_primes(int n)
{
    for (int i = 2; i <= n; i ++ )
    {
        if (!st[i]) primes[cnt ++ ] = i;
        for (int j = 0; primes[j] <= n / i; j ++ )
        {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) break;
        }
    }
}

//求n的阶乘里质因子p的个数
int get(int n, int p)
{
    int res = 0;
    while (n)
    {
        res += n / p;
        n /= p;
    }
    return res;
}

//高精度模版
vector<int> mul(vector<int> a, int b)
{
    vector<int> c;
    int t = 0;
    for (int i = 0; i < a.size(); i ++ )
    {
        t += a[i] * b;
        c.push_back(t % 10);
        t /= 10;
    }
    while (t)
    {
        c.push_back(t % 10);
        t /= 10;
    }
    return c;
}


int main()
{
    int a, b;
    cin >> a >> b;

    get_primes(a);

    for (int i = 0; i < cnt; i ++ )//枚举每一个质数
    {
        int p = primes[i];
        sum[i] = get(a, p) - get(a - b, p) - get(b, p);//当前质数的个数
    }

    vector<int> res;
    res.push_back(1);

    //用高精度乘法把质因子乘起来
    for (int i = 0; i < cnt; i ++ )//枚举所有质数
        for (int j = 0; j < sum[i]; j ++ )//枚举所有质数的次数
            res = mul(res, primes[i]);

    for (int i = res.size() - 1; i >= 0; i -- ) printf("%d", res[i]);
    puts("");

    return 0;
}

卡特兰数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 100010, mod = 1e9 + 7;


int qmi(int a, int k, int p)
{
    int res = 1;
    while (k)
    {
        if (k & 1) res = (LL)res * a % p;
        a = (LL)a * a % p;
        k >>= 1;
    }
    return res;
}


int main()
{
    int n;
    cin >> n;

    int a = n * 2, b = n;
    int res = 1;
    for (int i = a; i > a - b; i -- ) res = (LL)res * i % mod;

    for (int i = 1; i <= b; i ++ ) res = (LL)res * qmi(i, mod - 2, mod) % mod;

    res = (LL)res * qmi(n + 1, mod - 2, mod) % mod;

    cout << res << endl;

    return 0;
}

放球问题

image-20211203091207912

高斯消元

整型

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
int a[N][N];//增广矩阵
int x[N];//解集
bool freeX[N];//标记是否为自由变元
int GCD(int a,int b){
    return !b?a:GCD(b,a%b);
}
int LCM(int a,int b){
    return a/GCD(a,b)*b;
}
int Gauss(int equ,int var){//返回自由变元个数
    /*初始化*/
    for(int i=0;i<=var;i++){
        x[i]=0;
        freeX[i]=true;
    }
 
    /*转换为阶梯阵*/
    int col=0;//当前处理的列
    int row;//当前处理的行
    for(row=0;row<equ&&col<var;row++,col++){//枚举当前处理的行
        int maxRow=row;//当前列绝对值最大的行
        for(int i=row+1;i<equ;i++){//寻找当前列绝对值最大的行
            if(abs(a[i][col])>abs(a[maxRow][col]))
                maxRow=i;
        }
        if(maxRow!=row){//与第row行交换
            for(int j=row;j<var+1;j++)
                swap(a[row][j],a[maxRow][j]);
        }
        if(a[row][col]==0){//col列第row行以下全是0，处理当前行的下一列
            row--;
            continue;
        }
 
        for(int i=row+1;i<equ;i++){//枚举要删去的行
            if(a[i][col]!=0){
                int lcm=LCM(abs(a[i][col]),abs(a[row][col]));
                int ta=lcm/abs(a[i][col]);
                int tb=lcm/abs(a[row][col]);
                if(a[i][col]*a[row][col]<0)//异号情况相加
                    tb=-tb;
                for(int j=col;j<var+1;j++) {
                    a[i][j]=a[i][j]*ta-a[row][j]*tb;
                }
            }
        }
    }
 
    /*求解*/
    //无解：化简的增广阵中存在(0,0,...,a)这样的行，且a!=0
    for(int i=row;i<equ;i++)
        if (a[i][col]!=0)
            return -1;
 
    //无穷解: 在var*(var+1)的增广阵中出现(0,0,...,0)这样的行
    int temp=var-row;//自由变元有var-row个
    if(row<var)//返回自由变元数
        return temp;
 
    //唯一解: 在var*(var+1)的增广阵中形成严格的上三角阵
    for(int i=var-1;i>=0;i--){//计算解集
        int temp=a[i][var];
        for(int j=i+1;j<var;j++){
            if(a[i][j]!=0)
                temp-=a[i][j]*x[j];
        }
        if(temp%a[i][i]!=0)//有浮点数解，无整数解
            return -2;
        x[i]=temp/a[i][i];
    }
    return 0;
}
 
int main(){
    int equ,var;//equ个方程，var个变元
    while(scanf("%d%d",&equ,&var)!=EOF) {
 
        memset(a,0,sizeof(a));
        for(int i=0;i<equ;i++)//输入增广矩阵
            for(int j=0;j<var+1;j++)
                scanf("%d",&a[i][j]);
 
 
        int freeNum=Gauss(equ,var);//自由元个数
        if(freeNum==-1)//无解
            printf("无解\n");
        else if(freeNum==-2)//有浮点数解无整数解
            printf("无整数解\n");
        else if(freeNum>0){//有无穷多解
            printf("有无穷多解，自由变元个数为%d\n",freeNum);
            for(int i=0;i<var;i++){
                if(freeX[i])
                    printf("x%d是自由变元\n",i+1);
                else
                    printf("x%d=%d\n",i+1,x[i]);
            }
        }
        else{//有唯一解
            for(int i=0;i<var;i++)
                printf("x%d=%d\n",i+1,x[i]);
        }
        printf("\n");
    }
    return 0;
}


浮点型

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;

const int N = 110;
const double eps = 1e-6;

int n;
double a[N][N];


int gauss()
{
    int c, r;
  //消成上三角矩阵
    for (c = 0, r = 0; c < n; c ++ )//枚举每一列
    {
        int t = r;
        for (int i = r; i < n; i ++ )
            if (fabs(a[i][c]) > fabs(a[t][c]))//找到绝对值最大的那一行
                t = i;

            if (fabs(a[t][c]) < eps) continue;

        for (int i = c; i < n + 1; i ++ ) swap(a[t][i], a[r][i]);//把绝对值最大的一行换到最上面
        for (int i = n; i >= c; i -- ) a[r][i] /= a[r][c];//把该行第一个数变成1->倒着更新,不然第一个数先被更新成1除后面的数就无效了

      
        for (int i = r + 1; i < n; i ++ )
            if (fabs(a[i][c]) > eps)
                for (int j = n; j >= c; j -- )
                    a[i][j] -= a[r][j] * a[i][c];//把下边所有行的第c列消成0

        r ++ ;
    }

    if (r < n)
    {
        for (int i = r; i < n; i ++ )
            if (fabs(a[i][n]) > eps)//出现了0=非0的情况
                return -1;//无解
        return n-r;//多组解,返回自由元个数
    }
		//消成对角线矩阵
    for (int i = n - 1; i >= 0; i -- )
        for (int j = i + 1; j < n; j ++ )//倒着把其他系数全部消成0（解所在位置的系数是1）
            a[i][n] -= a[j][n] * a[i][j];

    return 0;//唯一解
}

int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < n + 1; j ++ )
            cin >> a[i][j];

    int t = gauss();

    if (t == 0)
    {
        for (int i = 0; i < n; i ++ ) printf("%.2lf\n", a[i][n]);
    }
    else if (t == 1) puts("Infinite group solutions");
    else puts("No solution");

    return 0;
}

高斯消元解异或方程组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 110;


int n;
int a[N][N];


int gauss() {
    int c, r;
    for (c = 0, r = 0; c < n; c++) {
        int t = r;
        for (int i = r; i < n; i++)
            if (a[i][c])
                t = i;

        if (!a[t][c]) continue;

        for (int i = c; i < n + 1; i++) swap(a[r][i], a[t][i]);
        for (int i = r + 1; i < n; i++)//将下面所有行的第c列消成0
            if (a[i][c])
                for (int j = n; j >= c; j--)
                    a[i][j] ^= a[r][j];//该行第c列肯定是1，所以下面行异或该行第c列肯定可以消成0（两个1异或）

        r++;
    }

    if (r < n) {
        for (int i = r; i < n; i++)
            if (a[i][n])
                return -1;//无解
        return n-r;//多组解,返回自由元个数
    }

    for (int i = n - 1; i >= 0; i--)
        for (int j = i + 1; j < n; j++)
            a[i][n] ^= a[i][j] & a[j][n];

    return 0;//唯一解
}


int main() {
    cin >> n;

    for (int i = 0; i < n; i++)
        for (int j = 0; j < n + 1; j++)
            cin >> a[i][j];

    int t = gauss();

    if (t == 0) {
        for (int i = 0; i < n; i++) cout << a[i][n] << endl;
    } else if (t >0) puts("Multiple sets of solutions");
    else puts("No solution");

    return 0;
}

用高斯消元把行列式化成上三角行列式再求解$O(N^3)$

取模(没有负数解)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
typedef long long ll;
ll A[110][110];

const int mod=1e9+7;

ll quick_pow(ll a, ll n, ll mod) {
    ll ans = 1;
    while(n) {
        if(n & 1) ans = ans * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return ans;
}

ll inv(ll a) {
    return quick_pow(a, mod - 2, mod);
}

ll gauss(int n){
    ll ans = 1;
    for(int i = 1; i <= n; i++){
        for(int j = i; j <= n; j++) {
            if(A[j][i]){
                for(int k = i; k <= n; k++) swap(A[i][k], A[j][k]);
                if(i != j) ans = -ans;
                break;
            }
        }
        if(!A[i][i]) return 0;
        for(ll j = i + 1, iv = inv(A[i][i]); j <= n; j++) {
                ll t = A[j][i] * iv % mod;
                for(int k = i; k <= n; k++)
                    A[j][k] = (A[j][k] - t * A[i][k] % mod + mod) % mod;
        }
        ans = (ans * A[i][i] % mod + mod) % mod;
    }
    return ans;
}


double(有负数解)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int Gauss1()
{
    for(int i=1;i<=n;i++){
        int p=i;
        while(!f[p][i] and p<=n)p++;
        if(p>=n+1)return 0;
        if(p!=i)swap(f[i],f[p]);
        for(int j=i+1;j<=n;j++)
        {
            double tmp=f[j][i]/f[i][i];
            for(int k=i;k<=n;k++)
            f[j][k]-=f[i][k]*tmp;
        }
    }
    double ans=1;
    for(int i=1;i<=n;i++)
    ans*=f[i][i];
    return (int)(ans+0.5);
}


二分模版

答案在左区间中

  • 当我们将区间$[l, r]$划分成$[l, mid]$和$[mid + 1, r]$时，其更新操作是$r = mid$或者$l = mid + 1$;，计算mid时不需要加1。
1
2
3
4
5
6
while (l < r)
   {
       int mid = l + r >> 1;
       if (check(mid)) r = mid;
       else l = mid + 1;
   }

答案在右区间中

  • 当我们将区间$[l, r]$划分成$[l, mid - 1]$和$[mid, r]$时，其更新操作是$r = mid - 1$或者$l = mid$;，此时为了防止死循环，计算mid时需要加1。
1
2
3
4
5
6
while (l < r)
   {
       int mid = l + r + 1 >> 1;
       if (check(mid)) l = mid;
       else r = mid - 1;
   }

image-20210507215948279

红色区间

三分

https://blog.csdn.net/deletewo/article/details/104102359

适用场景

三分算法适用于求解凸性函数的极值问题，二次函数就是一个典型的单峰函数。

二分利用的是函数的单调性，三分算法利用的是函数的单峰性。

20200128205206158

在区间$[l,r]$，令$m1 = l + (r-l)/3, m2 = r - (r-l)/3$，分别位于1/3、2/3处，接着计算这两个点的函数值，

如果$f(m1)>f(m2)$,求解区间有$[l,r]$变为$[l,m2]$。（就是将最接近极值点那个m点保留，然后 重新划分区间）

此外三分算法也强调严格的单调性，出现函数值相等的区间就不适用了。

浮点数

1
2
3
4
5
6
7
8
9
double l = 0,r = 10000;
while(r-l>=1e-9){//精度问题
    double m1 = l + (r-l)/3.0,m2 = r - (r-l)/3.0;
    if(f(m1)<f(m2))//凸函数，凹函数把符号反过来就行
        l = m1;
    else
        r = m2;
}

整数

1
2
3
4
5
6
7
8
9
10
11
while(r-l>=10){
    int m1=l+(r-l)/3,m2=r-(r-l)/3;
    if(f(m1)<f(m2)){
        l = m1;
    }
    else
        r = m2;
}
for(int i=l;i<=r;i++){//暴力枚举精度区间
    ans=min(ans,f(i));
}

一些结论

a+b=(a&b)+(a|b)

Miller- Rabin

一般底数仍然是随机选取，但当待测数不太大时，选择测试底数就有一些技巧了。比如，如果 被测数小于4 759 123 141，那么只需要测试三个底数2, 7和61就足够了。当然，你测试的越多，正确的范围肯定也越大。如果你每次都用前7个素数(2, 3, 5, 7, 11, 13和17)进行测试，所有不超过341 550 071 728 320的数都是正确的。如果选用2, 3, 7, 61和24251作为底数，那么10^16内唯一的强伪素数为46 856 248 255 981。这样的一些结论使得Miller-Rabin算法在OI中非常实用。通常认为，Miller-Rabin素性测试的正确率可以令人接受，随机选取 k个底数进行测试算法的失误率大概为4^(-k)。