题解 | #武汉理工大学第四届ACM校赛#

A

令 $k=k\mod 2n$

\begin{cases} k=0: \text{S}\ 回文则\ \text{Yes} \\ k=n:\text{Yes} \\ k>n:\text{S}\ 长度为\ \text{2n-k} \ 的前后缀相同且长度为\ \text{k-n} \ 的前后缀回文则\ \text{Yes} \\ k<n:\text{S}\ 长度为\ \text{k} \ 的前后缀相同且长度为\ \text{n-k} \ 的前后缀回文则\ \text{Yes} \end{cases}

这里考虑离线并用 $\text{hash}$ 维护， $O(n q)$ 。

C++ Code

#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

constexpr int B = 114514;
constexpr i64 P = 1000000000039;

i64 *p;

void init(int N) {
    p = new i64 [N + 1];
    for (int i = 0; i <= N; i++) {
        p[i] = 0;
    } 
    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;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    init(4E5);    
    int n, m;
    cin >> n >> m;
    string s;
    cin >> s;
    vector<pair<int, i64>> q;
    for (int i = 0; i < m; i++) {
        int o;
        cin >> o;
        if (o == 1) {
            char x;
            cin >> x;
            s.push_back(x);
        } else {
            i64 k;
            cin >> k;
            q.push_back({(int) s.size(), k});
        }
    }
    const int N = s.size();

    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(s[i]);
    }

    for (auto &[n, k] : q) {
        k = k % (2 * n);
        if (k > n) {
            cout << (
                hs.get(0, 2 * n - k) == hs.get(k - n, n) && 
                hs.get(0, k - n) == rhs.get(N - k + n, N) && 
                hs.get(2 * n - k, n) == rhs.get(N - n, N - 2 * n + k) ? "Yes" : "No" 
            ) << '\n';
        } else if (k == n) {
            cout << "Yes\n";
        } else if (k > 0) {
            cout << (
                hs.get(0, k) == hs.get(n - k, n) && 
                hs.get(0, n - k) == rhs.get(N - n + k, N) &&
                hs.get(k, n) == rhs.get(N - n, N - k) ? "Yes" : "No"
            ) << '\n';
        } else {
            cout << (hs.get(0, n) == rhs.get(N - n, N) ? "Yes" : "No") << '\n';
        }
    }

    return 0;
}

B

只做删除操作， $\text{dp}$ ， $O(n^3)$ 。

C++ Code

#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

constexpr int N = 500;
i64 f[N + 1][N + 1];

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    
    auto get = [&](int l, int r) {
        l--;
        r--;
        return 1LL * (a[r] - a[l]) * (a[r] - a[l]);
    };

    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= i - 2; j++) {
            for (int k = 0; k <= j; k++) {
                int pos = i - k - 1;
                f[i][j] = max(f[i][j], f[pos][j - k] + get(pos, i));
            }            
        }
    }
    cout << f[n][k] << '\n';

    return 0;
}

E

队友写的，感觉是模拟一下。

F

鸽巢定理， $O(6000^2)$ 。

C++ Code

#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

using Point = complex<int>;

#define x real
#define y imag

constexpr int N = 3000;
int vis[2 * N + 1][2 * N + 1][4];

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

    int n;
    cin >> n;
    vector<Point> a(n);
    for (int i = 0; i < n; i++) {
        int x, y;
        cin >> x >> y;
        a[i] = Point(x, y);
    }

    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            for (int k = j + 1; k < n; k++) {
                Point v = a[i] + a[j] + a[k] + Point(N, N);
                auto &f = vis[v.x()][v.y()];
                if (f[0] == 1) {
                    cout << "YES\n";
                    cout << f[1] + 1 << ' ' << f[2] + 1
                        << ' ' << f[3] + 1 << '\n'
                        << i + 1 << ' ' << j + 1 << ' ' << k + 1 << '\n';
                    return 0;
                } else {
                    f[0] = 1;
                    f[1] = i;
                    f[2] = j;
                    f[3] = k;
                }
            }
        }
    }
    cout << "NO\n";
    
    return 0;
}

H

队友写的，感觉是 dp 一下。

K

二分确定长度，贪心构造， $O(\log n)$ 。

C++ Code

#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

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

    i64 n;
    cin >> n;

    int N = 0;
    int l = 1, r = 5E5;
    while (l <= r) {
        int m = (l + r) >> 1;
        if ((1LL * m * m * m + 3LL * m * m + 2LL * m) / 6 >= n) {
            N = m;
            r = m - 1;
        } else {
            l = m + 1;
        }
    }
    
    vector<int> a(N);
    for (int i = 0; i < N; i++) {
        int j = i + 1;
        a[i] = min(1LL * j, n / (N - j + 1));
        n -= 1LL * a[i] * (N - j + 1);
    }

    cout << N << '\n';
    for (int i = 0; i < N; i++) {
        cout << a[i] << ' ';
    }

    return 0;
}

J

二分，容斥，快速分解质因子。

C++ Code

#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

using i128 = __int128;
 
i64 power(i64 a, i64 b, i64 m) {
    i64 res = 1;
    for (; b; b >>= 1, a = i128(a) * a % m) {
        if (b & 1) {
            res = i128(res) * a % m;
        }
    }
    return res;
}
 
bool isprime(i64 p) {
    if (p < 2) {
        return 0;
    }
    i64 d = p - 1, r = 0;
    while (!(d & 1)) {
        r++;
        d >>= 1;
    }
    int prime[] = {2, 3, 5, 7, 11, 13, 17, 19, 23};
    for (auto a : prime) {
        if (p == a) {
            return true;
        }
        i64 x = power(a, d, p);
        if (x == 1 || x == p - 1) {
            continue;
        }
        for (int i = 0; i < r - 1; i++) {
            x = i128(x) * x % p;
            if (x == p - 1) {
                break;
            }
        }
        if (x != p - 1) {
            return false;
        }
    }
    return true;
}
 
mt19937 rng((unsigned int) chrono::steady_clock::now().time_since_epoch().count());
 
i64 rho(i64 x) {
    i64 s = 0, t = 0;
    i64 c = i64(rng()) % (x - 1) + 1;
    i64 val = 1;
    for (int goal = 1; ; goal <<= 1, s = t, val = 1) {
        for (int step = 1; step <= goal; step++) {
            t = (i128(t) * t + c) % x;
            val = i128(val) * abs(t - s) % x;
            if (step % 127 == 0) {
                i64 g = gcd(val, x);
                if (g > 1) {
                    return g;
                }
            }
        }
        i64 g = gcd(val, x);
        if (g > 1) {
            return g;
        }
    }
}

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

    i64 n, k;
    cin >> n >> k;

    unordered_set<i64> st;
    function<void(i64)> get = [&](i64 x) {
        if (x < 2) {
            return;
        }
        if (isprime(x)) {
            st.insert(x);
            return;
        }
        i64 mx = rho(x);
        get(x / mx);
        get(mx);
    };
    
    get(n);
    
    vector<i64> p(st.begin(), st.end());

    i64 l = 1, r = n;
    i64 ans = 0;
    while (l <= r) {
        i64 m = (l + r) / 2;

        i64 sum = 0;
        function<void(int, i64, int)> dfs = [&](int i, i64 s, int c) {
            if (i == p.size()) {
                sum += c * s;
                return;
            }
            dfs(i + 1, s, c);
            dfs(i + 1, s / p[i], -c);
        };

        dfs(0, m, 1);
        if (sum < k) {
            l = m + 1;
            ans = l;
        } else {
            r = m - 1;
        }
    }
    cout << ans << '\n';
}