QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#467336 | #1289. A + B Problem | hmya | WA | 25ms | 10368kb | C++98 | 5.4kb | 2024-07-08 15:49:52 | 2024-07-08 15:49:53 |
Judging History
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;
int R=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;
while(R<n+m&&pre[R]-pre[i]<need)R++;
if(R==n+m)break;
R--;
// 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(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: 0ms
memory: 7920kb
input:
3 4 3 1000101 2 2 1111 1 1 00
output:
1101 110 0
result:
ok 3 lines
Test #2:
score: -100
Wrong Answer
time: 25ms
memory: 10368kb
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:
10011011010 11100 10101100 110100101 100001110 10000001110 1000010111 111101101 1110100000 111101010 11110000 1000011110 1001101111 10101111 101110101 11100 1111010 1000010 1011100011 10010101100 10010100 1001011 1000000101 1110 111 1111110001 10110111 1101001010 10001000 111000011 110 11111 1100101...
result:
wrong answer 1st lines differ - expected: '10011010100', found: '10011011010'