首页 > 代码库 > codeforces #270 ABCD
codeforces #270 ABCD
Codeforces Round #270
A - Design Tutorial: Learn from Math
题意：给出n，求出两个合数x和y使x+y=n。
题解：暴力筛合数，然后暴力找
1 //#pragma comment(linker, "/STACK:102400000,102400000") 2 #include<cstdio> 3 #include<cmath> 4 #include<iostream> 5 #include<cstring> 6 #include<algorithm> 7 #include<cmath> 8 #include<map> 9 #include<set>10 #include<stack>11 #include<queue>12 using namespace std;13 #define ll __int6414 #define usint unsigned int15 #define mz(array) memset(array, 0, sizeof(array))16 #define minf(array) memset(array, 0x3f, sizeof(array))17 #define REP(i,n) for(int i=0;i<(n);i++)18 #define FOR(i,x,n) for(int i=(x);i<=(n);i++)19 #define RD(x) scanf("%d",&x)20 #define RD2(x,y) scanf("%d%d",&x,&y)21 #define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z)22 #define WN(x) printf("%d\n",x);23 #define RE freopen("D.in","r",stdin)24 #define WE freopen("1.out","w",stdout)25 26 bool a[1111111];27 28 29 int main() {30 int x,i,n,j;31 RD(n);32 int n2=n/2;33 for(x=2; x<=n2; x++) {34 if(a[x]==0) {35 for(i=x+x; i<=n; i+=x) {36 a[i]=1;37 }38 }39 }40 for(x=4;x<=n2;x++){41 if(a[x]==1 && a[n-x]==1)break;42 }43 printf("%d %d\n",x,n-x);44 return 0;45 }
B - Design Tutorial: Learn from Life
题意：一堆人从1楼坐电梯，电梯一次最多装K人，给出各个人要去的各个楼层，上下电梯时间忽略不计，电梯移动一层需要1秒，求最少需要多少时间才能送完所有人并且电梯回到1楼。
题解：贪心，优先送最高的，空位顺便送低的。
1 //#pragma comment(linker, "/STACK:102400000,102400000") 2 #include<cstdio> 3 #include<cmath> 4 #include<iostream> 5 #include<cstring> 6 #include<algorithm> 7 #include<cmath> 8 #include<map> 9 #include<set>10 #include<stack>11 #include<queue>12 using namespace std;13 #define ll __int6414 #define usint unsigned int15 #define mz(array) memset(array, 0, sizeof(array))16 #define minf(array) memset(array, 0x3f, sizeof(array))17 #define REP(i,n) for(int i=0;i<(n);i++)18 #define FOR(i,x,n) for(int i=(x);i<=(n);i++)19 #define RD(x) scanf("%d",&x)20 #define RD2(x,y) scanf("%d%d",&x,&y)21 #define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z)22 #define WN(x) printf("%d\n",x);23 #define RE freopen("D.in","r",stdin)24 #define WE freopen("1.out","w",stdout)25 26 int a[2222];27 28 int main() {29 int n,k,i,j,x,ans;30 RD2(n,k);31 REP(i,n) {32 RD(x);33 a[x]++;34 }35 x=0;36 ans=0;37 for(i=2000;i>=2;i--) {38 if(a[i]>0) {39 a[i]-=x;40 int t=a[i]/k;41 int tt=t*k;42 int ttt=tt>=a[i]?t:t+1;43 ans+=ttt*(i-1)*2;44 x=ttt*k-a[i];45 //printf("%d %d %d\n",i,ttt,ans);46 }47 }48 WN(ans);49 return 0;50 }
C - Design Tutorial: Make It Nondeterministic
题意：每个人可以用自己的姓或者名字作为ID，给出各个人的名字，给出一个排名序列，若有一种选择ID的方法可以使排名正确，则输出YES，否则输出NO。
题解：贪心，排名1的人选字典序少的那个，然后都优先选字典序小的，不行了就选大的，再不行就NO。
1 //#pragma comment(linker, "/STACK:102400000,102400000") 2 #include<cstdio> 3 #include<cmath> 4 #include<iostream> 5 #include<cstring> 6 #include<algorithm> 7 #include<cmath> 8 #include<map> 9 #include<set>10 #include<stack>11 #include<queue>12 using namespace std;13 #define ll __int6414 #define usint unsigned int15 #define mz(array) memset(array, 0, sizeof(array))16 #define minf(array) memset(array, 0x3f, sizeof(array))17 #define REP(i,n) for(int i=0;i<(n);i++)18 #define FOR(i,x,n) for(int i=(x);i<=(n);i++)19 #define RD(x) scanf("%d",&x)20 #define RD2(x,y) scanf("%d%d",&x,&y)21 #define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z)22 #define WN(x) printf("%d\n",x);23 #define RE freopen("D.in","r",stdin)24 #define WE freopen("1.out","w",stdout)25 26 char s[111111][2][55];27 28 int cmp(char a[55],char b[55]) {29 int la=strlen(a),lb=strlen(b);30 int l=min(la,lb);31 int i;32 for(i=0; i<l; i++) {33 if(a[i]>b[i])return 1;34 if(b[i]>a[i])return -1;35 }36 if(la>lb)return 1;37 if(lb>la)return -1;38 return 0;39 }40 41 int main() {42 int n;43 RD(n);44 REP(i,n) {45 scanf(" %s%s",s[i][0],s[i][1]);46 //printf("%d %s!%s!\n",i,s[i][0],s[i][1]);47 }48 char q[55];49 int x,y=0,z,j;50 RD(x);51 y=x-1;52 if(cmp(s[y][0],s[y][1])==-1) z=0;53 else z=1;54 bool flag=1;55 REP(i,n-1) {56 RD(x);57 x--;58 if(cmp(s[x][0],s[x][1])==-1) j=0;59 else j=1;60 if(cmp(s[x][j] , s[y][z])==-1){61 if(cmp(s[x][j^1], s[y][z])==-1){62 flag=0;63 break;64 }else{65 y=x;66 z=j^1;67 }68 }else{69 y=x;70 z=j;71 }72 }73 if(flag)puts("YES");74 else puts("NO");75 return 0;76 }
D - Design Tutorial: Inverse the Problem
题意：给出各个点距离的邻接矩阵，判断这是不是一棵树。
题解：先根据样例特判一些情况，然后最小生成树，我是用可撸斯卡尔，当要加入的边的两个点x和y已经在同一集合，则判它们的距离是否正确。我的方法是找到一个中间点v，使x-v和v-y有路，找到(xv距离) + (vy距离)最小的那个值，当作x到y的距离。这是因为可撸斯卡尔是从小往大加边，肯定有至少一个中间点能使得这个有路。复杂度O(n^3)，略高，姿势不对就要TLE……更好的解法可以看这里：http://www.cnblogs.com/forgot93/p/4000850.html
1 //#pragma comment(linker, "/STACK:102400000,102400000") 2 #include<cstdio> 3 #include<cmath> 4 #include<iostream> 5 #include<cstring> 6 #include<algorithm> 7 #include<cmath> 8 #include<map> 9 #include<set> 10 #include<stack> 11 #include<queue> 12 using namespace std; 13 #define ll __int64 14 #define usint unsigned int 15 #define mz(array) memset(array, 0, sizeof(array)) 16 #define mf1(array) memset(array, -1, sizeof(array)) 17 #define minf(array) memset(array, 0x3f, sizeof(array)) 18 #define REP(i,n) for(int i=0;i<(n);i++) 19 #define FOR(i,x,n) for(int i=(x);i<=(n);i++) 20 #define RD(x) scanf("%d",&x) 21 #define RD2(x,y) scanf("%d%d",&x,&y) 22 #define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z) 23 #define WN(x) printf("%d\n",x); 24 #define RE freopen("D.in","r",stdin) 25 #define WE freopen("1.out","w",stdout) 26 const int inf=2*1e9+7; 27 const int maxn=2222; 28 const int maxm=maxn*maxn; 29 30 int a[2222][2222]; 31 int n; 32 33 34 int bx[maxm],by[maxm],bz[maxm]; 35 int bn; 36 inline void add(const int &x,const int &y,const int &z){ 37 bx[bn]=x; 38 by[bn]=y; 39 bz[bn]=z; 40 bn++; 41 } 42 43 int d[maxm]; 44 bool cmp(const int &x,const int &y){ 45 return bz[x]<bz[y]; 46 } 47 48 int f[maxm]; 49 int gf(const int &x){ 50 if(f[x]==-1)return x; 51 f[x]=gf(f[x]); 52 return f[x]; 53 } 54 55 struct Edge{ 56 int next,v,l; 57 }e[maxm]; 58 int head[maxn],en; 59 60 inline void addedge(const int &x,const int &y,const int &z){ 61 e[en].v=y; 62 e[en].l=z; 63 e[en].next=head[x]; 64 head[x]=en; 65 en++; 66 } 67 68 int dis[maxn][maxn]; 69 70 inline void gank(const int &x,const int &y){ 71 int mi=inf; 72 for(int i=head[x];i!=-1;i=e[i].next){ 73 if(dis[y][e[i].v]!=-1){ 74 //printf("(%d) %d + %d = %d\n",e[i].v,e[i].l,dis[y][e[i].v],e[i].l + dis[y][e[i].v]); 75 mi=min(mi , e[i].l + dis[y][e[i].v]); 76 } 77 } 78 dis[y][x]=dis[x][y]=mi; 79 } 80 81 bool farm(){ 82 int i,j,k,x,y,z; 83 bn=0; 84 REP(i,n){ 85 REP(j,n){ 86 if(i!=j){ 87 if(a[i][j]==0)return 0; 88 }else{ 89 if(a[i][j]!=0)return 0; 90 } 91 } 92 } 93 REP(i,n){ 94 REP(j,i){ 95 if(a[i][j]!=a[j][i])return 0; 96 add(i,j,a[i][j]); 97 } 98 } 99 REP(i,bn){100 d[i]=i;101 }102 sort(d,d+bn,cmp);103 mf1(f);104 //mf1(head);105 REP(i,n)REP(j,n)dis[i][j]=-1;106 en=0;107 mf1(head);108 REP(i,n)dis[i][i]=0;109 //en=0;110 REP(i,bn){111 int q=d[i];112 int &x=bx[q],&y=by[q],&z=bz[q];113 int fx=gf(x),fy=gf(y);114 if(fx!=fy){115 addedge(x,y,z);116 addedge(y,x,z);117 dis[x][y]=z;118 dis[y][x]=z;119 f[fx]=fy;120 }else{121 if(dis[x][y]==-1) gank(x,y);122 //printf("dis[%d][%d]=%d , z=%d\n",x,y,dis[x][y],z);123 if(dis[x][y]!=z)return 0;124 }125 }126 return 1;127 }128 129 130 131 int main() {132 int i;133 RD(n);134 REP(i,n)REP(j,n) RD(a[i][j]);135 if(farm())puts("YES");136 else puts("NO");137 return 0;138 }
codeforces #270 ABCD
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。