A - Team Olympiad
贪心水题。。都从第一个开始取即可。
代码如下：
#include #include #include #include #include #include #include #include #include #include #include using namespace std; #define LL __int64 int a[6000], b[6000]; int main() { int n, x, y, z, ans, i, j; while(scanf("%d",&n)!=EOF) { x=y=z=0; for(i=0;i B - Queue 通过用数组记录下一个位置，分别把偶数位置与奇数位置上的填满。 偶数位置上一定是从0开始的，奇数位置一定是从一个没有出度只有入度的一个数开始的。 代码如下： #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define LL __int64 int next[1100000], a[1100000], out[1100000]; struct node { int u, v; }fei[1100000]; int main() { int n, i, j, u, v, cnt, pos; while(scanf("%d",&n)!=EOF) { memset(next,-1,sizeof(next)); memset(out,0,sizeof(out)); for(i=0;i C - Hacking Cypher 分别从前和后扫一遍记录下能整除的位置。从前往后的很好处理。 至于从后往前的，对于第k位来说，可以先预处理10^k对b的余数和以及前k位对b的余数，然后，后几位=总数-前k位表示的数*10^k。所以只要满足总数%b==（前k位表示的数%b）*（10^k%b）%b，就标明后几位表示的数可以整除b。 这样就可以在O（n）的复杂度内完成了。 表示自己真是弱渣。。看别人都一会儿就做出来了。。自己却想了半个小时才想出来。。。 代码如下： #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define LL __int64 int a[1100000], b[1100000], c[1100000], d[1100000]; char s[1100000]; int main() { int aa, bb, i, x, len, pos, flag=0, y; gets(s); scanf("%d%d",&aa,&bb); memset(a,0,sizeof(a)); memset(d,0,sizeof(d)); x=1; c[1]=1%bb; for(i=2;i<=1000000;i++) { x=x*10%bb; c[i]=x; } len=strlen(s); x=0; y=0; for(i=0;i D - Chocolate 如果最终的面积相等的话，那么2的因子数与3的因子数一定相等。所以可以先求出2的因子数与3的因子数。然后这时候我们可以有两种操作：消去一个2或者把一个3变成2.所以这时候先把3较大的一方变成2，使得剩下的3相等，然后再消去2的因子数较大的一方使得相等。然后在判断这时候双方面积相等即可。 代码如下： #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define LL __int64 int main() { int a1, b1, a2, b2, x2, x3, y2, y3, ans, m1, m2, n1, n2; while(scanf("%d%d%d%d",&a1,&b1,&a2,&b2)!=EOF) { m1=a1; m2=a2; n1=b1; n2=b2; x2=x3=y2=y3=0; while(!(a1%2)||!(a1%3)) { if(a1%2==0) { x2++; a1/=2; } if(a1%3==0) { x3++; a1/=3; } } while(!(b1%2)||!(b1%3)) { if(b1%2==0) { x2++; b1/=2; } if(b1%3==0) { x3++; b1/=3; } } while(!(a2%2)||!(a2%3)) { if(a2%2==0) { y2++; a2/=2; } if(a2%3==0) { y3++; a2/=3; } } while(!(b2%2)||!(b2%3)) { if(b2%2==0) { y2++; b2/=2; } if(b2%3==0) { y3++; b2/=3; } } if(x3>=y3) { x2+=x3-y3; ans=x3-y3; for(int i=0; i =y2) { for(int i=0; i E - Restoring Increasing Sequence 贪心+模拟。 从前开始，保证每个数都是大于前面那个数的最小可能值。当有一个不可能的时候。就表明不可能存在。 代码写的太挫。。。。。 代码如下： #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define LL __int64 char s[110000][10]; int main() { int n, i, x, y, z, len, l, flag, j, k, pos; while(scanf("%d",&n)!=EOF) { getchar(); flag=0; for(i=1; i<=n; i++) { gets(s[i]); } z=0; l=1; s[0][0]='0'; for(i=1; i<=n; i++) { len=strlen(s[i]); if(len l) { for(j=0; j s[i-1][j]) { ff=1; for(k=0; k =0; k--) { if(s[i][k]=='?'&&s[i-1][k]!='9') { s[i][k]=s[i-1][k]+1; pos=k; break; } } if(pos==-1) { flag=1; } else { for(k=0; k =0;j--) { if(s[i][j]=='?'&&s[i-1][j]!='9') { s[i][j]=s[i-1][j]+1; pos=j; break; } } if(pos==-1) { flag=1; break; } for(j=0;j
通过用数组记录下一个位置，分别把偶数位置与奇数位置上的填满。
偶数位置上一定是从0开始的，奇数位置一定是从一个没有出度只有入度的一个数开始的。
#include #include #include #include #include #include #include #include #include #include #include using namespace std; #define LL __int64 int next[1100000], a[1100000], out[1100000]; struct node { int u, v; }fei[1100000]; int main() { int n, i, j, u, v, cnt, pos; while(scanf("%d",&n)!=EOF) { memset(next,-1,sizeof(next)); memset(out,0,sizeof(out)); for(i=0;i C - Hacking Cypher 分别从前和后扫一遍记录下能整除的位置。从前往后的很好处理。 至于从后往前的，对于第k位来说，可以先预处理10^k对b的余数和以及前k位对b的余数，然后，后几位=总数-前k位表示的数*10^k。所以只要满足总数%b==（前k位表示的数%b）*（10^k%b）%b，就标明后几位表示的数可以整除b。 这样就可以在O（n）的复杂度内完成了。 表示自己真是弱渣。。看别人都一会儿就做出来了。。自己却想了半个小时才想出来。。。 代码如下： #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define LL __int64 int a[1100000], b[1100000], c[1100000], d[1100000]; char s[1100000]; int main() { int aa, bb, i, x, len, pos, flag=0, y; gets(s); scanf("%d%d",&aa,&bb); memset(a,0,sizeof(a)); memset(d,0,sizeof(d)); x=1; c[1]=1%bb; for(i=2;i<=1000000;i++) { x=x*10%bb; c[i]=x; } len=strlen(s); x=0; y=0; for(i=0;i D - Chocolate 如果最终的面积相等的话，那么2的因子数与3的因子数一定相等。所以可以先求出2的因子数与3的因子数。然后这时候我们可以有两种操作：消去一个2或者把一个3变成2.所以这时候先把3较大的一方变成2，使得剩下的3相等，然后再消去2的因子数较大的一方使得相等。然后在判断这时候双方面积相等即可。 代码如下： #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define LL __int64 int main() { int a1, b1, a2, b2, x2, x3, y2, y3, ans, m1, m2, n1, n2; while(scanf("%d%d%d%d",&a1,&b1,&a2,&b2)!=EOF) { m1=a1; m2=a2; n1=b1; n2=b2; x2=x3=y2=y3=0; while(!(a1%2)||!(a1%3)) { if(a1%2==0) { x2++; a1/=2; } if(a1%3==0) { x3++; a1/=3; } } while(!(b1%2)||!(b1%3)) { if(b1%2==0) { x2++; b1/=2; } if(b1%3==0) { x3++; b1/=3; } } while(!(a2%2)||!(a2%3)) { if(a2%2==0) { y2++; a2/=2; } if(a2%3==0) { y3++; a2/=3; } } while(!(b2%2)||!(b2%3)) { if(b2%2==0) { y2++; b2/=2; } if(b2%3==0) { y3++; b2/=3; } } if(x3>=y3) { x2+=x3-y3; ans=x3-y3; for(int i=0; i =y2) { for(int i=0; i E - Restoring Increasing Sequence 贪心+模拟。 从前开始，保证每个数都是大于前面那个数的最小可能值。当有一个不可能的时候。就表明不可能存在。 代码写的太挫。。。。。 代码如下： #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define LL __int64 char s[110000][10]; int main() { int n, i, x, y, z, len, l, flag, j, k, pos; while(scanf("%d",&n)!=EOF) { getchar(); flag=0; for(i=1; i<=n; i++) { gets(s[i]); } z=0; l=1; s[0][0]='0'; for(i=1; i<=n; i++) { len=strlen(s[i]); if(len l) { for(j=0; j s[i-1][j]) { ff=1; for(k=0; k =0; k--) { if(s[i][k]=='?'&&s[i-1][k]!='9') { s[i][k]=s[i-1][k]+1; pos=k; break; } } if(pos==-1) { flag=1; } else { for(k=0; k =0;j--) { if(s[i][j]=='?'&&s[i-1][j]!='9') { s[i][j]=s[i-1][j]+1; pos=j; break; } } if(pos==-1) { flag=1; break; } for(j=0;j
分别从前和后扫一遍记录下能整除的位置。从前往后的很好处理。
至于从后往前的，对于第k位来说，可以先预处理10^k对b的余数和以及前k位对b的余数，然后，后几位=总数-前k位表示的数*10^k。所以只要满足总数%b==（前k位表示的数%b）*（10^k%b）%b，就标明后几位表示的数可以整除b。
这样就可以在O（n）的复杂度内完成了。
表示自己真是弱渣。。看别人都一会儿就做出来了。。自己却想了半个小时才想出来。。。
#include #include #include #include #include #include #include #include #include #include #include using namespace std; #define LL __int64 int a[1100000], b[1100000], c[1100000], d[1100000]; char s[1100000]; int main() { int aa, bb, i, x, len, pos, flag=0, y; gets(s); scanf("%d%d",&aa,&bb); memset(a,0,sizeof(a)); memset(d,0,sizeof(d)); x=1; c[1]=1%bb; for(i=2;i<=1000000;i++) { x=x*10%bb; c[i]=x; } len=strlen(s); x=0; y=0; for(i=0;i D - Chocolate 如果最终的面积相等的话，那么2的因子数与3的因子数一定相等。所以可以先求出2的因子数与3的因子数。然后这时候我们可以有两种操作：消去一个2或者把一个3变成2.所以这时候先把3较大的一方变成2，使得剩下的3相等，然后再消去2的因子数较大的一方使得相等。然后在判断这时候双方面积相等即可。 代码如下： #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define LL __int64 int main() { int a1, b1, a2, b2, x2, x3, y2, y3, ans, m1, m2, n1, n2; while(scanf("%d%d%d%d",&a1,&b1,&a2,&b2)!=EOF) { m1=a1; m2=a2; n1=b1; n2=b2; x2=x3=y2=y3=0; while(!(a1%2)||!(a1%3)) { if(a1%2==0) { x2++; a1/=2; } if(a1%3==0) { x3++; a1/=3; } } while(!(b1%2)||!(b1%3)) { if(b1%2==0) { x2++; b1/=2; } if(b1%3==0) { x3++; b1/=3; } } while(!(a2%2)||!(a2%3)) { if(a2%2==0) { y2++; a2/=2; } if(a2%3==0) { y3++; a2/=3; } } while(!(b2%2)||!(b2%3)) { if(b2%2==0) { y2++; b2/=2; } if(b2%3==0) { y3++; b2/=3; } } if(x3>=y3) { x2+=x3-y3; ans=x3-y3; for(int i=0; i =y2) { for(int i=0; i E - Restoring Increasing Sequence 贪心+模拟。 从前开始，保证每个数都是大于前面那个数的最小可能值。当有一个不可能的时候。就表明不可能存在。 代码写的太挫。。。。。 代码如下： #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define LL __int64 char s[110000][10]; int main() { int n, i, x, y, z, len, l, flag, j, k, pos; while(scanf("%d",&n)!=EOF) { getchar(); flag=0; for(i=1; i<=n; i++) { gets(s[i]); } z=0; l=1; s[0][0]='0'; for(i=1; i<=n; i++) { len=strlen(s[i]); if(len l) { for(j=0; j s[i-1][j]) { ff=1; for(k=0; k =0; k--) { if(s[i][k]=='?'&&s[i-1][k]!='9') { s[i][k]=s[i-1][k]+1; pos=k; break; } } if(pos==-1) { flag=1; } else { for(k=0; k =0;j--) { if(s[i][j]=='?'&&s[i-1][j]!='9') { s[i][j]=s[i-1][j]+1; pos=j; break; } } if(pos==-1) { flag=1; break; } for(j=0;j
如果最终的面积相等的话，那么2的因子数与3的因子数一定相等。所以可以先求出2的因子数与3的因子数。然后这时候我们可以有两种操作：消去一个2或者把一个3变成2.所以这时候先把3较大的一方变成2，使得剩下的3相等，然后再消去2的因子数较大的一方使得相等。然后在判断这时候双方面积相等即可。
#include #include #include #include #include #include #include #include #include #include #include using namespace std; #define LL __int64 int main() { int a1, b1, a2, b2, x2, x3, y2, y3, ans, m1, m2, n1, n2; while(scanf("%d%d%d%d",&a1,&b1,&a2,&b2)!=EOF) { m1=a1; m2=a2; n1=b1; n2=b2; x2=x3=y2=y3=0; while(!(a1%2)||!(a1%3)) { if(a1%2==0) { x2++; a1/=2; } if(a1%3==0) { x3++; a1/=3; } } while(!(b1%2)||!(b1%3)) { if(b1%2==0) { x2++; b1/=2; } if(b1%3==0) { x3++; b1/=3; } } while(!(a2%2)||!(a2%3)) { if(a2%2==0) { y2++; a2/=2; } if(a2%3==0) { y3++; a2/=3; } } while(!(b2%2)||!(b2%3)) { if(b2%2==0) { y2++; b2/=2; } if(b2%3==0) { y3++; b2/=3; } } if(x3>=y3) { x2+=x3-y3; ans=x3-y3; for(int i=0; i =y2) { for(int i=0; i E - Restoring Increasing Sequence 贪心+模拟。 从前开始，保证每个数都是大于前面那个数的最小可能值。当有一个不可能的时候。就表明不可能存在。 代码写的太挫。。。。。 代码如下： #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define LL __int64 char s[110000][10]; int main() { int n, i, x, y, z, len, l, flag, j, k, pos; while(scanf("%d",&n)!=EOF) { getchar(); flag=0; for(i=1; i<=n; i++) { gets(s[i]); } z=0; l=1; s[0][0]='0'; for(i=1; i<=n; i++) { len=strlen(s[i]); if(len l) { for(j=0; j s[i-1][j]) { ff=1; for(k=0; k =0; k--) { if(s[i][k]=='?'&&s[i-1][k]!='9') { s[i][k]=s[i-1][k]+1; pos=k; break; } } if(pos==-1) { flag=1; } else { for(k=0; k =0;j--) { if(s[i][j]=='?'&&s[i-1][j]!='9') { s[i][j]=s[i-1][j]+1; pos=j; break; } } if(pos==-1) { flag=1; break; } for(j=0;j
E - Restoring Increasing Sequence
贪心+模拟。
从前开始，保证每个数都是大于前面那个数的最小可能值。当有一个不可能的时候。就表明不可能存在。
代码写的太挫。。。。。
#include #include #include #include #include #include #include #include #include #include #include using namespace std; #define LL __int64 char s[110000][10]; int main() { int n, i, x, y, z, len, l, flag, j, k, pos; while(scanf("%d",&n)!=EOF) { getchar(); flag=0; for(i=1; i<=n; i++) { gets(s[i]); } z=0; l=1; s[0][0]='0'; for(i=1; i<=n; i++) { len=strlen(s[i]); if(len l) { for(j=0; j s[i-1][j]) { ff=1; for(k=0; k =0; k--) { if(s[i][k]=='?'&&s[i-1][k]!='9') { s[i][k]=s[i-1][k]+1; pos=k; break; } } if(pos==-1) { flag=1; } else { for(k=0; k =0;j--) { if(s[i][j]=='?'&&s[i-1][j]!='9') { s[i][j]=s[i-1][j]+1; pos=j; break; } } if(pos==-1) { flag=1; break; } for(j=0;j