问题 A: Edit Distance

时间限制: 1 Sec 内存限制: 128 MB Special Judge

提交 状态 题面

题目描述

A binary string is a non-empty sequence of 0’s and 1’s, e.g., 010110, 1, 11101, etc. The edit distance of two binary strings S and T, denoted by edit(S,T), is the minimum number of single-character edit (insert, delete,or substitute) to modify S into T. For example, the edit distance of 0011 and 1100 is 4, i.e. 0011->011 ->11->110->1100. The edit distance of 1100101 and 1110100 is 2, i.e. 1100101->1110101->1110100.

Ayu has a binary string S. She wants to find a binary string with the same length as S that maximizes the edit distance with S. Formally, she wants to find a binary string Tmax such that |S| = |Tmax| and edit(S,Tmax)≥edit(S,T’) for all binary string T’ satisfying |S| = |T’|.

She needs your help-> However, since she wants to make your task easier, you are allowed to return any binary string T with the same length as S such that the edit distance of S and T is more than half the length of S. Formally, you must return a binary string T such that |S| = |T| and edit(S,T) > |S|/2 .

Of course, you can still return Tmax if you want, since it can be proven that edit(S,Tmax) > |S|/2 for any binary string S. This also proves that there exists a solution for any binary string S. If there is more than one valid solution, you can output any of them.

输入

Input contains a binary string S (1≤|S|≤2000).

输出

Output in a line a binary string T with the same length as S that satisfies edit(S,T) > |S|/2.

样例输入

0011

样例输出

1100

提示

As illustrated in the example above, the edit distance of 0011 and 1100 is 4. Since 4 > 4/2 , 1100 is one of the valid output for this sample.

大水题

#pragma GCC optimize(3,"Ofast","inline")
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string.h>
#include <queue>
#include <vector>
#include <map>
#include <cmath>
#include <stack>
#include <set>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

int main()
{
    char s[2010];
    scanf("%s",s);
    int len=strlen(s);
    int Zreo=0,One=0;
    for(int i=0;i<len;i++){
        if(s[i]=='0') Zreo++;
        else One++;
    }
    if(Zreo>One){
        for(int i=0;i<len;i++){
            putchar('1');
        }
        putchar('\n');
    }
    else if(Zreo<One){
        for(int i=0;i<len;i++){
            putchar('0');
        }
        putchar('\n');
    }
    else{
        if(s[0]=='1'){
            putchar('0');
            for(int i=1;i<len;i++){
                putchar('1');
            }
            putchar('\n');
        }
        else{
            putchar('1');
            for(int i=1;i<len;i++){
                putchar('0');
            }
            putchar('\n');
        }
    }
    return 0;
}