先写C题强行跪烂
体会
调不出的痛苦
A. Bus to Udayland
智障题
听说有人WA了4发才过？
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 |
// <A.cpp> - 08/29/16 20:04:52 // This file is created by XuYike's black technology automatically. // Copyright (C) 2015 ChangJun High School, Inc. // I don't know what this program is. #include <iostream> #include <vector> #include <algorithm> #include <cstring> #include <cstdio> #include <cmath> using namespace std; typedef long long lol; int gi(){ int res=0,fh=1;char ch=getchar(); while((ch>'9'||ch<'0')&&ch!='-')ch=getchar(); if(ch=='-')fh=-1,ch=getchar(); while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar(); return fh*res; } bool gc(){ char ch=getchar(); while(ch!='O'&&ch!='X')ch=getchar(); return ch=='O'; } const int MAXN=1010; const int INF=1e9; bool s[MAXN][5]; int se,p; int main(){ int n=gi(); for(int i=1;i<=n;i++){ s[i][1]=gc(); s[i][2]=gc(); getchar(); s[i][3]=gc(); s[i][4]=gc(); if(s[i][1]&&s[i][2]){se=i;p=1;} if(s[i][3]&&s[i][4]){se=i;p=3;} } if(!se){printf("NO");return 0;} puts("YES"); for(int i=1;i<=n;i++){ if(se==i){ if(p==1){ putchar('+'); putchar('+'); putchar('|'); putchar(s[i][3]?'O':'X'); putchar(s[i][4]?'O':'X'); }else{ putchar(s[i][1]?'O':'X'); putchar(s[i][2]?'O':'X'); putchar('|'); putchar('+'); putchar('+'); } }else{ putchar(s[i][1]?'O':'X'); putchar(s[i][2]?'O':'X'); putchar('|'); putchar(s[i][3]?'O':'X'); putchar(s[i][4]?'O':'X'); } putchar('\n'); } return 0; } |
B. Chris and Magic Square
智障题
听说有人WA了4发仍然没过？
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 |
// <B.cpp> - 08/29/16 20:04:52 // This file is created by XuYike's black technology automatically. // Copyright (C) 2015 ChangJun High School, Inc. // I don't know what this program is. #include <iostream> #include <vector> #include <algorithm> #include <cstring> #include <cstdio> #include <cmath> using namespace std; typedef long long lol; int gi(){ int res=0,fh=1;char ch=getchar(); while((ch>'9'||ch<'0')&&ch!='-')ch=getchar(); if(ch=='-')fh=-1,ch=getchar(); while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar(); return fh*res; } const int MAXN=510; const int INF=1e9; int x,y; lol a[MAXN][MAXN]; int main(){ int n=gi(); if(n==1){printf("1");return 0;} for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(!(a[i][j]=gi()))x=i,y=j; lol h=0,s=0; for(int j=1;j<=n;j++)h+=a[x%n+1][j]; for(int j=1;j<=n;j++)s+=a[x][j]; a[x][y]=h-s; if(a[x][y]<=0){printf("-1");return 0;} for(int i=1;i<=n;i++){ lol q=0; for(int j=1;j<=n;j++)q+=a[i][j]; if(q!=h){printf("-1");return 0;} } for(int j=1;j<=n;j++){ lol q=0; for(int i=1;i<=n;i++)q+=a[i][j]; if(q!=h){printf("-1");return 0;} } lol q=0; for(int i=1;i<=n;i++)q+=a[i][i]; if(q!=h){printf("-1");return 0;} q=0; for(int i=1;i<=n;i++)q+=a[i][n-i+1]; if(q!=h){printf("-1");return 0;} printf("%I64d",a[x][y]); return 0; } |
C. Coloring Trees
暴力无比的dp
一开始以为数据范围是\(n^3\)的。。。王队切D之后一句话：“不是\(n^4\)xjb搞”
然后就I64调了20分钟
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 |
// <C.cpp> - 08/29/16 20:04:52 // This file is created by XuYike's black technology automatically. // Copyright (C) 2015 ChangJun High School, Inc. // I don't know what this program is. #include <iostream> #include <vector> #include <algorithm> #include <cstring> #include <cstdio> #include <cmath> using namespace std; typedef long long lol; int gi(){ int res=0,fh=1;char ch=getchar(); while((ch>'9'||ch<'0')&&ch!='-')ch=getchar(); if(ch=='-')fh=-1,ch=getchar(); while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar(); return fh*res; } const int MAXN=110; const int INF=1e9; int c[MAXN],d[MAXN][MAXN]; lol dp[MAXN][MAXN][MAXN]; inline void give(lol &x,lol y,lol z){if(y&&(!x||y+z<x))x=y+z;} int main(){ int n=gi(),m=gi()+1,k=gi(); for(int i=1;i<=n;i++)c[i]=gi(); for(int i=1;i<=n;i++) for(int j=1;j<m;j++)d[i][j]=gi(); dp[0][m][0]=1; for(int i=1;i<=n;i++){ if(c[i]) for(int p=1;p<=k;p++) for(int l=1;l<=m;l++)give(dp[i][c[i]][p],dp[i-1][l][p-(l!=c[i])],0); else for(int j=1;j<m;j++){ for(int p=1;p<=k;p++)give(dp[i][j][p],dp[i-1][j][p],d[i][j]); for(int l=1;l<=m;l++){ if(l==j)continue; for(int p=1;p<=k;p++)give(dp[i][j][p],dp[i-1][l][p-1],d[i][j]); } } } lol ans=0; for(int i=1;i<m;i++)give(ans,dp[n][i][k],0); printf("%I64d",ans-1); return 0; } |
D. Directed Roads
给了个基环外向森林
把每个基环外向树上的大小以及上面的环的大小求出来算算就行了
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 |
// <D.cpp> - 08/29/16 20:04:52 // This file is created by XuYike's black technology automatically. // Copyright (C) 2015 ChangJun High School, Inc. // I don't know what this program is. #include <iostream> #include <vector> #include <algorithm> #include <cstring> #include <cstdio> #include <cmath> using namespace std; typedef long long lol; int gi(){ int res=0,fh=1;char ch=getchar(); while((ch>'9'||ch<'0')&&ch!='-')ch=getchar(); if(ch=='-')fh=-1,ch=getchar(); while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar(); return fh*res; } const int MAXN=200010; const int MAXM=400010; const int INF=1e9; const int MOD=1e9+7; int bt=1,b[MAXN],next[MAXM],to[MAXM]; inline void add(int x,int y){ next[++bt]=b[x];b[x]=bt;to[bt]=y; next[++bt]=b[y];b[y]=bt;to[bt]=x; } int dep[MAXN],ans=1; bool vis[MAXN]; int mi[MAXN],size[MAXN]; void get(int x){ size[x]=1; for(int i=b[x];i;i=next[i]){ if(dep[to[i]])continue; dep[to[i]]=dep[x]+1; get(to[i]); size[x]+=size[to[i]]; } } void dfs(int x,int f){ vis[x]=1; for(int i=b[x];i;i=next[i]){ if((i^f)==1)continue; if(vis[to[i]]){ if(i&1){ int net=to[i]; to[i]=x;dep[x]=1; get(x); ans=1ll*ans*(mi[dep[net]]-2)%MOD*mi[size[x]-dep[net]]%MOD; } } else dfs(to[i],i); } } int main(){ int n=gi(); mi[0]=1;for(int i=1;i<=n;i++)mi[i]=(mi[i-1]<<1)%MOD; for(int i=1;i<=n;i++)add(i,gi()); for(int i=1;i<=n;i++)if(!vis[i])dfs(i,0); printf("%d",ans); return 0; } |
E. ZS and The Birthday Paradox
求\(2^n\)个数里选\(k\)个数有相同数的概率
首先显然如果\(k>2^n\)那么概率为\(1\)
否则答案为\(1-\frac{\prod_{i=1}^{k-1}(2^n-i)}{2^{(k-1)n}}\)
如果\(k-1\ge 1e6+3\)说明上面肯定有一项能被\(1e6+3\)整除，那么分子就是\(0\)了。
否则暴力把每一项乘进去
然后计算分子中\(2\)的个数，分子分母同时乘以\(2\)的逆元的那么多次方就可以了。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 |
// <E.cpp> - 09/01/16 15:18:37 // This file is created by XuYike's black technology automatically. // Copyright (C) 2015 ChangJun High School, Inc. // I don't know what this program is. #include <iostream> #include <vector> #include <algorithm> #include <cstring> #include <cstdio> #include <cmath> using namespace std; typedef long long lol; lol gl(){ lol res=0,fh=1;char ch=getchar(); while((ch>'9'||ch<'0')&&ch!='-')ch=getchar(); if(ch=='-')fh=-1,ch=getchar(); while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar(); return fh*res; } const int MAXN=100001; const int INF=1e9; const int MOD=1e6+3; const int N2=500002; int qpow(int x,lol y){ int res=1; while(y){ if(y&1)res=1ll*res*x%MOD; x=1ll*x*x%MOD; y>>=1; } return res; } int main(){ lol n=gl(),k=gl(),p=2; if(n<=60&&(1ll<<n)<k){printf("1 1");return 0;} int a,b,d=qpow(2,n); a=b=qpow(d,k-1); if(k-1<MOD){ int s=1; for(int i=1;i<=k-1;i++)s=1ll*s*(d-i+MOD)%MOD; a=(a-s+MOD)%MOD; } for(int i=1;i<=60&&i<n;i++,p<<=1){ lol x=(k-1)/p; a=1ll*a*qpow(N2,x)%MOD; b=1ll*b*qpow(N2,x)%MOD; } printf("%d %d",a,b); return 0; } |