ACM Template（持续更新）

由 Edwiv 发布于  ｜  535,547次浏览
ACM Template下载
ACM-Book下载
ACM-ICPC_Templates_Claris下载
ACM-ICPC_Templates_kuangbin下载

头文件 

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(ll i=(a);i<=(b);++i)
#define dep(i,a,b) for(ll i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)1e5+10;
const int mod=(int)1e9+7;

快读

inline int read(){
    int x=0,flag=0;
    char c=getchar();
    while(!isdigit(c)){
        if(c=='-') flag=1;
        c=getchar();
    }
    while(isdigit(c)){
        x=(x<<3)+(x<<1)+(c^48);
        c=getchar();
    }
    return flag?-x:x;
}
inline void write(ll x){
     if(x<0) putchar('-'),x=-x;
     if(x>9) write(x/10);
     putchar(x%10+'0');
}

string 操作：

s.assign(str); 
s.assign(str,1,3);//如果str是”iamangel” 就是把”ama”赋给字符串
s.assign(str,2,string::npos);//把字符串str从索引值2开始到结尾赋给s
s.assign(“gaint”); 
s.assign(“nico”,5);//把’n’ ‘I’ ‘c’ ‘o’ ‘\0’赋给字符串
s.assign(5,’x’);//把五个x赋给字符串
==,!=,<,<=,>,>=,compare()  //比较字符串
string s(“abcd”);
    s.compare(“abcd”); //返回0
    s.compare(“dcba”); //返回一个小于0的值
    s.compare(“ab”); //返回大于0的值
    s.compare(s); //相等
    s.compare(0,2,s,2,2); //用”ab”和”cd”进行比较 小于零
    s.compare(1,2,”bcx”,2); //用”bc”和”bc”比较。
r) copy() //将某值赋值为一个C_string
s) c_str() //将内容以C_string返回
u) substr() //返回某个子字符串
    s.substr(11);//从索引11往后的子串
    s.substr(5,6);//从索引5开始6个字符
k）find（）
string::size_type position;  
position = s.find("xx");  
//查找s 中flag 出现的所有位置。  
 flag="a";  
position=0;  
while((position=s.find_first_of(flag,position))!=string::npos)  
{  
//position=s.find_first_of(flag,position);  
cout<<"position  : "<<position<<endl;  
position++;  
 }

GCD

int gcd(int x,int y){return y?gcd(y,x%y):x;}

LCM

int lcm(int a,int b) {return a*b/gcd(a,b);  }

扩展欧几里得

int exgcd(int a, int b, int& x, int& y){//a*x+b*y=gcd(a,b)=d;(x,y)为其一组整数解
    int d = a;
    if(b != 0){
        d = exgcd(b, a % b, y, x);
        y -= (a / b) * x;
    }else {
        x = 1;
        y = 0;
    }
    return d;
}

扩欧求乘法逆元

int mod_inverse(int a, int m){ //a*inv%m=1
    int x, y;
    exgcd(a, m, x, y);
    return (m + x % m) % m; //(x+m)%m;
}

费马小定理求INV

a/b=a*b*pow(b,mod-2)%mod;

ll inv(ll b){return qpow(b,mod-2)%mod;}

中国剩余定理CRT

int crt(int a[],int w[],int len){//a[]存放余数  w[]存放两两互质的除数
    int i,d,x,y,m,n,ret;
    ret=0;
    n=1;
    for (i=0;i<len;i++)
        n*=w[i];
    for (i=0;i<len;i++){
        m=n/w[i];
        d=exgcd(w[i],m,x,y);
        ret=(ret+y*m*a[i])%n;
    }
    return (n+ret%n)%n;
}

扩展中国剩余定理

ll m[maxn],a[maxn];//除数，余数
int n;
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;
}
inline ll excrt() {
    ll M=1,A=0;
    for (int i=1;i<=n;i++) {
        ll x,y,d=exgcd(M,m[i],x,y),mm=m[i]/d;
        if ((a[i]-A)%d) {return -1;}
        x=(x%mm+mm)%mm;
        ll k=(ll)((ll)(a[i]-A)/d*x%mm+mm)%mm;
        ll nM=M*mm;
        A=(ll)((A+(ll)k*M)%nM);
        M=nM;
    }
    return A?A:A+M;
}
int main() {
    int T;cin>>T;
    rep(ca,1,T){
        scanf("%d",&n);
        rep(i,1,n) scanf("%lld",&m[i]);
        rep(i,1,n) scanf("%lld",&a[i]);
        printf("Case %d: %lld\n",ca,excrt());
    }
    return 0;
}

欧拉筛

bool check[maxn];//第i个数是否为素数
int prime[maxn],min_prime[maxn];//每个数的最小素因数
int Prime(int n){ //返回n中素数的个数
    memset(check,true,sizeof(check));
    int sum=0;
    for(int i=2;i<=n;i++){
        if(check[i]) prime[sum++]=i;
        for(int j=0;j<sum&&i*prime[j]<=n;j++){
            check[i*prime[j]]=false;
            min_prime[i*prime[j]]=prime[j];
            if(i%prime[j]==0) break;
        }
    } return sum;
}

欧拉筛打表

const int SIZE=3e5;
int pos=0,prime[SIZE];
void f(){
    int check[SIZE] = {0};
    for (int i = 2 ; i < SIZE ; i++){
        if (!check[i])
            prime[pos++] = i;
        for (int j = 0 ; j < pos && i*prime[j] < SIZE ; j++){
            check[i*prime[j]] = 1;
            if (i % prime[j] == 0)
                break;
        }
    }
}

莫比乌斯函数

void init(){
    int N=maxn;
    memset(prime,0,sizeof(prime));
    memset(mu,0,sizeof(mu));
    memset(vis,0,sizeof(vis));
    mu[1] = 1;
    cnt = 0;
    for(int i=2; i<N; i++){
        if(!vis[i]){
            prime[cnt++] = i;
            mu[i] = -1;
        }
        for(int j=0; j<cnt&&i*prime[j]<N; j++){
            vis[i*prime[j]] = 1;
            if(i%prime[j]) mu[i*prime[j]] = -mu[i];
            else{
                mu[i*prime[j]] = 0;
                break;
            }
        }
    }
}

母函数

void work(){
    a[0]=1;
    int last=0;
    rep(i,1,k){
        int last2=bag;
        memset(b,0,sizeof(int)*(last2+1));
        for(int j=0;j*v[i]<=last2;j++) //j=0可换成起始数量，无限个则去掉j<=c[i]
            for(int k=0;k<=last&&k+j*v[i]<=last2;k++)
                b[k+j*v[i]]+=a[k];
        memcpy(a,b,sizeof(int)*(last2+1));
        last=last2;
    }
}

⾼效判素数Miller-Rabin

ll qpow(ll a,ll b,ll M){
    ll ans=1;
    while(b){
        if(b&1){
            ans*=a; ans%=M;
        }
        a*=a;b>>=1;a%=M;
    }
}
ll qmul(ll x,ll y,ll mo){
    ll ret = 0; x%=mo;
    while(y){
        if(y&1) ret = (ret+x)%mo;
        x=(x<<1)%mo; y>>=1;
    }
    return ret;
}
bool MR(ll n,ll a){
    if (n==2) return 1;
    ll d=n-1, t;
    if(d&1) return 0;
    while(~d&1) d>>=1;
    t = qpow(a,d,n);
    while(d!=n-1 && t!=1 && t!=n-1) d<<=1,t=qmul(t,t,n);
    return (t==n-1) || (d&1);
}
bool isp(int n){//int范围
    if(n==1) return 0;
    if(n==2|| n== 7|| n==61) return 1;
    return MR(n,2) && MR(n,7) && MR(n,61);
}
bool isp(ll n){//1e16 (2^54) 范围
    if(n==1|| n==46856248255981LL) return 0;
    if(n==2|| n==3|| n==7|| n==61|| n==24251) return 1;
    return MR(n,2)&& MR(n,3)&& MR(n,7)&& MR(n,61)&& MR(n,24251);
}

⾼效分解质因数pollard-brent

//加上MR判素数
ll PB(ll n,int c=12323,int x0=2){
    if(~n&1) return 2;
    ll x,y,d=1,k=0,i=1;
    x=y=x0;
    while(1){
        x=(qmul(x,x,n)+c)%n; //f(x)=x*x+c，c可换24251或其他素数
        d=gcd(n+x-y,n);
        if(d!=1 && d<n) return d; //如莫名其妙TLE可尝试d<n改成
        d<=n
        if(y==x) return n;
        if(++k == i) y=x,i<<=1;
    }
}
ll s[110];int l=0;
void gn(ll n,int op=12323){
    if(isp(n)) {s[l++]=n;return;}
    ll x=PB(n);
    while(x==n) x=PB(n,--op);
    gn(x);
    gn(n/x);
}

约瑟夫环

int Joseph(int n,int m,int i){//n总人数 ，m报到的数，i第几个出队
    if(i==1)
        return (n+m-1)%n;
    else
        return (Joseph(n-1,m,i-1)+m)%n;
}
int main(){
    scanf(“%d%d”,&n,&m);
    for(int i=1;i<=10;i++)
        printf("第%2d次出环：%2d\n",i,Joseph(n,m,i)+1);
    return 0;
}

简化版约瑟夫

int main(){
    int n, m, i, s = 0,t;
    while(~scanf("%d",&t)){
        while(t--){
            s=0;
            scanf("%d%d", &n,&m); //n人，报到m出列
            for (i = 2; i <= n; i++){
                s = (s + m) % i;
                //printf("%d\n",s+1);
            }
            printf ("%d\n", s+1);
        }
    }
    return 0;
}

数位DP

ll dp[20][20][1800];
int num[20];
ll dfs(int len,int pos,int sum,bool flag){
    if (!len) return sum==0?1:0;
    if (sum<0) return 0;
    if (!flag && dp[len][pos][sum]!=-1) return dp[len][pos][sum];
    int mx=flag?num[len]:9;
    ll res=0;
    for (int i=0;i<=mx;i++) res+=dfs(len-1,pos,sum+i*(len-pos),flag && i==mx);
    if (!flag) dp[len][pos][sum]=res;
    return res;
}
ll solve(ll n){
    if (n<0) return 0;
    int len=0;
    for (;n;n/=10) num[++len]=n%10;
    ll sum=0;
    for (int i=1;i<=len;i++) sum+=dfs(len,i,0,true);
    return sum-(len-1);
}
int main(){
    memset(dp,-1,sizeof(dp));
    int T;
    ll a,b;
    scanf("%d",&T);
    while (T--){
        scanf("%lld%lld",&a,&b);
        printf("%lld\n",solve(b)-solve(a-1));
    }
    return 0;
}

高精度

struct bign{
    int d[1000];
    int len;
    bign(){
        memset(d,0,sizeof(d));
        len=0;
    }
};
bign change(char str[]){
    bign a;
    a.len=strlen(str);
    for(int i=0;i<a.len;i++){
        a.d[i]=str[a.len-i-1]-'0';//这里把大整数的地位切换为高位
    }
    return a;
}
int compare(bign a,bign b){
    if(a.len>b.len)return 1;//a大于b
    else if(a.len<b.len)return -1;//a<b
    else{
        for(int i=a.len-1;i>=0;i--){
            if(a.d[i]>b.d[i])return 1;
            else if(a.d[i]<b.d[i])return -1;
        }
        return 0;//两个数相等
    }
}
bign add(bign a,bign b){
    bign c;
    int carry=0;//这里的carry表示进位
    for(int i=0;i<a.len||i<b.len;i++){
        int temp=a.d[i]+b.d[i]+carry;
        c.d[c.len++]=temp%10;
        carry=temp/10;
    }
    if(carry!=0){
        c.d[c.len++] =carry;
    }
    return c;
}
//如果有一个数字为负数，我们可以使用高精度减法
bign sub(bign a,bign b){
    bign c;
    for(int i=0;i<a.len||i<b.len;i++){
        if(a.d[i]<b.d[i]) {
            if(a.d[i+1]>0){
                
                a.d[i+1]--;
                a.d[i]+=10;
            }
        }
        c.d[c.len++]=a.d[i]-b.d[i];
    }
    while(c.len-1>=1&&c.d[c.len-1]==0){
        c.len--;
    }
    return c;
}
bign multi(bign a,int b){
    bign c;
    int carry=0;
    for(int i=0;i<a.len;i++){
        int temp=a.d[i]*b+carry;
        c.d[c.len++]=temp%10;
        carry=temp/10;
    }
    while(carry!=0){
        c.d[c.len++]=carry%10;
        carry/=10;
    }
    return c;
}
//高精度与低精度的除法
bign divide(bign a,int b,int &r){//r为余数，这里表示为引用
    bign c;
    c.len=a.len;
    for(int i=a.len-1;i>=0;i--){
        r=r*10+a.d[i];
        if(r<b) c.d[i]=0;
        else{
            c.d[i]=r/b;
            r=r%b;
        }
    }
    while(c.len-1>=1&&c.d[c.len-1]==0){
        c.len--;
    }
    return c;
}
void print(bign a){
    for(int i=a.len-1;i>=0;i--){
        printf("%d",a.d[i]);
    }
}
int main(){
    char str1[1000],str2[1000];
    scanf("%s%s",str1,str2);
    bign a=change(str1);
    bign b=change(str2);
    print(add(a,b));
    return 0;
}


struct bign{
    int d[maxn],len;
    void clean(){while(len>1&&!d[len-1]) len--;}
    bign(){ memset(d, 0, sizeof(d)); len = 1;}
    bign(int num){ *this = num;} 
    bign(char* num) { *this = num; }
    bign operator = (const char* num){
        memset(d, 0, sizeof(d)); len = strlen(num);
        for(int i = 0; i < len; i++) d[i] = num[len-1-i] - '0';
        clean();
        return *this;
    }
    bign operator = (int num){
        char s[20]; sprintf(s, "%d", num);
        *this = s;
        return *this;
    }
    bign operator + (const bign& b){
        bign c = *this; int i;
        for (i = 0; i < b.len; i++){
            c.d[i] += b.d[i];
            if (c.d[i] > 9) c.d[i]%=10, c.d[i+1]++;
        }
        while (c.d[i] > 9) c.d[i++]%=10, c.d[i]++;
        c.len = max(len, b.len);
        if (c.d[i] && c.len <= i) c.len = i+1;
        return c;
    }
    bign operator - (const bign& b){
        bign c = *this; int i;
        for (i = 0; i < b.len; i++){
            c.d[i] -= b.d[i];
            if (c.d[i] < 0) c.d[i]+=10, c.d[i+1]--;
        }
        while (c.d[i] < 0) c.d[i++]+=10, c.d[i]--;
        c.clean();
        return c;
    }
    bign operator * (const bign& b)const{
        int i, j; bign c; c.len = len + b.len; 
        for(j = 0; j < b.len; j++) for(i = 0; i < len; i++) 
            c.d[i+j] += d[i] * b.d[j];
        for(i = 0; i < c.len-1; i++)
            c.d[i+1] += c.d[i]/10, c.d[i] %= 10;
        c.clean();
        return c;
    }
    bign operator / (const bign& b){
        int i, j;
        bign c = *this, a = 0;
        for (i = len - 1; i >= 0; i--)
        {
            a = a*10 + d[i];
            for (j = 0; j < 10; j++) if (a < b*(j+1)) break;
            c.d[i] = j;
            a = a - b*j;
        }
        c.clean();
        return c;
    }
    bign operator % (const bign& b){
        int i, j;
        bign a = 0;
        for (i = len - 1; i >= 0; i--)
        {
            a = a*10 + d[i];
            for (j = 0; j < 10; j++) if (a < b*(j+1)) break;
            a = a - b*j;
        }
        return a;
    }
    bign operator += (const bign& b){
        *this = *this + b;
        return *this;
    }
    bool operator <(const bign& b) const{
        if(len != b.len) return len < b.len;
        for(int i = len-1; i >= 0; i--)
            if(d[i] != b.d[i]) return d[i] < b.d[i];
        return false;
    }
    bool operator >(const bign& b) const{return b < *this;}
    bool operator<=(const bign& b) const{return !(b < *this);}
    bool operator>=(const bign& b) const{return !(*this < b);}
    bool operator!=(const bign& b) const{return b < *this || *this < b;}
    bool operator==(const bign& b) const{return !(b < *this) && !(b > *this);}
    string str() const{
        char s[maxn]={};
        for(int i = 0; i < len; i++) s[len-1-i] = d[i]+'0';
        return s;
    }
    void print(){
        dep(i,len-1,0) printf("%d",d[i]);
    }
};

快速幂

ll quick_power(ll base, ll n){
    ll res = 1;
    while (n){
        if (n & 1)
            res *= base; // res = (res * base) % mod;
        base *= base; //base = (base * base) % mod;
        n >>= 1;
    }
    return res;
}

母函数

void work(){
	a[0]=1;
	int last=0;
	rep(i,1,k){
		int last2=bag;
		memset(b,0,sizeof(int)*(last2+1));
		for(int j=0;j*v[i]<=last2;j++) //j=0可换成起始数量，无限个则去掉j<=c[i]
			for(int k=0;k<=last&&k+j*v[i]<=last2;k++) 
				b[k+j*v[i]]+=a[k];
		memcpy(a,b,sizeof(int)*(last2+1));
		last=last2;
	}
}

矩阵快速幂

int mod;
int n,m,sum;
struct mtix{
    int a[maxn][maxn];
    mtix(){memset(a,0,sizeof(a));}
}f;
mtix mul(mtix a,mtix b){
    mtix c;
    for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++)
            for (int k=1;k<=n;k++)
            {c.a[i][j]+=(a.a[i][k]*b.a[k][j])%mod;c.a[i][j]%=mod;}
    return c;
}
mtix mpow(int y){
    mtix ans;
    mtix tem=f;
    for (int i=1;i<=n;i++)
        ans.a[i][i]=1;
    for (;y;tem=mul(tem,tem),y>>=1)
        if (y&1) ans=mul(ans,tem);
    for (int i=1;i<=n;i++)
        sum+=ans.a[i][i];
    cout<<sum%mod<<endl;
    return ans;
}
int main(){
    cin>>n>>m;
    for (int i=1;i<=n;i++)
        for (int k=1;k<=n;k++)
            cin>>f.a[i][k];
    mpow(m);
}

单调栈

rep(i,1,n) while(a[l[i]-1]<a[i]) l[i]=l[l[i]-1];
dep(i,n,1) while(a[r[i]+1]<a[i]) r[i]=r[r[i]+1];

struct Stack{
    int L,R,val[maxn],id[maxn];
    void clear(){L=1,R=0;}
    void insert(int x,int i){
        while(L<=R&&x>=val[R]) R--;
        val[++R]=x;
        id[R]=i;
    }
    void erase(int i){if(L<=R&&id[L]==i) L++;}
    int top(){return val[L];}
}

0-1背包和完全背包

int T,n,bag;
int dp[maxn],v[maxn],w[maxn];
while(cin>>T){
    while(T--){
        memset(v,0,sizeof(v));
        memset(w,0,sizeof(w));
        memset(dp,0,sizeof(dp));
        cin>>n>>bag;
        for(int i=0;i<n;i++) cin>>v[i];
        for(int i=0;i<n;i++) cin>>w[i];
        for(int i=0;i<n;i++)
            for(int j=bag;j>=v[i];j—){//完全背包则正序循环
                dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
            }
        cout<<dp[bag]<<endl;
        }
    }

多重背包二进制优化

int tot=0
cin>>bag>>n;
while(n--){
    cin>>p>>h>>c; //价值 重量 数量
    for(int k=1;k<c;k<<=1){//二进制优化 转化为0-1背包
        v[tot]=k*p;
        w[tot++]=k*h;
        c-=k;
    }
    if(c){
        v[tot]=c*p;
        w[tot++]=c*h;
    }
}

可重叠KMP

void makeNext(const char P[],int next[]){
    int q,k;
    int m = strlen(P);
    next[0] = 0;
    for (q = 1,k = 0; q < m; ++q){
        while(k > 0 && P[q] != P[k])
            k = next[k-1];
        if (P[q] == P[k]){
            k++;
        }
        next[q] = k;
    }
}
int kmp(const char T[],const char P[],int next[]){
    int n,m;
    int i,q;
    n = strlen(T);
    m = strlen(P);
    makeNext(P,next);
    for (i = 0,q = 0; i < n; ++i){
        while(q > 0 && P[q] != T[i])
            q = next[q-1];
        if (P[q] == T[i]){
            q++;
        }
        if (q == m){
            printf("子串下标:%d\n",(im+1));
        }
    }
}
int main(){
    int i;
    int next[20]={0};
    char T[] = "ababxbababcadfdsss";
    char P[] = "abcdabd";
    kmp(T,P,next);
    for (i = 0; i < strlen(P); ++i){
        printf("%d ",next[i]);
    }
    return 0;
}

不可重叠KMP

void makeNext(const char P[],int next[]){
    int q,k;
    int m = strlen(P);
    next[0] = 0;
    for (q = 1,k = 0; q < m; ++q){
        while(k > 0 && P[q] != P[k])
            k = next[k-1];
        if (P[q] == P[k]){
            k++;
        }
        next[q] = k;
    }
}
int kmp(const char T[],const char P[],int next[]){
    int n,m;
    int i,q;
    n = strlen(T);
    m = strlen(P);
    makeNext(P,next);
    for (i = 0,q = 0; i < n; ++i){
        while(q > 0 && P[q] != T[i])
            q = next[q-1];
        if (P[q] == T[i]){
            q++;
        }
        if (q == m){
            printf("子串下标:%d\n",(im+1));
            q = 0;
        }
    }
}
int main(){
    int i;
    int next[20]={0};
    char T[] = "ababababa";
    char P[] = "aba";
    kmp(T,P,next);
    for (i = 0; i < strlen(P); ++i){
        printf("%d ",next[i]);
    }
    return 0;
}

后缀自动机

struct SAM{
    int next[maxn][27],fa[maxn],len[maxn];
    int root,tot,last; ll dp[maxn];
    void init(){
        tot=0;
        memset(dp,-1,sizeof(dp));
        last=root=newnode(0);
    }
    int newnode(int l){
        fa[tot]=-1;
        for(int i=0;i<27;++i)  next[tot][i]=-1;
        len[tot++]=l; return tot-1;
    }
    void insert(int x){
        int p=last; int cur=newnode(len[p]+1);
        while(p!=-1&&next[p][x]==-1){
            next[p][x]=cur; p=fa[p];
        }
        if(p==-1) fa[cur]=root;
        else{
            int q=next[p][x];
            if(len[q]==len[p]+1) fa[cur]=q;
            else{
                int tmp=newnode(len[p]+1);
                memcpy(next[tmp],next[q],sizeof(next[q]));
                fa[tmp]=fa[q]; fa[q]=fa[cur]=tmp;
                while(p!=-1&&next[p][x]==q){
                    next[p][x]=tmp; p=fa[p];
                }
            }
        }
        last=cur;
    }
    ll dfs(int u){
        if(dp[u]!=-1) return dp[u];
        ll res=1;
        for(int i=0;i<26;++i){
            if(next[u][i]==-1) continue;
            res+=dfs(next[u][i]);
        }
        return dp[u]=res;
    }
}sam;

回文自动机

struct PAM{
    int next[maxn][26],fail[maxn],len[maxn];
    int txt[maxn];
    int tot,root0,root1,last,size;
    void init(){
        last=tot=size=0; txt[size]=-1;
        root0=newnode(0); root1=newnode(-1);
        fail[root0]=1; fail[root1]=0;
    }
    int newnode(int l){
        len[tot]=l;
        memset(next[tot],0,sizeof(next[tot]));
        tot++; return tot-1;
    }
    int getfail(int x){
        while(txt[size-len[x]-1]!=txt[size]) x=fail[x];
        return x;
    }
    void insert(int c){
        txt[++size]=c; int now=getfail(last);
        if(!next[now][c]){
            int tmp=newnode(len[now]+2);
            fail[tmp]=next[getfail(fail[now])][c];
            next[now][c]=tmp;
        }
        last=next[now][c];
    }
}pam;

AC自动机

int trie[maxn][26];
int cntword[maxn];
int fail[maxn];
int cnt = 0;
void insertWords(string s){
    int root = 0;
    for(int i=0;i<s.size();i++){
        int next = s[i] - 'a';
        if(!trie[root][next])
            trie[root][next] = ++cnt;
        root = trie[root][next];
    }
    cntword[root]++;//当前节点单词数+1
}
void getFail(){
    queue <int>q;
    for(int i=0;i<26;i++){
        if(trie[0][i]){
            fail[trie[0][i]] = 0;
            q.push(trie[0][i]);
        }
    }
    while(!q.empty()){
        int now = q.front(); q.pop();
        for(int i=0;i<26;i++){
            if(trie[now][i]){
                fail[trie[now][i]] = trie[fail[now]][i];
                q.push(trie[now][i]);
            }
            else trie[now][i] = trie[fail[now]][i];
        }
    }
}
int query(string s){
    int now = 0,ans = 0;
    for(int i=0;i<s.size();i++){
        now = trie[now][s[i]-'a'];
        for(int j=now;j && cntword[j]!=-1;j=fail[j]){
            ans += cntword[j];
            cntword[j] = -1;
        }
    }
    return ans;
}

最长公共子序列LCS

char a[1010],b[1010];
int dp[1010][1010];
int main(){
    int lena,lenb,i,j;
    while(scanf("%s%s",&a,&b)!=EOF){
        lena=strlen(a);
        lenb=strlen(b);
        memset(dp,0,sizeof(dp));
        for(i=1;i<=lena;++i){
            for(j=1;j<=lenb;++j){
                if(a[i-1]==b[j-1])
                    dp[i][j]=dp[i-1][j-1]+1;
                else
                    dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
            }
        }
        printf("%d\n",dp[lena][lenb]);
    }
    return 0;
}

最长回文子串manacher算法

char str[maxn];//原字符串
char tmp[maxn<<1];//转换后的字符串
int Len[maxn<<1];
//转换原始串
int init(char *st){
    int i,len=strlen(st);
    tmp[0]='@';//字符串开头增加一个特殊字符，防止越界
    for(i=1;i<=2*len;i+=2){
        tmp[i]='#';
        tmp[i+1]=st[i/2];
    }
    tmp[2*len+1]='#';
    tmp[2*len+2]='


;//字符串结尾加一个字符，防止越界
    tmp[2*len+3]=0;
    return 2*len+1;//返回转换字符串的长度
}
int manacher(char *st,int len){
    int mx=0,ans=0,po=0;
    for(int i=1;i<=len;i++){
        if(mx>i)
            Len[i]=min(mx-i,Len[2*po-i]);
        else
            Len[i]=1;//如果i>=mx，要从头开始匹配
        while(st[i-Len[i]]==st[i+Len[i]])
            Len[i]++;
        if(Len[i]+i>mx){//若新计算的回文串右端点位置大于mx，要更新po和mx的值
            mx=Len[i]+i;
            po=i;
        }
        ans=max(ans,Len[i]);
    }
    return ans-1;//返回Len[i]中的最大值-1即为原串的最长回文子串额长度
}


const int maxn=2e6+10;
char s[maxn],s_new[maxn*2];
int p[maxn*2];
int odd[maxn],eve[maxn];
int init()
{
    int len=strlen(s);
    s_new[0]='


;//首标记 防止溢出
    s_new[1]='#';
    int j=2;
    for (int i=0;i<len;i++)
    {
        s_new[j++]=s[i];
        s_new[j++]='#';//插相同的特殊字符 变成奇
    }
    s_new[j]='\0';//尾标记 防止溢出
    return j;
}
int manacher()//求最长回文子串(注释为求回文子串个数)
{
    int len=init();
    int maxlen=-1; //int cnt=0;
    int id,mx=0;
    for (int i=1;i<len;i++)
    {
        if(i<mx) p[i]=min(mx-i,p[2*id-i]);
        else p[i]=1;
        while (s_new[i-p[i]]==s_new[i+p[i]]) p[i]++;
        if (mx<i+p[i]) id=i,mx=i+p[i];//根据mx的范围更新id
        maxlen=max(maxlen,p[i]-1); //cnt+=p[i]/2; 除以2是因为加了#字符
    }
    return maxlen; //return cnt;
}

后缀数组

int wstr[maxn],wv[maxn],wa[maxn],wb[maxn];
int Rank[maxn],height[maxn],sa[maxn],n,dp[maxn][26];
char str[maxn];
int cmp(char *r,int a,int b,int n){return r[a]==r[b]&&r[a+n]==r[b+n];}
void da(char *r,int n,int m){
    int i,j,p,*x=wa,*y=wb,*t;
    for(i=0;i<m;i++) wstr[i]=0;
    for(i=0;i<n;i++) wstr[x[i]=r[i]]++;
    for(i=1;i<m;i++) wstr[i]+=wstr[i-1];
    for(i=n-1;i>=0;i--) sa[--wstr[x[i]]]=i;
    for(j=1,p=1;p<n;j*=2,m=p){
        for(p=0,i=n-j;i<n;i++) y[p++]=i;
        for(i=0;i<n;i++) if(sa[i]>=j) y[p++]=sa[i]-j;
        for(i=0;i<m;i++) wstr[i]=0;
        for(i=0;i<n;i++) wstr[wv[i]=x[y[i]]]++;
        for(i=1;i<m;i++) wstr[i]+=wstr[i-1];
        for(i=n-1;i>=0;i--) sa[--wstr[wv[i]]]=y[i];
        for(t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1;i<n;i++)
            x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
    }
}
void calheight(char *r,int n){
    int i,j,k=0;
    for(i=1;i<=n;i++) Rank[sa[i]]=i;
    for(i=0;i<n;height[Rank[i++]]=k)
        for(k?k--:0,j=sa[Rank[i]-1];r[i+k]==r[j+k];k++);
}
void initRMQ(){
    int i,j,m;
    m=(int)(log((double)n)/log(2.00));
    for(i=1;i<=n;i++) dp[i][0]=height[i];
    for(j=1;j<=m;j++) for(i=1;i+(1<<j)-1<=n;i++)
        dp[i][j]=min(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);
}
int lcp(int x,int y){
    int t;
    x=Rank[x];y=Rank[y];
    if(x>y) swap(x,y); x++;
    t=(int)(log(double(y-x+1))/log(2.00));
    return min(dp[x][t],dp[y-(1<<t)+1][t]);
}
int check(int x){
    int minpos=maxn,maxpos=-1;
    rep(i,2,n){
        if(height[i]>=x){
            minpos=min(minpos,min(sa[j-1],sa[j]));
            maxpos=max(maxpos,max(sa[j-1],sa[j]));
        }
        else{
            if(maxpos-minpos>=i) return 1;
            minpos=maxn;maxpos=-1;
        }
        if(maxpos-minpos>=i) return 1;
    }
    return 0;
}
void solve(int ca){
    scanf("%s",str);
    da(str,n+1,128); calheight(str,n);
}

二分匹配

⼆分图中，选取最少的点数，使这些点和所有的边都有关联（把所有的边的覆盖）， 叫做最⼩点覆盖。 
1.最⼩点覆盖数=最⼤匹配数 
2.最⼤点独⽴集=总数-最⼩点覆盖集 
3.每个点拆分成出⼊两组：有向图的最⼩路径覆盖 = 总的点数（为拆分前的） - 最⼤匹配数 used－表示点是否访问过，match[i]－点i匹配的点，e－边，n－点数 
输⼊：e，n;
返回：最⼤匹配数; 
调⽤⽅法：hungary();



int n, m, k;
bool mp[maxn][maxn];
int match[maxn];
bool used[maxn];
bool find(int u) {
    for (int v = 0; v < m; ++v) {
        if (mp[u][v] && !used[v]) {
            used[v] = true;
            if (match[v] == -1 || find(match[v])) {
                match[v] = u;
                return true;
            }
        }
    }
    return false;
}
int hungary() {
    mst(match, -1);
    int ans = 0;
    for (int i = 0; i < n; ++i) {
        mst(used, false);
        if (find(i)) ++ans;
    }
    return ans;
}
int main() {
    while (~scanf("%d", &n) && n) {
        scanf("%d%d", &m, &k);
        int u, v;
        mst(mp, false);
        while (k--) {
            scanf("%*d%d%d", &u, &v);
            if (!u || !v) continue;
            mp[u][v] = true;
        }
        printf("%d\n", hungary());
    }
    return 0;
}

邻接表

//M为边数，N为点数
struct edge{
    int v,w,nxt;
}e[M];
int tot,head[N];
void init(){
    MS(head,-1);
    tot = 0;
}
void addedge(int u,int v,int w){
    e[tot] = {v,w,head[u]}; head[u] = tot++;
}

Tarjan

int n,m;
int sz, dfn[maxn],low[maxn],vis[maxn],belong[maxn];
int scc;//强连通分量个数
stack<int> sta;
void init(){
    rep(i,0,n) vis[i]=0,head[i]=-1,dfn[i]=0;
    while(!sta.empty()) sta.pop();
    scc = cnt = sz = 0;
}
void tarjan(int u){
    dfn[u]=low[u]=++sz; vis[u]=1; sta.push(u);
    for(int i = head[u]; ~i; i = g[i].next) {
        int v = g[i].to;
        if(!dfn[v]){
            tarjan(v);
            low[u] = min(low[u], low[v]);
        }else if(vis[v] && low[u] > dfn[v]) low[u]=dfn[v];
    }
    if(low[u]==dfn[u]) {
        scc++;
        while(1){
            int id = sta.top(); sta.pop();
            vis[id] = 0;
            belong[id]=scc;
            if(id == u) break;
        }
    }
}
void work(){ //缩点
    rep(i,1,n) if(!dfn[i]) tarjan(i);
    int de[maxn]={0,};
    rep(i,1,n)
    for(int j=head[i];j!=-1;j=g[j].next){
        int v=g[j].to;
        if(belong[i]!=belong[v]) de[belong[v]]++;
    }
    rep(i,1,scc) if(!de[i]) {//...}
}

Tarjan 边双

void tarjan(int u, int fa){
    dfn[u]=low[u]=++sz;sta.push(u);
    for(int k = head[u]; k+1; k = g[k].next){
        int v = g[k].to;
        if(!dfn[v]){
            tarjan(v, u);
            low[u] = min(low[u], low[v]);
            if(low[v] > dfn[u]) ++cut;  //割边+1
        } else if(v != fa)
            low[u] = min(low[u], dfn[v]);
    }
    if(dfn[u] == low[u]){
        ++bcc;  //边双连通分量+1
        do{
            int id=sta.top(); sat.pop();
            belong[id]=bcc;
        }
        while(id!=u);
    }
}

最短路Floyd

for (int k = 1; k <= n; k++) {
    for (int i = 1; i <= n; i++) {
        if (i == k) continue;
        for (int j = 1; j <= n; j++) {
            if (i == j || k == j) continue;
            dis[i][j] = min(dis[i][j], dis[i][k]+ dis[k][j]);
        }
    }
}

最短路SPFA

//N为点数
int n,d[N],c[N];
bool vis[N];
void init(){初始化邻接表}
int Spfa(int s,int n){
    int u,v,w;
    queue <int> q;
    mst(d,INF);mst(c,0);mst(vis,0);//求最⻓路时改初始d
    d[s]=0;
    q.push(s); vis[s]=1; c[s]=1;
    while(!q.empty()){
        u=q.front(); q.pop(); vis[u]=0;
        for(int k=head[u]; k!=-1; k=e[k].nxt){
            v=e[k].v, w=e[k].w;
            if( d[u]+w < d[v]){//求最⻓路时改松弛条件
                d[v]=d[u]+w;
                if(!vis[v]){
                    q.push(v); vis[v]=1;
                    if(++c[v]>n) //超过⼊队次数上限，说明有负环
                        return 0;
                }
            }
        }
    }
    return 1;
}

Dijkstra+堆优化

typedef pair<int,int> pii;
struct Edge {
    int v, w;
    int next;
}edge[maxn];
int head[maxn], d[maxn], tot;
bool vis[maxn];
void addedge(int u, int v, int w) {//起点，重点，距离
    edge[tot].v = v;
    edge[tot].w = w;
    edge[tot].next = head[u];
    head[u] = tot++;
}
void dijkstra(int s) {
    priority_queue<pii, vector<pii>, greater<pii> > Q;
    memset(d, INF, sizeof(d));
    d[s] = 0;
    memset(vis, false, sizeof(vis));
    Q.push(make_pair(d[s], s));
    while(!Q.empty()) {
        pii tmp = Q.top();
        Q.pop();
        int x = tmp.second;
        if(vis[x]) continue;
        vis[x] = true;
        for(int i = head[x]; i+1; i = edge[i].next) {
            if(d[edge[i].v] > d[x] + edge[i].w) {
                d[edge[i].v] = d[x] + edge[i].w;
                Q.push(make_pair(d[edge[i].v], edge[i].v));
            }
        }
    }
}

Dinic最大流

//最⼤流 ＝ 最⼩割
int tot=1,head[maxn<<1],dep[maxn],iter[maxn],Q[maxn],S,T;
struct node{int u,v,nxt,w;}g[maxn<<1];
void add(int u,int v,int w){g[++tot]={u,v,head[u],w};head[u]=tot;g[++tot]={v,u,head[v],0};head[v]=tot;}
int bfs(){
	rep(i,1,T) dep[i]=0,iter[i]=head[i];
	int ql=0,qr=0;Q[++qr]=S;dep[S]=1;
	while(ql<qr){
		int x=Q[++ql];
		for(int i=head[x];i;i=g[i].nxt) if(!dep[g[i].v]&&g[i].w) dep[g[i].v]=dep[x]+1,Q[++qr]=g[i].v;
	}
	return dep[T];
}
int dfs(int x,int f){
	if(x==T||!f) return f;
	int sf=0;
	for(int i=iter[x];i;i=g[i].nxt) if(dep[g[i].v]==dep[x]+1&&g[i].w){
		int w=dfs(g[i].v,min(g[i].w,f));
		if(f) {g[i].w-=w;g[i^1].w+=w;f-=w;sf+=w;}
	}
	return sf;
}
int dinic(){
	int ans=0;while(bfs()) ans+=dfs(S,inf);
	return ans;
}

最小费用最大流

struct Edge{
    int to,cap,cost,next,flow;
}g[1510*1510];
int head[maxn],cnt;
int pre[maxn],dis[maxn];
bool vis[maxn];
int n,m,C;
void init(){
    cnt=0;
    rep(i,0,n+1) head[i]=-1;
}
void addedge(int u,int v,int cap,int cost){
    g[cnt]={v,cap,cost,head[u],0};head[u]=cnt++;
    g[cnt]={u,0,-cost,head[v],0}; head[v]=cnt++;
}
bool spfa(int s,int t){
    queue<int> q;
    for(int i=0;i<=n;++i){
        dis[i]=INF; vis[i]=false; pre[i]=-1;
    }
    dis[s]=0; vis[s]=true;
    q.push(s);
    while (!q.empty()){
        int u = q.front(); q.pop();
        vis[u]=false;
        for(int i=head[u];~i;i=g[i].next){
            int v=g[i].to;
            if(g[i].cap>g[i].flow&&dis[v]>dis[u]+g[i].cost){
                dis[v]=dis[u]+g[i].cost;
                pre[v]=i;
                if(!vis[v]){
                    vis[v]=true;
                    q.push(v);
                }
            }
        }
    }
    if(pre[t]==-1) return false;
    else return true;
}
int MCMF(int s,int t){
    int flow=0,cost=0;
    while(spfa(s,t)){
        int Min=INF;
        for(int i=pre[t];i!=-1;i=pre[g[i^1].to]){
            if(Min>g[i].cap-g[i].flow)
                Min=g[i].cap-g[i].flow;
        }
        for(int i=pre[t];i!=-1;i=pre[g[i^1].to]){
            g[i].flow+=Min;
            g[i^1].flow-=Min;
            cost+=g[i].cost*Min;
        }
        flow+=Min;
    }
    //return flow;
    return cost;
}

最⼤团＋极⼤团Bron–Kerbosch算法

极⼤团计数： 
输⼊：some, g； 输出：S； 
调⽤⽅法：dfs(0,0,n,0)； 
复杂度爆炸，可处理⼀两百个点
int n,m,ans;
int mp[maxn][maxn],Some[maxn][maxn],None[maxn][maxn];
inline void dfs(int st,int sc,int nc) {
    if(!sc) {ans+=(!nc); return;}
    if(ans>1000) return;
    int u=Some[st][1];
    for(int e=1;e<=sc;++e) {
        int v=Some[st][e];
        if(mp[u][v]) continue;
        int nsc=0,nnc=0;
        for(int i=1;i<e;i++) if(mp[u][Some[st][i]] && mp[v][Some[st][i]]) Some[st+1][++nsc]=Some[st][i];
        for(int i=e+1;i<=sc;i++) if(mp[v][Some[st][i]]) Some[st+1][++nsc]=Some[st][i];
        for(int i=1;i<=nc;i++) if(mp[v][None[st][i]]) None[st+1][++nnc]=None[st][i];
        dfs(st+1,nsc,nnc);
        None[st][++nc]=v;
    }
}
int main() {
    while(scanf("%d%d",&n,&m)!=EOF) {
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
                mp[i][j]=0;
        ans=0;
        for(int i=0;i<m;i++) {
            int x,y;
            sc2(x,y);
            if(x==y) continue;
            mp[x-1][y-1]=1;
            mp[y-1][x-1]=1;
        }
        for(int i=0;i<n;i++) Some[0][i+1]=i;
        dfs(0,n,0);
        printf("%d\n",ans);
    }
}
最大团：
调⽤⽅式： MaximumClique()
输出：ans 
复杂度爆炸，可处理⼀两百个点

bool mp[maxn][maxn];
int best, n, num[maxn];
bool dfs(int *adj, int total, int cnt){
    int t[maxn], k;
    if(total == 0){
        if(cnt > best){
            best = cnt;
            return true;
        }
        return false;
    }
    for(int i = 0; i < total; ++i){
        if(cnt+total-i <= best) return false;
        if(cnt+num[adj[i]] <= best) return false;
        k = 0;
        for(int j = i+1; j < total; ++j)
            if(mp[adj[i]][adj[j]]) t[k++] = adj[j];
        //扫描与u相连的顶点中与当前要选中的adj[i]相连的顶点adj[j]并存储到数组t[]中，数量为k
        if(dfs(t, k, cnt+1)) return true;
    }
    return false;
}
int MaximumClique(){
    int adj[maxn], k;
    best = 0;
    for(int i = n; i >= 1; --i){
        k = 0;
        for(int j = i+1; j <= n; ++j)
            if(mp[i][j]) adj[k++] = j;
        //得到当前点i的所有相邻点存入adj
        dfs(adj, k, 1);    //每次dfs相当于必选当前i点看是否能更新best
        num[i] = best;
    }
    return best;
}
int main(){
    while(cin >> n && n){
        for(int i = 1; i <= n; ++i)
            for(int j = 1; j <= n; ++j){
                int x; cin >> x;
                mp[i][j] = x;
            }
        cout << MaximumClique() << endl;
    }
    return 0;
}

稳定婚姻问题

int couple[maxn];//每个女生匹配的男生
queue<int> que;//存没有匹配的男生
int man_like_woman_rank[maxn][maxn];//代表i男对女生的喜欢排名
int woman_like_man_val[maxn][maxn];//代表i女对j男的喜欢程度
int N;//每边的人数
void gale_shapley(){
    while(!que.empty())
        que.pop();
    for(int i=1;i<=N;++i)
        couple[i]=-1;
    for(int i=1;i<=N;++i)
        que.push(i);
    while(!que.empty()){
        int man=que.front(); que.pop();
        for(int i=1;i<=N;++i)
            if(man_like_woman_rank[man][i]!=-1){
                //选择未被拒绝且最喜欢的女生
                int woman=man_like_woman_rank[man][i];
                man_like_woman_rank[man][i]=-1;
                int pre=couple[woman];
                if(pre==-1){//对方没有匹配，直接匹配
                    couple[woman]=man;
                    break;
                }
                else{
                    if(woman_like_man_val[woman][man]>woman_like_man_val[woman][pre]){//更换匹配
                        que.push(pre);
                        couple[woman]=man;
                        break;
                    }
                }
            }
    }
}
string name[2][maxn];//保存名字
map<string, int> to_id[2];//名字映射到编号
void init(){
    to_id[0].clear();
    to_id[1].clear();
}
int main(){
    quickcin
    while(cin>>N){
        init();
        int cnt=0;
        string tmp;
        for(int i=1;i<=N;++i){
            cin>>name[0][i];
            int u=to_id[0][name[0][i]]=i;
            for(int j=1;j<=N;++j){
                cin>>tmp;
                int v=to_id[1][tmp];
                if(!v){
                    to_id[1][tmp]=v=++cnt;
                    name[1][cnt]=tmp;
                }
                man_like_woman_rank[u][j]=v;
            }
        }
        for(int i=1;i<=N;++i){
            cin>>tmp;
            int u=to_id[1][tmp];
            for(int j=1;j<=N;++j){
                cin>>tmp;
                int v=to_id[0][tmp];
                woman_like_man_val[u][v]=N-j+1;
            }
        }
        gale_shapley();
        bool ok=true;
        for(int i=1;i<=N;++i)
            if(couple[i]==-1){//有人没有匹配
                ok=false;
                break;
            }
        if(!ok){
            cout<<"Impossible\n\n"<<endl;
            continue;
        }
        for(int i=1;i<=N;++i)
            cout<<name[0][couple[i]]<<' '<<name[1][i]<<'\n';
        cout<<'\n';
    }
    return 0;
}

树状数组

int a[maxn],c[maxn];
int n,m;
int lowbit(int x){
    return x & (-x);
}
void modify(int x,int add){//⼀维
    while(x<=n){
        c[x]+=add;
        x+=lowbit(x);
    }
}
int get_sum(int x){
    int ret=0;
    while(x!=0){
        ret+=c[x];
        x-=lowbit(x);
    }
    return ret;
}
void modify(int x,int y,int data){//⼆维
    for(int i=x;i<n;i+=lowbit(i))
        for(int j=y;j<n;j+=lowbit(j))
            c[i][j]+=data;
}
int get_sum(int x,int y){
    int res=0;
    for(int i=x;i>0;i-=lowbit(i))
        for(int j=y;j>0;j-=lowbit(j))
            res+=c[i][j];
    return res;
}
//查询第K⼤
int find_kth(int k){
    int ans = 0, cnt = 0, i;
    for (i = 20; i >= 0; i--){
        ans += (1 << i);
        if (ans >= n|| cnt + a[ans] >= k)
            ans -= (1 << i);
        else cnt += a[ans];
    }
    return ans + 1;
}

并查集

int pre[maxn];
int tot[maxn];//集合元素数量
int Rank[maxn];//集合排名
int n,m,k;
void init(){
    for(int i=1;i<=n;++i){
        pre[i]=i;
        tot[i]=1;
    }
    mst(Rank,0);
}
int find(int x){
    if(x==pre[x])
        return x;
    else
        return pre[x]=find(pre[x]);
}

void join(int x, int y){
    x = find(x);
    y = find(y);
    if (Rank[x] > Rank[y]){
        pre[y] = x;
        if (x != y)
            tot[x] += tot[y];
    }
    else{
        pre[x] = y;
        if (x != y)
            tot[y] += tot[x];
        if (Rank[x] == Rank[y])
            Rank[y] += 1;
    }
}


int vis[maxn],m[maxn];
int pre[maxn];
struct nobe{
    double totnum,totarea;
    int id,num;
};
int cmp(nobe a,nobe b){
    if(a.totarea!=b.totarea)
        return a.totarea>b.totarea;
    return a.id<b.id;
}
void init(){
    for(int i=0;i<=10000;i++)
        pre[i]=i;
}
int find(int x){
    if(x==pre[x])
        return x;
    else
        return pre[x]=find(pre[x]);
}
void join(int a,int b){
    int x=find(a);
    int y=find(b);
    if(x!=y){
        if(x>y)
            pre[x]=y;
        else
            pre[y]=x;
    }
}
int main(){
    int n;
    nobe a[maxn];
    nobe res[maxn];
    nobe family[maxn];
    scanf("%d",&n);
    init();
    mst(vis,0);
    mst(m,0);
    for(int i=0;i<n;++i){
        int fa,ma,d,k;
        scanf("%d%d%d",&a[i].id,&fa,&ma);
        vis[a[i].id]=1;
        if(fa!=-1){
            join(fa,a[i].id);
            vis[fa]=1;
        }
        if(ma!=-1){
            join(ma,a[i].id);
            vis[ma]=1;
        }
        scanf("%d",&k);
        while(k--){
            scanf("%d",&d);
            if(d!=-1){
                join(a[i].id,d);
                vis[d]=1;
            }
        }
        scanf("%lf%lf",&a[i].totnum,&a[i].totarea);
    }
    FF(i,n){
        int id=find(a[i].id);
        family[id].id=id;
        family[id].totnum+=a[i].totnum;
        family[id].totarea+=a[i].totarea;
    }
    FF(i,10000)
    if(vis[i])
    {   family[find(i)].num++;
    }
    int cnt=0;
    FF(i,10000){
        if(vis[i]){
            int id=find(i);
            if(!m[id]){
                m[id]=1;
                double x=double(family[id].num);
                res[cnt].totnum=family[id].totnum*1.0/x;
                res[cnt].totarea=family[id].totarea*1.0/x;
                res[cnt].id=id;
                res[cnt++].num=int(x);
            }
        }
    }
    sort(res,res+cnt,cmp);
    printf("%d\n",cnt);
    FF(i,cnt)
    printf("%04d %d %.3lf %.3lf\n",res[i].id,res[i].num,res[i].totnum,res[i].totarea);
    return 0;
}

字典树Trie

struct trie {
    int next[maxn][26],cnt;
    bool exist[maxn]; //该结点结尾的字符串是否存在
    void insert(char *s, int l) {
        int p=0;
        for (int i=0;i<l;i++) {
            int c=s[i]-'a';
            if (!next[p][c]) next[p][c]=++cnt;// 如果没有，就添加结点
            p=next[p][c];
        }
        exist[p]=1;
    }
    bool find(char *s, int l){
        int p=0;
        for (int i=0;i<l;i++){
            int c=s[i]-'a';
            if(!next[p][c]) return 0;
            p=next[p][c];
        }
        return exist[p];
    }
};

Trie数组版

int trie[maxn][26];
int cntword[maxn];
int fail[maxn];
int cnt = 0;
void init(){
    for(int i=0;i<=tot;i++){
        flagg[i]=false;
        for(int j=0;j<10;j++)
            tree[i][j]=0;
    }
    tot=0;
}
void insertWords(string s){
    int root = 0;
    for(int i=0;i<s.size();i++){
        int next = s[i] - 'a';
        if(!trie[root][next])
            trie[root][next] = ++cnt;
        root=trie[root][next];
    }
    cntword[root]++;
}
bool find(string str){
    int len=str.length();
    int root=0;
    for(int i=0;i<len;i++){
        int id=str[i]-'0';
        if(!tree[root][id]) return false;
        root=tree[root][id];
    }
    return true;
}

主席树

int T[maxn];
int lson[maxn*36],rson[maxn*36],c[maxn*36];
int X[maxn],K[maxn];
int cnt=0,en;
int build(int l,int r){
    int root=cnt++;
    c[root]=0;
    if(l!=r){
        int mid=(l+r)>>1;
        lson[root]=build(l,mid);
        rson[root]=build(mid+1,r);
    }
    return root;
}
int update(int root,int pos,int val){
    int newroot=cnt++,tmp=newroot;
    c[newroot]=c[root]+val;
    int l=1,r=en;
    while(l<r){
        int mid=(l+r)>>1;
        if(pos<=mid){
            lson[newroot]=cnt++;
            rson[newroot]=rson[root];
            newroot=lson[newroot];
            root=lson[root];
            r=mid;
        }
        else{
            rson[newroot]=cnt++;
            lson[newroot]=lson[root];
            newroot=rson[newroot];
            root=rson[root];
            l=mid+1;
        }
        c[newroot]=c[root]+val;
    }
    return tmp;
}
int query(int lroot,int rroot,int k){
    int l=1,r=en;
    while(l<r){
        int mid=(l+r)>>1;
        if(c[lson[rroot]]-c[lson[lroot]]>=k){
            r=mid;
            lroot=lson[lroot];
            rroot=lson[rroot];
        }
        else{
            l=mid+1;
            k-=c[lson[rroot]]-c[lson[lroot]];
            rroot=rson[rroot];
            lroot=rson[lroot];
        }
    }
    return l;
}
void solve(){
	cnt=0;
    rep(i,1,n){
    	K[i]=read();X[i]=K[i];
    } sort(X+1,X+1+n);
    en=unique(X+1,X+1+n)-X-1;
    T[0]=build(1,en);
    rep(i,1,n){
        int pos=lower_bound(X+1,X+1+en,K[i])-X;
        T[i]=update(T[i-1],pos,1);
    }
    while(q--){
        int l,r,k;l=read();r=read();k=read();
        printf("%d\n",X[query(T[l-1],T[r],k)]);
    }
}
int main() {
	while(~scanf("%d%d",&n,&q)) solve();
}

动态开点主席树

int rt[maxn];//rt[i]表示由数组前i个元素组成的线段树的根结点
struct node{
    int l,r;
    int sum;
}T[maxn*20];
int tot=0;//结点编号
vector<int> v;
int getid(int k){
    return lower_bound(v.begin(),v.end(),k)-v.begin()+1;
}
void build(int &o,int l,int r){
    o=++tot;
    T[o].sum=0;
    if(l==r) return;
    int mid=(l+r)/2;
    build(T[o].l,l,mid);
    build(T[o].r,mid+1,r);
}
void update(int l,int r,int &now,int last,int k){
    T[++tot]=T[last];now=tot;T[tot].sum++;
    if(l==r) return;
    int mid=(l+r)>>1;
    if(k<=mid) update(l,mid,T[now].l,T[last].l,k);
    else update(mid+1,r,T[now].r,T[last].r,k);
}
int query(int l,int r,int x,int y,int k){
    if(l==r) return l;
    int mid=(l+r)>>1;
    int cnt=T[T[y].l].sum-T[T[x].l].sum;
    if(cnt>=k) return query(l,mid,T[x].l,T[y].l,k);
    else return query(mid+1,r,T[x].r,T[y].r,k-cnt);
}
int main(){
    int n,m;
    while(~scanf("%d%d",&n,&m)){
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);
            v.push_back(a[i]);
        }
        sort(v.begin(),v.end());
        v.erase(unique(v.begin(),v.end()),v.end());
        build(rt[0],1,n);
        for(int i=1;i<=n;i++) update(1,n,rt[i],rt[i-1],getid(a[i]));
        while(m--){
            int x,y,k;
            scanf("%d%d%d",&x,&y,&k);
            printf("%d\n",v[query(1,n,rt[x-1],rt[y],k)-1]);
        }
    }
    return 0;
}

地图BFS

int V[maxn];
int from,to,n;
int f[maxn];
struct pos{
    int num,steps;
};
int check(int x){
    if (x<0 || x>to || V[x]) return 0;
    else return 1;
}
void bfs(){
    queue<pos> Q;
    pos cur,nex;
    cur.num=from;
    cur.steps=0;
    Q.push(cur);
    V[cur.num]=1;
    while (!Q.empty()){
        cur=Q.front();
        Q.pop();
        if (cur.num==to){
            cout<<cur.steps<<endl;
            return;
        }
        for (int i=1;i!=3;i++){
            if (i==1) nex.num=cur.num+f[cur.num];
            if (i==2) nex.num=cur.num-f[cur.num];
            if (check(nex.num)){
                nex.steps=cur.steps+1;
                Q.push(nex);
                V[nex.num]=1;
            }
        }
    }
    cout<<"-1"<<endl;
}

地图DFS

char Map[maxn][maxn];
int dirt[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
int n,m,Time,wall,flag;
int si = 0,sj = 0,di = 0,dj = 0;
void dfs(int i,int j,int cnt){
    if(i==di&&j==dj&&cnt==Time){flag=1;return;}  //找到条件
    if(cnt>Time)return;  //超时直接返回
    for(int k=0;k<4;k++){
        int nexi=i+dirt[k][0];
        int nexj=j+dirt[k][1];
        if(nexi<0||nexi>=n||nexj<0||nexj>=m) continue;
        if(Map[nexi][nexj]!='X'){
            Map[nexi][nexj]='X';
            dfs(nexi,nexj,cnt+1);
            if(flag) return;
            Map[nexi][nexj]=‘.';  //重要！
        }
    }
}
int main(){
    while(cin>>n>>m>>Time&&(n||m||Time)){
        wall=0;flag=0;
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++){
                cin>>Map[i][j];
                if(Map[i][j]=='S'){
                    si=i; sj=j;
                }
                if(Map[i][j]=='D'){
                    di=i; dj=j;
                }
                if(Map[i][j]=='X')
                    wall++;
            }
        if((Time<(abs(si-di)+abs(sj-dj))) || (Time>=(n*m-wall))){  //步数剪枝
            cout<<"NO"<<endl;
            continue;
        }
        if((Time-abs(si-di)-abs(sj-dj))%2){  //奇偶剪枝
            cout<<"NO"<<endl;
            continue;
        }
        Map[si][sj]='X';
        dfs(si,sj,0);
        if(flag) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
    return 0;
}

凸包

struct point{
    int x,y;
}pt[maxn],ans[maxn]; //ans为凸包上的点
int cnt;//cnt为凸包点个数
int cmp(point a,point b){
    if(a.x==b.x) return a.y<b.y;
    return a.x<b.x;
}
int cross(point p0,point p1,point p2){//计算叉积
    return (p1.x-p0.x)*(p2.y-p0.y)-(p1.y-p0.y)*(p2.x-p0.x);
}
double dis(point a,point b){//计算两点距离
    return sqrt(1.0*(a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
void convex(int n){
    sort(pt,pt+n,cmp);
    cnt=0;
    for(int i=0;i<n;i++){//下凸包
        while(cnt>1&&cross(ans[cnt-2],ans[cnt-1],pt[i])<=0){
            cnt--;
        }
        ans[cnt++]=pt[i];
    }
    int key=cnt;
    for(int i=n-2;i>=0;i--){
        while(cnt>key&&cross(ans[cnt-2],ans[cnt-1],pt[i])<=0){
            cnt--;
        }
        ans[cnt++]=pt[i];
    }
}
int main(){
    int n,l;
    int t;
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&n,&l);
        for(int i=0;i<n;i++){
            scanf("%d%d",&pt[i].x,&pt[i].y);
        }
        convex(n);
        double res;
        for(int i=0;i<cnt-1;i++){
            res+=dis(ans[i],ans[i+1]);//凸包周长
        }
        printf("%.0lf\n",res);//.0代表小数点后保留0位数字，如果多出来，用四舍五入
        if(t) printf("\n");
    }
    return 0;
}

SG

//f[]：可以取走的石子个数
//sg[]:0~n的SG函数值
//vis[]:mex{}
int f[maxn],sg[maxn],vis[maxn];
void getSG(int n){
    int i,j;
    memset(sg,0,sizeof(sg));
    for(i=1;i<=n;i++){
        memset(vis,0,sizeof(vis));
        for(j=1;f[j]<=i&&f[j]<=m;j++) //注意加f[i]的限定条件，此处为f[j]<=m
            vis[sg[i-f[j]]]=1;
        for(j=0;j<=n;j++){    //求mes{}中未出现的最小的非负整数
            if(vis[j]==0){
                sg[i]=j;
                break;
            }
        }
        //cout<<i<<" "<<sg[i]<<endl;
    }
}

Nim-Sum算法

int main(){//Nim游戏 输出第一步有几种走法
    int m;
    int a[110];
    while(cin>>m&&m){
        int sum=0;
        memset(a,0,sizeof(a));
        for(int i=0;i<m;i++){
            cin>>a[i];
            sum^=a[i];
        }
        if(sum==0) {cout<<"0\n";continue;}
        int ans=0;
        for(int i=0;i<m;i++){
            if((a[i]^sum)<=a[i])
                ans++;
        }
        cout<<ans<<endl;
    }
}

离散化

vector<int> vv;
int getid(int x) { return lower_bound(vv.begin(),vv.end(),x)-vv.begin()+1; }
sort(vv.begin(),vv.end());vv.erase(unique(vv.begin(),vv.end()),vv.end());

Dinic

struct DINIC{
    #define maxn 2510
    #define maxe (int)1e6+10
    const ll inf=(ll)1e17;
    int dep[maxn],head[maxn],cur[maxn],tot;
    struct EDGE{int v,nxt;ll val;}g[maxe];
    void add(int u,int v,ll w){g[tot]={v,head[u],w};head[u]=tot++;}
    void init(){tot=0;memset(head,-1,sizeof(head));}
    void addedge(int u,int v,ll w){add(u,v,w);add(v,u,0);}
    bool bfs(int s,int t){
        memset(dep,0,sizeof(dep));
        queue<int> Q;Q.push(s); dep[s]=1;cur[s]=head[s];
        while(!Q.empty()){
            s=Q.front();Q.pop();
            for(int i=head[s],v;~i;i=g[i].nxt){
                if(g[i].val>0&&!dep[v=g[i].v]){
                    dep[v]=dep[s]+1;cur[v]=head[v];
                    if(v==t) return true;
                    Q.push(v);
                }
            }
        } return false;
    }
    ll dfs(int s,int t,ll flow){
        if(s==t||flow<=0) return flow;
        ll rest=flow;
        for(int &i=cur[s];~i;i=g[i].nxt){
            int v=g[i].v;
            if(g[i].val>0&&dep[v]==dep[s]+1){
                ll tmp=dfs(v,t,min(rest,g[i].val));
                if(tmp<=0) dep[v]=0;
                rest-=tmp;
                g[i].val-=tmp;g[i^1].val+=tmp;
                if(rest<=0) break;
            }
        }
        return flow-rest;
    }
    ll maxflow(int s,int t){
        ll ans=0;
        while(bfs(s,t)) ans+=dfs(s,t,inf);
        return ans;
    }
    //先init(),再addedge,最后flow.maxflow(s,t);
}dinic;

ZKW费用流

struct ZKW_SPFA{
    #define maxn 5005
    #define maxe 50050
    const int INF=(int)1e9;
    int dis[maxn],vis[maxn],head[maxn],tot;
    int n,Cost=0,Flow=0;
    struct Edge{int v,cap,cost,nxt;}g[maxe<<1];
    void init(int _n){tot=0;memset(head,-1,sizeof(head));n=_n;}
    void add(int u,int v,int cap,int cost){
        g[tot]={v,cap,cost,head[u]};head[u]=tot++;
    }
    void addedge(int u,int v,int cap,int cost){
        add(u,v,cap,cost);add(v,u,0,-cost);
    }
    bool spfa(int S,int T){
        for(int i=0;i<=n;i++) vis[i]=0,dis[i]=INF;
        deque<int>Q;Q.push_back(T);dis[T]=0;vis[T]=1;
        while(!Q.empty()){
            int u=Q.front();Q.pop_front();
            for(int i=head[u],v;~i;i=g[i].nxt)
                if(g[i^1].cap&&dis[v=g[i].v]>dis[u]+g[i^1].cost){
                    dis[v]=dis[u]+g[i^1].cost;
                    if(!vis[v]){
                        vis[v]=1;
                        if(!Q.empty()&&dis[v]<dis[Q.front()]) Q.push_front(v);
                        else Q.push_back(v);
                        //SLF优化
                    }
                } vis[u]=0;
        } return dis[S]<INF;
    }
    int dfs(int S,int T,int flow){
        if(S==T){vis[T]=1;return flow;}
        int used=0,res;vis[S]=1;
        for(int i=head[S],v;~i;i=g[i].nxt)
            if(!vis[v=g[i].v]&&g[i].cap&&dis[S]-g[i].cost==dis[v]){
                res=dfs(v,T,min(g[i].cap,flow-used));
                if(res) Cost+=res*g[i].cost,g[i].cap-=res,g[i^1].cap+=res,used+=res;
                if(used==flow)break;
            }
        return used;
    }
    void solve(int S,int T){
        while(spfa(S,T)){
            vis[T]=1;
            while(vis[T]) memset(vis,0,sizeof vis),Flow+=dfs(S,T,INF);
        }
    }
    //先zkw.init(n),再zkw.addedge(),再zkw.solve(S,T)
    //可以输出zkw.Flow和zkw.Cost
}zkw;

Dijkstra

typedef pair<int,int> pii;
int dis[maxn],vis[maxn];
void dijkstra(int s){
    priority_queue<pii,vector<pii>,greater<pii> > Q;
    rep(i,1,n) dis[i]=INF,vis[i]=0; dis[s]=0;
    Q.push({dis[s],s});
    while(!Q.empty()){
        pii tmp=Q.top();Q.pop();
        int x=tmp.second;
        if(vis[x]) continue; vis[x]=1;
        for(int i=head[x];i;i=g[i].nex){
        int v=g[i].v,w=g[i].w;
            if(dis[v]>dis[x]+w){
                dis[v]=dis[x]+w;
                Q.push({dis[v],v});
            }
        }
    }
}

组合数

struct Comb{
    static const int N=(int)1e6+100;
    ll fac[N],inv[N];
    Comb(){
        fac[0]=1;
        rep(i,1,N-1) fac[i]=fac[i-1]*i%mod;
        inv[N-1]=qpow(fac[N-1],mod-2);
        dep(i,N-2,0) inv[i]=inv[i+1]*(i+1)%mod;
    }
    ll operator()(ll a,ll b){
        if(a<b) return 0;
        return fac[a]*inv[a-b]%mod*inv[b]%mod;
    }
}comb;

LCA

struct LCA{
    int pre[30][maxn],dep[maxn],di[maxn];
    void init(){
        memset(pre,0,sizeof(pre));
    }
    void dfs(int u,int fa){
        dep[u]=dep[fa]+1;pre[0][u]=fa;
        for(int i=1;(1<<i)<=dep[u];++i) pre[i][u]=pre[i-1][pre[i-1][u]];
        for(int i=head[u],v;i;i=g[i].nxt) if((v=g[i].v)!=fa){
            di[v]=di[u]+g[i].w;
            dfs(v,u);
        }
    }
    int getlca(int u,int v){
        if(dep[u]<dep[v]) swap(u,v);
        dep(i,25,0) if(dep[u]-(1<<i)>=dep[v]) u=pre[i][u];
        if(u==v) return u;
        dep(i,25,0) if(pre[i][u]!=pre[i][v]) u=pre[i][u],v=pre[i][v];
        return pre[0][u];
    }
    int dis(int u,int v){return di[u]+di[v]-2*di[getlca(u,v)];}
    //先init(),再dfs(rt),再lca;
}lca;

三分

//凸函数的极大值
ll l,r;
while(l<r){
    ll lmid=l+(r-l)/3,rmid=r-(r-l)/3;
    if(calc(lmid)<=calc(rmid)) l=lmid+1;//凹函数的极小值把这两行换一下
    else r=rmid-1;
} printf("%lld\n",max(calc(l),calc(r)));

double l,r;
for(int i=0;i<300;i++){
    double lmid=l+(r-l)/3,rmid=r-(r-l)/3;
    if(calc(lmid)<=calc(rmid)) l=lmid;//凹函数的极小值把这两行换一下
    else r=rmid;
} printf("%.6f\n",calc(l));

RMQ

struct RMQ{
    ll fmin[maxn][25],fmax[maxn][25];
    void init(){
        for(int i=1;i<=n;++i) fmin[i][0]=fmax[i][0]=num[i];
        for(int i=1;(1<<i)<=n;++i) for(int j=1;j+(1<<i)-1<=n;++j){
            fmax[j][i]=max(fmax[j][i-1],fmax[j+(1<<(i-1))][i-1]);
            fmin[j][i]=min(fmin[j][i-1],fmin[j+(1<<(i-1))][i-1]);
        }
    }
    ll getmax(int l,int r){
        int k=(int)(log(double(r-l+1))/log((double)2));
        return max(fmax[l][k],fmax[r-(1<<k)+1][k]);
    }
    ll getmin(int l,int r){
        int k=(int)(log(double(r-l+1))/log((double)2));
        return min(fmin[l][k],fmin[r-(1<<k)+1][k]);
    }
    //先输入num[i],再init();
}rmq;

线段树

#define lson rt<<1
#define rson rt<<1|1
#define delf int mid=(l+r)>>1
int tr[maxn<<2],lz[maxn<<2];
void pushup(int rt){
    tr[rt]=max(tr[lson],tr[rson]);
    tr[rt]=min(tr[lson],tr[rson]);
    tr[rt]=tr[lson]+tr[rson];
}
void pushdown(int rt){
    if(!lz[rt]) return;
    lz[lson]+=lz[rt];lz[rson]+=lz[rt];
    tr[lson]+=lz[rt];tr[rson]+=lz[rt];
    lz[rt]=0;
}
void build(int l=1,int r=n,int rt=1){
    if(l==r){tr[rt]=a[l];lz[rt]=0;return;} delf;
    build(l,mid,lson);build(mid+1,r,rson);pushup(rt);
}
void update(int ql,int qr,int val,int l=1,int r=n,int rt=1){
    if(ql<=l&&r<=qr){
        tr[rt]+=val;lz[rt]=val;return;
    } delf; pushdown(rt);
    if(ql<=mid) update(ql,qr,val,l,mid,lson);
    if(mid<qr) update(ql,qr,val,mid+1,r,rson);
    pushup(rt);
}
int query(int ql,int qr,int l=1,int r=n,int rt=1){
    if(ql<=l&&r<=qr) return tr[rt];
    delf; int ans=0; pushdown(rt);
    if(ql<=mid) ans=max(ans,query(ql,qr,l,mid,lson));
    if(mid<qr) ans=max(ans,query(ql,qr,mid+1,r,rson));
    return ans;
}

凸包

struct point{int x,y;}pt[maxn],ans[maxn]; //ans为凸包上的点
int cnt;//cnt为凸包点个数
int cmp(point a,point b){
    if(a.x==b.x) return a.y<b.y;
    return a.x<b.x;
}
int cross(point p0,point p1,point p2){//计算叉积
    return (p1.x-p0.x)*(p2.y-p0.y)-(p1.y-p0.y)*(p2.x-p0.x);
}
double dis(point a,point b){//计算两点距离
    return sqrt(1.0*(a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
void convex(int n){
    sort(pt,pt+n,cmp);
    cnt=0;
    for(int i=0;i<n;i++){//下凸包
        while(cnt>1&&cross(ans[cnt-2],ans[cnt-1],pt[i])<=0) cnt--;
        ans[cnt++]=pt[i];
    }
    int key=cnt;
    for(int i=n-2;i>=0;i--){
        while(cnt>key&&cross(ans[cnt-2],ans[cnt-1],pt[i])<=0) cnt--;
        ans[cnt++]=pt[i];
    }
}

订阅评论
提醒
3 评论
内联反馈
查看所有评论
MaJorie
3 年 前

为什么这小破网站连树状数组求LIS的板子都没有！

回复
MaJorie
3 年 前

为什么这小破网站连拓扑的板子都没有！

回复
关山鸿雁
4 年 前

我什么时候才能变得像郑老师一样优秀啊.jpg

回复