算法竞赛程序模板 – Zechel

Biginteger大整数加乘模板

#include <bits/stdc++.h>
using namespace std;
struct BigInteger{
    const static int MOD = 10000;
    const static int DLEN = 4;

    int a[600], len;

    BigInteger()
    {
        memset(a, 0, sizeof(a));
        len = 1;
    }
    BigInteger(int v)
    {
        memset(a, 0, sizeof(a));
        len = 0;
        do
        {
            a[len++] = v%MOD;
            v /= MOD;
        }while(v);
    }
    BigInteger(const char s[])
    {
        memset(a, 0, sizeof(a));
        int L = strlen(s);
        len = L/DLEN;
        if(L%DLEN) len++;
        int idx = 0;
        for(int i = L - 1; i >= 0; i -= DLEN)
        {
            int t = 0;
            int k = i - DLEN + 1;
            if(k < 0) k = 0;
            for(int j = k;j <= i;j++)
                t = t*10 + s[j] - '0';
            a[idx++] = t;
        }
    }
    BigInteger operator + (const BigInteger &b) const
    {
        BigInteger res;
        res.len = max(len, b.len);
        for(int i = 0; i <= res.len; ++i)
            res.a[i] = 0;
        for(int i = 0; i < res.len; ++i)
        {
            res.a[i] += ((i < len)?a[i]:0)+((i < b.len)?b.a[i]:0);
            res.a[i+1] += res.a[i]/MOD;
            res.a[i] %= MOD;
        }
        if(res.a[res.len] > 0)res.len++;
        return res;
    }
    BigInteger operator * (const BigInteger &b) const
    {
        BigInteger res;
        for(int i = 0; i < len;i++)
        {
            int up = 0;
            for(int j = 0;j < b.len;j++)
            {
                int temp = a[i]*b.a[j] + res.a[i+j] + up;
                res.a[i+j] = temp%MOD;
                up = temp/MOD;
            }
            if(up != 0)
                res.a[i + b.len] = up;
        }
    res.len = len + b.len;
    while(res.a[res.len - 1] == 0 &&res.len > 1)res.len--;
    return res;
    }
    void output()
    {
        printf("%d",a[len-1]);
        for(int i = len-2;i >=0 ;i--)
            printf("%04d",a[i]);
        printf("\n");
    }
};
int main()
{
    char s1[] = "1012315431";
    char s2[] = "1215564813";
    BigInteger bi1(s1);
    BigInteger bi2(s2);
    BigInteger bi3 = bi1 + bi2;
    BigInteger bi4 = bi1*bi2;
    bi3.output();
    cout<<endl;
    bi4.output();
    return 0;
}

最长上升子序列

#include <bits/stdc++.h>
#define maxn 100005
#define INF 1000000005
using namespace std;
int vis[maxn];
int main()
{
    int n;
    scanf("%d",&n);
    fill(vis,vis+maxn,INF);
    for(int i=0;i<n;i++)
    {
        int A;
        scanf("%d",&A);
        *lower_bound(vis,vis+n,A)=A;
    }
    int len=lower_bound(vis,vis+n,INF)-vis;
}

线性筛求欧拉函数

#include <bits/stdc++.h>
#define maxn 1005
using namespace std;
int check[maxn];
int prime[maxn];
int tot=0;
int phi[maxn];
int solve(int n)
{
    memset(check,0,sizeof(check));
    memset(prime,0,sizeof(prime));
    memset(phi,0,sizeof(phi));
    tot=0;
    for(int i=2;i<=n;i++)
    {
        if(!check[i])
        {
            prime[tot]=i;
            tot++;
            phi[i]=i-1;
        }
        for(int j=0;j<tot&&prime[j]*i<=n;j++)
        {
            check[i*prime[j]]=1;
            phi[i*prime[j]]=phi[i]*(i%prime[j]?prime[j]-1:prime[j]);
            if(i%prime[j]==0)break;
        }
    }
    int sum=0;
    for(int i=2;i<=n;i++)sum+=phi[i];
    return sum;
}
int main()
{
    int C,n;
    scanf("%d",&C);
    for(int i=1;i<=C;i++)
    {
        scanf("%d",&n);
        cout<<i<<" "<<n<<" ";
        int ans=0;
        ans=solve(n);
        ans=3+2*ans;
        cout<<ans<<endl;
    }
}

拓展中国剩余定理+exgcd+快乘

#include <bits/stdc++.h>
#define maxn 1000005
using namespace std;
typedef long long ll;
ll a[maxn],b[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,x,y);
    ll z=x;
    x=y;
    y=z-y*(a/b);
    return d;
}
ll mul(ll a,ll b,ll mod)
{
    ll res=0;
    while(b>0)
    {
        if(b&1) res=(res+a)%mod;
        a=(a+a)%mod;
        b>>=1;
    }
    return res;
}
ll china()
{
    ll x,y,k;
    ll M=a[1],ans=b[1];
    for(int i=2;i<=n;i++)
    {
        ll k=M,m=a[i];
		ll c=((b[i]-ans)%m+m)%m;
        ll d=exgcd(k,m,x,y);
		ll thea=m/d;
        if(c%d!=0) 
        {
        	return -1; 
		}
        x=mul(x,c/d,thea);
        ans+=x*M;
        M*=thea;
        ans=(ans%M+M)%M;
    }
    return (ans%M+M)%M;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld %lld",&a[i],&b[i]);
    }
    ll ans=china();
    printf("%lld",ans);
}

哈希求后缀数组

#include <bits/stdc++.h>
#define maxn 300005
using namespace std;
unsigned long long f[maxn],p[maxn];
char s[maxn];
int SA[maxn];
int len;
void pre()
{
    p[0]=1;
    memset(f,0,sizeof(f));
    for(int i=1;i<=len;i++)
    {
        f[i]=f[i-1]*131+(s[i]-'a'+1);
        p[i]=p[i-1]*131;
    }
}
int getlen(int X,int Y)
{
    int x=max(X,Y),y=min(X,Y);
    int L=1,R=len-y+1,ans=0;
    while(L<=R)
    {
        int mid=(L+R)/2;
        if(mid>=1&&x+mid-1<=len&&y+mid-1<=len&&(f[x+mid-1]-f[x-1]*p[mid]==f[y+mid-1]-f[y-1]*p[mid]))
        {
            ans=mid;
            L=mid+1;
        }
        else R=mid-1;
    }
    return ans;
}
bool cmp(int x,int y)
{
    int k=getlen(x,y);
    return s[x+k]<s[y+k];
}
int main()
{
    scanf("%s",s+1);
    len=strlen(s+1);
    pre();
    for(int i=1;i<=len;i++)SA[i]=i;
    sort(SA+1,SA+len+1,cmp);
    for(int i=1;i<=len;i++)printf("%d ",SA[i]-1);
    printf("\n");
    for(int i=1;i<=len;i++)
    {
        if(i==1){printf("0 ");continue;}
        int d=getlen(SA[i],SA[i-1]);
        printf("%d ",d);
    }
}

单高精度乘除法

#include <bits/stdc++.h>
using namespace std;
struct imf
{
    int x,y;
    int sum;
}num[1005];
int cmp(imf a,imf b)
{
    return a.sum<b.sum;
}
int one[20000]={0},two[20000]={0},re[20000]={0};
int len=1,t=0,r=0;
void mul(int x)
{
    int f=0;
    len+=6;
    for(int i=0;i<len;i++)
    {
        int k=one[i]*x+f;
        one[i]=k%10;
        f=k/10;
    }
    while(one[len])len--;
}
void cut(int y)
{
    for(int i=t;i>=0;i--)
    {
        if(i>=1)two[i-1]+=((two[i]%y)*10);
        two[i]/=y;
    }
    while(two[t]==0)t--;
}
int check()
{
    if(t>r)
    {
        return 1;
    }
    else if(t==r)
    {
        for(int u=r;u>=0;u--)
        {
            if(two[u]>re[u])
            {
                return 1;
            }
            else if(two[u]<re[u])
            {
                return 0;
            }
        }
        return 0;
    }
    else if(t<r)
    {
        return 0;
    }
}
int main()
{
    int n;
    cin>>n;
    int a,b;
    cin>>a>>b;
    for(int i=0;i<n;i++)
    {
        cin>>num[i].x>>num[i].y;
        num[i].sum=num[i].x*num[i].y;
    }
    sort(num,num+n,cmp);
    one[0]=1;
    mul(a);
    for(int j=0;j<n;j++)
    {
        memcpy(two,one,sizeof(one));
        t=len;
        cut(num[j].y);
        if(check())
        {
            memcpy(re,two,sizeof(two));
            r=t;
        }
        mul(num[j].x);
    }
    for(int i=r;i>=0;i--)
    {
        cout<<re[i];
    }
}

埃氏筛区间素数

#include <bits/stdc++.h>
using  namespace std;
long long L,R;
int num[50005]={0},prime[50005];
int tot=0;
int re[1000005]={0};
void generator()
{
    for(int i=2;i<=50000;i++)
    {
        if(!num[i])
        {
            prime[tot]=i;
            tot++;
        }
        for(int j=0;j<tot&&i*prime[j]<=50000;j++)
        {
            num[i*prime[j]]=1;
            if(i%prime[j]==0)break;
        }
    }
} 
int main()
{
    cin>>L>>R;
    generator();
    for(int i=0;i<tot;i++)
    {
        for(long long j=max(2ll,(L-1)/prime[i]+1)*prime[i];j<=R;j+=prime[i])
        {
            re[j-L]=1;
        }
    }
    long long ans=0;
    for(long long k=L;k<=R;k++)
    {
        if(!re[k-L])ans++;
    }
    cout<<ans;
}

SPFA算法求负环

#include <bits/stdc++.h>
#define INF 100000000
#define len 505
using namespace std;
struct imf
{
	int to,val;
};
int n;
vector<imf>Q[len];
queue<int>G;
int d[len];
int v[len]={0};
int pl[len]={0};
void SPFA()
{
	while(!G.empty())G.pop();
	int check=0;
	G.push(1);
	d[1]=0;
	pl[1]++;
	while(!G.empty())
	{
		int tmp=G.front();
		G.pop();
		v[tmp]=0;
		for(int i=0;i<Q[tmp].size();i++)
		{
			int x=Q[tmp][i].to,y=Q[tmp][i].val;
			if(d[x]>d[tmp]+y)
			{
				d[x]=d[tmp]+y;
				if(!v[x])
				{
					G.push(x);
					v[x]=1;
					pl[x]++;
					if(pl[x]>=n)check=1;    //每个点入栈次数不能超过n-1次,否则有负环
				}
			}
			if(check)break;
		}
		if(check)break;
	}
	if(check)cout<<"YES"<<endl;
	else cout<<"NO"<<endl;
}
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		memset(Q,0,sizeof(Q));
		memset(v,0,sizeof(v));
		memset(pl,0,sizeof(pl));
		fill(d,d+len,INF);
		int m,w,S,E,T;
		scanf("%d %d %d",&n,&m,&w);
		for(int i=0;i<m;i++)
		{
			scanf("%d %d %d",&S,&E,&T);
			Q[S].push_back((imf){E,T});
			Q[E].push_back((imf){S,T});
		}
		for(int i=0;i<w;i++)
		{
			scanf("%d %d %d",&S,&E,&T);
			Q[S].push_back((imf){E,-T});
		}
		SPFA();
	}
}

Lucas定理+组合数+线性求乘法逆元

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 4e4;
int mod = 999911659;
int n,q,jc[N],jcinv[N],inv[N];
int pow(int a,int b,int p)
{
    int res = 1;
    for(;b;b >>= 1)
    {
        if(b&1)res = (LL)res * a % p;
        a = (LL)a * a % p;
    }
    return res;
}

void init(int p)
{
    jcinv[0] = jcinv[1] = inv[1] = jc[1] = jc[0] = 1;
    for(int i = 2;i <= p;i ++)
    {
        inv[i]=(LL)(p-p/i)*inv[p%i]%p;
        jcinv[i] = jcinv[i-1] * inv[i] % p;
        jc[i] =(LL)jc[i-1] * i % p;
    }
}

int C(int x,int y,int p)
{
    if(y > x)return 0;
    return (LL)jc[x]*jcinv[y]*jcinv[x-y]%p;
}

int lucas(int x,int y,int p)
{
    if(y == 0)return 1;
    return (LL)C(x%p,y%p,p) * lucas(x/p,y/p,p) % p;
}

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注

川公网安备 51130202000337号