QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#467324#1289. A + B ProblemhmyaAC ✓32ms10436kbC++985.3kb2024-07-08 15:47:392024-07-08 15:47:39

Judging History

你现在查看的是最新测评结果

  • [2024-07-08 15:47:39]
  • 评测
  • 测评结果:AC
  • 用时:32ms
  • 内存:10436kb
  • [2024-07-08 15:47:39]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
int T;
char S[2000005];
int cnt[2000005];
int pre[2000005];
int main(){
    // freopen("partition.in","r",stdin);
    // freopen("partition.out","w",stdout);
    scanf("%d",&T);
    while(T--){
        int n,m;
        scanf("%d%d",&n,&m);
        if(n<m)swap(n,m);
        for(int i=1;i<=n+m;i++)cnt[i]=0;
        getchar();
        scanf("%s",S);
        for(int i=0;i<n+m;i++)pre[i]=(S[i]=='1');
        for(int i=1;i<n+m;i++)pre[i]+=pre[i-1];
        int tot1=n,tot2=m;
        // printf("%s\n",S);
        int st=0;
        int need=n+1,lst=-1;
        for(int i=0;i<m;i++){
            if(S[i]=='1'){//考虑以[0,i]为前缀给第二个串,然后再后面二分出一个位置使得其1的个数为n-m+i+1
                int need=n-m+i+1;
                int L=i,R=n+m;
                while(L+1<R){
                    int mid=L+R>>1;
                    if(pre[mid]-pre[i]>=need){
                        R=mid;
                    }
                    else{
                        L=mid;
                    }
                }
                if(R==n+m)break;
                if(i+1+(R-i-(pre[R]-pre[i]))>m)break;
                tot1=n-need;
                tot2=m-(i+1+((R-i)-(pre[R]-pre[i])));
                // printf("%d %d %d %d\n",i,tot1,tot2,R);
                st=R+1;
                lst=i;
            }
        }
        // printf("%d %d\n",tot1,tot2);
        for(int i=n;i>tot1;i--)cnt[i]++;
        for(int i=0;i<=lst;i++)cnt[m-i]+=(S[i]=='1');
        // while(true){
        //     printf("%d %d %d\n",tot1,tot2,st);
        //     int fir=st;
        //     while(fir<n+m&&S[fir]=='0'){fir++;}//S[fir]=='1'
        //     if(fir==n+m){
        //         break;
        //     }
        //     //这个策略的前提就是找到最近的一个1,考虑肯定是整体右移来的1更好啊。
        //     //也就是说下一个1不是fir,而是tot2往后找到的第一个1
        //     int neta=tot1-tot2+fir-st+1;
        //     //考虑现在一共需要tot1-tot2+fir-st+1个1,计算出neta之后二分出这个位置
        //     int L=fir,R=n+m;
        //     while(L+1<R){
        //         int mid=L+R>>1;
        //         if(pre[mid]-pre[fir]>=neta){
        //             R=mid;
        //         }
        //         else{
        //             L=mid;
        //         }
        //     }
        //     if(pre[R]-pre[fir]<neta){
        //         break;
        //     }
        //     if((R-fir)-neta>tot2-(fir-st+1)){
        //         break;
        //     }
        //     if(tot2<fir-st+1){
        //         break;
        //     }
        //     tot2=tot2-(fir-st+1)-((R-fir)-neta);
        //     tot1=tot1-neta;
        //     cnt[need]++;
        //     st=R+1;
        //     need=need-neta-1;
        // }
        //问能不能进到第need位,首先从前往后找到第一个1,丢给tot2,然后把差的1全部拉过来,然后补齐差位,这是需要进位的情况。
        //对于不需要进位的情况,能直接选就选,否则就不选
        // for(int i=n+m;i>=1;i--){
        //     printf("%d",cnt[i]);
        // }
        // puts("");
        for(int i=st;i<n+m;i++){
            // printf("%d %c %d %d\n",i,S[i],tot1,tot2);
            if(S[i]=='0'){
                if(tot1<tot2&&tot1)tot1--;
                else if(tot2)tot2--;
                else tot1--;
                // else tot1--;
            }
            else{
                if(tot1<tot2)cnt[tot2--]++;
                else cnt[tot1--]++;
            }
        }
        // for(int i=n+m;i>=1;i--){
        //     printf("%d",cnt[i]);
        // }
        // puts("");
        for(int i=1;i<=n+m;i++){
            cnt[i+1]+=cnt[i]/2;
            cnt[i]&=1;
        }
        bool tag=false;
        for(int i=n+m;i>=1;i--){
            if(!cnt[i]){
                if(!tag)continue;
                putchar('0');
            }
            else{
                putchar('1');
                tag=true;
            }
        }
        if(!tag){
            putchar('0');
        }
        puts("");
    }
    return 0;
}
/*
贪心。

考虑现在上面和下面各是a和b,那么考虑来一个1,选择最大的给出。

考虑来一个0,那就把最小的卖了。

从结果考虑,考虑第i位能不能是1?

保证n>=m,则考虑:
1. 首先快速拿到一个1,然后再向上拿连续的1就可以了,这里确定下来可以把这一位变成1,如果没法确定就去找下一位。
2. 拿到了的话现在就来考虑当前的n=m的状态下能否再来做一次,判定什么的可以直接二分所以懒得管了,一切都是为了能够快速拿到一个1。

如果拿不到这个1,那就去下一个,下一个如果想要拿1可以直接放一个进去,肯定比进位简单。

1. 如果还有办法进位,那就进位
2. 如果没法进位了,那后面也都没法进位了,那就贪心取1吧。

容易发现策略的根本就是短的取一个前缀,然后长的取一个全1,然后剩下的贪心。

枚举1的位置,假设这个1前面的作为前缀存在,然后找一段全1,把前面选过的1全盖上,容易发现这个东西肯定是取前缀最优啊,而且取得越多越好。
*/

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 7792kb

input:

3
4 3
1000101
2 2
1111
1 1
00

output:

1101
110
0

result:

ok 3 lines

Test #2:

score: 0
Accepted
time: 32ms
memory: 10436kb

input:

11110
10 8
111011010011100100
3 5
01011000
7 6
1110101010000
9 1
0110100101
1 9
0100001110
8 10
000101101011111000
9 6
011111111000111
1 9
1011101101
10 7
00100011000100000
4 9
1000101101010
8 4
100100110000
8 9
00101111011000101
8 9
11000000101011110
7 6
1111010100110
2 9
01001110101
4 5
100010100
...

output:

10011010100
11100
10101000
110100101
100001110
10000001100
1000010111
111101101
1110100000
111101010
11110000
1000011101
1001011110
10101110
101110101
11100
1111010
1000010
1011100010
10010101001
10010001
1001010
1000000010
1110
111
1111110001
10110111
1100010101
10000000
111000011
110
11111
1100101...

result:

ok 11110 lines