首页 > 代码库 > Moscow Pre-Finals Workshop 2016. National Taiwan U Selection

Moscow Pre-Finals Workshop 2016. National Taiwan U Selection

A. As Easy As Possible

每个点往右贪心找最近的点,可以得到一棵树,然后倍增查询即可。

时间复杂度$O((n+m)\log n)$。

#include <bits/stdc++.h>using namespace std ;typedef long long LL ;typedef long long Int ;typedef pair < int , int > pi ;#define clr(a,x) memset ( a , x , sizeof a ) char s[100020];int a[100020];int n;int nxt[100020][4];int dp[18][100020];int cg(char c){	if(c==‘e‘)return 0;	if(c==‘a‘)return 1;	if(c==‘s‘)return 2;	return 3;}void prepare(){	int cur[4];	for(int i=0;i<n;i++)a[i]=cg(s[i]);	for(int i=0;i<4;i++)cur[i]=n;	for(int i=n-1;i>=0;i--){		cur[a[i]]=i;		for(int j=0;j<4;j++){			nxt[i][j]=cur[j];		}	}	for(int i=0;i<4;i++)nxt[n][i]=n;	for(int i=0;i<n;i++){		int cur=nxt[i][0];		for(int it2=1;it2<4;it2++){			cur=nxt[cur][(it2)%4];		}		dp[0][i]=cur;	}	for(int it=1;(1<<it)<=n;it++){		for(int i=0;i<n;i++)dp[it][i]=n;		int len=1<<it;		for(int i=0;i<n;i++){			int to=dp[it-1][i]+1;			if(to>=n){dp[it][i]=n;continue;}			dp[it][i]=dp[it-1][to];		}	}	/*	for(int i=0;(1<<i)<=n;i++){		for(int j=0;j<n;j++)printf("%d ",dp[i][j]);puts("");	}	*/}int main(){	scanf("%s",s);		n=strlen(s);	prepare();	int q;	scanf("%d",&q);	while(q--){		int l,r;scanf("%d%d",&l,&r);		l--,r--;		int ans=0;		int cur=l;		int maxx=0;while((1<<maxx)<=n)maxx++;		maxx--;		//printf("maxx=%d\n",maxx);		for(int i=maxx;i>=0&&l<=r;i--){			if(dp[i][l]<=r){			//	printf("l=%d dp=%d\n",l,dp[i][l]);				ans|=1<<i;				l=dp[i][l]+1;				continue;			}		}		printf("%d\n",ans);		}	return 0;}

  

B. Be Friends

从高位到低位依次考虑,对于每一位,按这一位将数字分成两个集合,显然这两个集合要优先连边,那么只需要找到横跨这两个集合的最小的边即可,用Trie完成查询。

时间复杂度$O(n\log^2m)$。

#include<cstdio>#include<algorithm>const int N=100010,M=N*32;int n,i,a[N],q[N],son[M][2],tot;long long ans;inline void ins(int p){  for(int o=29,x=0;~o;o--){    int w=p>>o&1;    if(!son[x][w])son[x][w]=++tot;    x=son[x][w];  }}inline int ask(int p){  int t=0;  for(int o=29,x=0;~o;o--){    int w=p>>o&1;    if(son[x][w])x=son[x][w];else x=son[x][w^1],t|=1<<o;  }  return t;}void solve(int o,int l,int r){  if(o<0||l>r)return;  int L=l-1,R=r+1;  for(int i=l;i<=r;i++)if(a[i]>>o&1)q[++L]=a[i];else q[--R]=a[i];  for(int i=l;i<=r;i++)a[i]=q[i];  solve(o-1,l,L),solve(o-1,R,r);  if(l>L||R>r)return;  for(int i=l;i<=L;i++)ins(a[i]);  int ret=~0U>>1;  for(int i=R;i<=r;i++)ret=std::min(ret,ask(a[i]));  ans+=ret;  for(int i=0;i<=tot;i++)son[i][0]=son[i][1]=0;  tot=0;}int main(){  scanf("%d",&n);  for(i=1;i<=n;i++)scanf("%d",&a[i]);  solve(29,1,n);  printf("%lld",ans);  return 0;}

  

C. Coprime Heaven

留坑。

 

D. Drawing Hell

游戏的最终局面一定是一个三角剖分,因此边数只与凸包上的点数有关,判一下奇偶性即可。

 

E. Easiest Game

合法的$(r,s)$需要满足:

1.$r+s\leq\min(n,m)$

2.$\gcd(r,s)=1$

3.$r\bmod 2\neq s\bmod 2$

4.$\max(r,s)\leq\lfloor\frac{\max(n,m)}{2}\rfloor$

假设没有互质的限制,那么可以直接$O(1)$算出答案$f(n,m)$,加上限制之后$ans=\sum_{d}\mu(d)f(\lfloor\frac{n}{d}\rfloor,\lfloor\frac{m}{d}\rfloor)$,分段计算即可。

时间复杂度$O(n+T\sqrt{n})$。

#include<stdio.h>#include<algorithm>#include<math.h>#include<string.h>#include<string>#include<vector>#include<set>#include<map>#include<queue>#include<time.h>#include<assert.h>#include<iostream>using namespace std;typedef long long LL;typedef pair<int,int>pi;const int Maxp=10000002;int pri[3000020],cntp;bool isp[Maxp];int miu[Maxp],sum[Maxp];int realans;void precal(){	for(int i=2;i<Maxp;i++){		if(!isp[i]){pri[cntp++]=i;miu[i]=-1;}		for(int j=0;j<cntp;j++){			if(1LL*pri[j]*i>=Maxp)break;			isp[pri[j]*i]=1;			if(i%pri[j]){				miu[i*pri[j]]=-miu[i];			}			else{				miu[i*pri[j]]=0;				break;			}		}	}	sum[1]=1;	for(int i=2;i<Maxp;i++){		sum[i]=sum[i-1];		if(i&1)sum[i]+=miu[i];	}}int n,m;int done[111][111];bool has[111][111];int cnt[111][111];int di[4][2]={{1,1},{1,-1},{-1,1},{-1,-1}};bool ok(int x,int y){	return x>=1&&x<=n&&y>=1&&y<=m;	}bool check(int dx,int dy){	memset(done,0,sizeof done);	queue<pi>q;	done[1][1]=1;q.push(pi(1,1));	while(!q.empty()){		pi u=q.front();q.pop();		int x=u.first,y=u.second;		for(int i=0;i<4;i++){			int nx=x+dx*di[i][0],ny=y+dy*di[i][1];			if(ok(nx,ny)&&!done[nx][ny]){done[nx][ny]=1;q.push(pi(nx,ny));}		}		for(int i=0;i<4;i++){			int nx=x+dy*di[i][0],ny=y+dx*di[i][1];			if(ok(nx,ny)&&!done[nx][ny]){done[nx][ny]=1;q.push(pi(nx,ny));}		}	}	bool flag=1;	for(int i=1;i<=n&&flag;i++)for(int j=1;j<=m&&flag;j++)if(!done[i][j]){flag=0;break;}	return flag;}bool should(int x,int y){	if(x>y)swap(x,y);	return ((x+y)<=min(n,m))&&(__gcd(x,y)==1)&&((x%2)!=(y%2))&&(max(x,y)<=max(n,m)/2);}void solve(){	vector<pi>rep;	memset(has,0,sizeof has);	for(int i=1;i<=max(n,m);i++){		for(int j=1;j<=max(n,m);j++){			if(check(i,j)){				//printf("i=%d j=%d\n",i,j);				realans++;				has[i][j]=1;				rep.push_back(pi(i,j));			}			//if(should(i,j)!=has[i][j])printf("wax=%d y=%d hasval=%d\n",i,j,has[i][j]);		}	}	//printf("ans[%d][%d]=\n",n,m);	//for(pi u:rep)printf("%d %d\n",u.first,u.second);}LL cal(int st,int ed,int del){	if(st>ed)return 0;	int n=(ed-st)/del+1;	ed=st+(n-1)*del;	return 1LL*(st+ed)*n/2;}LL f(int A,int B){	LL ret=0;	if(A-1<=B){		ret=cal(2,A-1,2);//2+4+...+A-1	}	else{		ret=cal(2,B,2);		if((A-B+B)&1)ret+=cal(2*B-A+1,B-1,2);		else ret+=cal(2*B-A+2,B-1,2);	}	return ret;	}LL go(int n,int m){	if(n==1&&m==1)return 1;	if(n>m)swap(n,m);	int A=n,B=m/2;	LL ret=0;	for(int g=1,ng;g<=B&&g<=A;g=ng+1){		int val1=A/g,val2=B/g;		ng=min(A/val1,B/val2);		ret+=1LL*(sum[ng]-sum[g-1])*f(val1,val2);		//printf("g=%d ret=%lld val1=%d val2=%d\n",g,ret,val1,val2);	}	return ret/2;	return ret;}int main(){	/*	int LIM=100;	for(n=1;n<=LIM;n++)		for(m=n;m<=LIM;m++){solve();}	puts("ok");	*/	/*	for(int i=1;i<=LIM;i++){		for(int j=1;j<=LIM;j++){			printf("%2d ",cnt[min(i,j)][max(i,j)]);		}		puts("");	}	*/	precal();	int _;scanf("%d",&_);	while(_--){		scanf("%d%d",&n,&m);//	for(n=1;n<=100;n++)//		for(m=1;m<=100;m++){		LL ans=go(n,m);		printf("%lld\n",ans);		//realans=0;		//solve();		//if((realans+1)/2!=ans){printf("wan=%d wam=%d\n",n,m);while(1);}		//printf("real=%d\n",(realans+1)/2);	}	return 0;}

  

F. Fibonacci of Fibonacci

打表可以发现循环节为$26880696$,然后直接用矩阵快速幂计算答案即可。

#include<cstdio>#define rep(i) for(int i=0;i<2;i++)int T,n,P;struct mat{  int v[2][2];  mat(){rep(i)rep(j)v[i][j]=0;}  mat operator*(const mat&b){    mat c;    rep(i)rep(j)rep(k)c.v[i][j]=(1LL*v[i][k]*b.v[k][j]+c.v[i][j])%P;    return c;  }}G,B;int fib(int n,int p){  P=p;  G=B=mat();  G.v[0][1]=G.v[1][0]=G.v[1][1]=B.v[1][0]=1;  for(;n;n>>=1,G=G*G)if(n&1)B=G*B;  return B.v[0][0];}int main(){  scanf("%d",&T);  while(T--)scanf("%d",&n),printf("%d\n",fib(fib(n,26880696),20160519));  return 0;}

  

G. Global Warming

留坑。

 

H. Hash Collision

设$f[i][j]$表示长度为$i$的串中Hash值为$j$的方案数,那么$ans=\sum_{i=0}^{m-1}C(f[n][i],2)$。

从$f[i][]$转移到$f[i+1][]$的复杂度为$O(26)$,而从$f[i][]$转移到$f[2i][]$可以用FFT做到$O(m\log m)$,因此倍增计算$f[n][]$即可。

时间复杂度$O(m\log m\log n)$。

#include<cstdio>#include<cmath>#include<algorithm>using namespace std;const int N=65555,P=1000003,M=1000;int n,i,j,k,pos[N],f[N],g[N],seed,m,ans;int A[N],B[N],C[N];namespace FFT{struct comp{	double r,i;comp( double _r=0, double _i=0){r=_r,i=_i;}	comp operator+(const comp&x){return comp(r+x.r,i+x.i);}	comp operator-(const comp&x){return comp(r-x.r,i-x.i);}	comp operator*(const comp&x){return comp(r*x.r-i*x.i,r*x.i+i*x.r);}	comp conj(){return comp(r,-i);}}A[N],B[N];int a0[N],b0[N],a1[N],b1[N];const double pi=acos(-1.0);void FFT(comp*a,int n,int t){	for(int i=1;i<n;i++)if(i<pos[i])swap(a[i],a[pos[i]]);	for(int d=0;(1<<d)<n;d++){		int m=1<<d,m2=m<<1;		double o=pi*2/m2*t;comp _w(cos(o),sin(o));		for(int i=0;i<n;i+=m2){			comp w(1,0);			for(int j=0;j<m;j++){				comp&A=a[i+j+m],&B=a[i+j],t=w*A;				A=B-t;B=B+t;w=w*_w;			}		}	}	if(t==-1)for(int i=0;i<n;i++)a[i].r/=n;}void mul(int*a,int*b,int*c){	int i,j;	for(i=0;i<k;i++)A[i]=comp(a[i],b[i]);	FFT(A,k,1);	for(i=0;i<k;i++){		j=(k-i)&(k-1);		B[i]=(A[i]*A[i]-(A[j]*A[j]).conj())*comp(0,-0.25);	}	FFT(B,k,-1);	for(i=0;i<k;i++)c[i]=((long long)(B[i].r+0.5))%P;}void mulmod(int*a,int*b,int*c){	int i;	for(i=0;i<k;i++)a0[i]=a[i]/M,b0[i]=b[i]/M;	for(mul(a0,b0,a0),i=0;i<k;i++){		c[i]=1LL*a0[i]*M*M%P;		a1[i]=a[i]%M,b1[i]=b[i]%M;	}	for(mul(a1,b1,a1),i=0;i<k;i++){		c[i]=(a1[i]+c[i])%P,a0[i]=(a0[i]+a1[i])%P;		a1[i]=a[i]/M+a[i]%M,b1[i]=b[i]/M+b[i]%M;	}	for(mul(a1,b1,a1),i=0;i<k;i++)c[i]=(1LL*M*(a1[i]-a0[i]+P)+c[i])%P;}}int cnt,q[55];int main(){	scanf("%d%d%d",&n,&m,&seed);	for(k=1;k<m;k<<=1);k<<=1;	j=__builtin_ctz(k)-1;	for(i=0;i<k;i++)pos[i]=pos[i>>1]>>1|((i&1)<<j);	int len=1;	//for(i=0;i<m;i++)printf("%d ",f[i]);puts("");	while(n)q[++cnt]=n&1,n>>=1;	for(j=‘A‘;j<=‘Z‘;j++)f[j%m]++;	for(int o=cnt-1;o;o--){		for(i=0;i<k;i++)A[i]=B[i]=0;		int mul=1;		for(i=0;i<len;i++)mul=1LL*mul*seed%m;		for(i=0;i<m;i++){			A[1LL*i*mul%m]=(A[1LL*i*mul%m]+f[i])%P;			B[i]=f[i];		}		len<<=1;		FFT::mulmod(A,B,C);		for(i=0;i<m;i++)f[i]=0;		for(i=0;i<k;i++)f[i%m]=(f[i%m]+C[i])%P;		if(q[o]){			for(i=0;i<m;i++)g[i]=0;			for(i=0;i<m;i++)if(f[i])for(j=‘A‘;j<=‘Z‘;j++)g[(1LL*i*seed+j)%m]=(g[(1LL*i*seed+j)%m]+f[i])%P;			for(i=0;i<m;i++)f[i]=g[i];			len++;		}	}	for(i=0;i<m;i++)ans=(1LL*f[i]*(f[i]-1+P)+ans)%P;	ans=1LL*ans*((P+1)/2)%P;	printf("%d",ans);	return 0;}

  

I. Increasing or Decreasing

经典数位DP。

#include <bits/stdc++.h>using namespace std ;typedef long long LL ;typedef pair < int , int > pi ;#define clr(a,x) memset ( a , x , sizeof a ) typedef long long Int ;int dp[20][3][10][2];int num[22];int dfs(int cur,int dd,int bef,int qd){	if(cur<0)return 1;	int &t=dp[cur][dd][bef][qd];	if(t>=0)return t;	t=0;	for(int i=0;i<10;i++){		if((dd==1)&&(i>bef)&&qd)continue;		if((dd==2)&&(i<bef)&&qd)continue;		int ndd;		int nqd=qd||(i>0);		if(qd==0)ndd=0;		else{			if(i<bef)ndd=1;			else if(i>bef)ndd=2;			else ndd=dd;		}		t+=dfs(cur-1,ndd,i,nqd);	}	return t;}int deal(LL x){	if(!x)return 1;	int tot=0;	while(x){num[tot++]=x%10,x/=10;}	reverse(num,num+tot);	int dd=0;	int ret=0;	for(int i=0;i<tot;i++){		int curdd;		for(int j=0;j<10;j++){			if(num[i]<=j)continue;			if(i==0)curdd=0;			else{				if(j>num[i-1])curdd=2;				else if(j==num[i-1])curdd=0;				else curdd=1;			}			if(dd&&curdd&&(dd!=curdd))continue;			int nqd=((i==0)&&(j==0))?0:1;			ret+=dfs(tot-i-2,max(dd,curdd),j,nqd);			//if(!i)printf("val=%d\n",tot-i-2);		}		if(i==0)curdd=0;		else{			if(num[i]>num[i-1])curdd=2;			else if(num[i]==num[i-1])curdd=0;			else curdd=1;		}		//printf("%d %d ret=%d\n",i,num[i],ret);		if(dd&&curdd&&(dd!=curdd)){dd=-1;break;}		//printf("dd=%d curdd=%d\n",dd,curdd);		dd=max(dd,curdd);	}	if(dd>=0)ret++;	return ret;}int main(){	memset(dp,-1,sizeof dp);	int _;scanf("%d",&_);	while(_--){		LL l,r;		scanf("%lld%lld",&l,&r);		int ans=deal(r);		ans-=deal(l-1);		printf("%d\n",ans);	}	return 0;}

  

J. Just Convolution

因为数据随机,所以可以取出$A$中最大$200$项和$B$中所有项暴力更新答案,然后再取出$B$中最大$200$项和$A$中所有项暴力更新答案,最后再取出$A$中和$B$中最大的$3000$项更新答案即可。

#include <bits/stdc++.h>using namespace std ;const int MAXN = 200005 ;struct Node {	int x , i ;	bool operator < ( const Node& a ) const {		return x > a.x ;	}} ;Node a[MAXN] , b[MAXN] ;int c[MAXN] ;int n ;void solve () {	for ( int i = 0 ; i < n ; ++ i ) {		scanf ( "%d" , &a[i].x ) ;		a[i].i = i ;	}	for ( int i = 0 ; i < n ; ++ i ) {		scanf ( "%d" , &b[i].x ) ;		b[i].i = i ;	}	for ( int i = 0 ; i < n ; ++ i ) {		c[i] = 0 ;	}	sort ( a , a + n ) ;	sort ( b , b + n ) ;	int k = min ( n , 3000 ) ;	for ( int i = 0 ; i < k ; ++ i ) {		for ( int j = 0 ; j < k ; ++ j ) {			int t = ( a[i].i + b[j].i ) % n ;			c[t] = max ( c[t] , a[i].x + b[j].x ) ;		}	}	int m = min ( n , 200 ) ;	for ( int i = k ; i < n ; ++ i ) {		for ( int j = 0 ; j < m ; ++ j ) {			int t1 = ( a[i].i + b[j].i ) % n ;			int t2 = ( b[i].i + a[j].i ) % n ;			c[t1] = max ( c[t1] , a[i].x + b[j].x ) ;			c[t2] = max ( c[t2] , b[i].x + a[j].x ) ;		}	}	for ( int i = 0 ; i < n ; ++ i ) {		i && putchar ( ‘ ‘ ) ;		printf ( "%d" , c[i] ) ;	}	puts ( "" ) ;}int main () {	while ( ~scanf ( "%d" , &n ) ) solve () ;	return 0 ;}

  

Moscow Pre-Finals Workshop 2016. National Taiwan U Selection