### 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 Orphansstring 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;}}
}