codeforce 1474A Puzzle From the Future 模拟 C

codeforce 1474A Puzzle From the Future 模拟 C A. Puzzle From the Future time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output

In the 2022">20222022 year, Mike found two binary integers a">aa and b">bb of length n">nn (both of them are written only by digits 0">00 and 1">11) that can have leading zeroes. In order not to forget them, he wanted to construct integer d">dd in the following way:

  • he creates an integer c">cc as a result of bitwise summing of a">aa and b">bb without transferring carry, so c">cc may have one or more 2">22-s. For example, the result of bitwise summing of 0110">01100110 and 1101">11011101 is 1211">12111211 or the sum of 011000">011000011000 and 011000">011000011000 is 022000">022000022000;
  • after that Mike replaces equal consecutive digits in c">cc by one digit, thus getting d">dd. In the cases above after this operation, 1211">12111211 becomes 121">121121 and 022000">022000022000 becomes 020">020020 (so, d">dd won't have equal consecutive digits).

Unfortunately, Mike lost integer a">aa before he could calculate d">dd himself. Now, to cheer him up, you want to find any binary integer a">aa of length n">nn such that d">dd will be maximum possible as integer.

Maximum possible as integer means that 102>21">102>21102>21, 012<101">012<101012<101, 021=21">021=21021=21 and so on.

Input

The first line contains a single integer t">tt (1≤t≤1000">1≤t≤10001≤t≤1000) — the number of test cases.

The first line of each test case contains the integer n">nn (1≤n≤105">1≤n≤1051≤n≤105) — the length of a">aa and b">bb.

The second line of each test case contains binary integer b">bb of length n">nn. The integer b">bb consists only of digits 0">00 and 1">11.

It is guaranteed that the total sum of n">nn over all t">tt test cases doesn't exceed 105">105105.

Output

For each test case output one binary integer a">aa of length n">nn. Note, that a">aa or b">bb may have leading zeroes but must have the same length n">nn.

Example input Copy 
5
1
0
3
011
3
110
6
111000
6
001011
output Copy 
1
110
100
101101
101110
Note

In the first test case, b=0">b=0b=0 and choosing a=1">a=1a=1 gives d=1">d=1d=1 as a result.

In the second test case, b=011">b=011b=011 so:

  • if you choose a=000">a=000a=000, c">cc will be equal to 011">011011, so d=01">d=01d=01;
  • if you choose a=111">a=111a=111, c">cc will be equal to 122">122122, so d=12">d=12d=12;
  • if you choose a=010">a=010a=010, you'll get d=021">d=021d=021.
  • If you select a=110">a=110a=110, you'll get d=121">d=121d=121.
We can show that answer a=110">a=110a=110 is optimal and d=121">d=121d=121 is maximum possible.

In the third test case, b=110">b=110b=110. If you choose a=100">a=100a=100, you'll get d=210">d=210d=210 and it's the maximum possible d">dd.

In the fourth test case, b=111000">b=111000b=111000. If you choose a=101101">a=101101a=101101, you'll get d=212101">d=212101d=212101 and it's maximum possible d">dd.

In the fifth test case, b=001011">b=001011b=001011. If you choose a=101110">a=101110a=101110, you'll get d=102121">d=102121d=102121 and it's maximum possible d">dd.

b=001011">a=101110">d=102121">d">分析

题目要求最大，肯定先以位数优先

所以不能和前一位相同

那么第一个最大是2，形成不了2就用1

再就是前面和后面不能一样

b=001011">a=101110">d=102121">d">代码

b=001011">a=101110">d=102121">d">https://codeforces.com/contest/1474/submission/105585368

#include 
#include 
#include 
#include 
#include 
#include <string.h>
#include 
#include 
#include <string>
#include 
#include 
#include 
#include 
#include 
#include 
#include <set>
#include 
#include 
#include <string.h>
#include 
#define sf scanf
#define pf printf
#define lf double
#define p123 printf("123\n");
#define pn printf("\n");
#define pk printf(" ");
#define p(n) printf("%d",n);
#define pln(n) printf("%d\n",n);
#define s(n) scanf("%d",&n);
#define ss(n) scanf("%s",n);
#define ps(n) printf("%s",n);
#define sld(n) scanf("%lld",&n);
#define pld(n) printf("%lld",n);
#define slf(n) scanf("%lf",&n);
#define plf(n) printf("%lf",n);
#define sc(n) scanf("%c",&n);
#define pc(n) printf("%c",n);
#define gc getchar();
#define ll long long
#define re(n,a) memset(n,a,sizeof(n));
#define len(a) strlen(a)
#define eps 1e-13
#define zero(x) (((x) > 0? (x):(-x)) < eps)
using namespace std;
char a[200000];
int main(){
    int t;
    s(t)
    while(t --){
        int n;
        s(n) gc
        ss(a)
        //cin >> s;
        int temp = 0;
        for(int i = 0;  i< n; i ++){
            if(temp == 2){
                if(a[i] == '1'){
                    p(0)
                    temp = 1;
                }else if(a[i] == '0'){
                    p(1)
                    temp = 1;
                }
            }else if(temp == 1){
                if(a[i] == '1'){
                    p(1)
                    temp = 2;
                }else if(a[i] == '0'){
                    p(0)
                    temp = 0;
                }
            }else if(temp == 0){
                if(a[i] == '1'){
                    p(1)
                    temp = 2;
                }else if(a[i] == '0'){
                    p(1)
                    temp = 1;
                }
            }
        }
        pn

    }
    return 0;
}
ACM

相关

acm讲解

「acmhdu - 6314」Matrix

第十三届河南省ACM-ICPC游记

ACM模板

Hyperf 接入阿里云ACM应用配置管理中心

[ACM] BFS & 双端BFS & A* & 双边BFS

计算几何 / Geometry（ACM-Template 2.0）

ACM入门方式

Linux 下使用 acme.sh 配置 Let's Encrypt 免费 SSL 证书 + 通配符证书

如何写好一篇高质量的IEEE/ACM Transaction级别的计算机科学论文?

ACM- java在acm中的快速读入，多组读入，快速输出模板

ACM - 动态规划 - P1282 多米诺骨牌

标签