CodeForces-584C Marina and Vasya

Table of Contents

CodeForces-584C Marina and Vasya #

题目大意 #

给定长度均为 $n$ 的字符串 $s_1, s_2$ 和整数 $t$ . 记 $f(a, b)$ 为 $a[i] \not = b[i]$ 的 $i$ 的个数. 构造 $s_3$ 使得 $f(s1, s3) = f(s2, s3) = t$ . 如果不存在这样的字符串, 返回 $-1$ .

Solution 1 #

记 $x = n - f(s1, s2)$ 为 $s1, s2$ 相同的字符数. 记 $y = n - t$ . 如果 $x \geq y$ , 那么 $s3$ 由 $s1, s2$ 相同的一部分与和它们都不相同的一部分构成. 如果 $x < y$ , 那么需要从剩余的 $n - x = f(s1, s2)$ 分拆出两个大小为 $y$ 的部分. 如果做不到这样的分拆, 应当返回 $-1$ . 代码如下:

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, t;
    string s1, s2;
    cin >> n >> t >> s1 >> s2;
    t = n - t;
    set<int> s;
    for (int i = 0; i < n; i++) {
        if (s1[i] == s2[i]) {
            s.insert(i);
        }
    }
    int x = s.size();
    if (2 * (t - x) + x > n) {
        printf("-1\n");
        return 0;
    }
    string ans = "";
    int cnt = t;
    for (int i = 0; i < n; i++) {
        if (s.count(i)) {
            if (cnt > 0) {
                ans.push_back(s1[i]);
                cnt--;
            }
            else {
                ans.push_back('a' + (s1[i] - 'a' + 1) % 26);
            }
        }
        else {
            ans.push_back('a');
            while (ans[i] == s1[i] || ans[i] == s2[i]) {
                ans[i]++;
            }
        }
    }
    if (cnt == 0) {
        cout << ans << endl;
        return 0;
    }
    cnt = t - s.size();
    bool is_one = true; // 是否在拆第一部分
    for (int i = 0; i < n; i++) {
        if (!s.count(i)) {
            if (cnt > 0) {
                if (is_one) {
                    ans[i] = s1[i];
                    cnt--;
                }
                else {
                    ans[i] = s2[i];
                    cnt--;
                }
            }
            if (cnt == 0 && is_one) {
                cnt = t - s.size();
                is_one = false;
            }
        }
    }
    cout << ans << endl;
    return 0;
}