【2024年码蹄杯】本科组省赛

个人主页：Guiat
归属专栏：算法竞赛

正文

总共8道题。

1. MC0355 · 开篇签到

【题目】 MC0355 · 开篇签到

【分析】
输出严格次小值。

【AC_Code】

#include <iostream>
#include <algorithm>
#define IOS ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);using namespace std;const int N = 1e5 + 10; int a[N];void solve()
{int n; cin >> n; for (int i = 0; i < n; i ++) cin >> a[i];sort(a, a + n); int pos = 0;for (int i = 0; i < n; i ++) if (a[i] == a[0]) pos ++;cout << a[pos] << '\n';
}int main()
{IOS int _ = 1;   // cin >> _;while (_ --) solve();return 0;
}

2. MC0357 · 移动移动移动

【题目】MC0357 · 移动移动移动

【分析】

考察贪心。

全是1的串直接加，剩余不全为1的串只保留一边连续1长度的最大值。

【AC_Code】

#include <iostream>
#define IOS ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);using namespace std;int cnt1, cnt2, m1, m2, ans;void solve()
{int n; cin >> n;for (int i = 0; i < n; i ++){string s; cin >> s; cnt1 = 0; cnt2 = 0;for (int i = 0; i < s.length() && s[i] == '1'; i ++) cnt1 ++;for (int i = s.length() - 1; i >= 0 && s[i] == '1'; i --) cnt2 ++;if (cnt1 == s.size()) ans += cnt1;else { m1 = max(cnt1, m1); m2 = max(cnt2, m2); }}cout << ans + max(m1, m2) << '\n';
}int main()
{IOS int _ = 1;   // cin >> _;while (_ --) solve();return 0;
}

3. MC0357 · 移动移动移动

【题目】MC0357 · 移动移动移动

【分析】

考察：逆元、快速幂、阶乘预处理、逆元求组合数。

【AC_Code】

#include <iostream>
#define IOS ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);using namespace std;
using ll = long long;const ll N = 3e5 + 10, mod = 998244353;ll f[N], inf[N];ll ksm(ll a, ll b)
{ll res = 1;while (b){if (b & 1) { res = res * a % mod; }a = a * a % mod; b >>= 1;}return res;
}ll inv(ll a) { return ksm(a, mod - 2); }ll C(ll a, ll b) { return f[a] * inf[b] % mod * inf[a - b] % mod; }void init()
{f[0] = inf[0] = 1;for (ll i = 1; i <= N; i++){f[i] = f[i - 1] * i % mod;inf[i] = inf[i - 1] * inv(i) % mod;}
}void solve()
{int x1, y1, x2, y2, n, p, q; cin >> x1 >> y1 >> x2 >> y2 >> n >> p >> q;ll cx = x2 - x1, cy = y2 - y1;if (cx + cy > n || cx < 0 || cy < 0) return cout << 0 << '\n', void();ll ans = C(n, cx) * ksm(p * inv(100) % mod, cx) % mod * ksm(q * inv(100) % mod, n - cx) % mod;cout << ans << '\n';
}int main()
{IOS init(); ll t = 1; cin >> t;while (t --) solve();return 0;
}

4. MC0358 · 请相信我会做图论

【题目】MC0358 · 请相信我会做图论

【分析】

考查图论dfs。

【AC_Code】

#include <iostream>
#include <algorithm>
#include <vector>
#define int long long
#define IOS ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);using namespace std;
using pii = pair<int, int>;const int N = 1e5 + 10; int w[N], vis[N], ans; vector<int> u[N];void dfs(int a)
{if (vis[a]) return ; vis[a] = 1;for (int i = 0; i < u[a].size(); i ++){int next = u[a][i]; w[next] = min(w[a], w[next]);dfs(next);}
}bool cmp(pii& a, pii& b) { return a.second < b.second; }void solve()
{int n, m; cin >> n >> m; pii t[n + 1];for (int i = 1; i <= n; i ++) cin >> w[i], t[i].first = w[i], t[i].second = i;while (m --) { int a, b; cin >> a >> b; u[a].push_back(b); }sort(t + 1, t + n + 1);for (int i = 0; i < n; i ++) dfs(t[i].second);for (int i = 1; i <= n; i ++) ans += w[i]; cout << ans << '\n';for (int i = 1; i <= n; i ++) cout << w[i] << " \n"[i == n];
}signed main()
{IOS int _ = 1;   // cin >> _;while (_ --) solve();return 0;
}

5. MC0359 · 我会等差数列

【题目】MC0359 · 我会等差数列

【分析】

前缀和 + 二分查找临界位置 + 处理特殊情况。

【AC_Code】

#include <iostream>
#define IOS ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);using namespace std;const int N = 1e6 + 10; int n, q, a[N], f[N]; long pre[N];void init()
{f[1] = 1; f[2] = 2;for (int i = 3; i <= n; i ++){if (a[i] + a[i - 2] == 2 * a[i - 1]) f[i] = f[i - 1] + 1;else f[i] = 2;}for (int i = 1; i <= n; i ++) pre[i] = pre[i - 1] + f[i];
}void solve()
{cin >> n >> q; for (int i = 1; i <= n; i ++) cin >> a[i]; init();while (q --){int l, r; cin >> l >> r;if (f[r] >= r - l + 1){cout << long(r - l + 1) * (r - l + 2) / 2 << '\n'; continue;}int _l = l, _r = r;while (_l < _r){int mid = (_l + _r) >> 1;if (f[mid] < mid - l + 1) _r = mid;else _l = mid + 1;}cout << pre[r] - pre[_l - 1] + long(_l - l) * (_l - l + 1) / 2 << '\n';}
}int main()
{IOS int _ = 1;   // cin >> _;while (_ --) solve();return 0;
}

6. MC0360 · 我会修改图

【题目】MC0360 · 我会修改图

【分析】

离线 + 并查集 + 启发式合并。

【AC_Code】

#include <bits/stdc++.h>
#define IOS ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);using namespace std;const int N = 2e5 + 10, M = 4e5 + 10;
int a[N], s[N], edg[M][2], op[M][3]; bool del[M];
map<int, int> cnt[N]; vector<int> ans;int find(int u) { return u == s[u] ? u : s[u] = find(s[u]); }void merge(int u, int v)
{u = find(u); v = find(v);if (u == v) return ;if (cnt[u].size() < cnt[v].size()) swap(u, v);s[v] = u;for (const auto& pair : cnt[v]){int w = pair.first, c = pair.second; cnt[u][w] += c;}
}void solve()
{int n, m, q; cin >> n >> m >> q;for (int i = 1; i <= n; i ++) { cin >> a[i]; s[i] = i; cnt[i][a[i]] = 1; }for (int i = 1; i <= m; i ++) cin >> edg[i][0] >> edg[i][1];for (int i = 1; i <= q; i ++){cin >> op[i][0] >> op[i][1];if (op[i][0] == 2) cin >> op[i][2];else del[op[i][1]] = true;}for (int i = 1; i <= m; i ++){if (del[i]) continue;merge(edg[i][0], edg[i][1]);}for (int i = q; i >= 1; i --){if (op[i][0] == 1) { int x = op[i][1]; merge(edg[x][0], edg[x][1]); }else{int x = op[i][1], y = op[i][2], u = find(x), target = y - a[x];int count = cnt[u].count(target) ? cnt[u][target] : 0;ans.push_back(count - (a[x] == target ? 1 : 0));}}reverse(ans.begin(), ans.end()); for (int x : ans) cout << x << '\n';
}int main()
{IOS int _ = 1;   // cin >> _;while (_ --) solve();return 0;
}

7. MC0361 · 团队能量

【题目】MC0361 · 团队能量

【分析】

【AC_Code】

#include <iostream>
#include <algorithm>
#define IOS ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);using namespace std;
using ll = long long;const int N = 1e6 + 10; ll n, k, a[N], f[N], M = 2e18;void solve()
{int n, k; cin >> n >> k; for (int i = 1; i <= n; i ++) cin >> a[i];sort(a + 1, a + 1 + n);for (int i = 0; i <= n + 1; i ++) f[i] = M;f[0] = 0; f[2] = a[2] - a[1];for (int i = 3; i <= n; i ++){f[i] = f[i - 2] + a[i] - a[i - 1];if (k <= 2) continue;f[i] = min(f[i], f[i - 3] + a[i] * 2 - a[i - 2] - a[i - 1]);}cout << f[n] << '\n';
}int main()
{IOS int _ = 1;   // cin >> _;while (_ --) solve();return 0;
}

8. MC0362 · 异或

【题目】MC0362 · 异或

【分析】

【AC_Code】

#include <iostream>
#include <vector>
#define IOS ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);using namespace std;const int N = 5e5 + 10, mod = 1e9 + 7;
int n, q, k, a[N], f[N][30][2], ans; vector<int> e[N], path { 0 };void dfs(int u, int fa)
{path.push_back(u);for (int i = 0; i < 30; i ++){f[u][i][a[u] >> i & 1] ++;f[path[max(0, (int)path.size() - k - 2)]][i][a[u] >> i & 1] --;}for (int v : e[u]){if (v == fa) continue;dfs(v, u);}path.pop_back();
}void dfs_sum(int u, int fa)
{for (int v : e[u]){if (v == fa) continue;dfs_sum(v, u);for (int i = 0; i < 30; i ++) { f[u][i][0] += f[v][i][0]; f[u][i][1] += f[v][i][1]; }}
}void solve()
{cin >> n >> q >> k; for (int i = 1; i <= n; i ++) cin >> a[i];for (int i = n - 1, u, v; i --; ) { cin >> u >> v; e[u].push_back(v); e[v].push_back(u); }dfs(1, 0); dfs_sum(1, 0);for (int x; q --; ){cin >> x; ans = 0;for (int i = 0; i < 30; i ++){ans += f[x][i][0] * (1l << i) % mod * f[x][i][1] % mod;ans %= mod;}cout << ans << '\n';}
}int main()
{IOS int _ = 1;   // cin >> _;while (_ --) solve();return 0;
}

结语
感谢您的阅读！期待您的一键三连！欢迎指正！