2025CSP-S复赛解析
2025-11-15 21:01:11
发布于:福建
T1:P14361 [CSP-S 2025] 社团招新 / club(官方数据)
解析
首先不考虑每个人数限制,让所有人根据自己的喜好,选择满意度最高的部门,此时算得的满意度之和即为最理想的答案,接下来我们考虑如何调度人员,可以在损失满意度最少的情况下,满足各部门的人数限制。假设目前人数最多的部门中共有 x 人(显然,至多只有一个部门的人数会超过限制),我们改变其中 个人的意愿,将他们安排到其他部门。显然,这一操作也不会导致其他部门的人数过多。因而只需统计人数最多的部门中,所有人最大满意度与次大满意度之差(改变其部门的最小代价),找到部门中最小的 个人并将其换到第二喜欢的部门即可。
答案
#include <bits/stdc++.h>
#define ll long long
#define N 100100
using namespace std;
ll T, n, del[N];
struct Num
{
ll a, b, c;
} num[N];
inline bool cmp(ll u, ll v) { return del[u] < del[v]; }
int main()
{
cin >> T;
while (T--)
{
ll ans = 0;
vector<ll> A, B, C; // 表示各部门中包含哪些成员
scanf("%lld", &n);
for (int i = 1; i <= n; i++)
{
scanf("%lld%lld%lld", &num[i].a, &num[i].b, &num[i].c);
ll mx = max({num[i].a, num[i].b, num[i].c});
// 计算最大值,并根据最大值选择其部门
if (num[i].a == mx)
{
A.push_back(i);
del[i] = mx - max(num[i].b, num[i].c);
}
else if (num[i].b == mx)
{
B.push_back(i);
del[i] = mx - max(num[i].a, num[i].c);
}
else
{
C.push_back(i);
del[i] = mx - max(num[i].a, num[i].b);
}
ans += mx;
}
if (A.size() > n / 2) // 第一个部门超标,找到最小的 x-n/2 人改变志愿
{
sort(A.begin(), A.end(), cmp);
for (int i = 0; i < A.size() - n / 2; i++)
ans -= del[A[i]];
}
if (B.size() > n / 2) // 第二个部门超标,找到最小的 x-n/2 人改变志愿
{
sort(B.begin(), B.end(), cmp);
for (int i = 0; i < B.size() - n / 2; i++)
ans -= del[B[i]];
}
if (C.size() > n / 2) // 第三个部门超标,找到最小的 x-n/2 人改变志愿
{
sort(C.begin(), C.end(), cmp);
for (int i = 0; i < C.size() - n / 2; i++)
ans -= del[C[i]];
}
printf("%lld\n", ans);
}
}
T2:P14362 [CSP-S 2025] 道路修复 / road(官方数据)
解析
我们考虑使用 kruskal 算法计算最小生成树的过程,对于最开始的边集,尽管它包含了 条边,但我们将其排序之后,直接执行一遍 kruskal 算法,那么,只有最终出现在最小生成树上的那些边才有用,而其余的被抛弃的边,不管添加了任何的新城镇,这些边仍然不会出现。由于 ,那么我们只保留 条边,随后枚举任何可能出现的选择城镇集合,能达到 的复杂度。随后,我们考虑到直接枚举任何可能出现的集合,其实有大量的重复计算,我们改用 dfs 来搜索可行集合,每次加入一个新点的时候,就只需要加入 条新边,随后我们再按照同样的思路保留关键边,这样我们的最终复杂度就只有 了。
答案
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct DSU
{
vector<int> fa;
DSU(int n) : fa(n)
{
iota(fa.begin(), fa.end(), 0);
}
int getfa(int x)
{
return fa[x] == x ? x : fa[x] = getfa(fa[x]);
}
bool unite(int x, int y)
{
x = getfa(x), y = getfa(y);
if (x == y)
return false;
fa[x] = y;
return true;
}
};
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m, k;
cin >> n >> m >> k;
vector<array<int, 3>> edges(m);
for (auto &[w, u, v] : edges)
{
cin >> u >> v >> w;
--u, --v;
}
vector ex(k, vector(n, array<int, 3>{}));
vector<int> c(k);
for (int i = 0; i < k; i++)
{
cin >> c[i];
for (int j = 0; j < n; j++)
{
cin >> ex[i][j][0];
ex[i][j][1] = j, ex[i][j][2] = n + i;
}
sort(ex[i].begin(), ex[i].end());
}
sort(edges.begin(), edges.end());
DSU dsu(n + k);
ll sum = 0;
vector<array<int, 3>> new_edges;
int blocks = n;
for (auto [w, x, y] : edges)
{
if (dsu.unite(x, y))
{
sum += w;
new_edges.push_back({w, x, y});
--blocks;
}
}
ll ans = sum;
auto search = [&](auto &&self, int dep, int cnt, ll exc, vector<array<int, 3>> edges) -> void
{
if (dep == k)
{
return;
}
self(self, dep + 1, cnt, exc, edges);
++cnt, exc += c[dep];
edges.insert(edges.end(), ex[dep].begin(), ex[dep].end());
inplace_merge(edges.begin(), edges.begin() + edges.size() - n, edges.end());
DSU dsu(n + k);
int blocks = n + cnt;
ll now_cost = exc;
vector<array<int, 3>> new_edges;
for (auto [w, x, y] : edges)
{
if (dsu.unite(x, y))
{
now_cost += w;
new_edges.push_back({w, x, y});
--blocks;
}
}
if (blocks == 1)
{
ans = min(ans, now_cost);
}
self(self, dep + 1, cnt, exc, new_edges);
};
search(search, 0, 0, 0, new_edges);
cout << ans << "\n";
return 0;
}
P14363 [CSP-S 2025] 谐音替换 / replace(官方数据)
解析
我们注意到不管是数据还是询问,只要能对上,那肯定是前缀相同后缀相同,中间有一段不同的修改,我们预处理出每一对中间的实际转换的内容,容易发现,实际产生贡献的询问和转换串,中间的修改肯定是完全相同的,而转换串两边的前后缀分别是询问串前缀的后缀和后缀的前缀,也就是被包含在询问串的中间。那么,我们对中间的转换哈希一下,然后对于任何中间相同的串,我们对前缀和后缀分别建好 trie,这样对每个询问,就相当于查询两边的 trie 上都是当前点的祖先的点有几个。对于这个问题,我们可以对 trie 计算 dfs 序之后将其转换为二维数点问题,使用树状数组即可维护,最终的总复杂度为 。
答案
#include <bits/stdc++.h>
using namespace std;
using i64 = unsigned long long;
using i128 = __int128_t;
using pii = pair<int, int>;
const i64 P = 1'000'000'000'000'000'003, b = 1'000'000'007;
i64 get_hash(string s)
{
i64 v = 0;
for (auto x : s)
v = (i128(v) * b + x) % P;
return v;
}
const int N = 200005;
int n, q, ans[N];
string s1[N], s2[N], t1[N], t2[N];
i64 vs[N], vt[N];
pii os[N], ot[N];
map<i64, vector<int>> ms, mt;
const int M = 2500005;
int ch[M][26], tot, dfn, ord[M], ed[M];
void clear()
{
while (tot)
{
memset(ch[tot], 0, sizeof ch[tot]);
--tot;
}
tot = 2;
dfn = 0;
}
int insert(int p, const string &s)
{
for (auto c : s)
{
int &q = ch[p][c - 'a'];
if (!q)
q = ++tot;
p = q;
}
return p;
}
int get_id(int p, const string &s)
{
for (auto c : s)
{
int q = ch[p][c - 'a'];
if (q)
{
p = q;
}
else
{
break;
}
}
return p;
}
i64 work(string &s1, string &s2)
{
int n = s1.length();
int l = 0, r = n - 1;
while (l < n && s1[l] == s2[l])
++l;
if (l == n)
return 0;
while (s1[r] == s2[r])
--r;
assert(l <= r);
i64 v = get_hash(s1.substr(l, r - l + 1) + s2.substr(l, r - l + 1));
s1 = s2.substr(0, l);
reverse(s1.begin(), s1.end());
s2 = s2.substr(r + 1, n - r - 1);
return v;
}
void dfs(int u)
{
ord[u] = ++dfn;
for (int c = 0; c < 26; ++c)
{
if (ch[u][c])
dfs(ch[u][c]);
}
ed[u] = dfn;
}
namespace BIT
{
int c[M];
void clear()
{
memset(c + 1, 0, tot * 4);
}
void modify(int p, int x)
{
for (; p <= tot; p += p & -p)
c[p] += x;
}
void modify(int l, int r, int x)
{
modify(l, x);
modify(r + 1, -x);
}
int query(int p)
{
int res = 0;
for (; p; p -= p & -p)
res += c[p];
return res;
}
}
struct node
{
int x, y, z;
node() {}
node(int x, int y, int z) : x(x), y(y), z(z) {}
};
vector<node> mdf[M];
vector<pii> qry[M];
void add_mdf(int l1, int r1, int l2, int r2)
{
mdf[l1].emplace_back(l2, r2, 1);
mdf[r1 + 1].emplace_back(l2, r2, -1);
}
void add_qry(int x, int y, int id)
{
qry[x].emplace_back(y, id);
}
int main()
{
ios::sync_with_stdio(0), cin.tie(0);
cin >> n >> q;
for (int i = 1; i <= n; ++i)
{
cin >> s1[i] >> s2[i];
vs[i] = work(s1[i], s2[i]);
ms[vs[i]].push_back(i);
}
for (int i = 1; i <= q; ++i)
{
cin >> t1[i] >> t2[i];
if (t1[i].length() != t2[i].length())
continue;
vt[i] = work(t1[i], t2[i]);
mt[vt[i]].push_back(i);
}
// cerr << "?" << endl;
for (const auto &[v, a] : ms)
{
if (!mt.count(v))
continue;
const auto &b = mt[v];
assert(v);
clear();
for (auto i : a)
{
os[i] = pii(insert(1, s1[i]), insert(2, s2[i]));
}
for (auto i : b)
{
ot[i] = pii(get_id(1, t1[i]), get_id(2, t2[i]));
}
dfs(1), dfs(2);
// cerr << "? " << v << " " << tot << " " << dfn << endl;
for (int i = 1; i <= dfn; ++i)
mdf[i].clear(), qry[i].clear();
for (auto i : a)
{
auto [u, v] = os[i];
add_mdf(ord[u], ed[u], ord[v], ed[v]);
}
for (auto i : b)
{
auto [u, v] = ot[i];
add_qry(ord[u], ord[v], i);
}
BIT::clear();
for (int i = 1; i <= dfn; ++i)
{
for (auto [l, r, x] : mdf[i])
BIT::modify(l, r, x);
for (auto [x, id] : qry[i])
ans[id] = BIT::query(x);
}
}
for (int i = 1; i <= q; ++i)
cout << ans[i] << "\n";
return 0;
}
T4:P14364 [CSP-S 2025] 员工招聘 / employ(官方数据)
解析
令 ( 表示前 天中,难度较高的天数的数量。令 表示 小于等于 的 的数量。我们考虑对于难度较高的天,先不分配具体是谁参加面试。最后答案乘以 即可。令 表示前 天中,有 天是不录用人的,且剩下 天中有 天是没有确定具体是谁去面试的方案数。我们称 的人为 “弱人”,其它人为 “强人”。若 ,。若 ,且下一天录用人, 。若 ,且下一天不录用人, 。时间复杂度 。
答案
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int P = 998244353;
template <int P>
struct ModInt {
int x;
static int shift(int x) {
while (x < 0) x += P;
while (x >= P) x -= P;
return x;
}
ModInt(int x = 0) : x(shift(x)) {}
ModInt& operator+=(const ModInt &other) {
if ((x += other.x) >= P) x -= P;
return *this;
}
ModInt& operator-=(const ModInt &other) {
if ((x -= other.x) < 0) x += P;
return *this;
}
ModInt& operator*=(const ModInt &other) {
x = (ll)x * other.x % P;
return *this;
}
friend ModInt operator+(ModInt a, const ModInt &b) {
return a += b;
}
friend ModInt operator-(ModInt a, const ModInt &b) {
return a -= b;
}
friend ModInt operator*(ModInt a, const ModInt &b) {
return a *= b;
}
ModInt pow(ll exp) const {
ModInt res = 1, base = *this;
while (exp) {
if (exp & 1) res = res * base;
base = base * base;
exp >>= 1;
}
return res;
}
ModInt inv() const {
return pow(P - 2);
}
};
using Mint = ModInt<P>;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
string s;
cin >> n >> m >> s;
vector<int> cnt(n + 1);
for (int i = 0, x; i < n; i++) {
cin >> x;
++cnt[x];
}
for (int i = 1; i <= n; i++) {
cnt[i] += cnt[i - 1];
}
vector<vector<vector<Mint>>> f(n + 1, vector<vector<Mint>>(n + 1, vector<Mint>(n + 1, Mint(0))));
f[0][0][0] = 1;
// i = n days
// j = failed people
// k = succeed non filled people
// candidate = cnt[j] - (j - c0) - (n - j - k)
vector<Mint> fct(n + 1, 1), ifc(n + 1);
for (int i = 1; i <= n; i++) {
fct[i] = fct[i - 1] * i;
}
ifc[n] = fct[n].inv();
for (int i = n - 1; i >= 0; i--) {
ifc[i] = ifc[i + 1] * (i + 1);
}
auto C = [&](int a, int b) -> Mint {
if (b < 0 || b > a) return 0;
return fct[a] * ifc[b] * ifc[a - b];
};
int c0 = 0;
for (int i = 0; i < n; i++) {
if (s[i] == '0') {
for (int j = c0; j <= i; j++) {
int x = cnt[j + 1] - cnt[j];
Mint pl = fct[x];
for (int k = 0; k <= i - j; k++) {
for (int z = 0; z <= cnt[j + 1] - cnt[j] && z <= k; z++) {
f[i + 1][j + 1][k - z] += f[i][j][k] * C(k, z) * C(cnt[j + 1] - cnt[j], z) * fct[z];
}
}
}
c0++;
} else {
for (int j = c0; j <= i; j++) {
for (int k = 0; k <= i - j; k++) {
// not succeed
int candidate = cnt[j] - (j - c0) - (i - j - k);
if (candidate > 0) {
for (int z = 0; z <= cnt[j + 1] - cnt[j] && z <= k; z++) {
f[i + 1][j + 1][k - z] += f[i][j][k] * candidate * C(k, z) * C(cnt[j + 1] - cnt[j], z) * fct[z];
}
}
// succeed
if (k + 1 <= n) {
f[i + 1][j][k + 1] += f[i][j][k];
}
}
}
}
}
Mint ans = 0;
for (int j = 0; j <= n - m; j++) {
for (int k = 0; k <= n; k++) {
if (n - cnt[j] >= k) {
ans += f[n][j][k] * C(n - cnt[j], k) * fct[k];
}
}
}
ans *= fct[c0];
cout << ans.x << "\n";
return 0;
}
这里空空如也









有帮助,赞一个