外观
Skip to content 查看源代码：
查看源代码：
CF2151.md
---
title: CF2151
createTime: 2025/10/3
categories:
- IT
tags:
- OI
---
## A. [Incremental Subarray](https://codeforces.com/contest/2151/problem/A)
:::note 题意
求 $[1,\ 1,2,\ 1,2,3,\ 1,2,3,4,\ \dots,\ 1, 2, 3, \dots,n]$ 的指定子**串**的数量，保证答案至少为 $1$。
:::
答案至少为 $1$ 省了很多事。过于简单，详见代码，不再赘述。
:::details Code
```cpp
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int t;
cin >> t;
while (t--) {
int n, m;
cin >> n >> m;
bool one=false;
int pre=-1, mx=-1;
for (int i=1; i<=m; i++) {
int a;
cin >> a;
mx = max(mx, a);
one |= (i>1 && a-pre!=1);
pre = a;
}
cout << (one? 1: n-mx+1) << '\n';
}
return 0;
}
```
:::
## B. [Incremental Path](https://codeforces.com/contest/2151/problem/B)
:::note 题意
有一个包含黑白格的长条，初始时有 $m$ 个黑格。一个人有两种操作：
- A：跳到下一格
- B：跳到下一个白格
有一条长度为 $n$ 的操作串 $s$。一个人将行动 $n$ 次，第 $i$ 次将从 $1$ 出发，依次执行操作 $1 \sim i$，并把终点格变为黑色。
求结束后所有的黑色格。
:::
显然第 $i+1$ 次行动和第 $i$ 次行动的前 $i-1$ 次操作是完全相同的。而第 $i$ 次操作可能会因为格子黑白的改变而产生不一样的结果。
于是考虑记录下 $i-1$ 次操作后到达的格子，然后暴力完成剩下两次操作，得到第 $i+1$ 次行动的终点。
由于此算法中一个黑色格子最多被访问 $2$ 次，复杂度是正确的。
:::details Code
```cpp
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+10;
set<int> black;
char cmd[maxn];
inline int walk(int pos, int ci) {
if (cmd[ci] == 'A') {
return pos+1;
}
do {
pos++;
} while (black.count(pos));
return pos;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int t;
cin >> t;
while (t--) {
black.clear();
int n, m;
cin >> n >> m >> (cmd+1);
for (int i=1; i<=m; i++) {
int a;
cin >> a;
black.insert(a);
}
black.insert(walk(1, 1));
int pre = 1;
for (int i=2; i<=n; i++) {
pre = walk(pre, i-1);
black.insert(walk(pre, i));
}
cout << black.size() << '\n';
for (int i: black) {
cout << i << ' ';
}
cout << '\n';
}
return 0;
}
```
:::
## C. [Incremental Stay](https://codeforces.com/contest/2151/problem/C)
:::note 题意
数轴上有 $2n$ 个点 $\{a_i\}$，要把它们两两配对成 $n$ 条线段。
若一个点最多被 $k$ 条线段覆盖，对于所有 $k \in [1,n]$ 求最大的线段总长。
:::
老办法，考虑把左右贡献拆开，则有
$$
\mathrm{ans} = \sum_{i=1}^{n} r_i-l_i = \left( \sum_{i=1}^{n} r_i \right) - \left( \sum_{i=1}^{n} l_i \right) = S - 2\left( \sum_{i=1}^{n} l_i \right)
$$
即最小化左端点的坐标之和。
接下来考虑 $k$ 的限制。等价地，任意前缀点集中左端点数减右端点数不超过 $k$。
容易想到贪心策略 $\underbrace{LLL \cdots L}_{k\text{ 个 }L}\ \underbrace{RLRL \cdots RL}_{n-k\text{ 个 }RL}$，可以使用逐步调整法证明。每次将 $L$ 往前调，直到不可再调整时即为此形态。
如何计算答案？容易想到前缀和化，设 $\displaystyle s_i=\sum_{1\le j\le i} a_j, t_i=\sum_{1\le j\le i}^{j \equiv i \pmod{2}} a_j$，则
$$
\sum_{i=1}^{n} l_i = s_k + t_{2n-k} - t_k
$$
:::details Code
```cpp
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=4e5+10;
int a[maxn], s[maxn], t[maxn];
signed main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int T;
cin >> T;
while (T--) {
int n;
cin >> n;
for (int i=1; i<=2*n; i++) {
cin >> a[i];
s[i] = s[i-1] + a[i];
if (i > 1) {
t[i] = t[i-2] + a[i];
}
}
for (int k=1; k<=n; k++) {
cout << s[2*n] - 2*(s[k]+t[2*n-k]-t[k]) << ' ';
}
cout << '\n';
}
return 0;
}
```
:::
## D. [Grid Counting](https://codeforces.com/contest/2151/problem/D)
:::note 题意
有一个大小为 $n \times n$ 的网格，每个格子有一个黑白的颜色。格子的颜色必须满足：
- 对于 $0\le d<n$ 恰有一个黑色格子和左上角的切比雪夫距离为 $d$；
- 对于 $0\le d<n$ 恰有一个黑色格子和右上角的切比雪夫距离为 $d$；
- 第 $i$ 行恰有 $a_i$ 个黑色格子。
求着色方案数 $\bmod 998244353$。
:::
这种“某集合内恰有一个”的思路和数独十分相似，都是先找出可以确定的格子，然后借以排除一系列的格子。如下图，绿色部分代表第 $i$ 步确定的格子（范围），红色部分代表第 $i$ 步排除的格子：
:::center
{width=480px}
:::
因此，可以证明格子颜色分布满足后两条要求，当且仅当每个绿色区域中恰有一个黑色格子。
考虑从下到上安排黑色格子。设安排到第 $i$ 行之前已经安排了 $c$ 个，则第 $i$ 行有 $\displaystyle\binom{\max\{n+2-2i-c, 0\}}{a_i}$ 种安排方式。故
$$
\mathrm{ans} =
\begin{cases}
\displaystyle\prod_{i=1}^{n} \binom{\max\{n+2-2i-\sum_{j=i+1}^{n}a_j, 0\}}{a_i}, &\displaystyle\sum_{i=1}^{n} a_i = n \\
0, &\text{otherwise}
\end{cases}
$$
:::details Code
```cpp
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=2e5+10, mod=998244353;
int a[maxn];
int fac[maxn], ifac[maxn];
inline int qpow(int x, int y) {
int ans = 1;
while (y) {
if (y & 1) {
ans = ans * x % mod;
}
y >>= 1;
x = x * x % mod;
}
return ans;
}
void pre(int n) {
fac[0] = 1;
for (int i=1; i<=n; i++) {
fac[i] = fac[i-1] * i % mod;
}
ifac[n] = qpow(fac[n], mod-2);
for (int i=n; i>=1; i--) {
ifac[i-1] = ifac[i] * i % mod;
}
}
inline int binom(int x, int y) {
if (x < 0 || y < 0 || x < y) {
return 0;
}
return ifac[y]*ifac[x-y]%mod * fac[x] % mod;
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
for (int i=1; i<=n; i++) {
cin >> a[i];
}
pre(n);
int ans = 1, c = 0;
for (int i=n; i>=1; i--) {
// printf("ans *= binom(%lld, %lld)\n", n+2-2*i-c, a[i]);
ans = ans * binom(max(n+2-2*i-c,0ll), a[i]) % mod;
c += a[i];
}
if (c != n) {
ans = 0;
}
cout << ans << '\n';
}
return 0;
}
```
:::
## E. [Limited Edition Shop](https://codeforces.com/contest/2151/problem/E)
:::note 题意
有 $n$ 个物品，价值分别为 $\{v_i\}$。有两个排列 $\{a_i\}, \{b_i\}$。A 和 B 合作，进行游戏。
每回合有两种操作：
- A 取走排列 $\{a_i\}$ 中最早的未被取到的物品；
- B 取走排列 $\{b_i\}$ 中最早的未被取到的物品。
问 A 取走的物品的最大可能总价值。
:::
设 $a_1, \dots, a_i$ 和 $b_1, \dots b_j$ 都被取走（不管是谁取的）的最大总价值为 $f(i,j)$，
设 $\{b_i\}$ 的逆排列为 $b'_i$，则有状态转移方程
$$
f(i,j) = \max\begin{cases}
f(i-1,j) + [b'_{a_i}>j]v_{a_i} & (\text{A 尝试取}) \\
f(i,j-1) & (\text{B 取})
\end{cases}
$$
根据单调性有
$$
f(i, j) =
\begin{cases}
f(i-1, j) + v_{a_i}, &j < b'_i \\
\max\{f(i-1,j), f(i,b'_{a_i}-1)\}, &j \ge b'_i
\end{cases}
$$
考虑把 $j$ 一维用数据结构维护，根据状态转移方程需要支持区间加、区间推平、单点查询和线段树上二分操作。
时间复杂度 $O(n \log n)$。
:::warning 注意
- DP 应有 $0$ 下标，代表未选；
- 由于加完之后线段树内部的单调性可能被打破，因此必须在加之前二分好。
:::
:::details Code
```cpp
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 2e5+10;
int n;
int v[maxn], a[maxn], ib[maxn];
struct sgt {
int z[maxn*4]; // filled=1 or 叶节点：推平值；否则：增加值
bool filled[maxn*4]; // filled=1 时，等效于下传前先推平
int l[maxn*4], r[maxn*4]; // 在且仅在升序时代表值域
inline int lc(int x) { return x<<1; }
inline int rc(int x) { return (x<<1)|1; }
inline int md(int x, int y) { return (x+y)>>1; }
void pushup(int tn) {
l[tn] = l[lc(tn)];
r[tn] = r[rc(tn)];
}
void pushdown(int tn) {
// printf("pushdown(#%lld, filled=%d, z=%lld)\n", tn, filled[tn], z[tn]);
int lcn=lc(tn), rcn=rc(tn);
if (filled[tn]) {
filled[lcn] = filled[rcn] = true;
z[lcn] = l[lcn] = r[lcn] = 0;
z[rcn] = l[rcn] = r[rcn] = 0;
}
z[lcn] += z[tn]; l[lcn] += z[tn]; r[lcn] += z[tn];
z[rcn] += z[tn]; l[rcn] += z[tn]; r[rcn] += z[tn];
z[tn] = filled[tn] = 0;
}
void add(int tn, int tl, int tr, int x, int y, int a) {
// printf("add(#%lld[%lld,%lld]; [%lld,%lld]; %lld)\n", tn, tl, tr, x, y, a);
if (y < tl || tr < x) {
return;
}
if (x <= tl && tr <= y) {
z[tn] += a;
l[tn] += a;
r[tn] += a;
return;
}
pushdown(tn);
int mid = md(tl, tr);
add(lc(tn), tl, mid, x, y, a);
add(rc(tn), mid+1, tr, x, y, a);
pushup(tn);
}
void fill(int tn, int tl, int tr, int x, int y, int m) {
// printf("fill(#%lld[%lld,%lld]; [%lld,%lld]; %lld)\n", tn, tl, tr, x, y, m);
if (y < tl || tr < x) {
return;
}
if (x <= tl && tr <= y) {
z[tn] = l[tn] = r[tn] = m;
filled[tn] = 1;
return;
}
pushdown(tn);
int mid = md(tl, tr);
fill(lc(tn), tl, mid, x, y, m);
fill(rc(tn), mid+1, tr, x, y, m);
pushup(tn);
}
int query(int tn, int tl, int tr, int x) {
if (tl == tr) {
return z[tn];
}
pushdown(tn);
int mid = md(tl, tr);
if (x <= mid) {
return query(lc(tn), tl, mid, x);
} else {
return query(rc(tn), mid+1, tr, x);
}
}
int max_below(int tn, int tl, int tr, int m) {
// 仅在有序时可用
if (l[tn] >= m) {
return -1;
}
if (r[tn] <= m) { // 等号随意
return tr;
}
pushdown(tn);
int mid = md(tl, tr);
return max(
max_below(lc(tn), tl, mid, m),
max_below(rc(tn), mid+1, tr, m)
);
}
void modify(int i, int a) {
int val = query(1, 0, n, i-1) + a,
pos = max_below(1, 0, n, val);
// printf("max below %lld -> %lld\n", val, pos);
add(1, 0, n, 0, i-1, a);
fill(1, 0, n, i, pos, val);
}
void clear() {
filled[1] = true;
z[1] = l[1] = r[1] = 0; // 清空要完全
}
} segtree;
signed main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
// cin >> n;
// while (true) {
// char op; cin >> op;
// if (op == 'a') {
// int i, a; cin >> i >> a;
// segtree.modify(i, a);
// }
// // else if (op == 'q')
// {
// for (int i=0; i<=n; i++) { cout << segtree.query(1,0,n,i) << ' '; }
// cout << endl;
// }
// }
int t;
cin >> t;
while (t--) {
segtree.clear();
cin >> n;
for (int i=1; i<=n; i++) {
cin >> v[i];
}
for (int i=1; i<=n; i++) {
cin >> a[i];
}
for (int i=1; i<=n; i++) {
int b;
cin >> b;
ib[b] = i;
}
for (int i=1; i<=n; i++) {
segtree.modify(ib[a[i]], v[a[i]]);
// printf("modify(%lld, %lld)\n", ib[a[i]], v[a[i]]);
// printf("[ ");
// for (int j=0; j<=n; j++) { printf("%lld ", segtree.query(1,0,n,j)); }
// printf("]\n");
}
cout << segtree.query(1, 0, n, n) << '\n';
}
return 0;
}
```
:::
写这个超融合线段树真是累人。
## F. [Attraction Theory](https://codeforces.com/contest/2151/problem/F)
:::note 题意
数轴上 $1 \sim n$ 的每个整数位置有一个点，并且每个位置有权值 $a_i$。
每次可以选定一个位置，将这个位置左边的点右移一格，右边的点左移一格。
对于一个可能的状态，设第 $i$ 个点移到了 $p_i$，设所有 $\{p_i\}$ 组成的数列集为 $\mathscr{P}$，求
$$
\sum_{\{p_i\} \in \mathscr{P}} \sum_{i=1}^{n} a_{p_i}
$$
:::
不难发现 $\{p_i\}$ 一定单调，故计数时可以等价为多重集。
设其对应的桶为 $\{c_p\}$，所有桶组成的集合为 $\mathscr{C}$。
对求和换序，则有
$$
\mathrm{ans} = \sum_{\{c_p\} \in \mathscr{C}} \sum_{p=1}^{n} a_p c_p = \sum_{p=1}^{n} \sum_{\{c_p\} \in \mathscr{C}} a_p c_p
$$
接下来我们探究一下 $\{c_p\}$ 可能满足的性质。
:::note 引理
$\{c_p\}$ 是满足以下要求的所有数列：
- $\displaystyle\sum_{p=1}^{n} c_p = n$；
- 设 $l$ 是 $\{c_p\}$ 的第一个非零项，设 $r$ 是 $\{c_p\}$ 的最后一个非零项，则
- $c_l, c_r \in \mathbb{N}^*$；
- $\forall l<p<r, c_p \in \{ 2n+1 \mid n\in\mathbb{N} \}$。
---
注意到操作可以任意平移 $\{c_p\}$，因此可以只看非零段，而零的位置不重要。
在平移意义下，操作可以分解为 $2$ 种：
- 把任意三项合并成一项
- 把边界的两项合并成一项
**必要性**
显然和不变。
而若在中间的三项都是奇数，三项相加仍为奇数。因为初始状态下中间项都为奇数，所以所有合法状态下所有中间项都为奇数。
**充分性**
考虑对操作进行反向。对于中间的非 $1$ 奇数 $c$，可以变为 $1, c-2, 1$；对于两端的 $c$ 可以变为 $1, c$ 或 $c, 1$。
容易发现符合条件的非全 $1$ 数列一定能被反向操作，且反向操作后仍然符合条件。因此，所有符合条件的数列都能被反向操作回初始状态。
:::
设所有非零段处于 $[l,r]$ 的合法 $\{c_p\}$ 的集合为 $\mathscr{C}_{[l,r]}$，设 $s_{[l,r]}(i) = \displaystyle\sum_{\{c_p\} \in \mathscr{C}_{[l,r]}} c_p$，由对称性设
$$
s_{[l,r]}(i) = \begin{cases}
A(r-l+1), & i \in \{l, r\} \\
A(r-l+1) + b(r-l+1), & l \le i \le r \\
0, & \text{otherwise}
\end{cases}
$$
于是
$$
\begin{align*}
\sum_{p=1}^{n} \sum_{\{c_p\} \in \mathscr{C}} a_p c_p &= \sum_{p=1}^{n} \sum_{1 \le l \le r \le n} a_p s_{[l,r]}(p) \\
&= \sum_{1\le\mathrm{len}\le n} \sum_{p=1}^{n} \begin{gathered}
&a_p A(\mathrm{len}) \#\{l\mid 1\le l\le n, 1\le l+\mathrm{len}-1\le n\}
\\ &+ \\
&a_p B(\mathrm{len})([p+\mathrm{len}-1 \le n]+[p-\mathrm{len}+1 \ge 1])
\end{gathered} \\
&= \sum_{1\le\mathrm{len}\le n} \begin{aligned}
& A(\mathrm{len}) \left( \sum_{i=1}^{u(\mathrm{len})-1} ia_i + \sum_{i=1}^{u(\mathrm{len})-1} ia_{n-i+1} + \sum_{p=u}^{n-u+2} a_p \right) \\
+\ & B(\mathrm{len}) \left(\sum_{p=1}^{n} a_p + \sum_{p=\mathrm{len}}^{n-\mathrm{len}+1} a_p\right)
\end{aligned} \\
&= \sum_{1\le\mathrm{len}\le n} A(\mathrm{len})S(\mathrm{len}) + B(\mathrm{len})T(\mathrm{len})
\end{align*}
$$
其中 $u(\mathrm{len}) = \max(\mathrm{len}, n-\mathrm{len}+1)$。
$S(\mathrm{len})$ 和 $T(\mathrm{len})$ 都可以用前缀和搞定，接下来看看怎么搞定 $A(\mathrm{len}), B(\mathrm{len})$。
设 $W(\mathrm{len})$ 是方案个数，由和的性质有
$$2B(\mathrm{len}) + \mathrm{len}A(\mathrm{len}) = \mathrm{len}W(\mathrm{len})$$
考虑固定首尾之和为 $w$，则剩下部分的和为 $n-w$，对中间各数应用 $x \mapsto \dfrac{x+1}{2}$，则可以使用插板法，共有
$$
\binom{n-w/2-1}{\mathrm{len}-3}
$$
种方案，则
$$2B(\mathrm{len}) = \displaystyle\sum_{w} w(w-1)\binom{n-w/2-1}{\mathrm{len}-3}$$
$$W(\mathrm{len}) = \displaystyle\sum_{w} (w-1)\binom{n-w/2-1}{\mathrm{len}-3}$$
鸽了。