题解 | #第五届太原理工大学程序设计新生赛决赛（重现赛）#

A

考虑构造长度为 $n$ 的字符串，每 $k$ 个 $1$ 中间插入一个 $0$ ， $1$ 的数量够了就剩下全是 $0$ ，如果最终 $1$ 的数量不够则输出 $\text{NO}$ ，复杂度 $O (n)$ 。

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, m, k;
    cin >> n >> m >> k;

    int c = 0;

    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        if ((i + 1) % (k + 1) != 0 && c < m) {
            a[i] = 1;
            c++;
        }
    }

    if (c != m) {
        cout << "NO\n";
        return 0;
    }
    cout << "YES\n";
    for (auto &x : a) {
        cout << x;
    }
    cout << '\n';
    
    return 0;
}

B

找最右边的 C，找不到就输出 $\text{draw}$ ，然后数该 C 前面有几个 B 和 C，记为 $\text{cnt}$ ， $\text{cnt - 1}$ 即为答案，复杂度 $O (n)$ 。

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;
    string s;
    cin >> n >> s;
    int k = -1;
    for (int i = n - 1; i >= 1; i--) {
        if (s[i] == 'C') {
            k = i;
            break;
        }
    }
    if (k == -1) {
        cout << "draw\n";
        return 0;
    }
    int ans = 0;
    for (int i = 0; i < k; i++) {
        if (s[i] != 'A') {
            ans++;
        }
    }
    if (ans < 1) {
        cout << "draw\n";
        return 0;
    }
    ans--;
    cout << ans << '\n';
    
    return 0;
}

C

注意到 $\sum y\le 10^{6}$ ，直接模拟即可，复杂度 $O(n+\sum y)$ 。

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;

    vector<int> a(n);
    while (q--) {
        int x, y;
        cin >> x >> y;
        x--;

        int y1 = y;
        for (int i = x; i >= 0 && y1; i--) {
            a[i] += y1;
            y1--;
        }

        int y2 = y - 1;
        for (int i = x + 1; i < n && y2; i++) {
            a[i] += y2;
            y2--; 
        }
    }

    for (int i = 0; i < n; i++) {
        cout << a[i] << " \n"[i == n - 1];
    }
    
    return 0;
}

若 $\sum y$ 没有限制，则是树状数组区间加等差数列板题，复杂度 $O(n\log n+q\cdot \log n)$ ，当然了也可以不用树状数组。

D

先全部按位或起来，然后考虑去掉每一个，对所有值取最大。实现上考虑每一位上的 $1$ 的数量，复杂度 $O(31\cdot n)$ 。

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;
    cin >> n;
    vector<int> b(31);
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < 31; j++) {
            if (a[i] >> j & 1) {
                b[j]++;
            }
        }
    }

    int ans = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < 31; j++) {
            if (a[i] >> j & 1) {
                b[j]--;
            } 
        }
        int res = 0;
        for (int j = 30; j >= 0; j--) {
            res *= 2;
            res += (b[j] != 0);
        }
        for (int j = 0; j < 31; j++) {
            if (a[i] >> j & 1) {
                b[j]++;
            }
        }
        ans = max(ans, res);
    }

    cout << ans << '\n';
    return 0;
}

E

先找最左侧 $\text{1}$ 和最右侧 $\text{1}$ ，记为 $l, r$ ，看中间有没有 $\text{0}$ ，有 $\text{0}$ 或者 $r - l + 1 > k$ 则输出 $\text{delicious}$ ，然后把所有 $\text{?}$ 变成 $\text{1}$ ，然后枚举区间， $l, r$ 要被包含于该区间，复杂度 $O (n)$ 。

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, m;
    string s;
    cin >> n >> m >> s;

    int l = -1, r = -1;
    for (int i = 0; i < n; i++) {
        if (s[i] == '1') {
            if (l == -1) {
                l = i;
            }
            r = i;
        }
    }
    
    for (int i = l; i <= r; i++) {
        if (s[i] == '0') {
            cout << "delicious\n";
            return 0;
        }
    }

    if (r - l + 1 > m) {
        cout << "delicious\n";
        return 0;
    }

    vector<int> sum(n + 1);
    for (int i = 0; i < n; i++) {
        sum[i + 1] = sum[i] + (s[i] != '0');
    }
    int ans = 0;
    for (int i = m; i <= n; i++) {
        if (l == -1 && sum[i] - sum[i - m] == m) {
            ans++;
        }
        if (i - m <= l && r < i && sum[i] - sum[i - m] == m) {
            ans++;
        }
    }
    if (ans == 0) {
        cout << "delicious\n";
        return 0;
    }
    cout << ans << '\n';
    
    return 0;
}

F

$p$ 很小，算的时候记录一下 $x^{y}$ 的值就行，这里用了快速幂，复杂度 $O(9\cdot p\cdot \log p+n)$ ，预处理的话复杂度是 $O(9\cdot p+n)$ 。

C++ Code

#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

unsigned _seed = 0x80000001;
int _readt;

void _srand(int seed) {
    _seed = seed | 0x80000000;
    _readt = 0;
}

int _read() {
    _seed ^= _seed >> 10;
    _seed ^= _seed << 9;
    _seed ^= _seed >> 25;
    _readt ^= 1;
    if (_readt) {
        return _seed % 9 + 1;
    } else {
        return _seed % 10000000;
    }
}

int power(int a, int b, int p) {
    int res = 1;
    for (; b; b >>= 1, a = a * a % p) {
        if (b & 1) {
            res = res * a % p;
        }
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int P[10][100];

    for (int i = 0; i < 10; i++) {
        for (int j = 0; j < 100; j++) {
            P[i][j] = -1;
        }
    }

    int n, p, seed;
    cin >> n >> p >> seed;

    _srand(seed);
    int ans = 0;

    for (int i = 0; i < n; i++) {
        int x, y;
        x = _read();
        y = _read();
        y %= (p - 1);
        if (P[x][y] != -1) {
            ans += P[x][y];
        } else {
            P[x][y] = power(x, y, p);
            ans += P[x][y];
        }
        
        if (ans >= p) {
            ans -= p;
        }
    }
    cout << ans << '\n';

    return 0;
}

G

枚举修改方案（其实只有两种），注意若原本就是回文，则必须修改中间那个字符，复杂度 $O (n)$ 。

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;
    string s;
    cin >> n >> s;
    set<string> st;
    for (int i = 0; i < n; i++) {
        if (s[i] != s[n - 1 - i]) {
            char o = s[i];
            s[i] = s[n - 1 - i];
            st.insert(s);
            s[i] = o;
        }
    }
    if (st.empty()) {
        if (s[n / 2] == 'a') {
            s[n / 2]++;
        } else {
            s[n / 2] = 'a';
        }
        cout << s << '\n';
        return 0;
    }
    cout << *st.begin() << '\n';
                           
    return 0;
}

H

简单草稿纸模拟发现好像只有 $1$ 的时候 $\text{Bob}$ 能赢，复杂度 $O (1)$ 。

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;
    cin >> n;
    if (n == 1) {
        cout << "Bob\n";
        return 0;
    } 
    cout << "Alice\n";
    
    return 0;
}

I

签到。

C++ Code

#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    string s;
    cin >> s;
    if (s.find("eat") != -1) {
        cout << "eeffQAQ\n";
    } else {
        cout << "What does it mean?\n";
    }

    return 0;
}

J

重构这个图，只保留 Y 到 T，Y 到 U，U 到 T 的单向边，然后记下出度（Y U 边不管），若该边为 Y U 边，对答案贡献 $deg_u\cdot deg_v$ ，但是会出现 T 被用了两次的情况，然后根号分治跑个三元环计数，减掉三元环的数量就是答案，复杂度 $O(n+m\cdot \sqrt{m})$ 。

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, m;
    string s;
    cin >> n >> m >> s;
    
    vector<int> deg(n);
    vector<array<int, 2>> e;

    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;

        u--, v--;

        if (s[u] == 'T') {
            swap(u, v);
        }

        bool ok = 0;
        if (s[u] == 'U' && s[v] == 'Y') {
            ok = 1;
        } else if (s[u] == 'Y' && s[v] == 'U') {
            ok = 1;
        } else if (s[u] == 'Y' && s[v] == 'T') {
            ok = 1;
        } else if (s[u] == 'U' && s[v] == 'T') {
            ok = 1;
        }

        if (ok) {
            if (s[v] == 'T') {
                deg[u]++;
            }
            e.push_back({u, v});
        }
    }

    i64 ans = 0;
    for (auto &[u, v] : e) {
        if (s[v] != 'T') {
            ans += 1LL * deg[u] * deg[v];
        }
    }

    vector<vector<int>> g(n);
    deg.assign(n, 0);
    for (auto &[u, v] : e) {
        deg[u]++;
        deg[v]++;
    }
    for (auto &[u, v] : e) {
        if (deg[u] > deg[v]) {
            g[u].push_back(v);
        } else if (deg[u] == deg[v] && u > v) {
            g[u].push_back(v);
        } else {
            g[v].push_back(u);
        }
    }

    vector<int> pre(n, -1);
    
    int cnt = 0;
    for (int x = 0; x < n; x++) {
        for (auto &y : g[x]) {
            pre[y] = x;
        }
        for (auto &y : g[x]) {
            for (auto &z : g[y]) {
                if (pre[z] == x) {
                    cnt++;
                }
            }
        }
    }

    cout << ans - cnt << '\n';

    return 0;
}

K

观察到每个人会把车停在两辆车的中间，模拟一下就行，用 $\text{dfs}$ ，复杂度 $O (n)$ 。

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;
    cin >> n;
    
    if (n <= 2) {
        cout << 1 << '\n';
        return 0;
    }
    vector<int> a(n);
    a[0] = 1;
    a[n - 1] = 1;

    function<void(int, int)> dfs = [&](int l, int r) {
        if (l == r) {
            return;
        }
        int mid = (l + r) >> 1;
        
        bool ok = 1;
        if (mid + 1 < n && a[mid + 1] == 1) {
            ok = 0;
        }
        if (mid - 1 >= 0 && a[mid - 1] == 1) {
            ok = 0;
        }
        if (ok) {
            a[mid] = 1;
            dfs(l, mid);
            dfs(mid, r);
        }
    };
    int ans = 0;
    dfs(0, n - 1);
    for (int i = 0; i < n; i++) {
        if (a[i] == 1) {
            ans++;
        }
    }
    cout << ans << '\n';
    
    return 0;
}

L

$\text{dp}$ ，复杂度 $O(3\cdot n)$ 。

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;
    cin >> n;
    vector<int> a(3 * n);
    for (int i = 0; i < 3 * n; i++) {
        cin >> a[i];
    }
    vector<i64> f(3 * n);
    for (int i = 0; i < 3; i++) {
        f[i] = a[i];
    }
    for (int i = 3; i < 3 * n; i++) {
        f[i] = min({f[i - 1], f[i - 2], f[i - 3]}) + a[i];
    }
    cout << min({f[3 * n - 1], f[3 * n - 2], f[3 * n - 3]}) << '\n';
    
    return 0;
}

N

搞成一样长，然后直接加，复杂度 $O (1)$ 。

C++ Code

#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    string a, b;
    cin >> a >> b;
    int A = stoi(a), B = stoi(b);
    int N = max(a.size(), b.size());

    for (int i = 0; i < N - (int) a.size(); i++) {
        A *= 10;
    }
    for (int i = 0; i < N - (int) b.size(); i++) {
        B *= 10;
    }
    cout << A + B << '\n';
    
    return 0;
}