牛客周赛34

A 小红的字符串生成

小红拿到了两个字符，请你输出这两个字符可以生成的所有字符串。按任意顺序输出均可。

void solve() {
    string a, b;cin >> a >> b;
    if (a == b) {
        cout << "2\n" << a << '\n' << a + a << '\n';
    } else {
        cout << "4\n" << a << '\n' << a + b << '\n';
        cout << b << '\n' << b + a << '\n';
    }
}

B 小红的非排列构造

小红拿到了一个数组，她修改尽可能少的元素使其变成非排列。你能帮帮她吗？

void solve() {
    int n;cin >> n;vector<int> a(n);for (auto& i : a)cin >> i;
    sort(a.begin(), a.end());
    for (int i = 0;i < n;i++) {
        if (a[i] != i + 1) {
            cout << "0\n";return;
        }
    }
    cout << "1\n1 " << n + 1 << '\n';
}

C 小红的数字拆解

小红拿到了一个偶数，她希望你将其切割成尽可能多的偶数。你能帮帮她吗？

void solve() {
    string s;cin >> s;
    vector<string> a;
    int j = 0;
    string t = "";

    for (int i = 0;i < s.size();i++) {
        t += s[i];
        if ((s[i] - '0') % 2 == 0) {
            a.push_back(t);t = "";
        }
    }

    sort(a.begin(), a.end(), [](auto x, auto y) {
        if (x.size() == y.size())
            return x < y;
        return x.size() < y.size();
        });
    for (auto i : a)cout << i << '\n';
}

D 小红的陡峭值

小红定义一个数组的陡峭值为相邻两数差的绝对值之和。
现在小红拿到了一个长度为 $n$ 的、仅由正整数组成的数组，但她有一些元素看不清了（用 0 表示），只记得数组的陡峭值恰好等于 1。
小红希望你能还原整个数组，你能帮帮她吗？如果无解，输出-1

调了半天，超级细节题。

细节：

• 当全为 0 时，直接输出 2 1 1 1 ... 1
• 算出的陡峭值>1，则无解
• 算出的陡峭值=1 则一定有解
• 算出的陡峭值=0，则特判只能在 0，n-1 下标位置，例如 1 0 1 1 1 则无解

void solve() {
    int n;cin >> n;vector<int> a(n), b;for (auto& i : a)cin >> i;
    for (int i = 0;i < n;i++) {
        if (a[i]) {
            b.push_back(a[i]);
        }
    }
    if (b.size() == 0) {
        for (int i = 0;i < n;i++) {
            a[i] = 1;
        }
        a[0] = 2;
        for (auto i : a)cout << i << ' ';
        return;
    }

    int cnt = 0;
    for (int i = 1;i < b.size();i++) {
        cnt += abs(b[i] - b[i - 1]);
    }
    if (cnt > 1) {
        cout << "-1\n";return;
    }
    if (cnt == 1) {
        int v1 = 0, v2 = 0, x = 0, y = 0;
        for (int i = 0;i < n;i++) {
            if (a[i]) {
                v1 = a[i];//第二个数字的结尾
                x = i;
            }
        }
        for (int i = 0;i < n;i++) {
            if (a[i] && a[i] != v1) {
                v2 = a[i];//第一个数字的结尾
                y = i;
            }
        }
        for (int i = 0;i <= y;i++) {
            a[i] = v2;
        }
        for (int i = y + 1;i < n;i++) {
            a[i] = v1;
        }

        for (auto i : a)cout << i << ' ';
        return;
    }
    if (cnt == 0) {
        int v = 0;
        for (int i = 0;i < n;i++) {
            if (a[i]) {
                v = a[i];
            }
        }
        int cnt1 = 0;
        for (int i = 0;i < n;i++) {
            if (!a[i] && !cnt1 && (i == 0 || i == n - 1))
                a[i] = v + 1, cnt1++;
            else a[i] = v;
        }

        int cnt2 = 0;
        for (int i = 1;i < a.size();i++) {
            cnt2 += abs(a[i] - a[i - 1]);
        }
        if (cnt2 != 1) {
            cout << "-1\n";return;
        }
        for (auto i : a)cout << i << ' ';
        return;
    }
}

E 小红的树形 dp

小红拿到了一棵树，每个节点上有一个字符，每个节点上的字符为'd'、'p'、'?'这三种。
现在请你将所有'?'字符变成'd'或者'p'字符，需要满足任意两个相邻节点的字符不同。你能帮帮她吗？

Solution

二分图/树形 DP/DFS

牛客周赛round34直播回放，二分图，置换环_哔哩哔哩_bilibili

二分图/树形 DP 需要学习🥲

(待更 $\dots$)

树一定是二分图

vector<int> g[200010];
int dp[200010];
void dfs(int x, int pr, int p) {
    dp[x] = p;
    for (auto i : g[x]) {
        if (i == pr)continue;
        dfs(i, x, 1 - p);
    }
}
void solve() {
    int n;cin >> n;string s;cin >> s;s = ' ' + s;
    for (int i = 0;i < n;i++) {
        int x, y;cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    dfs(1, 0, 1);
    set<int> d, p;
    for (int i = 1;i <= n;i++) {
        if (s[i] == 'd')d.insert(dp[i]);
        if (s[i] == 'p')p.insert(dp[i]);
    }
    if (d.size() > 1 || p.size() > 1) {
        cout << "-1\n";return;
    }
    if (d.size() == 1 && p.size() == 1 && (*d.begin()) == (*p.begin())) {
        cout << "-1\n";return;
    }
    if ((*d.begin()) == 1) {
        for (int i = 1;i <= n;i++) {
            if (dp[i] == 1)cout << "d";
            else cout << "p";
        }
    } else {
        for (int i = 1;i <= n;i++) {
            if (dp[i] == 1)cout << "p";
            else cout << "d";
        }
    }
}

F 小红的矩阵构造

构造一个 $n\times m$ 的矩阵要求满足所有元素之和为 $x$ ($x$ 是偶数)，且每行、每列的异或和全部相等。若无解输出 -1

Solution

构造

原题：

Problem - E - Codeforces

int a[1010][1010];
void solve() {
    int n, m, x;cin >> n >> m >> x;
    if (x == 2) {
        cout << "-1\n";return;
    }
    if (x % 4 == 0) {
        a[0][0] = a[0][1] = a[1][0] = a[1][1] = x / 4;
        for (int i = 0;i < n;i++) {
            for (int j = 0;j < m;j++) {
                cout << a[i][j] << " \n"[j == m - 1];
            }
        }
    } else {
	    a[2][1] = a[2][2] = a[1][2] = a[1][3] = a[3][1] = a[3][3] = 1;
        x -= 6;
        a[0][0] = a[0][1] = a[1][0] = a[1][1] = x / 4;
        for (int i = 0;i < n;i++) {
            for (int j = 0;j < m;j++) {
                cout << a[i][j] << " \n"[j == m - 1];
            }
        }
    }
}

G 小红的元素交换

小红拿到了一个排列，其中初始所有元素都是白色，但有一些元素被染成了红色。
小红每次操作可以选择交换任意一个红色元素和一个白色元素的位置。她希望操作尽可能少的次数使得数组变成升序。

若无解，输出 -1

Solution

置换环

(待更 $\dots$)没看懂

置换环是用来求解数组排序元素间所需最小交换次数这类问题。

若这题没有颜色限制，则每个环内的最小交换次数 为环上数量-1

总交换次数则为 $n-num(circle)$

牛客周赛round34直播回放，二分图，置换环_哔哩哔哩_bilibili

void solve() {
    int n;cin >> n;vector<int> a(n + 1);for (int i = 1;i <= n;i++)cin >> a[i];
    vector<bool> vis(n + 1, 0);
    string s;cin >> s;s = ' ' + s;
    vector<int> white, red, both;
    for (int i = 1;i <= n;i++) {
        vector<int> clr(26, 0);
        int cnt = 0;
        if (!vis[i]) {
            clr[s[i] - 'A'] = 1;
            vis[i] = 1;
            cnt++;
            for (int j = a[i];!vis[j];j = a[j]) {
                clr[s[j] - 'A'] = 1;
                vis[j] = 1;
                cnt++;
            }
            if (clr['W' - 'A'] && !clr['R' - 'A']) {//白环
                white.push_back(cnt);
            } else if (!clr['W' - 'A'] && clr['R' - 'A']) {//红环
                red.push_back(cnt);
            } else {
                both.push_back(cnt);
            }
        }
    }
    sort(red.begin(), red.end());
    sort(white.begin(), white.end());

    int ans = 0;
    while (white.size() && red.size()) {//白环和红环混合
        if (red.back() == 1 || white.back() == 1)break;
        int v1 = red.back(), v2 = white.back();
        red.pop_back(), white.pop_back();
        both.push_back(v1 + v2);
        ans++;
    }
    if (!both.size() && red.size() && white.size() && (red.back() > 1 || white.back() > 1)) {
        int v1 = red.back(), v2 = white.back();
        red.pop_back(), white.pop_back();
        both.push_back(v1 + v2);
        ans++;
    }
    if (red.size() && red.back() > 1 && !both.size()) {
        cout << "-1\n";return;
    }
    if (white.size() && white.back() > 1 && !both.size()) {
        cout << "-1\n";return;
    }
    while (both.size() && red.size()) {//混环和红环混合
        if (red.back() == 1)break;

        int v1 = red.back(), v2 = both.back();
        red.pop_back(), both.pop_back();
        both.push_back(v1 + v2);
        ans++;
    }
    while (both.size() && white.size()) {//混环和白环混合
        if (white.back() == 1)break;

        int v1 = white.back(), v2 = both.back();
        white.pop_back(), both.pop_back();
        both.push_back(v1 + v2);
        ans++;
    }
    for (auto i : both)ans += i - 1;
    cout << ans << '\n';
}

(待更 $\dots$)

void solve() {
    int n;cin >> n;vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    string s;cin >> s;

    if (!is_sorted(a.begin(),a.end()) && count(s.begin(), s.end(), s[0]) == n) {
        cout << -1 << '\n';return 0;
    }

    int res = 0;
    int white = 0, red = 0;
    for (int i = 0; i < n; i++) {
        if (a[i] == i + 1) continue;
        int state = 0;
        int tmp = 0;
        while (a[i] != i + 1) {
            int p1 = i, p2 = a[i] - 1;
            swap(a[p1], a[p2]);
            tmp++;
            state |= (s[p1] == 'R' ? 2 : 1);
            state |= (s[p2] == 'R' ? 2 : 1);
        }
        if (state == 3) {
            res += tmp;
        } else {
            res += tmp + 2;
            if (state == 1) {
                white++;
            } else {
                red++;
            }
        }
    }
    cout << res - min(white, red) * 2 << '\n';
}