当前位置: 首页 > news >正文

题解:AtCoder ARC207A Affinity for Artifacts

题意

给定长度为 \(n\) 的序列 \(a\) 和一个数 \(X\),求有多少种 \(a\) 的重排 \(b\) 使得 \(\sum\limits_{i=1}^n\max(b_i-i+1,0)\leq X\)\(1\leq n\leq 100\)\(1\leq a_i,X\leq 10^9\)

题解

你说得对,但我怎么见过这个 trick?见过了怎么还做不出来呢?

首先考虑把 \(\sum\) 里面的式子写成更喜闻乐见的形式,注意到 \(\max(b_i-(i-1),0)+\min(b_i,i-1)=b_i\),于是我们设 \(S=\sum\limits_{i=1}^na_i,X'=S-X\),把原题条件转化为 \(\sum\limits_{i=1}^n\min(b_i,i-1)\geq X'\)

显然 \(0\leq \sum\limits_{i=1}^n\min(b_i,i-1)\leq \sum\limits_{i=0}^{n-1}i=\dfrac{n(n-1)}{2}\),因此若 \(X'>\dfrac{n(n-1)}{2}\) 则无解,若 \(X'<0\) 则答案为 \(n!\)。这样 \(X'\) 就被限制到了 \(\mathcal{O}(n^2)\) 量级。

看到形如 \(\sum\min(x_i,y_i)\) 的式子,想到将其转化为匹配问题的 trick。具体来说,我们把 \(a_1,\cdots,a_n\) 视作左部点,\(0,\cdots,n-1\) 视作右部点,把这 \(2n\) 个点放一起按权值从大到小排序。从左往右考虑每个点 \(i\),那么我们的决策就是,要么把 \(i\) 和前面某个尚未匹配的不同类型的点 \(j\) 匹配,造成 \(v_i\) 的贡献,要么留着不匹配,等后面的点来匹配它。

容易想到对这个过程 DP。令 \(f_{i,j,k,s}\) 表示考虑前 \(i\) 个数,有 \(j\) 个左部点尚未匹配,有 \(k\) 个右部点尚未匹配,当前匹配的权值和为 \(s\) 的方案数。考虑转移,不妨假设第 \(i\) 个点是左部点,右部点的情况类似。讨论这个点是否和前面的点匹配:

  • \(i\) 个点不匹配:\(f_{i,j,k,s}\leftarrow f_{i,j,k,s}+f_{i-1,j-1,k,s}\)
  • \(i\) 个点和前面的点匹配:此时 \(1\sim i-1\) 中有 \(k+1\) 个右部点,可以任选一个和当前点匹配,于是 \(f_{i,j,k,s}\leftarrow f_{i,j,k,s}+(k+1)f_{i-1,j,k+1,s-v_i}\)

\(s=\mathcal{O}(n^2)\),这样我们就得到了 \(\mathcal{O}(n^5)\) 的做法。

考虑优化。设 \(L_i,R_i\) 分别表示前 \(i\) 个点中左部点、右部点的数量。可以发现,我们能由 \(i,j\) 计算出 \(k\):前 \(i\) 个点中有 \(j\) 个未匹配的左部点,也就会有 \(L_i-j\) 组左右部点的匹配,于是就有 \(R_i-L_i+j\) 个未匹配的右部点。因此我们的 DP 状态可以简化成 \(f_{i,j,s}\),时间复杂度优化至 \(\mathcal{O}(n^4)\),可以通过本题。

代码

#include <bits/stdc++.h>using namespace std;#define lowbit(x) ((x) & -(x))
typedef long long ll;
typedef pair<int, int> pii;
const int N = 101, MOD = 998244353;template<typename T> inline void chk_min(T &x, T y) { x = min(x, y); }
template<typename T> inline void chk_max(T &x, T y) { x = max(x, y); }
inline int add(int x, int y) { return x += y, x >= MOD ? x - MOD : x; }
inline int sub(int x, int y) { return x -= y, x < 0 ? x + MOD : x; }
inline void cadd(int &x, int y) { x += y, x < MOD || (x -= MOD); }
inline void csub(int &x, int y) { x -= y, x < 0 && (x += MOD); }int n, ans, a[N], f[N << 1][N << 1][N * (N - 1) / 2], cnt[N << 1][2];
ll S, X;
pii p[N << 1];int main() {ios::sync_with_stdio(0), cin.tie(0);cin >> n >> X;for (int i = 1; i <= n; ++i) cin >> a[i], S += a[i];X = S - X;if (X > n * (n - 1) / 2) return cout << "0", 0;if (X < 0) {int fc = 1;for (int i = 1; i <= n; ++i) fc = (ll)fc * i % MOD;return cout << fc, 0;}for (int i = 1; i <= n; ++i) p[i] = {a[i], 0}, p[i + n] = {i - 1, 1};sort(p + 1, p + (n << 1) + 1, greater<>());for (int i = 1; i <= n << 1; ++i) cnt[i][0] = cnt[i - 1][0] + !p[i].second, cnt[i][1] = cnt[i - 1][1] + p[i].second;f[0][0][0] = 1;int u = n * (n - 1) / 2;for (int i = 1; i <= n << 1; ++i) for (int j = 0; j <= cnt[i][0]; ++j) {int k = cnt[i][1] - cnt[i][0] + j;if (k < 0 || k > cnt[i][1]) continue;for (int s = 0; s <= u; ++s) {if (p[i].second) {if (p[i].first <= s) cadd(f[i][j][s], (ll)(j + 1) * f[i - 1][j + 1][s - p[i].first] % MOD);if (k) cadd(f[i][j][s], f[i - 1][j][s]);} else {if (p[i].first <= s) cadd(f[i][j][s], (ll)(k + 1) * f[i - 1][j][s - p[i].first] % MOD);if (j) cadd(f[i][j][s], f[i - 1][j - 1][s]);}}}for (int s = X; s <= u; ++s) cadd(ans, f[n << 1][0][s]);cout << ans;return 0;
}
http://www.hskmm.com/?act=detail&tid=35326

相关文章:

  • 构造单
  • [笔记]高斯消元
  • 半导体设备各细分领域的国内外龙头公司
  • CSP-S 34
  • 02.Python百行代码实现抽奖系统
  • CSP-S 35
  • CSP-S 29
  • 2025网络安全振兴杯wp
  • 10.20每日总结
  • CSP-S 31
  • 后缀树
  • ES原理、zookeeper、kafka
  • CF1606E Arena 题解(动态规划)
  • 服务器CPU市场概况2025
  • CSP-S 24
  • 读书笔记:深入理解java虚拟机
  • CSP-S 19
  • CSP-S 20
  • Flutter应用设置插件 - 轻松打开iOS和Android系统设置
  • CSP-S 22
  • Project. 2025.11化学小组pre
  • MySQLDay1
  • 蛋白表达标签:重组蛋白研究的精妙引擎
  • 106.腾讯地图位置服务再出错
  • 心理咨询系统
  • Adaptive Learning Rate(自适应学习率) - -一叶知秋
  • Luogu P10034 「Cfz Round 3」Circle 题解 [ 蓝 ] [ 背包 DP ] [ 质数筛 ] [ 图论 ] [ 构造 ]
  • 2025.10.20模拟赛
  • SQLite简单使用
  • 新学期每日总结(第12天)