听说要450+分才能进队。。感觉作为ZJ选手在CQ根本进不了队啊。。2道板子题1道原神题1道语文题，要我考最少跪两道。。

T1 不同的最小割

和ZJOI2011最小割几乎一样，不同的最小割个数为$n-1$，分治后求得，时间复杂度$O(n*maxflow)$似乎人人都闭眼打分治最小割，作为拉原题选手好方啊

#include<bits/stdc++.h>
#define CL(a) memset(a,0,sizeof(a))
#define N 855
#define M 333333
using namespace std;bool v[N];
int n,m,o,i,j,x,y,z,u,p,S,T,Q,fl,tot,L,R,a[N],A[N][N],d[N],fir[N],pre[N],nb[N],la[M],va[M],ne[M],cur[N],q[N],V[N*N];
void ins(int x,int y,int z){
    la[++tot]=y;ne[tot]=fir[x];va[tot]=z;fir[x]=tot;
    la[++tot]=x;ne[tot]=fir[y];va[tot]=0;fir[y]=tot;
}
void dfs(int x){v[x]=1;for(int i=fir[x];i;i=ne[i])if(va[i]&&!v[la[i]])dfs(la[i]);}
void fz(int l,int r){
	if(l==r)return;u=S=a[l];T=a[r];CL(nb);CL(d);CL(pre);CL(v);fl=0;
	for(i=2;i<=tot;i+=4)va[i+2]=va[i]=(va[i]+va[i+1]+va[i+2]+va[i+3])/2,va[i+1]=va[i+3]=0;
	memcpy(cur,fir,sizeof(fir));
    for(nb[0]=n;d[S]<n;){
        if(u==T){
            for(p=1e9,i=S;i!=T;i=la[cur[i]])if(va[cur[i]]<p)p=va[cur[u=i]];
            for(fl+=p,i=S;i!=T;i=la[cur[i]])va[cur[i]]-=p,va[cur[i]^1]+=p;
        }
        for(i=cur[u];i;i=ne[i])if(va[i]&&d[la[i]]+1==d[u])break;
        if(i)cur[u]=i,pre[la[i]]=u,u=la[i];else{
            if(0==--nb[d[u]])break;
            for(i=cur[u]=fir[u],p=n;i;i=ne[i])if(d[la[i]]<p&&va[i])p=d[la[i]];
            ++nb[d[u]=p+1];if(u!=S)u=pre[u];
        }
    }dfs(S);L=l,R=r;
    for(i=1;i<=n;i++)if(v[i])for(j=1;j<=n;j++)if(!v[j])A[i][j]=A[j][i]=min(A[i][j],fl);
    for(i=l;i<=r;i++)if(v[a[i]])q[L++]=a[i];else q[R--]=a[i];
    for(i=l;i<=r;i++)a[i]=q[i];fz(l,L-1);fz(R+1,r);
}
int main(){
	for(scanf("%d%d",&n,&m),i=tot=1;i<=n;i++)a[i]=i;
	for(memset(A,63,sizeof A);m--;ins(x,y,z),ins(y,x,z))scanf("%d%d%d",&x,&y,&z);
	fz(1,n);for(i=1;i<=n;i++)for(j=i+1;j<=n;j++)V[++o]=A[i][j];
	sort(V+1,V+o+1);printf("%d",unique(V+1,V+o+1)-V-1);
}

T2 K远点对

#include<bits/stdc++.h>
#define N 100010
#define Mx(a,b)(a<b?a=b:a)
#define Mi(a,b)(a>b?a=b:a)
#define inf 2147483647ll*2147483647
using namespace std;typedef long long LL;LL A,E[N];int n,k,i,j,t,e,o,O,rt,q[N];
struct W{int x,y;LL z;}p[N];bool cp(W a,W b){return a.z>b.z;}
struct P{int l,r,d[2],mi[2],mx[2];}T[N];bool cmp(P a,P b){return a.d[O]<b.d[O]||a.d[O]==b.d[O]&&a.d[O^1]<b.d[O^1];}
LL S(int x){return 1ll*x*x;}LL D(int a,int b){return S(T[a].d[0]-T[b].d[0])+S(T[a].d[1]-T[b].d[1]);}
LL md(P k){return S(max(max(T[i].d[0]-k.mi[0],k.mx[0]-T[i].d[0]),0))+S(max(max(T[i].d[1]-k.mi[1],k.mx[1]-T[i].d[1]),0));}
int bt(int l,int r,int o){
    O=o;int k=l+r>>1,i,u;nth_element(T+l+1,T+k+1,T+r+1,cmp);for(i=0;i<2;i++)T[k].mi[i]=T[k].mx[i]=T[k].d[i];
    if(l<k)for(u=T[k].l=bt(l,k-1,o^1),i=0;i<2;i++)Mi(T[k].mi[i],T[u].mi[i]),Mx(T[k].mx[i],T[u].mx[i]);
    if(k<r)for(u=T[k].r=bt(k+1,r,o^1),i=0;i<2;i++)Mi(T[k].mi[i],T[u].mi[i]),Mx(T[k].mx[i],T[u].mx[i]);
    return k;
}
void qu(int k){
	LL d=D(k,i),dl=-inf,dr=-inf;
	if(d>A)A=d,o=k;if(T[k].l)dl=md(T[T[k].l]);if(T[k].r)dr=md(T[T[k].r]);
	if(dl>dr){if(dl>A)qu(T[k].l);if(dr>A)qu(T[k].r);}else{if(dr>A)qu(T[k].r);if(dl>A)qu(T[k].l);}
}
int main(){
	for(scanf("%d%d",&n,&k),i=1;i<=n;i++)scanf("%d%d",&T[i].d[0],&T[i].d[1]);
	for(rt=bt(1,n,0),i=1;i<=n;i++)A=o=0,qu(rt),p[i]=W{i,o,A};
	for(sort(p+1,p+n+1,cp),i=1;i<=min(k*2,n);i++)q[++t]=p[i].x,q[++t]=p[i].y;
	for(sort(q+1,q+t+1),o=unique(q+1,q+t+1)-q-1,i=1;i<=o;i++)for(j=i+1;j<=o;j++)E[++e]=D(q[i],q[j]);
	sort(E+1,E+e+1);printf("%lld",E[e-k+1]);
}

数位DP，$f[i][x][y][A][B][C][D]$表示第$i$位，前一个数是$x$，前第二个数是$y$，是否出现连续三个，是否出现$4$，是否出现$8$，是否比当前数大的方案数。使用记忆化搜索可以无脑转移。

#include<bits/stdc++.h>
#define CL(a) memset(a,0,sizeof a)
typedef long long LL;int i,j,t,q[22];LL V,L,R,f[13][10][10][2][2][2][3];bool v[13][10][10][2][2][2][3];
LL dp(int k,int x,int y,int A,int B,int C,int D){
	if(k==1)return x&&A&&!(B&&C)&&!D;
	if(v[k][x][y][A][B][C][D])return f[k][x][y][A][B][C][D];v[k][x][y][A][B][C][D]=1;
	for(int i=0;i<10;i++)f[k][x][y][A][B][C][D]+=dp(k-1,i,x,A|(i==x&&x==y),B|(i==4),C|(i==8),D?i>=q[13-k]:i>q[13-k]);
	return f[k][x][y][A][B][C][D];
}
LL G(LL x){
	if(x<1e10)x=1e10,V=-1;else V=0;for(t=0;x;x/=10)q[++t]=x%10;CL(f);CL(v);
	for(i=0;i<10;i++)V+=dp(11,i,i^1,0,i==4,i==8,i>q[1]);return V;
}
int main(){scanf("%lld%lld",&L,&R);printf("%lld",G(R)-G(L-1));}

T4 密钥破解

通过泼辣的肉求出r后可以通过扩欧轻易求出$d$，通过快速幂轻易求出$n$，为了水一发经验抄了发泼辣的肉。。为什么别人泼辣的肉都这么短。。拉板选手表示十分羞愧

#include<bits/stdc++.h>
typedef long long LL;int i,t;LL e,c,n,d,y,R,q[8];
LL mul(LL a,LL b,LL p){LL v=0;for(;b;a=(a+a)%p,b>>=1)if(b&1)v=(v+a)%p;return v;}
LL pw(LL a,LL b,LL p){LL v=1;for(a%=p;b;a=mul(a,a,p),b>>=1)if(b&1)v=mul(v,a,p);return v;}
void ex(LL a,LL b,LL&x,LL&y){if(!b){x=1;y=0;return;}ex(b,a%b,y,x);y-=a/b*x;}
LL G(LL a,LL b){if(!a)return 1;if(a<0)return G(-a,b);LL t;for(;b;)t=a%b,a=b,b=t;return a;}
bool ck(LL a,LL n,LL x,LL t){
	LL V=pw(a,x,n),la=V,i;
	for(i=1;i<=t;la=V,i++)if(V=mul(V,V,n),V==1&&la!=1&&la!=n-1)return 1;
	return V!=1;
}
bool mr(LL n){
	if(n<2)return 0;if(n==2)return 1;if(n%2==0)return 0;LL x=n-1,t=0,i;for(;x%2==0;x>>=1)t++;
	for(i=20;i;i--)if(ck(rand()%(n-1)+1,n,x,t))return 0;return 1;
}
LL pr(LL x,LL c){
    LL i=1,k=2,x0=rand()%x,y=x0,d;
    for(;i++;){
        x0=(mul(x0,x0,x)+c)%x;d=G(y-x0,x);
        if(d!=1&&d!=x)return d;if(y==x0)return x;
        if(i==k)y=x0,k+=k;
    }
}
void ff(LL n){
	if(mr(n)){q[++t]=n;return;}
	LL p=n;for(;p>=n;)p=pr(p,rand()%(n-1)+1);
	ff(p);ff(n/p);
}
int main(){
	srand(23333);scanf("%lld%lld%lld",&e,&n,&c);ff(n);
	R=(q[1]-1)*(q[2]-1);ex(e,R,d,y);if(d<0)d+=R;printf("%lld %lld",d,pw(c,d,n));
}

T5 路由表

直接把所有点加到Tire里，由于没有重复，于是可以每次暴力得到询问Tire链上每个点出现的时间，然后单调扫一遍判断就可以了，时间复杂度$O(32n)$。读了半小时题TAT

#include<bits/stdc++.h>
#define N 1111111
using namespace std;typedef unsigned int U;char s[9];int Q,A,B,C,D,L,R,u,o,t,i,id,di,q[33],c[N][26],V[N];U x;
char ch;void G(int&x){for(ch=getchar();ch<'0'||ch>'9';ch=getchar());for(x=0;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';}
int main(){
	for(scanf("%d",&Q);Q--;)
		if(scanf("%s",s),s[0]=='A'){
			G(A);G(B);G(C);G(D);G(L);x=(U)A*16777216+B*65536+C*256+D;
			for(u=0,i=31;i>=32-L;u=c[u][o],i--)if(!c[u][o=x>>i&1])c[u][o]=++id;V[u]=++di;
		}else{
			G(A);G(B);G(C);G(D);G(L);G(R);x=(U)A*16777216+B*65536+C*256+D;
			for(u=t=0,i=31;~i;i--){
				if(V[u=c[u][o=x>>i&1]]&&V[u]<=R){for(;t&&q[t]>V[u];t--);q[++t]=V[u];
				}if(!u)break;
			}printf("%d\n",lower_bound(q+1,q+t+1,L)-q+t+1);
		}
}

T6 仿光滑数

#include<bits/stdc++.h>
using namespace std;typedef long long LL;LL n,o;int k,i,j,t,p[66];bool f[133];struct P{LL V;int x,y,z;bool operator<(P a)const{return a.V>V;}}w;priority_queue<P>Q;
int main(){
	for(scanf("%lld%d",&n,&k),i=2;i<128;i++){if(!f[i])p[++t]=i;for(j=i;j<128;j+=i)f[j]=1;}
	for(i=1;i<=t;i++)for(o=1,j=0;o*p[i]<=n;Q.push(P{o,j,i-1,i}))o*=p[i],j++;
	for(;k--;)if(w=Q.top(),Q.pop(),w.x-1)for(i=w.y;i;i--)Q.push(P{w.V/p[w.z]*p[i],w.x-1,i,w.z});
	printf("%lld",w.V);
}

• 相关文章推荐
• 全局相关文章