NOIP2023 国庆集训 A 组 Day2

A. 叉叉计算（cross）

真就大水题一题，打暴力AC

#include <bits/stdc++.h>
using namespace std;
const int N = 100100;
char zf[N];
int num1[28], num2[28][N], d[28][N];
int ans;
int main() {
    freopen("cross.in", "r", stdin);
    freopen("cross.out", "w", stdout);
    cin >> zf + 1;
    int l = strlen(zf + 1), r;
    int t = 0;
    for (int i = 1; i <= l; i++) {
        int lta = zf[i] - &#039;a&#039; + 1;
        if (lta > t) {
            t = lta;
        }
        d[lta][++num1[lta]] = i;
        for (int j = 1; j <= 26; j++) {
            if (lta == j) {
                num2[j][i] = num2[j][i - 1] + 1;
            } else {
                num2[j][i] = num2[j][i - 1];
            }
        }
    }
    for (int i = 1; i <= t; i++) {
        for (int j = 1; j < num1[i]; j += 2) {
            for (int k = i + 1; k <= t; k++) {
                l = d[i][j] - 1, r = d[i][j + 1];
                if ((num2[k][r] - num2[k][l]) % 2 != 0) {
                    ans++;
                } else {
                    if ((num2[k][r] - num2[k][l]) != 0) {
                        if (num2[k][l] % 2 != 0) {
                            ans++;
                        }
                        if (num2[k][r] % 2 != 0) {
                            ans++;
                        }
                    }
                }
            }
        }
    }
    cout << ans << endl;
    return 0;
}

B. 病毒分裂（split）

快速幂，AC

#include <bits/stdc++.h>
using namespace std;
long long k, n, p;
long long ksm(long long x, long long y) {
    if (y == 0) {
        return 1;
    }
    long long l = y / 2;
    long long cmt = (ksm(x, l)) % p;
    long long s = (cmt * cmt) % p;
    if (y & 1) {
        s = (s * x) % p;
    }
    return s;
}
long long solve(long long x, long long y) {
    if (y == 1) {
        return x;
    }
    long long l = y / 2;
    long long cmt = solve(x, l);
    long long t = ksm(x, l);
    long long s = (cmt * t + cmt) % p;
    if (y & 1) {
        s = (s + ksm(x, y)) % p;
    }
    return s;
}
int main() {
    freopen("split.in", "r", stdin);
    freopen("split.out", "w", stdout);
    long long sum;
    cin >> k >> n >> p;
    long long ans = (solve(k, n - 2) + 1) % p;
    cout << ans << endl;
    return 0;
}

C. 慢跑问题（jogging）

拓扑+DP，AC

#include <bits/stdc++.h>
using namespace std;
const int N = 100100, N1 = 2000100, N2 = 2100;
int d[N], pre[N];
int n, ml, md;
int cnt;
struct edge {
    int next, to, dist;
} s[N1];
void add(int a, int b, int c) {
    s[++cnt].next = pre[a];
    s[cnt].to = b;
    s[cnt].dist = c;
    pre[a] = cnt;
}
int main() {
    freopen("jogging.in", "r", stdin);
    freopen("jogging.out", "w", stdout);
    cin >> n >> ml >> md;
    for (int i = 1; i <= ml; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        if (u < v) {
            add(u, v, w);
        } else {
            add(v, u, w);
        }
    }
    for (int i = 1; i <= md; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        if (u < v) {
            add(u, v, -w);
        } else {
            add(v, u, -w);
        }
    }

    for (int i = 1; i <= n; i++) {
        d[i] = INT_MAX;
    }
    d[1] = 0;
    for (int i = 1; i <= n; i++) {
        if (d[i] != INT_MAX) {
            for (int j = pre[i]; j; j = s[j].next) {
                int cmp = s[j].to;
                if (d[cmp] > d[i] + s[j].dist) {
                    d[cmp] = d[i] + s[j].dist;
                }
            }
        }
    }
    cout << d[n] << endl;
    if (d[n] < 0) {
        cout << "YES" << endl;
    } else {
        cout << "NO" << endl;
    }
    return 0;
}

D. 距离之美（good）

不会做

总结

今天300分，第一，老师奖了杯17块的饮料