题解 | #2023牛客暑期多校训练营2#

我是一个演员 QAQ

D

倒着取没取过的每个人自己所能取的最大就行， $O (n m + m k)$ 。

C++ Code

#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

void solve() {
    int n, m, k;
    cin >> n >> m >> k;

    vector<vector<int>> a(n, vector<int>(m));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> a[i][j];
        }
    }
  
    vector<int> vis(m);
    for (int i = k - 1; i >= 0; i--) {
        int mx = 0;
        int k = 0;
        for (int j = 0; j < m; j++) {
            if (!vis[j] && a[i % n][j] > mx) {
                mx = a[i % n][j];
                k = j;
            }
        }
        vis[k] = 1;
    }
  
    for (int i = 0; i < m; i++) {
        if (vis[i]) {
            cout << i + 1 << ' ';
        }
    }
    cout << '\n';
}
            
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

E

考虑在 $x$ 后面加 $0$ ，最多加到 $18$ 位， $O(18\cdot \log(10^{18}))$ 。

C++ Code

#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

void solve() {
    int x;
    cin >> x;
    for (i64 p = 1; __int128(x) * p <= 1E18; p *= 10) {
        i64 tx = p * x;
        i64 y = sqrtl(tx);
        while (y * y < tx) {
            y++;
        }
        if (y * y / p == x) {
            cout << y << '\n';
            return;
        }
    }
    cout << "-1\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

F

这里是队友猜的。

$n$ 为偶数，所有状态都能得到，先手必胜。

$n$ 为奇数，不能得到所有状态， $r_{0} + g_{0} + b_{0}$ 为偶数，先手必胜。

$O (1)$ 。

G

贪心， $j$ 从 $0$ 开始，每次找离 $j$ 最近的 $i$ ，只要 $[j, i)$ 是中心对称 $j$ 就跳到 $i$ ，能跳到 $n$ 就证明 Yes。

使用 $\text{hash}$ 实现， $O (n)$ 。

C++ Code

#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

unordered_map<char, char> mp = {
    {'s', 's'},
    {'o', 'o'},
    {'x', 'x'},
    {'z', 'z'},
    {'b', 'q'},
    {'q', 'b'},
    {'d', 'p'},
    {'p', 'd'},
    {'u', 'n'},
    {'n', 'u'}
};

constexpr int B = 777;
constexpr i64 P = 10000000000031;

constexpr int N = 5E6;
  
i64 p[N + 1];
  
void init() {
    p[0] = 1;
    for (int i = 1; i <= N; i++) {
        p[i] = p[i - 1] * B % P;
    }
}

struct StringHash {
    vector<i64> h;
    StringHash() : h(1) {}
    void push_back(char ch) {
        h.push_back((h.back() * B + ch) % P);
    }
    i64 get(int l, int r) { // [l, r)
        return (h[r] + __int128(h[l]) * (P - p[r - l])) % P;
    }
};

void solve() {
    string s;
    cin >> s;
    int n = s.size();
    for (int i = 0; i < n; i++) {
        if (!mp.count(s[i])) {
            cout << "No\n";
            return;
        }
    }
    StringHash hs, rhs;
    for (int i = 0; i < n; i++) {
        hs.push_back(s[i]);
    }
    for (int i = n - 1; i >= 0; i--) {
        rhs.push_back(mp[s[i]]);
    }
    int j = 0;
    for (int i = 1; i <= n; i++) {
        if (hs.get(j, i) == rhs.get(n - i, n - j)) {
            j = i;
        }
    }
    cout << (j == n ? "Yes" : "No") << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    init();
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    
    return 0;
}

H

$\text{A}$ 相当于 $x\rightarrow(-x)+(-1)$ ， $\text{B}$ 相当于 $x\rightarrow x+1$ 。

前缀和跑出 $\text{A}$ 的数量和 $1$ 的量。

先看区间有几个 $\text{A}$ ，确定正负，然后看是加上这段的 $1$ 的量还是减去 $1$ 的量。

$O (n + 50 q)$ 。

C++ Code

#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, q;
    cin >> n >> q;
    string s;
    cin >> s;
    vector<int> a(n + 1), b(n + 1);

    for (int i = 0; i < n; i++) {
        a[i + 1] = a[i] + (s[i] == 'A');
        b[i + 1] = b[i] + (a[i] % 2 ? -1 : 1);
    }

    i64 ans = 0;
    for (int i = 0; i < q; i++) {
        int l, r;
        string t;
        cin >> l >> r >> t;
        l = (ans ^ l) % n + 1;
        r = (ans ^ r) % n + 1;
        if (l > r) {
            swap(l, r);
        }
        i64 x = 0;
        int N = t.size();
        for (int j = 0; j < N; j++) {
            x *= 2;
            x += t[j] - '0';
        }
        int add = b[r] - b[l - 1];
        if (a[l - 1] % 2) {
            x -= add;
        } else {
            x += add;
        }
        if ((a[r] - a[l - 1]) % 2) {
            x = -x;
        }
        i64 p = 1LL << N;
        x = ((x % p) + p) % p;
        ans = x;
        for (int i = N - 1; i >= 0; i--) {
            cout << (ans >> i & 1);
        }
        cout << '\n';
    }

    return 0;
}

I

如果 $n$ 是偶数，输出：

ooooxxxxooooxx
xxxxooooxxxxoo
ooooxxxxooooxx
xxxxooooxxxxoo

这样两种的数量肯定相同。

如果 $n$ 是奇数，最后一行交替。

C++ Code

#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

void solve() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n / 2 * 2; i++) {
        int p = i % 2;
        for (int j = 0; j < m; j++) {
            int c = (p + (j / 4) % 2) % 2;
            cout << (c ? 'x' : 'o');
        }
        cout << '\n';
    }
    if (n % 2 == 1) {
        for (int i = 0; i < m; i++) {
            cout << (i % 2 ? 'o' : 'x');
        }
        cout << '\n';
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}