zhangas

Pay more attention

0%

Posted on Edited on

CF836div2

T2:给定数字n 构造数列a1…an s.t.
a1^a2^…^an=(a1+a2+…+an)/n &&(ai>=1)
intput:
3
1
4
3
output:
69
13 2 8 1
7 7 7

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
性质 a为偶数的时候a^1==a+1 a为奇数的时候 a^1==a-1
a^a=0 0^a=a 
so: 当n为奇数的时候 n个1满足条件 1^1^1==1 (1+1+1)/3=1成立
当n为偶数的时候 1^3==2 (1+3)/2==2 只需让其余的全为2即可
void solve(){
    int t=read();while(t--){
        int n=read();
        if(t%2){
            for(int i=0;i<n;i++){
                cout<<"1 ";
            }
        }
        else{
            cout<<"1 3 ";
            for(int i=0;i<n-2;i++){
                cout<<"2 ";
            }
        }
        puts("");
    }
}

T4 构造严格递增数列满足 max(a1,a2,a3…an)-min(a1,a2,a3…an)=√a1+a2+…+an

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
假定每个数为4n 那么 a1+a2+...+an==4n^2 √a1+a2+...+an==2n
设最大值为x最小值为y x+y=8n x-y=2n -> x=5n y=3n 
如果输入的n是奇数 中间的数为4n 向左为4n-1 4n-2... 向右为4n+1 4n+2...
void solve(){
    int t=read();while(t--){
        int n=read();
        cout<<3*n<<" ";
        int t=4*n-n/2+1;
        for(int i=0;i<n/2-1;i++){
            cout<<t<<" ";
            t++;
        }
        if(n%2)cout<<4*n<<" ";
        t=4n+1;
        for(int i=0;i<n/2-1;i++){
            cout<<t<<" ";
            t++;
        }
        cout<<5*n；
        puts("");
    }
}

ABC279

T3 给定两个大小相同A B字符矩阵 问A矩阵可以通过列的交换化成B矩阵吗? 可以的话输出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
将A字符矩阵的每一个列向量存入map中 接着讲B字符矩阵从map中减去
const int N=4e5;
mp<vector<char>,int>mp;
string s[N];
int main(){
    int h=read(),w=read();
    for(int i=0;i<h;i++){
        cin>>s[i];
    }
    for(int j=0;j<w;j++){
        vector<char>v;
        for(int i=0;i<h;i++){
            v.push_back(s[i][j]);
        }
        mp[v]++;
    }
    for(int i=0;i<h;i++){
        cin>>s[i];
    }
    for(int j=0;j<w;j++){
        vector<char>v;
        for(int i=0;i<h;i++){
            v.push_back(s[i][j]);
        }
        mp[v]--;
    }
    //检查是否合法
    for(auto i:mp){
        if(i.second){//不为0
            puts("No");
            return 0;
        }
    }
    puts("Yes");
    return 0;
}

Posted on Edited on

队列模拟

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<queue>
queue<int>ql;
int n=read(),k=read();
for(int i=1;i<=n;i++){
    q.push(i);
}
//开始操作
int now=1;//用来计数 当now == k的时候满足条件 让q.front() 输出并出列
while(q.size()){
    if(now==k){
        cout<<q.front()<<" ";
        q.pop();
        now=1;//初始化
    }
    else{//如果不满足是第k个, 则将队头转移到队尾
        now++;
        q.push(q.front());
        q.pop();
    }
}

公式法

f(10,3)=(f(9,3)+3)%10
∴ 从n中依次删去第k的数子
f(n,k)=(f(n-1,k)+k)%n

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//函数的两种实现方式
int josephus(int n,int k){
    if(n==1)return 0;
    return (josephus(n-1,k)+k)%n;
}
//第二种
int josephus(int n,int k){
    //从底层向上推
    int value=0;//value 即为f(0,k) -> 向上递推到 f(m,k)
    for(int i=1;i<=n;i++){//从n 一直到 1推出答案 共n次
        value=(value+k)%i; //i即使n的变化值
    }
    return value;
}
int n=read(),k=read();
cout<<josephus(n,k)+1<<endl;

Posted on Edited on

背包问题

线性DP

数字三角形

从顶部出发，在每一结点可以选择移动至其左下方的结点或移动至其右下方的结点，一直走到底层，要求找出一条路径，使路径上的数字的和最大。
input:
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
output:
30

1
2
3
4
5
6
7
8
9
10
11
//从下向上DP更新
//f[i][j]=max(f[i+1][j],f[i+1][j+1])+a[i][j];
for(int j=1;j<=n;j++){
    f[n][j]=a[n][j];//将最后一行输入到f数组中
}
for(int i=n-1;i>=1;i--){//从n-1行开始
    for(int j=1;j<=i;j++){
        f[i][j]=max(f[i+1][j],f[i+1][j+1])+a[i][j];
    }
}
cout<<f[1][1];

最长上升子序列

给定一个长度为 N 的数列，求数值严格单调递增的子序列的长度最长是多少。
input:
7
3 1 2 1 8 5 6
output:
1 2 5 6
4

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
vector<int> q;
q.push_back(a[0]);
for(int i=0;i<n;i++){
    if(a[i]>q.back()){
        q.push_back(a[i]);
    }
    else{
        *lower_bound(q.begin(),q.end(),a[i])=a[i];
    }
}
for(auto i:q){
    cout<<i<<" ";
}

cout<<endl<<q.size();

最长公共子序列

给定两个长度分别为 N 和 M 的字符串 A 和 B，求既是 A 的子序列又是 B 的子序列的字符串长度最长是多少。
input：
4 5
acbd
abedc
output：
abd
3

1
2
3
4
5
6
7
8
9
10
11
12
13
//f[i][j]表示A的前i个于B的前j个的最长公共子序列
//f[i][j]=max(f[i-1][j-1]AB都不选,f[i][j-1]A选B不选,f[i-1][j]A不选B选,f[i-1][j-1]+1AB都选)
const int N=1005;
char a[N],b[N];
int f[N][N];
int n=read(),m=read();
scanf("%s,a+1);scanf("%s,b+1);
for(int i=1;i<=n;++i){
    for(int j=1;j<=m;j++){
        f[i][j]=max(f[i-1][j],f[i][j-1]);
        if(a[i]==b[j]) f[i][j]=max(f[i][j],f[i-1][j-1]+1);
    }
}

区间DP

石子合并

设有 N 堆石子排成一排，其编号为 1，2，3，…N。

每堆石子有一定的质量，可以用一个整数来描述，现在要将这 N 堆石子合并成为一堆。

每次只能合并相邻的两堆，合并的代价为这两堆石子的质量之和，合并后与这两堆石子相邻的石子将和新堆相邻，合并时由于选择的顺序不同，合并的总代价也不相同。
input：
4
1 3 5 2
output：
22
假设f[i][j]表示从第i个到第j个合并所付出的最小的代价 f[1][n]即为答案 

1
2


Posted on Edited on

整数转string

1
string str = to_string(*val);

and support int, LL, ULL, double types

进制转换

1
2
3
4
5
6
7
十进制转十六进制
char c[30];
sprintf(c,"%x",num);
cout<<c;
十进制转八进制
sprintf(c,"%o",num);
cout<<c;

factorial n.阶乘
inversion n.倒置,反转 (逆元)
fact[]表示阶乘 infact表示阶乘的逆元

回文串

输入字符串s 判断是否是回文串

1
2
3
4
5
6
7
8
9
10
11
12
13
scanf("%s",&c);
int l=strlen(c);
	int f=0;
	for(int i=0, j=l - 1;i<j;i++,j--){
        if(c[i]!=c[j]){
           	f=1;
           	printf("No.\n");
            break;
        }
    }
	if(!f){
		printf("Yes.\n");
	}

计算e

利用公式e=1+1/(1!)+…+1/(n!) 求e的近似值 

1
2
3
4
5
6
7
8
int n;
scanf("%d",&n);
double fn=1.0,sum=1.0;//fn计算阶乘 注意两者都为浮点型
for(int i=1;i<=n;i++){
    fn*=i;
    sum+=1/fn;
}
printf("%.*lf",10,sum);

前导0输出

printf输出数字,位数不够前面补0，适用于输出编号

printf的输出格式%[flags][width][.perc][F|N|h|l]type
用到了flags中的0,将输出的前面补上0,直到占满指定列宽为止

1
2
int a=1;
printf("%03d",a);

output: 001

1
2
3
int a=1;
int n=3; //n表示位数 用 * 代替位数，在后面的参数列表中用变量控制
printf("%0*d",n,a);

output: 001

最小公倍数和最大公约数的计算

借助库函数__gcd()

int、long long类型都可以，需要注意的是两个类型必须要相同，还有不能用浮点型

最大公约数

1
2
3
4
5
6
7
8
9
#include<iostream> 
#include<algorithm>
using namespace std;
int main(){
	int a,b;
	cin>>a>>b;
	cout<<__gcd(a,b);
	return 0;
}

最小公倍数*最大公约数=两数之积

1
cout<<a*b/__gcd(a,b);

Posted on Edited on

数论

质数判断(试除法)

复杂度为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;
}

Posted on Edited on

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

染色法 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;
}

Posted on Edited on

普利姆算法(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;
}

Posted on Edited on

不用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;
}

Posted on Edited on

输入样例：
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;
}

Posted on Edited on

.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位取反