D. Divide

题目链接：戳这里

思路：用一个数组记录下每个二进制位上的值，满2进位，从高位到低位扫一遍，找到不能被均分的最高位（当前位为1而且不是进位获得的），该位置代表的值减去比它低位的值就是答案了

AC Code：

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 #define LL long long
 5 const long M=110000;
 6 LL pos[M],JinWei[M],ans[M],max_pos;
 7 long n,t;
 8 int main(){
 9     scanf("%d",&t);
10     for (long l=1;l<=t;++l){
11         scanf("%d",&n);
12 
13         memset(pos,0,sizeof(pos));
14         memset(JinWei,0,sizeof(JinWei));
15         max_pos=0;
16         long max1=0;
17         while (n--){
18             long x,a;
19             scanf("%d%d",&a,&x);
20             pos[a]+=x;
21             max1=std::max(max1,a);
22         }
23 
24         for (long i=0;i<M;++i)
25         if (pos[i]>1){
26             pos[i+1]+=(pos[i]>>1);
27             JinWei[i+1]=1;
28             pos[i]=pos[i]%2;
29         }
30 
31         max_pos=-1;
32         for (long i=M-1;i>=0;--i)
33             if (pos[i] && !JinWei[i]){
34                 max_pos=i;
35                 break;
36             }
37 
38         printf("Case #%d: ",l); 
39         if (max_pos<0) printf("0
");
40         else{
41             memset(ans,0,sizeof(ans));
42             ans[max_pos]=1;
43             for (long i=max_pos-1;i>=0;--i)
44                 if (pos[i]){
45                     ans[max_pos]=0;
46                     for (long j=max_pos-1;j>=i;--j)
47                         ans[j]=1;
48                     max_pos=i;
49                 }
50         long output=0;
51         for (long i=M-1;i>=0;--i){
52             if (ans[i]) output=1;
53             if (output) printf("%d",ans[i]);
54         }
55         printf("
");
56         }
57     }
58     return 0;
59 }

By 王桢旭