526互联

2023 CCPC Henan Provincial Collegiate Programming Contest

发布时间 2023-05-25 15:57:48作者: Kidding_Ma

链接：https://codeforces.com/gym/104354

A. 小水獭游河南

使用 \(\text{hash}\)，\(O(\sum n)\)。

C++ Code 
#include "bits/stdc++.h"
 
using namespace std;
using i64 = long long;
 
constexpr int B = 114514;
constexpr i64 P = 1000000000039;
 
vector<i64> p;
 
void init(int N) {
    p.assign(N, 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 toi64(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();
    StringHash hs;
    for (int i = 0; i < n; i++) {
        hs.push_back(s[i]);
    }
    StringHash rhs;
    for (int i = n - 1; i >= 0; i--) {
        rhs.push_back(s[i]);
    }
    vector<int> vis(26);
    for (int i = 0; i < n - 1; i++) {
        if (!vis[s[i] - 'a']) {
            vis[s[i] - 'a'] = 1;
            if (hs.toi64(i + 1, n) == rhs.toi64(0, n - i - 1)) {
                cout << "HE\n";
                return;
            }
        } else {
            break;
        }
    }
    cout << "NaN\n";
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    init(1E5);
 
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
 
    return 0;
}

B. Art for Rest

前缀最大和后缀最小，\(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;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
 
    int inf = 1E9;
 
    vector<int> pre(n + 1), suf(n + 1, inf);
    for (int i = 0; i < n; i++) {
        pre[i + 1] = max(pre[i], a[i]);
    }
 
    reverse(a.begin(), a.end());
    for (int i = 0; i < n; i++) {
        suf[i + 1] = min(suf[i], a[i]);
    }
 
    reverse(suf.begin(), suf.end());
 
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        bool ok = 1;
        for (int j = i; j <= n; j += i) {
            if (pre[j] > suf[j]) {
                ok = 0;
                break;
            }
        }
        ans += (ok == 1);
    }
 
    cout << ans << '\n';
 
    return 0;
}

C. Toxel 与随机数生成器

\(\text{kmp}\)，\(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);
    
    string s;
    cin >> s;
    int n = s.size();
    vector<int> nex(n + 1);
    for (int i = 1, j = 0; i < n; i++) {
        while (j && s[i] != s[j]) {
            j = nex[j];
        }
        if (s[i] == s[j]) {
            j++;
        }
        nex[i + 1] = j;
    }
 
    for (int i = 0; i <= n; i++) {
        if (nex[i] >= 1000) {
            cout << "No\n";
            return;
        }
    }
    cout << "Yes\n";

    return 0;
}

E. 矩阵游戏

dp，\(O(nmx)\)。

C++ Code 
#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

constexpr int N = 500;
constexpr int M = 1000;

int f[N + 1][M + 1];

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

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

    for (int i = 0; i <= m; i++) {
        for (int j = 0; j <= x; j++) {
            f[i][j] = 0;
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            for (int k = x; k >= 0; k--) {
                f[j + 1][k] = max(f[j + 1][k], f[j][k]) + (a[i][j] == '1');
                if (k && a[i][j] == '?') {
                    f[j + 1][k] = max(f[j + 1][k - 1], f[j][k - 1]) + 1;
                }
            }
        }
    }

    cout << f[m][x] << '\n';
}

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

    int t;
    cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

F. Art for Last

使用 \(\text{ST}\) 表，\(O(n\log n)\)，还有别的方法。

C++ Code 
#include "bits/stdc++.h"
 
using namespace std;
using i64 = long long;
 
template <typename T>
struct SparseTable {
    int n;
    function<T(const T&, const T&)> func;
    vector<vector<T>> a;
    SparseTable(const vector<T> &init, const function<T(const T&, const T&)> &f) : n(init.size()), func(f) {
        int lg = __lg(n);
        a.assign(lg + 1, vector<T>(n));
        a[0] = init;
        for (int i = 1; i <= lg; i++) {
            for (int j = 0; j <= n - (1 << i); j++) {
                a[i][j] = func(a[i - 1][j], a[i - 1][(1 << (i - 1)) + j]);
            }
        }  	    
    }
    T get(int l, int r) {// [l, r)
    	int lg = __lg(r - l);
    	return func(a[lg][l], a[lg][r - (1 << lg)]);
    }
};
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    auto b = a;
    sort(b.begin(), b.end());
    vector<int> c(n - 1);
    for (int i = 0; i < n - 1; i++) {
        c[i] = b[i + 1] - b[i];
    }
    auto Min = [&](const int &a, const int &b) {
        return min(a, b);
    };
    SparseTable<int> mn(c, Min);
    i64 ans = 1E18;
    for (int i = 0; i + k - 1 < n; i++) {
        int x = b[i + k - 1] - b[i];
        int y = mn.get(i, i + k - 1);
        ans = min(ans, 1LL * x * y);
    }
    cout << ans << '\n';
    return 0;
}

G. Toxel 与字符画

模拟。

C++ Code 
#include "bits/stdc++.h"

using namespace std;
using i64 = long long;
using i128 = __int128;

constexpr i64 inf = 1E18;

i64 mul(i64 a, i64 b) {
    i128 res = static_cast<i128>(a) * b;
    if (res > inf) {
        return inf + 1;
    }
    return res;
}

i64 power(i64 a, i64 b) {
    i64 res = 1;
    for (; b; b >>= 1, a = mul(a, a)) {
        if (b & 1) {
            res = mul(res, a);
        }
    }
    return res;
}

vector<string> a = {
    "................................................................................",
    "................................................................................",
    "0000000.......1.2222222.3333333.4.....4.5555555.6666666.7777777.8888888.9999999.",
    "0.....0.......1.......2.......3.4.....4.5.......6.............7.8.....8.9.....9.",
    "0.....0.......1.......2.......3.4.....4.5.......6.............7.8.....8.9.....9.",
    "0.....0.......1.2222222.3333333.4444444.5555555.6666666.......7.8888888.9999999.",
    "0.....0.......1.2.............3.......4.......5.6.....6.......7.8.....8.......9.",
    "0.....0.......1.2.............3.......4.......5.6.....6.......7.8.....8.......9.",
    "0000000.......1.2222222.3333333.......4.5555555.6666666.......7.8888888.9999999.",
    "................................................................................"
};

vector<string> b = {
    "............................................................",
    "00000.....1.22222.33333.4...4.55555.66666.77777.88888.99999.",
    "0...0.....1.....2.....3.4...4.5.....6.........7.8...8.9...9.",
    "0...0.....1.22222.33333.44444.55555.66666.....7.88888.99999.",
    "0...0.....1.2.........3.....4.....5.6...6.....7.8...8.....9.",
    "00000.....1.22222.33333.....4.55555.66666.....7.88888.99999.",
    "............................................................",
    "............................................................",
    "............................................................",
    "............................................................"
};


vector<string> c = {
    "................................",
    "................................",
    "........IIIIIII.N.....N.FFFFFFF.",
    "...........I....NN....N.F.......",
    "=======....I....N.N...N.F.......",
    "...........I....N..N..N.FFFFFFF.",
    "=======....I....N...N.N.F.......",
    "...........I....N....NN.F.......",
    "........IIIIIII.N.....N.F.......",
    "................................"
};

void solve() {
    i64 A, B;
    scanf("%lld^{%lld}", &A, &B);
    int N = 10;
    i64 res = power(A, B);
    vector<string> ans(N);
    for (int i = 0; i < N; i++) {
        ans[i] += ".";
    }
    auto get = [&](const int &l, const int &len, const vector<string> &s) {
        for (int i = 0; i < N; i++) {
            ans[i] += s[i].substr(l, len);
        }

    };

    string SA = to_string(A);
    string SB = to_string(B);
    for (auto &x : SA) {
        int y = x - '0';
        get(y * 8, 8, a);
    }
    for (auto &x : SB) {
        int y = x - '0';
        get(y * 6, 6, b);
    }
    get(0, 8, c);
    if (res > inf) {
        get(8, 24, c);
    } else {
        string t = to_string(res);
        for (auto &x : t) {
            int y = x - '0';
            get(y * 8, 8, a);
        }
    }
    for (auto &x : ans) {
        cout << x << '\n';
    }
}

int main() {

    int t;
    scanf("%d", &t);
    while (t--) {
        solve();
    }

    return 0;
}

H. Travel Begins

贪心，\(O(t)\)。

C++ Code 
#include "bits/stdc++.h"
 
using namespace std;
using i64 = long long;
 
void solve() {
    int n, k;
    cin >> n >> k;
    int cnt = min(n * 2, k - 1);
    int ans2 = n - cnt / 2 + cnt;
    int ans1 = max(0, n - cnt / 2);
    cout << ans1 << ' ' << ans2 << '\n';
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
 
    return 0;
}

J. Mocha 沉迷电子游戏

计算几何，分两种情况，\(O(t)\)。

C++ Code 
#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

using Real = double;
using Point = complex<Real>;

const double Pi = acos(-1.0);

void solve() {
    int x, y;
    cin >> x >> y;
    Point p = Point(x, y);
    cin >> x >> y;
    Point a = Point(x, y);
    cin >> x >> y;
    Point b = Point(x, y);
    int v, t;
    cin >> v >> t;
    int r = v * t;
    Point c = (a + b) / 2.0;
    const double pa = abs(p - a);
    const double pc = abs(p - c);
    const double ab = abs(a - b);
    double ans = 0;
    const double ad = sqrt(pa * pa - 1LL * r * r);
    if (r > pa) {
        cout << Pi * r * r << '\n';
        return;
    }
    if (r <= pc) {   
        ans += ad * r;
        ans += pc * ab / 2;
        double ang = asin(ad / pa) + asin(ab / 2 / pa);
        ans += (Pi - ang) * r * r;
    } else {
        ans += ad * r * 2;
        double ang = asin(ad / pa);
        ans += (Pi - 2 * ang) * r * r;
    }
    cout << ans << '\n';
}

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

    cout << fixed << setprecision(15);

    int t;
    cin >> t;
    while (t--) {
        solve();
    }   

    return 0;
}

K. 排列与质数

小的全排列，大的构造，\(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 < 5) {
        cout << -1 << '\n';
        return 0;
    }
    if (n == 5) {
        cout << "1 3 5 2 4\n";
        return 0;
    }
    if (n == 6) {
        cout << "1 3 5 2 4 6\n";
        return 0;
    }

    if (n == 7) {
        cout << "1 3 5 2 7 4 6\n";
        return 0;
    }

    if (n == 8) {
        cout << "1 3 5 2 7 4 6 8\n";
        return 0;
    }

    if (n == 9) {
        cout << "1 3 5 2 4 7 9 6 8\n";
        return 0;
    }

    if (n == 10) {
        cout << "1 3 5 2 4 6 9 7 10 8\n";
        return 0;
    }

    if (n == 11) {
        cout << "1 3 5 2 4 6 11 9 7 10 8\n";
        return 0;
    }

    vector<int> ans;

    if (n % 2 == 0) {
        for (int i = 1; i < n - 1; i += 2) {
            ans.push_back(i);
            if (i == 5) {
                ans.push_back(2);
            }
        }
        for (int i = n; i >= 3; i -= 2) {
            ans.push_back(i);
            if (i == n - 4) {
                ans.push_back(n - 1);
            }
        }
    } else {
        for (int i = 1; i <= n; i += 2) {
            ans.push_back(i);
            if (i == 5) {
                ans.push_back(2);
            }
            if (i == n - 6) {
                ans.push_back(n - 1);
            }
        }
        for (int i = n - 3; i >= 4; i -= 2) {
            ans.push_back(i);
        }
    }
    for (int i = 0; i < n; i++) {
        cout << ans[i] << " \n"[i == n - 1];
    }

    return 0;
}