虽然打的时候是深夜但是状态比较好 但还是犯了好多错误..加分场愣是打成了降分场
ABC都比较水 一会敲完去看D 很快的就想出了求0和1个数的办法 然后一直wa在第四组..快结束的时候B因为低级错误被hack了...做完B想出了D的正解企图绝杀..然而还是失败了..
想了想还是由于自己不够认真吧..手速做完前三题 看着能涨分的名次就不太努力的做D了..中间还水了一下群..浪费了很多时间 导致最后没有能够完成D
A n个数 大于b被抛弃 不然就加入容器 如果容器中的和大于d 清理容器 直接模拟就好
B n个x轴点和初始坐标a 问走完至少n-1个点需要多少时间 可以想到走n-1个点一定是最优的 那么排序之后分别尝试抛弃x[1]和x[n] 输出最小值 当n==1时 直接输出0 因为这个被hack..
C 给出一个字符串 在其中选择一个连续非空子串 使其中的所有字母都-1 求这样操作一下这个字符串能达到的最小字典序 可以想到从前往后每个点的重要程度是依次下降的 寻找到第一个不是a的位置 使其作为子串的起点 再向右寻找直到尾点是a 如果找不到起点 说明全是a 那就把最后一个变为z
D 给出 a00 a01 a10 a11 分别代表 在一个由0 1组成的字符串中 00 01 10 11对的个数 问是否存在这样的字符串 有就输出 否则输出im
可以由a00 和 a11求出0 1 的个数x y 需要注意的是a00为0的时候 x有两个可能值 0 1 所以x与y的组合情况有四种
当我们确定了x和y存在的时候 可以想出 x*y == a01 + a10 在四种情况中如果都不满足 就输出im
当有一个满足的时候 就是说 x个0和y个1一定可以组成满足题意的式子 这时候进行简单的特判 即一个为0的时候 直接输出另外一个
当都不为0的时候 可以将其摆为0..01..101..10..0的形式 先在1的尾部尝试放0 如果a10可以整除 就不用在1中间插0
当把尾部和可能存在的中间的部位插完之后 我们的策略一定是满足a10的 因为式子成立 所以剩下的0全部放在最前 一定是可以成立的
每次进行字符串的输出之后直接return 0 到最后再搞一个输出im出来
虽然比较长 .. 但是大部分都是复制粘贴的..
一个trick即test4 是0 0 0 0 这时候 可能的字符串是存在的 即0或者1 .. 利用上面提到的四种情况是可以得到的..但是自己居然认为这个是错点..写了特判输出im..真傻..
#include<stdio.h> #include<string.h> #include<algorithm> #include<math.h> #include<map> #include<queue> #include<iostream> #include<vector> #include<string> #include<set> #include<stack> using namespace std; long long a10,a01,a11,a00; int main() { cin>>a00>>a01>>a10>>a11; if(a00==0&&a01==0&&a10==0&&a11==0) { printf("0 "); return 0; } long long x; /// 0 long long y; /// 1 long long a000=a00*2; long long a111=a11*2; long long q= sqrt(a000); bool ok = true; bool fin = false; if((q*(q+1))==a000) { x=q+1; } else ok=false; if(ok) { long long w= sqrt(a111); if((w*(w+1))==a111) { y=w+1; } else ok=false; if(ok) { /// 1 - if(a000==0) x=1; if(a111==0) y=1; if((x*y)==(a01+a10)) { if((x+y)>1000000) { printf("Impossible "); return 0; } if(x==0&&y==0) { printf("Impossible "); return 0; } else if(x==0) { for(int i=0; i<y; i++) { printf("1"); } printf(" "); return 0; } else if(y==0) { for(int i=0; i<x; i++) { printf("0"); } printf(" "); return 0; } /// x y int aa01=a01; int aa10=a10; int cnt =0; int ss=-1; while(true) { y--; if(aa01>x) { cnt ++; aa01-=x; } else { ss=aa01; aa01=0; } if(aa01==0) break; } if(y>=0) { if(ss==-1) { for(int i=1; i<=y; i++) printf("1"); for(int i=1; i<=x; i++) printf("0"); for(int i=1; i<=cnt; i++) printf("1"); printf(" "); } else { for(int i=1; i<=y; i++) printf("1"); for(int i=1; i<=ss; i++) printf("0"); printf("1"); for(int i=ss; i<x; i++) printf("0"); for(int i=1; i<=cnt; i++) printf("1"); printf(" "); } return 0; } } /// 2 if(a000==0) x=0; if(a111==0) y=1; if((x*y)==(a01+a10)) { if((x+y)>1000000) { printf("Impossible "); return 0; } if(x==0&&y==0) { printf("Impossible "); return 0; } else if(x==0) { for(int i=0; i<y; i++) { printf("1"); } printf(" "); return 0; } else if(y==0) { for(int i=0; i<x; i++) { printf("0"); } printf(" "); return 0; } int aa01=a01; int aa10=a10; int cnt =0; int ss=-1; while(true) { y--; if(aa01>x) { cnt ++; aa01-=x; } else { ss=aa01; aa01=0; } if(aa01==0) break; } if(y>=0) { if(ss==-1) { for(int i=1; i<=y; i++) printf("1"); for(int i=1; i<=x; i++) printf("0"); for(int i=1; i<=cnt; i++) printf("1"); printf(" "); } else { for(int i=1; i<=y; i++) printf("1"); for(int i=1; i<=ss; i++) printf("0"); printf("1"); for(int i=ss; i<x; i++) printf("0"); for(int i=1; i<=cnt; i++) printf("1"); printf(" "); } return 0; } } /// 3 if(a000==0) x=1; if(a111==0) y=0; if((x*y)==(a01+a10)) { if((x+y)>1000000) { printf("Impossible "); return 0; } if(x==0&&y==0) { printf("Impossible "); return 0; } else if(x==0) { for(int i=0; i<y; i++) { printf("1"); } printf(" "); return 0; } else if(y==0) { for(int i=0; i<x; i++) { printf("0"); } printf(" "); return 0; } int aa01=a01; int aa10=a10; int cnt =0; int ss=-1; while(true) { y--; if(aa01>x) { cnt ++; aa01-=x; } else { ss=aa01; aa01=0; } if(aa01==0) break; } if(y>=0) { if(ss==-1) { for(int i=1; i<=y; i++) printf("1"); for(int i=1; i<=x; i++) printf("0"); for(int i=1; i<=cnt; i++) printf("1"); printf(" "); } else { for(int i=1; i<=y; i++) printf("1"); for(int i=1; i<=ss; i++) printf("0"); printf("1"); for(int i=ss; i<x; i++) printf("0"); for(int i=1; i<=cnt; i++) printf("1"); printf(" "); } return 0; } } /// 4 if(a000==0) x=0; if(a111==0) y=0; if((x*y)==(a01+a10)) { if((x+y)>1000000) { printf("Impossible "); return 0; } if(x==0&&y==0) { printf("Impossible "); return 0; } else if(x==0) { for(int i=0; i<y; i++) { printf("1"); } printf(" "); return 0; } else if(y==0) { for(int i=0; i<x; i++) { printf("0"); } printf(" "); return 0; } int aa01=a01; int aa10=a10; int cnt =0; int ss=-1; while(true) { y--; if(aa01>x) { cnt ++; aa01-=x; } else { ss=aa01; aa01=0; } if(aa01==0) break; } if(y>=0) { if(ss==-1) { for(int i=1; i<=y; i++) printf("1"); for(int i=1; i<x; i++) printf("0"); for(int i=1; i<=cnt; i++) printf("1"); printf(" "); } else { for(int i=1; i<=y; i++) printf("1"); for(int i=1; i<=ss; i++) printf("0"); printf("1"); for(int i=ss; i<=x; i++) printf("0"); for(int i=1; i<=cnt; i++) printf("1"); printf(" "); } return 0; } } printf("Impossible "); return 0; } else { printf("Impossible "); } } else { printf("Impossible "); } }