### 2024 江西省赛题解(A,C,D,G,H,J,K,L) BEFI待补

A.

输出 $a+b+c$ 即可。

void slove () {
    int a, b, c;
    cin >> a >> b >> c;
    cout << (a + b + c) << endl;
}

B.

C.

如果 ${\sum }_{i=1}^n{a}_i=S$ 那么存在所有人说的都是真话的可能。

否则，我们可以假设 $n-1$ 个人说的是真话，最后一个人是假话。

void slove () {
    int n, s;
    cin >> n >> s;

     vector <int> a(n + 1);
     for (int i = 1; i <= n; i++) {
        cin >> a[i];
        s -= a[i];
     }

     if (s == 0) cout << n << endl;
     else cout << n - 1 << endl;
}

D.

设 $x,y$ 的最大公约数是 $d$，最小公倍数是 $lcm$，则有 $x=k_{1}d,y=k_{2}d,lcm=\frac{xy}{d}$。

思考一个问题，对 $x,y$ 进行操作后，它们求和会变大还是变小？

$x+y=(k_1+k_2)d$，$d+lcm=(k_1{k}_2+1)d$

对于任意正整数都有 $k_1+k_2\le k_1{k}_2+1$。所以我们能用操作就用操作。

当什么时候取等号？设 $(k_1\le k_2)$，则当且仅当 $k_1=1$ 时取等号，也就是 $x$ 是 $y$ 的因子时取等号。

往更本质思考，$gcd$ 的操作是把 $x,y$ 的每种质因子最小出现次数留下后组成的值，$lcm$ 是把 $x,y$ 中每种质因子的最多出现次数留下来组成的值。

当什么时候和取最大？当任意操作都会取等号的时候。

也就是当数组中任意两个数都成倍数关系的时候。

所以可以对于每种质因子，为每种质因子创建一个出现次数列表，将出现次数最多的依次从后往前分配。

使得最后的数最大，次大，$\cdots$，直到最小。

int power(int a, int b) {
    int s = 1;
    while (b) {
        if (b & 1) s = s * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return s;
}

void solve () {
    int n;
    cin >> n;

    map <int, vector <int>> mp;

    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;

        for (int j = 2; j * j <= x; j++) {
            int cnt = 0;
            while (x % j == 0) {
                x /= j;
                cnt ++;
            }
            if (cnt) mp[j].emplace_back(cnt);
        }

        if (x > 1) mp[x].emplace_back(1);
    }



    vector <int> ans (n + 1, 1);
    for (auto &[a, v] : mp) {
        int bnt = n;
        sort (v.begin(), v.end());
        while (v.size()) {
            ans[bnt--] = ans[bnt] * power(a, v.back()) % MOD;
            v.pop_back();
        }
    }

    int sum = 0;
    for (int i = 1; i <= n; i++) sum = (sum + ans[i]) % MOD;
    cout << sum << endl;

}

E.

F.

G.

如果一个数是 $5$ 的倍数，它的最后一位必须是 $5$ 或 $0$。

因为是 $11$ 进制，不管是 $11$ 的多少次幂，其个位数都是 $1$。

题目给出的是 a b 表示连续 a 个 $b\times 11^{\alpha }$，答案就是累加 $a\times b$ 的值。

最终判断是否是 $5$ 的倍数即可。

void solve () {
    int n;
    cin >> n;

    int sum = 0;
    for (int i = 1; i <= n; i++) {
        int a; char b;
        cin >> a >> b;
        if (b == 'A') {
            continue;
        } else {
            sum += a*(int)(b - '0');
        }
    }

    cout << (sum % 5 == 0 ? "Yes" : "No") << endl;
}

H.

转换为计算 $K$ 中的每一位对最终答案的贡献。

最好是画图模拟这个样例。

发现 $K_{1,1}$ 的贡献是 $I$ 矩阵的 $(1,1)\sim (1+n-k,1+m-l)$。

发现 $K_{i,j}$ 的贡献是 $I$ 矩阵的 $(i,j)\sim (i+n-k,j+m-l)$。

如果 $I$ 矩阵的$(i,j)\sim (i+n-k,j+m-l)$ 大于 $0$ 那么 $K_{i,j}$ 取 $1$ 即可，如果小于 $0$ 取 $-1$，否则取 $0$。

const int N = 1e3 + 7;
 
int I[N][N], K[N][N], S[N][N];
 
void slove () {
    int n, m, k, l;
    cin >> n >> m >> k >> l;
 
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> I[i][j];
            S[i][j] = S[i - 1][j] + S[i][j - 1] + I[i][j] - S[i - 1][j - 1];
        }
    }
 
    auto getS =[&](int x1, int y1, int x2, int y2) {
        return S[x2][y2] - S[x1 - 1][y2] - S[x2][y1 - 1] + S[x1 - 1][y1 - 1];
    };
 
    int ans = 0;
 
    for (int i = 1; i <= k; i++) {
        for (int j = 1; j <= l; j++) {
            int x1 = i, y1 = j;
            int x2 = i + n - k, y2 = j + m - l;
 
            int sum = getS(x1, y1, x2, y2);
            ans += (sum > 0 ? sum : -sum);
        }
    }

    cout << ans << endl;
}

I.

J.

模拟。

void solve () {
    string s;
    cin >> s;

    // 判断一下是不是 Thirteen Orphans
    string temp = s;
    map <char, set<int>> mp;

    for (int i = 0; i < 28; i += 2) {
        mp[s[i + 1]].insert((int)(s[i] - '0'));
    }

    bool is_Thirteen = true;

    for (auto i : mp) {
        if (i.first == 'p' or i.first == 's' or i.first == 'm') {
            if (i.second.size() != 2 or !i.second.count(1) or !i.second.count(9)) {
                is_Thirteen = false;
                break;
            }
        } else {
            if (i.second.size() != 7) {
                is_Thirteen = false;
                break;
            }
        } 
    }

    if (is_Thirteen) {
        cout << "Thirteen Orphans" << endl;
        return;
    }

    map <pair<char,char>, int> mmp;

    for (int i = 0; i < 28; i += 2) {
        mmp[pair<char,char>{s[i], s[i + 1]}]++;
    }

    bool is_Pairs = true;

    int bnt = mmp.size();
    for (auto i : mmp) {
        if (i.second != 2) is_Pairs = false;
    }

    if (bnt == 7 and is_Pairs) {
        cout << "7 Pairs" << endl;
        return;
    }

    cout << "Otherwise" << endl;
}

K.

输出 $2^{n-1}$。

int power (int a, int b, int mod) {
    int s = 1;
    while (b) {
        if (b & 1) s = s * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return s;
}

void slove () {
    int n;
    cin >> n;
    cout << power(2, n - 1, 998244353ll) << endl;
}

L.

首先对 $K$ 个点都跑一遍单源最短路 $Dijkstra$，时间复杂度 $O(knlogn)$。

需要观察到一个很重要的性质：门开和门关最多执行 $2K$ 次，其他时候都是承接上一秒的状态，对于上一秒的状态直接记录即可。门开和门关时重新计算一下每个点到哪个门是最近的。

时间复杂度是 $O(T+2k^{2}n)$。

#define int long long
#define endl '\n'
#define PII pair<int,int>
#define INF 1e18
const int N = 1e5 + 7;

int d[20][N], flag[20][N], a[N], door[20];
vector <PII> g[N];
int n, m, k, T;

void dijkstra(int start) {
    int s = start;
    start = door[start];

    priority_queue <PII, vector<PII>, greater<>> q;
    for (int i = 1; i <= n; i++) d[s][i] = INF;

    d[s][start] = 0;
    q.push(PII{0, start});

    while (q.size()) {
        auto [road, u] = q.top();
        q.pop();

        if (flag[s][u]) continue;
        flag[s][u] = 1;

        for (auto [v, w] : g[u]) {
            if (d[s][v] > road + w) {
                d[s][v] = road + w;
                q.push(PII{d[s][v], v});
            }
        }
    }
}

void slove () {
    cin >> n >> m >> k >> T;

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

    map <int, PII> mp;

    for (int i = 1; i <= k; i++) {
        int l, r;
        cin >> door[i] >> l >> r;
        mp[door[i]] = {l, r};
    }

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

        g[u].emplace_back(v, w);
        g[v].emplace_back(u, w);
    }

    for (int i = 1; i <= k; i++) {
        dijkstra(i);
    }


    vector <vector<int>> dp(2, vector<int>((1 << 16), -2));

    for (int i = 1; i <= T; i++) {
        int state = 0;
        bool is_fail = false;

        for (int j = 1; j <= k; j++) {
            auto [l, r] = mp[door[j]];

            if (l <= i and i <= r) {
                state |= (1 << j);
            }
        }

        if (dp[(i - 1) % 2][state] != -2) {
            dp[i % 2][state] = dp[(i - 1) % 2][state];
            cout << dp[i % 2][state] << endl;
        } else {
            int sum = 0;
             
            for (int j = 1; j <= n; j++) {
                int dis = INF;

                for (int t = 1; t <= k; t++) {
                    if (state & (1 << t)) {
                        dis = min(dis, d[t][j]);
                    }
                }

                if (dis == INF) {
                    is_fail = true;
                    break;
                } else sum += a[j]*dis;
            }

            if (is_fail) dp[i % 2][state] = -1;
            else dp[i % 2][state] = sum;

            cout << dp[i % 2][state] << endl;
        }
    }
}