Equidistant String

题面翻译

题目描述

Susie 喜欢字符串。她的字符串只包含数字 $0$ 和 $1$。今天，她使用了汉明距离法计算了它们之间的距离。

汉明距离的定义表示两个相同长度字符串对应位置的不同字符的数量。

有2个长度为 $n$ 的字符串 $s$ 和 $t$ 她还想要一个长度为 $n$ 的字符串 $p$ 使得 $p$ 到 $s$ 的距离等于 $p$ 到 $t$ 的距离

请你帮她找到这样的字符串 $p$。可能有很多种答案，找到一种即可。

输入格式

第一行是字符串 $s$

第二行是字符串 $t$

输出格式

输出一行字符串 $p$，如果不存在满足要求的字符串 $p$，输出 impossible

样例说明

第一组样例：汉明距离为3

答案也可以为 $1001$

第二组样例：无法找到满足要求的字符串

translated by Yang080108

题目描述

Little Susie loves strings. Today she calculates distances between them. As Susie is a small girl after all, her strings contain only digits zero and one. She uses the definition of Hamming distance:

We will define the distance between two strings $ s $ and $ t $ of the same length consisting of digits zero and one as the number of positions $ i $ , such that $ s_{i} $ isn’t equal to $ t_{i} $ .

As besides everything else Susie loves symmetry, she wants to find for two strings $ s $ and $ t $ of length $ n $ such string $ p $ of length $ n $ , that the distance from $ p $ to $ s $ was equal to the distance from $ p $ to $ t $ .

It’s time for Susie to go to bed, help her find such string $ p $ or state that it is impossible.

输入格式

The first line contains string $ s $ of length $ n $ .

The second line contains string $ t $ of length $ n $ .

The length of string $ n $ is within range from $ 1 $ to $ 10^{5} $ . It is guaranteed that both strings contain only digits zero and one.

输出格式

Print a string of length $ n $ , consisting of digits zero and one, that meets the problem statement. If no such string exist, print on a single line “impossible” (without the quotes).

If there are multiple possible answers, print any of them.

样例 #1

样例输入 #1

0001
1011

样例输出 #1

0011

样例 #2

样例输入 #2

000
111

样例输出 #2

impossible

提示

In the first sample different answers are possible, namely — 0010, 0011, 0110, 0111, 1000, 1001, 1100, 1101.

唯一要注意的是，当i处两个字符串的i处的字符不一样时，不可以轮流添加1，0，如果两个字符串是s1=1010,s2=0101, 如果轮流加1和0，s就是1010，这样s到s1的距离是0，到s2的距离是4，所以正确做法是前面一半和s1相同，后面一半和s2相同

错误

const int N = 1e6 + 10;
int a[N];
void solve()
{
    string s1, s2;
    cin >> s1 >> s2;
    int ans = 0;
    for (int i = 0; i < s1.size(); i++)
    {
        if (s1[i] != s2[i]) ans++;
    }
    if (ans % 2 == 1)
    {
        cout << "impossible" << '\n';
        return;
    }
    string s;
    int top = 1;
    for (int i = 0; i < s1.size(); i++)
    {
        if (s1[i] != s2[i])
        {
            if (top == 1) s += "1";
            else s += "0";
            top ^= 1;
        }
        else s += s1[i];
    }
    cout << s << '\n';
}

正确

const int N = 1e6 + 10;
int a[N];
void solve()
{
    string s1, s2;
    cin >> s1 >> s2;
    int ans = 0;
    for (int i = 0; i < s1.size(); i++)
    {
        if (s1[i] != s2[i]) ans++;
    }
    if (ans % 2 == 1)
    {
        cout << "impossible" << '\n';
        return;
    }
    string s;
    int top = ans / 2;
    for (int i = 0; i < s1.size(); i++)
    {
        if (s1[i] != s2[i]&&top>=1)
        {
            s += s1[i];
            top--;
        }
        else s += s2[i];
    }
    cout << s << '\n';
}