首页 > 代码库 > 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
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。