2020年私人训练

1月13日 - 1月15日:二分答案

1月16日 - 1月17日:并查集

#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;
        }
    }
}

1月18日 - 1月19日:矩阵快速幂

#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);
}

1月20日:素数筛

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;
            }
        }
    }
}
Last modification:January 27th, 2020 at 11:30 am
如果觉得我的文章对你有用,请随意赞赏