zhangas

Pay more attention

0%

Veröffentlicht am Bearbeitet am

数论

质数判断(试除法)

复杂度为O(sqrt(n))
若n%d==0, 则n%n/d==0
只需d<=n/d 即d*d<=n

1
2
3
4
5
6
7
8
9
10
11
12
bool checkprime(int n){
    if(n<2){
        return false;
    }
    //不写成i*i<=n是怕int类型溢出
    for(int i=2;i<=n/i;i++){
        if(n%i==0){
            return false;
        }
    }
    return true;
}

分解质因数(试除法)

复杂度为O(logn)~O(sqrt(n))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void divide(int n){
    if(n<2){
        return;
    }
    for(int i=2;i<=n/i;i++){
        if(n%i==0){//i是质因数
            int s=0;
            while(n/i==0){
                n/=i;
                s++;
            }
            cout<<i<<" "<<s<<endl;
        }
    }
    if(n>1){
        cout<<n<<" "<<1<<endl;
    }
    pust("");
    return;
}

筛质数 统计质数个数

① 埃式筛法
唯一分解定理 任意合数可由素数p1^a1 p2^a2 p3^a3…pk^a3之积表示
(算术基本定理: 任何一个大于1的合数 N可以唯一分解成有限个质数的乘积)
1/2+1/3+…+1/n之和称为调和级数 当n->∞时 Σ->ln n+c (c称为欧拉常数≈0.57721)
时间复杂度为O(nloglogn)

1
2
3
4
5
6
7
8
9
10
void get_primes(int n){
    for(int i=2;i<=n;i++){
        if(!st[i]){
            prime[cnt++]=i;
            for(int j=i+i;j<=n;j+=i){
                st[j]=true;
            }
        }
    }
}

② 线性筛法
根据素数定理 从2到x的素数个数为x/ln x
若只遍历素数 时间复杂度为O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int cnt;//质数的数量 
int primes[N];//从2到n的质数集 
bool st[N];//判断是否为质数 
void get_primes(int n){
	for(int i=2;i<=n;i++){
		if(!st[i]){
			prime[cnt++]=i;
		}
        for(int j=0;primes[j]<n/i;j++){
            st[primes[j]*i]=true;//用最小质因子去筛合数
            if(i%primes[j]==0){
                break;
            }
        }
	}
}

试除法求一个数的所有约数

1
2
3
4
5
6
7
8
9
10
11
12
13
vector<int> get_advisor(int n){
    vector<int> a;
    for(int i=1;i<=n/i;i++){
        if(n%i==0){
            a.push_back(i);
            if(i!=n/i){
                a.push_back(n/i);
            }
        }
    }
    sort(a.begin(),a.end());
    return a;
}

约数个数 约数之和

约数个数定理:任何大于1的正整数n可以表示分解质因数n=Π(pi^ai)
则n的正约数个数为Π(ai+1) (pi^ai的约数有pi^1 pi^2…pi^ai共有ai+1个)
INT范围内 最大的约数个数为1536个
n的约数之和为Π(pi^0+pi^1+…+pi^ai)可由乘法分配律展开证明

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
//给定n个整数ai 求这些数的乘积的约数的个数
//利用哈希表存储pi的ai次方 约数的个数为Π(ai+1)
const int mod=1e9+7;//数据大需要取模
unordered_map<int,int>primes;
int main(){
    int n;cin>>n;
    while(n--){
        int x;cin>>x;
        for(int i=2;i<=x/i;i++){
            while(x%i==0){
                x/=i;
                primes[i]++;
            }
        }
        if(x>1){//如果x很大的话 x的质因数为自身
            primes[x]++;
        }
    }
    LL res=1;//求约数的个数
    for(auto prime:primes){
        res=res*(prime.second+1)%mod;
    }
    cout<<res<<endl;

    LL sum=1;//求约数的和
    for(auto prime:primes){
        int p=prime.first,a=prime.second;
        LL t=1;
        while(a--){//做法巧妙 求p^0 到p^a次方的和的计算
            t=(t*p+1)%mod;
        }
        sum=(sum*t)%mod;
    }
    cout<<sum<<endl;

    return 0;
}

欧几里得算法(辗转相除法)

证明: gcd(a,b)==gcd(b,a%b)=d;
a=xd b=yd 即证gcd((xd)%(yd),yd)==d
x y互质 故gcd(x%y,y)==1 同乘d 证毕

1
2
3
4
int gcd(int a,int b){
    return b?gcd(b,a%b):a;
    //当b==0时 gcd(a,0)为a
}

欧拉函数

1∼N 中与 N互质的数的个数被称为欧拉函数,记为 φ(N).
在算数基本定理中 N=Π(pi^αi)则
φ(N)=N*Π(1-1/pi)

1-1/pi=(pi-1)/pi
容质原理
① 去掉p1、p2、p3…pn的所有倍数(可能一个数被去除了两次)
② 加上所有pipj的倍数(任意两个)
② 减去所有pipjpk的倍数(任意三个)
···
···
N-N/p1-N/p2…-N/pk
+N/(pipj) i,j∈[1,n]&& i!=j
-N/(pipj*pk) i,j,k∈[1,n]&& i!=j&& i!=k&& j!=k
···
···
化简可得到欧拉函数的计算式 (由组合数公式可以确定各式的正负)
欧拉函数与质因子的次数无关

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
//当i%pj==0时候 pj的质因子在i中已经出现过 根据算数基本定理,所以pj*i表示的底数与i的底数相同

//求欧拉函数
typedef long long ll;
ll phi(ll a){
    ll res=a;
    for(int i=2;i<=a/i;i++){//求质数
        if(a%i==0){
            //与分解的底数有关 与幂指数无关
            res=res*(i-1)/i;
        }
        while(a%i==0){
            a/=i;
        }
    }
    if(a>1){
        res=res*(a-1)/a;
    }
    return a;
}
//筛法求欧拉函数
int primes[N],st[N],phi[N];//储存欧拉函数的值
int cnt;//质数的个数
void get_eulers(int n){
    phi[1]=1;

    for(int i=2;i<=n/i;i++){
        if(!st[i]){
            primes[cnt++]=i;
            phi[i]=i-1;
            //p是质数的话 phi为 i-1
        }
        //用质数筛选
        for(int j=0;primes[j]<=n/i;j++){
            st[primes[j]*i]==true;
            if(i%primes[j]==0){
                phi[primes[j]*i]=phi[i]*primes[j];
                break;
            }
            else{
                phi[primes[j]*i]=phi[i]*(primes[j]-1);
            }
        }
    }
}

//欧拉定理: a^φ(n)≡1 (mod n) 
//费马定理: 当n为质数的时候 a^p-1≡1 (mod p)

快速幂

给定 n组a,k,p 求a^k mod p的值

1
2
3
4
5
6
7
8
9
10
11
12
13
//时间复杂度为O(log k)
typedef long long ll;
ll qmi(ll a,ll k,ll p){
    int res=1;
    while(k){
        if(k&1){
            res=(ll)res*a%p;
        }
        k>>=1;
        a=(ll)a*a%p;
    }
    return res;
}

求逆元 (需满足p为质数)
设x为b的乘法逆元
a*x≡a/b(mod p) a与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
typedef long long ll;
int qmi(ll a,ll k,ll p){
    int res=1;
    while(k){
        if(k&1){
            res=(ll)res*a%p;
        }
        k>>=1;
        a=(ll)a*a%p;
    }
}
int main(){
    int n;cin>>n;
    ll a,p;
    while(n--){
        cin>>a>>p;
        if(a%p){//只有当a与p互质时 才有解
            cout<<qmi(a,p-2,p)<<endl;
        }
        else{
            puts("impossible");
        }
    }
    return 0;
}

裴蜀定理(拓展欧几里得实现)

对于任意正整数a,b 一定∃非0整数x, y s.t. ax+by=gcd(a,b)
根据拓展欧几里得定理 对给定a,b 求出满足条件的一组x和y
gcd(a,b)=gcd(b,a%b)
当b==0时 gcd(a,0)==a 对ax+0y==a a=1 b=0时成立
当b!=0时 gcd(b,a%b,y,x)==d by+(a%b)x=d && a%b==a-a/ba -> ax+b(y-a/bx)=d 故x不变 y更新为y-a/bx

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int exgcd(int a,int b,int &x,int &y){
    if(!b){
        x=1,y=0;
        return a;
    }
    int d=gcd(b,a%b,y,x);
    y=y-a/b*x;
    return d;
}
int main(){
    int x;cin>>x;
    int a,b,x,y;
    while(n--){
        cin>>a>>b;
        exgcd(a,b,x,y);
        cout<<x<<" "<<y<<endl;
    }
    return 0;
}

找到ax0+by0=d时
x=x0+b/dk y=y0+b/dk k∈Z 即为满足条件的通解

线性同余方程求解

给定a,b,m求 求是否∃x s.t. ax ≡ b(mod m)
-> ax=ym+b 令y’=-y ->ax+ym=b ->解∃的条件为gcd(a,m)| b
a是gcd(a,m)的倍数 m是gcd(a,m)的倍数 所以拓展a,m后的和一定也是gcd(a,m)的倍数
只有当gcd(a,m)| b时 才有解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int exgcd(int a,int b,int &x,int &y){
    if(!b){
        x=1,y=0;return b;
    }
    int d=gcd(b,a%b);
    y-=a/b*x;
}
int main(){
    int n;cin>>n;
    int a,b,m,x,y;
    while(n--){
        cin>>a>>b>>b;
        int d=exgcd(a,m,x,y);//求ax+my=d 对应x y d的值 
        if(b%d){//不满足gcd(a,m) |b
            puts("impossible");
        }
        else{//求ax+my=b 等式两边同乘b/d %m在m范围内
            cout<<(ll)x*(b/d)%m<<endl;
        }
    }
}

中国剩余定理

对a1…an和m1…mn 求最小的非负整数x
s.t. ∀i∈[1,n] x≡mi (mod ai)
记M为Πmi Mi为M/mi Mi^-1表示Mi模mi的逆
∴x=Σ ai* Mi* Mi^-1
数据范围
1≤ai≤231−1
1≤n≤25 

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
typedef long long ll;
ll exgcd(ll a,ll b,ll &x,ll &y){
    if(!b){
        x=1,y=0;return a;
    }
    ll d=exgcd(b,a%b,y,x);
    y-=a/b*x;
    return d;
}
int main(){
    int n;cin>>n;
    ll a1,a2,m1,m2;
    cin>>a1>>m1;
    //n=1 时 求x≡m1(mod a1) x=k1*a1+m1 k1∈Z 
    bool has_answer=true;//标识是否有答案
    for(int i=0;i<n-1;i++){
        cin>>a2>>m2;
        ll k1,k2;
        ll d=exgcd(a1,a2,k1,k2);
        if((m2-m1)%d){
            has_answer=false;
            break;
        }
        //k1a-k2a2=d 同乘以(m2-m1)/d
        k1*=(m2-m1)/d;
        //k1= k1+k1*(a2/d) 把k1化为满足条件的最小整数
        ll t= a2/d;
        //k1%t ∈ (-t,t) 
        k1 = (k1%t+t)%t;
        
        //更新m1 和a1 ->存储的答案
        m1 = k1*a1+m1;
        a1=abs(a1*a2/d);//a1更新为a1与a2 的的最小公倍数 为正数
    }
    if(has_answer){
        //x≡m1(mod a1) -> x=k1*a1+m1 k1∈Z
        cout<<(m1%a1+a1)%a1<<endl;
    }
    else{
        puts("-1");
    }
}

x=k1a1+m1
=(k1+k(a2/d))a1+m1
=a1k1+m1+k[a1,a2] a1与a2的最小公倍数 a1a2/d
∴m1 = k1a1+m1; a1=abs(a1*a2/d);

高斯消元

解的判断

① 完美阶梯型 唯一解
② 0=bn (bn!=0)无解
③ 0=0有无穷解

步骤

枚举每一列的 c
① 从第r列中 找到绝对值最大的一行
② 将该行换到最上面
③ 将该行第一个数变成1
④ 将下面所有行的第c列消成0

1

组合计数

数学公式: C(b,a)=a!/(b!*(a-b)!);
证明: 0!=1;
(n+1)!=(n+1)*n! 当n==0时
n!=1 证得

I 递推的方式:

a,b∈[1,2000]
C(b,a)=C(b,a-1)+C(b-1,a-1);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//时间复杂度O(N^2)
const int N=2010,mod=1e9+7;
void init(){
    for(int i=0;i<N;i++){
        for(int j=0;j<n;j++){
            if(!j){//从i中选0个 为1种情况
                a[i][j]=1;
            }
            else{
                a[i][j]=a[i-1][j]+a[i-1][j-1];
            }
        }
    }
}
init();
cout<<c[a][b]<<endl;//O(1)的时间查询

II 预处理出阶乘和阶乘的逆元:

a,b∈[1,1e5] n∈[1,1e5]
数学公式: C(b,a)=a!/(b!*(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
//时间复杂度O(Nlog N)
typedef long long ll;
const int N=1e5+10,mod=1e9+7;
int fact[N],infact[N];
int qmi(ll a,ll k,ll p){
    int res=1;
    while(k){
        if(k&1){
            res=(ll)res*a%p;
        }
        k>>=1;
        a=(ll)a*a%p;
    }
    return res;
}
int main(){
    //0!=1;
    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;cin>>n;
    while(n--){
        ll a,b;cin>>a>>b;
        cout<<(ll)fact[a]*infact[b]%mod*infact[a-b]%mod<<endl;
    }
}

lucas定理

给定 n 组询问,每组询问给定三个整数 a,b,p,其中 p 是质数,请你输出 C(b,a)mod p 的值。
a,b∈[1,1e18]
p∈[1，1e5]
a,b对p取模
C(b,a)=C(b%p,a%p)*C(b/p,a/p) (mod 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
33
34
35
36
37
int p;
int qmi(int a,int k){
    int res=1;
    while(k){
        if(k&1){
            res=(ll)res*a%p;
        }
        k>>=1;
        a=(ll)a*a%p;
    }
    return res;
}
int C(int a,int b){
    //定义法
    int res=1;
    for(int i=b,j=1;i>=1;i--,j++){
        res=(ll)res*j%p;
        res=(ll)res*qmi(i,p-2,p)%p;
    }
    return res;

}
int lucas(ll a,ll b){
    if(a<p&&b<p){
        return C(a,b);
    }
    else{
        return (ll)C(a%p,b%p)+lucas(a/p,b/p);
    }
}
int main(){
    int n;cin>>n;
    while(n--){
        ll a,b;cin>>a>>b;
        cout<<lucas(a,b)<<endl;
    }
}

高精度乘法 (不求模)

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
//线性筛
bool st[N];
int primes[N];
int cnt;
void get_primes(int n){
    for(int i=2;i<=n;i++){
        //如果i是质数
        if(!st[i]){
            primes[cnt++]=i;
        }
        //用i去筛选i的倍数
        for(int j=0;primes[j]<=n/i;j++){
            st[primes[j]*i]=true;
            if(i%primes[j]==0){
                break;
            }
        }
    }
}
//指数 
int sum[N];//存储primes[i]对应的指数
int get(int n,int p){
    int res=0;
    while(n){
        res+=rn/p;
        n/=p;
    }
    return res;
}
vector<int> mul(vector<int> a,int b){
    vector<int> c;
    int t;
    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,int b;
    cin>>a>>b;
    //默认a大 求a质数表示的底数
    get_primes(a);

    //从1到a的质数线性筛选出primes[i]的指数
    for(int i=0;i<cnt;i++){
        int p=primes[i];
        sum[i]=get(a,p)-get(b,p)-get(a-b,p);
    }

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

    for(int i=0;i<cnt;i++){
        //sum里面是乘的次数
        for(int j=0;j<sum[i];j++){
            res=mul(res,primes[i]);
        }
    }
    //输出
    for(int i=res.size()-1;i>=0;i--){
        cout<<res[i];
    }

    return 0;
}

卡特兰数

给定 n 个 0 和 n 个, 它们将按照某种顺序排成长度为 2n 的序列, 求它们能排列成的所有序列中, 能够满足任意前缀序列中 0 的个数都不少于 1 的个数的序列有多少个.

输出的答案对 1e9+7 取模
1≤n≤10^5

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
//答案为 C(n,2*n)-C(n-1,2*n) -> C(n,2*n)/(n+1)
//求n+1 %mod的逆元 fact[2*n] infact[n]  
typedef long long ll;
const int mod=1e9+7,N=2e5+10;//fact[]的访问到2*n
int fact[N],infact[N];
//快速幂 求逆元
int qmi(int a,int k,int p){
    int res=1;//初始化为1 a^k %p
    while(k){
        if(k&1){
            res=(ll)res*a%p;
        }
        k>>=1;
        a=(ll)a*a%p;
    }
    return res;
}
int main(){
    int n;cin>>n;
    //初始化边界 0!=1 1/(0!)=1
    fact[0]=infact[0]=1;
    //预处理出N
    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;
    }
    //输出
    cout<<(ll)fact[2*n]*infact[n]%mod*infact[n]%mod*qmi(n+1,mod-2,mod)%mod;
}

容斥原理

给定一个整数 n 和 m 个不同的质数 p1 p2 …pm
请你求出 1∼n 中能被 p1 p2 …pm 中的至少一个数整除的整数有多少个.

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
typedef long long ll;
const int N=20;
int p[N];//储存质数
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;cin>>n>>m;
    for(int i=0;i<m;i++)cin>>p[i];
    int ans=0;//储存答案
    for(int i=1;i<1<<m;i++){
        int t=1;//质数的乘积
        int cnt=0;//2进制中1的个数 即取出的集合个数
        for(int j=0;j<m;j++){//遍历质数
            if(i>>j&1){
                cnt++;
                if((ll)t*p[j]>n){
                    t=-1;//不能选出
                    break;
                }
                t*=p[j];
            }
        } 
        if(t!=-1){
            if(cnt%2){//奇数
                ans+=n/t;
            }
            else{
                ans-=n/t;
            }
        }
    }
    // n/t -> n是p的倍数 集合为1p 2p 3p...np
    // n不是p的倍数 1p 2p ...(n/p)p 
    cout<<ans<<endl;
    return 0;
}

简单博弈论

Mex运算

设S表示一个非负整数集合.定义mex(S)为求出不属于集合S的最小非负整数运算,即:
mes(S)=min{x};
例如:S={0,1,2,4},那么mes(S)=3;

1
2
3
4
5
6
7
//实现
for(int i=0;;i++){
    if(!S.count(i)){
        f[x]=i;
        return f[x];
    }
}

SG函数

在有向图游戏中,对于每个节点x,设从x出发共有k条有向边,分别到达节点y1,y2,····yk,定义SG(x)的后记节点y1,y2,····
yk的SG函数值构成的集合在执行mex运算的结果,即:
SG(x)=mex({SG(y1),SG(y2)····SG(yk)})
特别地,整个有向图游戏G的SG函数值被定义为有向图游戏起点s的SG函数值,即 SG(G)=SG(s).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int f[M],s[N];//s存储的是可供选择的集合,f存储的是所有可能出现过的情况的sg值
int sg(int x){
    if(f[x]!=-1) return f[x];
    //因为取石子数目的集合是已经确定了的,所以每个数的sg值也都是确定的,如果存储过了,直接返回即可
    unordered_set<int> S;
    //有序集合,在函数内部定义,下一次递归中的S不与本次相同
    for(int i=0;i<m;i++){
        int sum=s[i];
        if(x>=sum) S.insert(sg(x-sum));
        //先延伸到终点的sg值后,再从后往前排查出所有数的sg值
    }

    for(int i=0;;i++) if(!S.count(i)) 
    return f[x]=i;
}

Veröffentlicht am Bearbeitet am

二分图:
将点集分为两部分 边只存在于两个集合之间
当且仅当 不存在奇数环

染色法 O(n+m)

因不存在奇数环 故染色过程中没有矛盾

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
//邻接表存储 无向图存储两边
const int N=1e5+5,M=2e5+10;
int h[N],e[M],ne[M],idx;
void add(int a,int b){
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;
}
int color[N];
int a,b;
int n,m;
bool dfs(int u,int c){
    color[u]=c;
    for(int i=h[u];i!=-1;i=ne[i]){
        int j=e[i];
        if(!color[j]){
            if(!dfs(j,3-c)){
                return false;
            }
        }
        else if(color[j]==c){
            return false;
        }
    }
    return true;
}
int main(){
    memset(h,-1,sizeof(h));
    cin>>n>>m;
    while(m--){
        cin>>a>>b;
        add(a,b);
        add(b,a);
    }
    //开始染色
    bool flag=true;
    for(int i=1;i<=n;i++){
        if(!color[i]){
            if(!dfs(i,1)){
                flag=false;
                break;
            }
        }
    }
    if(!flag){
        puts("No");
    }
    else{
        puts("Yes");
    }
    return 0;
}

匈牙利算法 O(m*n)

实际运行时间一般远小于O(m*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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
int n1,n2,m;
const int N=510,M=2e5+10;
int h[N],e[M],ne[M],idx;
int n1,n2,m;
bool st[N];
int match[N];//右侧点在左侧的匹配点
void add(int a,int b){
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;
}
bool find(int x){
    for(int i=h[x];i!=-1;i=ne[i]){
        int j=e[i];
        //判断右侧的点
        if(!st[j]){
            st[j]=true;
            //未匹配or该左侧节点可以匹配另一个右节点
            if(!match[j]||find(match[j])){
                match[j]=x;
                return true;
            }
        }
    }
    return false;
}
int main(){
    memset(h,-1,sizeof(h));
    cin>>n1>>n2>>m;
    while(m--){
        cin>>a>>b;
        add(a,b);
    }
    //匹配成功的对数
    int res=0;
    //遍历左侧的点
    for(int i=1;i<=n1;i++){
        memset(st,false,sizeof(st));
        if(find(i)){
            res++;
        }
    }
    cout<<res<<endl;
    retrurn 0;
}

Veröffentlicht am Bearbeitet am

普利姆算法(prim)

朴素版 稠密图常用 O(n^2)

借助临界矩阵存储g[N][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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
const int INF=0x3f3f3f3f;
int prim(){
    int res=0;//最小生成树的距离
    memset(dist,0x3f,sizeof(dist));

    for(int i=0;i<n;i++){
        int t=-1;
        for(int j=1;j<=n;j++){
            if(!st[j]&&(t==-1||dist[t]>dist[j]){
                t=j;
            }
        }
        //不是第一个点且到集合的距离为INF 说明与集合不相连
        if(i&&dist[t]==INF){
            return INF;
        }
        if(i){
            res+=dist[t];
        }
        //拓展其他节点到集合的距离
        for(int j=1;j<=n;j++){
            dist[j]=min(dist[j],g[t][j]);
        }
        st[t]=true;//将该点加入集合
    }
    return res;
}
int main(){
    memset(g,0x3f,sizeof(g));
    cin>n>>m;
    while(m--){
        cin>>a>>b>>c;
        g[a][b]=g[b][a]=min(g[a][b],c);
    }
    int t=prim();
    if(prim==INF){
        cout<<"impossible<<endl;
    }
    else{
        cout<<t<<endl;
    }
    return 0;
}

堆优化版O(m*logn)

不常用

克鲁斯卡尔算法(Kruskal)

稀疏图常用 O(m*logm)

①将所有边按权重从小到大排序O(m*logn)
②枚举每条边a b和权重c
if(a b不连通){
将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
//排序
struct Edge{
    int a,b,w;
    bool operator<(const Edge &W){
        return w<W.w;
    }
}edges[N];

sort(edges,edges+m);

//并查集初始化
for(int i=1;i<=n;i++){
    p[i]=i;
}
int find(int x){
    if(p[x]!=x){
        p[x]=find(f[x]);
    }
    return p[x];
}

//枚举每条边
int res=0,cnt=0;
for(int i=0;i<m;i++){
    int a=edges[i].a,b=edges[i].b,w=edges[i].w;
    a=find(a),b=find(b);
    if(a!=b){
        f[a]=b;
        res+=w;
        cnt++;
    }
}
//输出
if(cnt!=n-1){//n个节点的最小生成树 有n-1条边
    puts("impossible);
}
else{
    cout<<res<<endl;
}

Veröffentlicht am Bearbeitet am

不用while, for, do-while等关键词实现循环

整数求和

输入样例：
10
1 2 3 4 5 6 7 8 9 10
输出样例:
55

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<iostream>
using namespace std;
int n,t,sum;//全局变量 
void circle(int i){
	cin>>t;
	sum+=t;
	if(i==n){
		cout<<sum<<endl;
		return;
	}
	circle(i+1);
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);

	cin>>n;
	circle(1);//递归模拟 for(int i=1;i<=n;i++)
	return 0;
}

分解出整数n 中第k个数

输入样例：
31859 3
输出样例:
8

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<iostream>
using namespace std;
const int N=1e5+5;
int k;
char c[N];
void circle(int i){
	scanf("%c",&c[i]);//以字符型输入
	if(c[i]==' '){
		return;
	}
	circle(i+1);
}
int main(){
	circle(1);
	cin>>k;
	cout<<c[k];
	return 0;
}

Veröffentlicht am Bearbeitet am

输入样例：
I love Beijing.
输出样例：
I
love
Beijing.

字符型数组输入

1
2
3
char c[maxn];
cin>>c;
int len=strlen(c);

字符串型输入

1
2
3
string s;
getline(cin,s);
int len=s.size();

主函数

1
2
3
4
5
6
7
8
9
10
11
12
for(int i=0;i<len;i++){
		int j=i;
		while(j<len&&s[j]!=' '){
			j++;
		}
        //输出一个单词
		for(int k=i;k<j;k++){
			cout<<s[k];
		}
		puts("");
		i=j+1;
}

Veröffentlicht am Bearbeitet am

.empty();//空返回true 非空返回false

vector

1
2
3
4
5
6
7
8
9
10
11
12
#include<vector>
vector<int> a(n,x);//初始化n个空间为x
for(auto item: a){//遍历容器
    cout<<item<<" ";
}
a.size();//返回大小
a.empty();//判断是否为空
a.clear();//清空
a.front()/a.back()//返回头 尾元素
a.push_back()/a.pop_back()//添加 删除末尾元素
a.begin()//a[0]
a.end()//a[a.size()]

pair

比一般的结构体多实现了比较函数

1
2
3
pair<int,string> p;//把需要排序的一类元素 放到first里面
p.first()/p.second()//返回第一二个元素
pair<int,pair<int,string>>p;//三列的pair

string 字符串

1
2
3
4
5
string s;
s.size()/s/length()//返回字符串的长度
s.substr(n,m);//n起始位置 m是数组的长度 
s.c_str();//返回该字符串的指针常量 与c语言兼容(c语言无法直接输出string类型的变量)
printf("%s",s.c_str());//输出字符串s

queue 队列

1
2
3
4
5
6
7
8
9
#include<queue>
queue<int> q;
q.size();
q.empty();
q.push();//在队尾添加一个元素
q.front();//返回队头元素
q.back();//返回队尾元素
q.pop();//弹出队头元素

虽然没有clear函数 但可以通过构造新队列初始化 如下 

1
2
3
4
queue<int>q;
q=queue<int> ();
//或者
q=queue<int> {};

priority_queue 优先队列 (堆)

1
2
3
4
5
6
7
8
9
10
priority_queue<int>q;//定义默认是 大根堆(堆顶是最大的元素)
q.push();//插入元素到堆末(并进行排序)
q.top();//返回堆顶的值
q.pop();//弹出堆顶的值
priority_queue<int,vector<int>,greater<int>>q;//定义 小根堆(堆顶是最小的元素)

//小根堆的遍历方式 与大根堆的遍历方式略有不同
for(auto item:(vector<int>&)q){
    cout<<item<<" ";
}

如果是大根堆的话 定义结构体需要重载小于号

1
2
3
4
5
6
7
8
struct node{
    int a,b;
    bool operator < (const node& t) const {
        return a < t.a;
    }
};
priority_queue<node>q;
q.push({1,2});

如果是大根堆的话 定义结构体需要重载大于号

1
2
3
4
5
6
7
struct node{
    int a,b;
    bool operator > (const node& t) const{
        return a>t.a;
    }
};
priority_queue<node,vector<node>,greater<node>> q;

栈 stack

1
2
3
4
5
6
7
#include<stack>
stack<int>stk;
stk.size();//返回大小
stk.empty();//判断是否为空
stk.push();//向栈顶添加元素
stk.top();//返回栈顶的值
stk.pop();//弹出栈顶

deque 双端队列

速度比一般的数组慢上几倍

1
2
3
4
5
6
7
8
#include<deque>//双端队列具有清楚的功能
deque<int>q;
q.front();//返回队列头
q.back();//返回队列尾
q.push_front()/q.push_back()//向队列的头 尾插入元素
q.size();//返回队列的大小
q.clear();//清除双端队列
q.begin()/q.end();//支持迭代器

set/multiset map/multimap 基于平衡二叉树(红黑树) 动态维护有序序列

支持以下操作

1
2
size(),empty(),clear() 
begin(),end(); ++ -- 返回前驱和后继(前一个迭代器) 时间复杂度为o(logn)

set/multiset

set容器中元素不能重复而multiset可以

1
2
3
4
5
6
7
insert();//插入一个数
find();//查询一个数
count();//返回某一个数的个数
erase();//①输入一个数x 删除所有x O(k+logn)
        //②输入一个迭代器 删除这个迭代器
lower_bound();//返回第一个不小于x的数字
upper_bound();//返回第一个不大于x的数字

map/multimap

1
2
3
4
5
6
7
map<PII,int>mp;
mp.insert({a,b});//添加数对a->b
insert();//插入一个pair
erase();//输入的是一个pari或者是迭代器
find();
支持[]
lower_bound()/upper_bound()

无序容器 (哈希容器(也叫散列表))

unordered_set unordered_map unordered_multiset unordered_multimap

和上面操作类似 

1
2
优点: 增删改查的时间复杂度为O(1),set map容器的时间复杂度为O(logn)基于红黑树的高度
缺点: 不支持lower_bound()和upper_bound()操作   也不支持迭代器的++ --

bitset 压位运算

& 按位与 : 如果对应位都为1,那么结果就是1;如果任意一个位是0,则结果就是0
| 按位或 : 与& 的区别在于 如果对应位中任一个操作数为1 那么结果就是1(不需要两个对应位都为1)
~ 取反 : 对位求反 1变0, 0变1
^ 按位异或 : 跟 | 类似, 但有一点不同的是 如果两个操作位都为1的话，结果产生0
<<左移 >>右移
== !=
[]

1
2
3
4
5
6
7
8
9
10
11
12
bitset<N> bst;//N必须是一个整型常数
count();//返回有多少个1

any();//判断是否至少有一个1
none();//判断是否全为0

set();;//所有位置成1
set(k,v);//讲第k位变成v
reset();//把所有位置变为0

flip();//取反 等价于~
flip(k);//把第k位取反

Veröffentlicht am Bearbeitet am

头文件<string.h>

1
strcmp(str1,str2);

比较两个字符串,如果两个字符串相等,则返回0.
若str1大于str2(比较第一个不相等的字符的ASCII码)返回一个正数(不一定是1)
若str1小于str2(比较第一个不相等的字符的ASCII码)返回一个负数(不一定是-1)

1
strncmp(str1,str2,n);

比较两个字符串的前n个字符,其他与strcmp同理

1
stricmp(str1,str2);

忽略两个字符串中的大小写,即对大小写不敏感.

Veröffentlicht am Bearbeitet am

头文件<math.h>

原型

1
double ceil(double x)

调用

1
2
int x;
cout<<ceil(x*1.0);

function:返回大于或等于 x 的最小的整数值.
warning:当-1< x < 0 返回值是 -0

Veröffentlicht am Bearbeitet am

dijkstra 所有边权都是正数

朴素版 O(n^2)

n:节点个数
m:边的个数

n^2~m (同一数量级)
稠密图: 用邻接矩阵存储d[t][j]表示从t到j的权重

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 g[N][N];//权重
int dist[N];//到一号点的距离
bool st[N];//表示哪些点的最短距离已经确定
void dijkstra(){
    memset(dist,0x3f,sizeof(dist));
    dist[1]=0;//初始化一号点的距离为0

    for(int i=1;i<=n;i++){
        int t=-1;
        for(int j=1;j<=n;j++){
            if(!st[j]&&(dist[t]>dist[j||t==-1])){
                t=j;
            }
        }

        st[t]=true;//最短距离已经确定

        for(int j=1;j<=n;j++){
            if(dist[j]>dist[t]+g[t][j]){
                dist[j]=dist[t]+g[t][j];
            }
        }
    }
}
int main(){
    cin>>n>>m;
    memset(g,0x3f,sizeof(g));
    //读入的时候 存在重边 和自环
    while(m--){
        cin>>x>>y>>z;
        g[x][y]=min(g[x][y],z);//取长度最短的边
    }
    dijkstra();
    

}

堆优化版O(m*logn)

n~m (同一数量级)
稀疏图: 用邻接表存储

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
#include<iostream>
#include<queue>
#include<string.h>
using namespace std;
int h[N],e[N],ne[N],w[N],idx;
int n,m,s;
void add(int a,int b,int c){
    e[idx]=b;
    w[dix]=c;//权重为c
    ne[a]=h[a];
    h[a]=idx++;
}
//拓展 遍历每个节点的出度
void dijkstra(){
    memset(dist,0x3f,sizeof(dist));
    priority_queue<PII,vector<PII>,greater<PII>> heap;
    //PII: distance 序号
    heap.push({0,s});
    dist[s]=0；

    while(heap.size()){
        int t=heap.top();
        heap.pop();

        int distance=t.first,ver=t.second;

        if(st[ver])continue;

        st[ver]=true;

        for(int i=h[ver];i!=-1;i=ne[i]){
            int j=e[i],c=w[i];
            if(dist[j]>distance+c){
                dist[j]=distance+c;
                heap.push({dist[j],j});
            }
        }
    }
    
}
int main(){
    //链表初始化
    memset(h,-1,sizeof(-1));
    
    cin>>n>>m>>s;
    int a,b,c;
    while(m--){
        cin>>a>>b>>c;
        add(a,b,c);
    }
    dijkstra();

    for(int i=1;i<=n;i++){
        cout<<dist[i]<<" ";
    }

    return 0;
}

Bellman_Ford

利用结构体存储 O(n*m)

松弛操作
两层循环

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
//N为最大节点的个数
int n,m,a,b,w;
int dist[N];//存储到第一节点的距离
int backup[N];
struct Egde{
    int a,int b,int w;
}edges[M];//M为最大边数
void bellman_ford(){
    memset(dist,-1,sizeof(dist));
    for(int i=0;i<k;i++){//题干中最大步数k
        memcpy(backup,dist,sizeof(dist));
        for(int j=1;j<=m;j++){//开始拓展
            int a=edges[j].a,b=edges[j].b,w=edges[j].w;
            dist[b]=min(dist[b],backup[a]+w);       
        }
    }
}
//主函数
cin>>n>>m>>k;
for(int i=0;i<m;i++){
    cin>>a>>b>>w;
    edges[i]={a,b,w};
}
bellman_ford();
if(dist[n]>0x3f3f3f3f/2){//为什么不是0x3f3f3f3f3f呢
    //存在负权时 (+∞-w)<+∞ dist[]的值可能会被更新为比+∞小一点的数
    cout<<"impossible"<<endl;
}
else{
    cout<<dist[n];
}

目的是实现三角不等式即

1
dist[b]<=dist[a]+w;

SPFA

利用BFS优化松弛操作 O(m)~O(n*m)

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
const int N=1e5+5;
int e[N],ne[N],w[N],h[N],idx;
int add(int a,int b,int c){
    e[idx]=b;
    w[idx]=c;
    ne[idx]=h[a];
    h[a]=idx++;
}
void spfa(){
    memset(dist,0x3f,sizeof(dist));
    queue<int>q;
    q.push(1);

    dist[1]=0;
    st[1]=true;

    while(q.size()){
        int t=q.front();
        q.pop();

        st[t]=false;

        for(int i=h[t];i!=-1;i=ne[i]){
            int j=ne[i];
            if(dist[j]>dist[t]+w[i]){
                dist[j]=dist[t]+w[i];
                if(!st[j]){
                    q.push(j);
                    st[j]=true;
                }
            }
        }
    }
}
int main(){
    memset(h,-1,sizeof(h));
    //省略输入...

    if(dist[n]==0x3f3f3f3f){
        cout<<"impossible<<ednl;
    }
    else{
        cout<<dist[n]<<endl;
    }
    return 0;
}

可以用来判断是否存在重环和自环

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void spfa(){
    queue<int>q;
    for(int i=1;i<=n;i++){
        q.push(i);
        st[i]=true;
    }

    while(q.size()){
        int t=q.front();
        q.pop();

        st[t]=false;
    }
    return false;
}

Floyd

邻接矩阵存储 不能出现负权回路 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
42
43
44
45
46
47
48
const int INF=1e9;
int n,m,k;//n是节点的个数 m是边数
int a,b,w;
int g[N][N];
void floyd(){
    for(int k=1;k<=n;k++){//寻找i和j之间的节点 且满足经过k的路径更短
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                g[i][j]=min(g[i][j],g[i][k]+g[k][j]);
            }
        }
    }
}
int main(){
    //初始化
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(i==j){
                g[i][j]=0;
            }
            else{
                g[i][j]=INF;
            }
        }
    }
    //输入操作

    while(m--){
        cin>>a>>b>>w;
        //重边保留边权最小的
        g[a][b]=min(g[a][b],w);
    }

    floyd();
    //处理数据
    while(k--){
        cin>>a>>b;
        //出现负权边 可能更新距离后比INF略小
        if(g[a][b]>=INF/2){
            cout<<"impossible"<<endl;
        }
        else{
            cout<<g[a][b]<<endl;
        }
    }
    return 0;
}

Veröffentlicht am Bearbeitet am

单链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int e[maxn],ne[maxn];
//e指的是当前节点的值 而ne指的是当前节点的下一个节点的指针
int head,idx;
//head表示头节点的下标 而idx是当前节已经用到了那个点
void init(){
	head=-1;
	idx=0;
}//初始化
void add_to_head(int x){
	e[idx]=x;
	ne[idx]=head;
	head=idx;
	idx++;
}//在头节点插入值为x的节点
void add(int k,int x){
	e[idx]=x;
	ne[idx]=ne[k];
	ne[k]=idx;
	idx++;
}//在第k个节点的后面插入值为x的节点
void remove(int k){
	ne[k]=ne[ne[k]];
}//删去第k个节点

双链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int idx;
int e[maxn],l[maxn],r[maxn];//e是当前节点的值 l是上一节点的指针 r是下一节点的指针
void init(){//初始化
	r[0]=1;//左边界
	l[1]=0;//右边界
	idx=2;//0 1 两个节点已经被使用

}
void add(int k,int x){//在第k个节点后插入值为x的节点
	e[idx]=x;
	r[idx]=r[k];
	l[idx]=k;

	l[r[k]]=idx;
	r[k]=idx;
	idx++;
}//若实现在第k个节点的前面插入 相当于在第k个节点前面的节点后面插入值为x的节点
void del(int k){//删除第k个节点
	r[l[k]]=r[k];
	l[r[k]]=l[k;]
}

调用函数

1
2
add(r[0],x);//在链表的最左端插入值为x的节点 
add(l[1],x);//在链表的最右端插入值为x的节点

模拟栈

栈顶插入 栈顶弹出 判断是否为空 查询栈顶元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int stk[maxn];
int tt=0;
void push(int x){
	stk[++tt]=x;
}
void pop(){
	--tt;
}
bool empty(){
	return tt>0?false:true;
}
int query(){
	return stk[tt];
}

模拟队列

队尾插入 队头弹出 判断是否为空 查询队头元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int q[maxn];
int tt=-1,hh=0;
void push(int x){
	q[++tt]=x;
}
void pop(){
	hh++;
}
bool empty(){
	return hh>tt?false:true;
}
int query(){
	return q[hh];
}

单调栈

输出左侧第一个比当前数字小的数 没有输出-1

1
2
3
4
const int maxn=1e5+10;
int stk[maxn];
int tt=0;
int n,x;

主函数

1
2
3
4
5
6
7
8
9
10
11
12
13
for(int i=0;i<n;i++){
		cin>>x;
		while(tt&&stk[tt]>=x){//栈不空且栈顶比不比x小
			tt- -;//栈顶出栈
		}
		if(tt){
			cout<<stk[tt]<<" ";
		}
		else{
			cout<<"-1 ";
		}
		stk[++tt]=x;//x入栈
	}

单调队列

有一个大小为 k 的滑动窗口,它从数组的最左边移动到最右边且每次向右移动一个位置,分别输出窗口的最大值和最小值.
初始化并读入到a[]中

1
2
3
4
5
6
7
const int maxn=1e6+10;
int a[maxn],q[maxn];
int tt=-1,hh=0;

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

求最小值

1
2
3
4
5
6
7
8
9
10
11
12
for(int i=0;i<n;i++){//i指向窗口的末端
    	if(hh<=tt&&i-q[hh]+1>k){//队列不为空且滑动窗口的大小>k
    		hh++;
		}
    	while(hh<=tt&&a[q[tt]]>=a[i]){
    		tt--;
		}
		q[++tt]=i;
		if(i>=k-1){
			cout<<a[q[hh]]<<" ";
		}
    }

求最大值

1
2
3
4
5
6
7
8
9
10
11
12
for(int i=0;i<n;i++){//i指向窗口的末端
    	if(hh<=tt&&i-q[hh]+1>k){//队列不为空且滑动窗口的大小>k
    		hh++;
		}
    	while(hh<=tt&&a[q[tt]]<=a[i]){
    		tt--;
		}
		q[++tt]=i;
		if(i>=k-1){
			cout<<a[q[hh]]<<" ";
		}
    }

KMP字符串匹配

初始化并输入

1
2
3
4
5
6
const int N=1e5+10,M=1e6+10;
char p[N],s[M];//p是子串 s是母串 
int ne[N];//next
int n,m;

cin>>n>>p+1>>m>>s+1;

求next[]

1
2
3
4
5
6
7
8
9
10
ne[1]=0;
for(int i=2,j=0;p[i];i++){
	while(j&&p[i]!=p[j+1]){
		j=ne[j];
	}
	if(p[i]==p[j+1]){
		j++;
	}
	ne[i]=j;
}

KMP算法

1
2
3
4
5
6
7
8
9
10
11
12
for(int i=1,j=0;s[i];i++){
		while(j&&s[i]!=p[j+1]){
			j=ne[j];
		}
		if(s[i]==p[j+1]){
			j++;
		}
		if(j==n){//匹配成功时 i在字符串s上对应串p的末尾 
			cout<<i-n<<" ";//输出的是数组的初位置 不需要+1
			j=ne[j];
		}
	}

Trie字符串统计

I x 向集合中插入一个字符串 x
Q x 询问一个字符串在集合中出现了多少次
初始化

1
2
3
4
const int maxn=1e5+10;
int son[maxn][26],cnt[maxn];//son[]子节点 cnt[]统计一个串出现了多少次
int idx=0;//表示用到了第几个节点
char op[2];//操作符的读入

插入操作

1
2
3
4
5
6
7
8
9
10
11
void insert(char str[]){
	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]++;//计算串的出现次数
}

查找操作

1
2
3
4
5
6
7
8
9
10
int query(char str[]){
	int p=0;
	for(int i=0;str[i];i++){
		int u=str[i]-'a';
		if(!son[p][u]){
			return 0;//找不到子节点直接返回0
		}
	}
	return cnt[p];
}

主函数

1
2
3
4
5
6
7
8
9
10
11
int n;
cin>>n;
while(n--){
	cin>>op>>str;
	if(op[0]=='I'){
		insert(str);
	}
	if(op[0]=='Q'){
		cout<<query(str)<<endl;
	}
}

并查集

①讲两个集合合并
②询问两个集合是否在一个集合当中

基本原理:每个集合用一棵树来表示.树根的标号就是整个集合的编号.每个节点存储它的父节点.p[x]表示 x 的父节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//初始化
for(int i=1;i<=n;i++){
	fa[i]=i;//让i的父节点指向i
}
//判断树根
if(p[x]==x){

}
//求x的集合编号
while(p[x]!=x){
	x=p[x];
}
//路程压缩优化
int find(int x){//查询x的属于哪个集合 (返回x的根节点)
	if(p[x]!=x){
		p[x]=find(p[x]);//路径压缩 路径上所有的点都指向树根
	}
	return p[x];
}
//合并两个集合 px是a的集合编号 py是b的集合编号
px=find(x);
py=find(y);
p[px]=py;//让a的根节点的父节点指向b的根节点

模拟堆

① I x 插入一个数 x;
② PM 输出当前集合中的最小值;(输出堆顶 h[1])
③ DM 删除当前集合中的最小值(数据保证此时的最小值唯一);
④ D k 删除第 k 个插入的数;
⑤ C k x 修改第 k 个插入的数,将其变为 x;

预处理

1
2
3
4
5
6
7
int n;
int siz;//堆的末尾
int m;//记录使用节点个数
int k,x;//输入第k个插入的数字 x存储这个数字
int h[N];//存储节点
int ph[N],hp[N];//ph指向第i个插入的数的下标x 插入序数映射到堆的下标 
//hp指向下标是x的数是第i个插入的数 由堆的下标映射到插入序数
1
2
3
4
5
void heap_swap(int a,int b){//堆排列特有的交换方式
	swap(ph[hp[a]],ph[hp[b]]);
	swap(hp[a],hp[b]);
	swap(h[a],h[b]);
}

两个堆的排序函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void down(int u){//u是节点的序号 寻找三个节点中最小的节点
	int t=u;
	if(u*2<=siz&&h[u*2]>h[t]){//未出界 且满足比子节点大 
		t=u*2;
	}
	if(u*2+1<=siz&&h[u*2+1]>h[t]){
		t=u*2+1;
	}
	if(t!=u){
		heap_swap(u,t);
		down(t);
		
	}
	return;
}
void up(int u){//交换比u大的父节点
	while(u/2>=1&&h[u/2]>h[u]){
		heap_swap(u,u/2);
		u/=2;
	}
	return;
}

操作实现

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
if(!strcmp(op,"I")){//插入数x
	cin>>x;
	m++;siz++;
	ph[m]=siz;hp[siz]=m;
	h[siz]=x;
	up(siz);
}
else if(!strcmp(op,"DM")){//删除堆顶
	heap_swap(1,siz);
	siz--;
	up(1);
	down(1);
}
else if(!strcmp(op,"D")){//删除第K的插入的数字
	cin>>k;
	k=ph[k];//在交换的过程中ph[k]会变化 预先存储到k上
	heap_swap(k,siz);
	siz--;
	up(k);
	down(k);
}
else if(!strcmp(op,"C")){//将第k个插入的数改变成x
	cin>>k>>x;
	k=ph[k];//同理
	h[k]=x;
	up(k);
	down(k);

}

哈希表

开放寻址法(蹲坑法)

1
2
3
const int null=0x3f3f3f3f;//极大值1061109567与INT_MAX同一数量级 且不会溢出
const int N=2e5+3;
int h[N];
1
2
3
4
5
6
7
8
9
10
int find(int x){//哈希表特有的搜索函数
	int k=(x%N+N)%N;
	while(h[k]!=null&&h[k]!=x){
		k++;
		if(k==N){//搜到了最后一个槽也是满的 让k回到头节点
			k=0;
		}
	}
	return k;//返回x在哈希表中的位置 若不存在返回null
}
1
2
3
4
5
6
7
8
9
10
11
12
memset(h,0x3f,sizeof(h));
//插入x操作
int k=find(x);
h[k]=x;
//查询x操作
int k=find(x);
if(h[k]!=null){
	puts("Yes");
}
else{
	puts("No");
}

拉链法

1
2
3
const int N=2e5+3;
int h[N];
int e[N],ne[N],idx;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void insert(int x){
	int k=(x%N+N)%N;//负数取模还是负数 会导致数组越界 (+N)%N 避免这一问题
	e[idx]=x;
	ne[idx]=k;
	h[k]=idx;
	idx++;
}
bool find(int x){
	int k=(x%N+N)%N;
	for(int i=h[k];i!=-1;i=ne[i]){
		if(e[k]==x){
			return true;
		}
	}
	return false;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
memset(h,-1,sizeof(h));//-1表示链表的末尾
if(*op=='I'){
	cin>>x;
	insert(x);
}
else if(*op=='Q'){
	cin>>x;
	if(find(x)){
		puts("Yes");
	}
	else{
		puts("No");
	}
	}
}

字符串哈希

判断一个字符串的两个子区间是否完全相等

1
2
3
4
5
6
7
typedef unsigned long long ULL;
const int N=1e5+5,Q=133;
char str[N];//存储字符串
ULL p[N];//对Q进行预处理
ULL h[N];
int n,m;//n是字符串的长度 m是操作次数
int l1,r1,l2,r2,
1
2
3
ULL get(int l,int r){
	return h[r]-h[l-1]*p[r-l+1];//前缀和计算
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//预处理
cin>>n>>m;
p[0]=1;
for(int i=1;i<=n;i++){
	p[i]=p[i-1]*Q;
	h[i]=h[i-1]*Q+str[i];
}
while(m--){
	cin>>l1>>r1>>l2>>r2;
	if(get(l1,r1)==get(l2,r2)){
		puts("Yes");
	}
	else{
		puts("No");
	}
}