2020年算法入门训练

二分答案

并查集

#include<stdio.h>
#include<stdlib.h>
#include <bits/stdc++.h>
#define fcin freopen("C:/Users/Administrator/Desktop/input.txt","r",stdin)
using namespace std;
typedef long long ll;
const int maxn=2e5+7;
int f[maxn];  //上级数组
int rk[maxn]; //数的高度      
int sz[maxn];    //每个联通块的里元素个数
int mi[maxn],mx[maxn];
int find(int x){    //查找上级
    return f[x]==x?x:f[x]=find(f[x]);
}
void add(int x,int y){ //不是同源,替换
    if((x=find(x))!=(y=find(y))){
        if(x>y){
            f[y]=x,sz[y]+=sz[x];sz[x]=0;
            mi[x]=min(mi[x],mi[y]);    //维护最小值
            mx[x]=max(mx[x],mx[y]);    //维护最大值
        }
        else{
            f[x]=y,sz[x]+=sz[y];sz[y]=0;
            mi[y]=min(mi[y],mi[x]);    //维护最小值
            mx[y]=max(mx[y],mx[x]);    //维护最大值
        }
    }
}
bool IsSame(int x,int y){   //检测连通性
    if(find(x)==find(y))return true;
    return false;
}
void Init(int n){   //初始化f,rk
    for(int i=1;i<=n;i++)f[i]=i,rk[i]=1,sz[i]=1;
}
int main(){
    fcin;
}
/*树层次优化add*/
void add(int x,int y){
    if((x=find(x))!=(y=find(y))){
        if(rk[x]>rk[y])f[y]=x;    //令y的上级的上级为x的上级
        else{
            if(rk[x]==rk[y])rk[y]++;
            f[x]=y;
        }
    }
}

矩阵快速幂

#include<stdio.h>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e6+7;
int mod;
struct Matix{
    static const int _size=2;
    ll m[50][50];
    Matix(){
        memset(m, 0, sizeof(m));
    }
    void InitC(ll a=1){
        for(int i=0;i<_size;++i)m[i][i]=a;
    }
    Matix operator*(const Matix &m2){
        Matix t;
        for (int i = 0; i < _size; ++i)
            for (int j = 0; j < _size; ++j)
                for (int k = 0; k < _size; ++k)
                    t.m[i][j] = (t.m[i][j] + m[i][k] * m2.m[k][j]) % mod;
        return t;
    };
    ll* const operator [] (const int i){
        return m[i];
    }
    Matix operator^(int k) {
         Matix x = *this, ans;
         ans.InitC();        //初始化对角矩阵
         while (k) {
             if (k&1)
                 ans = ans * x;
            x = x * x;
            k >>= 1;
           }
           return ans;
      }
    Matix operator^(char *s){        //10进制快速幂
        Matix g = *this,res;
        res.InitC();
        int len=strlen(s);
        for(int i=len-1;i>=0;--i){
            if(s[i]!='0')res=res*(g^(s[i]-'0'));
            g=g^10;
        }
        return res;
    }
}g, u;
ll x[10];
char n[maxn];
int main(){
    ll a,b,ans=0;
    scanf("%lld%lld%lld%lld",&x[0],&x[1],&a,&b);
    scanf("%s%lld",n,&mod);
    g[0][0]=0,g[0][1]=1,g[1][0]=b,g[1][1]=a;
    u=g^n;      //求g的n次方
    for(int i=0;i<2;i++)ans=(ans+x[i]*u[0][i])%mod;
    printf("%lld\n",ans);
}

素数筛

const int MAX=1e7+7;//求MAX范围内的素数
long long su[MAX],cnt;
bool isprime[MAX];
void prime()
{
    cnt=1;
    memset(isprime,1,sizeof(isprime));//初始化认为所有数都为素数
    isprime[0]=isprime[1]=0;//0和1不是素数
    for(long long i=2;i<=MAX;i++)
    {
        if(isprime[i])
            su[cnt++]=i;//保存素数i
        for(long long j=1;j<cnt&&su[j]*i<MAX;j++)
        {
            isprime[su[j]*i]=0;//筛掉小于等于i的素数和i的积构成的合数
        }
    }
}

//欧拉筛  --线性,效率目前较高切代码量较短的筛法
int p[maxn], check[maxn], tot = 0;
void prime()
{
    check[1]=1;
    check[0]=1;
    for(int i=2;i<maxn;i++)
    {
        if(!check[i])p[++tot]=i;
        for(int j=1;j<=tot&&i*p[j]<maxn;j++)
        {
            check[i*p[j]]=1;
            if(!(i%p[j]))break;//*****关键
        }
    }
}
//埃式筛法
int vis[maxn];
void Prime(){
    mem(vis,0);           //初始化都是素数
    vis[0] = vis[1] = 1;  //0 和 1不是素数
    for (int i = 2; i <maxn; i++) {
        if (!vis[i]) {         //如果i是素数,让i的所有倍数都不是素数
            if(i*i>=maxn)break;    
            for (int j = i*i; j <maxn; j += i) {    //i*i开始比i+i有一定优化
                vis[j] = 1;
            }
        }
    }
}

线段树

#include<stdio.h>
#include<iostream>
using namespace std;
typedef long long ll;
const int maxn=1e5+7;
struct SegTree{
    #define ls rt<<1
    #define rs ls|1
    #define mid ((l+r)>>1)
    ll sum[maxn<<2],lz[maxn<<2];
    void Down(int l,int r,int rt){  // 区间加lazy传递
        if(lz[rt]){
            ll v=lz[rt];
            sum[ls]+=(mid-l+1)*v;
            sum[rs]+=(r-mid)*v;
            lz[ls]+=v;lz[rs]+=v;lz[rt]=0;
        }
    }
    void Build(int l,int r,int rt,ll *a){
        sum[rt]=lz[rt]=0;
        if(l==r){sum[rt]=a[l];return;};
        Build(l,mid,ls,a);
        Build(mid+1,r,rs,a);
        sum[rt]+=sum[ls]+sum[rs];
    }
    //rt l r是一块的,代表当前节点的编号和区间
    //ql qr是你查询的区间
    //可单点修改可区间修改,单点修改就ql=qr
    void Add(int l,int r,int ql,int qr,ll v,int rt){
        if(ql<=l&&r<=qr){
            sum[rt]+=(r-l+1)*v;
            lz[rt]+=v;
            return;
        }
        Down(l,r,rt);
        if(ql<=mid)Add(l,mid,ql,qr,v,ls);
        if(qr>mid)Add(mid+1,r,ql,qr,v,rs);
        sum[rt]=sum[ls]+sum[rs];
    }
    //区间查询
    ll Query(int l,int r,int ql,int qr,int rt){
        if(ql<=l&&r<=qr)return sum[rt];
        Down(l,r,rt);
        ll ans=0;
        if(ql<=mid)ans+=Query(l,mid,ql,qr,ls);
        if(qr>mid)ans+=Query(mid+1,r,ql,qr,rs);
        return ans;
    }

}seg;
ll a[maxn];
char opt[5];
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)scanf("%lld",&a[i]);
    seg.Build(1,n,1,a);
    while(m--){
        int l,r;
        ll v;
        scanf("%s",opt);
        if(opt[0]=='Q'){
            scanf("%d%d",&l,&r);
            printf("%lld\n",seg.Query(1,n,l,r,1));
        }
        else {
            scanf("%d%d%lld",&l,&r,&v);
            seg.Add(1,n,l,r,v,1);
        }
    }
    return 0;
}

树状数组

#include<stdio.h>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+7;
struct BinaryTree{
    int a[maxn];    //原数组
    int tree[maxn],n;
    int d[maxn];    //a[i]*i的树状数组,用于维护区间修改区间查询
    #define lowbit(x) (x&(-x))
    void add(int x,int v){      //单点修改
        while(x<=n)tree[x]+=v,x+=lowbit(x);
    }
    ll query(int x){        //区间查询
        ll sum=0;
        while(x)sum+=tree[x],x-=lowbit(x);
        return sum;
    }
    void Add(int x,int v){  //区间修改版本
        int p=x;
        while(x<=n){
            tree[x]+=v,d[x]+=v*p;
            x+=lowbit(x);
        }
    }
    ll Query(int x){        //区间查询版本
        ll sum=0,p=x;
        while(x){
            sum+=(p+1)*tree[x]-d[x];
            x-=lowbit(x);
        }
        return sum;
    }
}bt,Bt;
int main(){
    scanf("%d",&bt.n);
    for(int i=1;i<=bt.n;i++){
        scanf("%d",&bt.a[i]),bt.add(i,bt.a[i]);
    }
    printf("%lld\n",bt.query(5)-bt.query(2));
    scanf("%d",&Bt.n);
    for(int i=1;i<=Bt.n;i++){
        scanf("%d",&Bt.a[i]),Bt.Add(i,Bt.a[i]),Bt.Add(i+1,-Bt.a[i]);
    }
    int l,r,x;
    scanf("%d%d%d",&l,&r,&x);       //修改区间
    Bt.Add(l,x),Bt.Add(r+1,-x);
    printf("%lld\n",Bt.Query(5)-Bt.Query(2));   //区间查询
    return 0;
}
Last modification:March 8th, 2020 at 11:47 am
如果觉得我的文章对你有用,请随意赞赏