2023.08.07 模拟赛题解
A.[USACO21OPEN] Balanced Subsets P
思路
本场比赛第一道计数。
分析原条件，发现不管是横着从上往下看、还是竖着从左往右看，同一行或者同一列的 \(l\) 端一定满足先单调不升，再单调不降；\(r\) 端相反，满足先单调不降，再单调不升；显然 \(l \leq r\)。
所以考虑 DP。
考虑方程 \(f_{i, l, r, 0 /1, 0 / 1}\) 表示考虑到前 \(i\) 行，左端为 \(l\)，右端为 \(r\) ，\(l\) 是否处于单调不降状态， \(r\) 是否处于单调不升状态。
但是正确性有些问题，因为出现 \(l_1 \geq l_2 \geq l_3 \cdots \geq l_p = l_{p + 1} = \cdots = l_q \leq l_{q + 1} \leq \cdots \leq l_{n}\) 的以及 \(r\) 端同理的情况时，我们会算多。
所以考率将相等且处于峰顶或者谷底的 \(pos\) 划归到前一半状态中去。具体来说 DP 状态中升降状态的改变 \(0 \to 1\) 只有在 \(l_{pre} < l\) 或 \(r_{pre} > r\) 时才能在相应的端点处转移出 \(0 \to 1\) 的。
具体的方程都很显然，可以随便手推。
然后我们就得到了 \(O (n^5)\) 的具有启发性的暴力做法。
发现我们可以做个前缀和来计算。具体来说，在转移中对于 \((l,r)\) 区间只会由一些左右端 \(pos\) 在一个区间内的上个阶段 DP 值求得。所以直接二维前缀和。
Code
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 1e9 + 7;
int n, sm[155][155], f[155][155][155][2][2], S[155][155][155][2][2], Ans;
char s[155][155];
int Query_Sum (int u, int xl, int xr, int yl, int yr, int p, int q){
if (xl > xr || yl > yr)
return 0;
int x = min (xl, xr), y = min (yl, yr);
int xx = max (xl, xr), yy = max (yl, yr);
return ((S[u][xx][yy][p][q] - S[u][xx][y - 1][p][q] - S[u][x - 1][yy][p][q] + S[u][x - 1][y - 1][p][q]) % mod + mod) % mod;
}
signed main (){
scanf ("%lld", &n);
for (int i = 1;i <= n;++ i){
scanf ("\n%s", s[i] + 1);
for (int j = 1;j <= n;++ j)
sm[i][j] = sm[i][j - 1] + (int) (s[i][j] == 'G');
}
for (int i = 1;i <= n;++ i){
for (int l = 1;l <= n;++ l)
for (int r = l;r <= n && s[i][r] == 'G';++ r){
f[i][l][r][0][0] = Query_Sum (i - 1, l, r, l, r, 0, 0) + 1;
f[i][l][r][0][1] = Query_Sum (i - 1, l, r, r, n, 0, 1) + Query_Sum (i - 1, l, r, r + 1, n, 0, 0);
f[i][l][r][1][0] = Query_Sum (i - 1, 1, l, l, r, 1, 0) + Query_Sum (i - 1, 1, l - 1, l, r, 0, 0);
f[i][l][r][1][1] = Query_Sum (i - 1, 1, l, r, n, 1, 1) + Query_Sum (i - 1, 1, l - 1, r, n, 0, 1) + Query_Sum (i - 1, 1, l, r + 1, n, 1, 0) + Query_Sum (i - 1, 1, l - 1, r + 1, n, 0, 0);
f[i][l][r][0][0] %= mod;
f[i][l][r][0][1] %= mod;
f[i][l][r][1][0] %= mod;
f[i][l][r][1][1] %= mod;
}
for (int x = 1;x <= n + 1;++ x)
for (int y = 1;y <= n + 1;++ y)
for (int p = 0;p < 2;++ p)
for (int q = 0;q < 2;++ q){
S[i][x][y][p][q] = S[i][x - 1][y][p][q] + S[i][x][y - 1][p][q] - S[i][x - 1][y - 1][p][q] + f[i][x][y][p][q];
(S[i][x][y][p][q] = S[i][x][y][p][q] % mod + mod) %= mod;
}
for (int p = 0;p < 2;++ p)
for (int q = 0;q < 2;++ q)
(Ans += S[i][n][n][p][q]) %= mod;
}
printf ("%lld\n", Ans);
return 0;
}
B.[JOI Open 2016] 「高層ビル街/Skyscraper/摩天大楼」
思路
本场比赛第二道计数。
本年度第？道 JOI。
但是好像是道 fw 题，感觉这类题除了找性质乱整一下之外，就只有考虑排序+DP+插入+细节，或者整个 \(O(n^2)\) 甚至 \(O(n^3)\) 再用四边形不等式之类的乱搞一下。反正这题挺板的，上我以前写过的题解：
听说有种东西叫做连续段 DP？（感觉好高级）但是其实就是选择 DP 顺序的一个很经典的例子。考虑换一种顺序进行 DP。
令 \(S=\sum_{i=1}^{n-1} |v_i - v_{i+1}|\)。
考虑将 \(v\) 从大到小排序，然后尝试放入序列中。每次可以把当前的数插入原序列中，考虑手动划分出一些折线段（请结合自己的手绘图像）。显然每次把 \(v_i\) 的状态推向 \(v_{i+1}\) 的话，对于每不是最左右段的某一段的两个端点一定会连向 \(\leq v_{i+1}\) 的某个点，所以这一段对 \(S\) 的贡献为 \(2(v_{i+1} - v_i)\)。当然因为最左段或者最右段的特殊性，我们可以在 DP 的状态中钦定当前的最左段的左端点能否再延伸，最右端同理。当然最左段的右端和最右段的左端可以正常延伸和转移。
具体地，定义 \(f_{t,i,l,0/1,0/1}\) 表示放入前 \(t\) 大的数，当前划分了 \(i\) 段，已经知道的对 \(S\) 的贡献为 \(l\)，左段的左端点是否能延伸，右段的右端点是否能延伸。
转移式如下：
稍稍有一点冗长，但是其实很好理解的，其实就是分类讨论左段（就是 \(q = 0\) 的情况）、右段（就是 \(p=0\) 的情况）、中间（就是 \(i>1\) 的情况）进行计算。
Code
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 1e9 + 7;
int n, L, a[105], f[2][105][1005][2][2], Ans;
bool cmp (int i, int j){
return i > j;
}
int w (int i){
return i & 1;
}
int r (int i){
return w (i) ^ 1;
}
signed main (){
scanf ("%lld%lld", &n, &L);
for (int i = 1;i <= n;++ i)
scanf ("%lld", &a[i]);
sort (a + 1, a + n + 1, cmp);
for (int i = 0;i < 2;++ i)
for (int j = 0;j < 2;++ j)
f[1][1][0][i][j] = 1;
for (int t = 1;t < n;++ t){
for (int i = 1;i <= t + 1;++ i)
for (int l = 0;l <= L;++ l)
for (int p = 0;p < 2;++ p)
for (int q = 0;q <= 2;++ q)
f[r (t)][i][l][p][q] = 0;
for (int i = 1;i <= t;++ i)
for (int l = 0;l <= L;++ l)
for (int p = 0;p < 2;++ p)
for (int q = 0;q < 2;++ q){
if (f[w (t)][i][l][p][q] < 1)
continue;
int x = l + (2 * i - p - q) * (a[t] - a[t + 1]);
if (x > L)
continue;
if (i > 1)
(f[r (t)][i + 1][x][p][q] += f[w (t)][i][l][p][q] * (i - 1) % mod) %= mod;
if (p < 1){
(f[r (t)][i + 1][x][0][q] += f[w (t)][i][l][p][q]) %= mod;
(f[r (t)][i + 1][x][1][q] += f[w (t)][i][l][p][q]) %= mod;
}
if (q < 1){
(f[r (t)][i + 1][x][p][0] += f[w (t)][i][l][p][q]) %= mod;
(f[r (t)][i + 1][x][p][1] += f[w (t)][i][l][p][q]) %= mod;
}
if (i > 1)
(f[r (t)][i][x][p][q] += (i - 1 << 1) * f[w (t)][i][l][p][q] % mod) %= mod;
if (p < 1){
(f[r (t)][i][x][0][q] += f[w (t)][i][l][p][q]) %= mod;
(f[r (t)][i][x][1][q] += f[w (t)][i][l][p][q]) %= mod;
}
if (q < 1){
(f[r (t)][i][x][p][0] += f[w (t)][i][l][p][q]) %= mod;
(f[r (t)][i][x][p][1] += f[w (t)][i][l][p][q]) %= mod;
}
if (i > 1)
(f[r (t)][i - 1][x][p][q] += (i - 1) * f[w (t)][i][l][p][q] % mod) %= mod;
}
}
for (int i = 0;i <= L;++ i)
(Ans += f[w (n)][1][i][1][1]) %= mod;
printf ("%lld\n", Ans);
return 0;
}
C.[USACO21DEC] HILO P
思路
本场比赛第三道计数。
考虑期望 DP。
记录 \(f_{i,j,0/1}\) 表示还剩 \(i\) 个有用的 LO（小于 \(x+0.5\) 的数） 可选，还剩 \(j\) 个有用的 HI（大于 \(x+0.5\) 的数） 可选，前面一个选的是 LO 还是 HI。
然后就可以愉快地 DP 惹。记得期望 DP 倒着转移更方便。
好吧其实并不愉快，因为直接做的复杂度是 \(O(n^3)\) 的（o.0），是过不去的 qwq 。所以考虑前缀和优化，具体很显然，看代码就行。
Code
#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
int n, x, y, Ans;
int inv[5001];
int f[5001][5001][2], pre[5001][2];
signed main (){
scanf ("%d%d", &n, &x);
y = n - x;
inv[1] = 1;
for (int i = 2;i <= n;++ i)
inv[i] = 1ll * inv[i - mod % i] * (mod / i + 1) % mod;
for (int i = 0;i <= x;++ i)
for (int j = 0;j <= y;++ j){
f[i][j][0] = 1ll * (pre[i][0] + pre[j][1]) * inv[i + j] % mod;
f[i][j][1] = 1ll * (pre[i][0] + pre[j][1] + i) * inv[i + j] % mod;
(pre[i][0] += f[i][j][1]) %= mod;
(pre[j][1] += f[i][j][0]) %= mod;
}
Ans = f[x][y][0];
for (int i = 1;i <= n;++ i)
Ans = 1ll * Ans * i % mod;
printf ("%d\n", Ans);
return 0;
}
D.[ZJOI2016] 小星星
思路
本场第四道计数。
但是世纪计数好题，直接吹爆 ZJ 出题组。
考虑朴素的 DP 做法。记录 \(f_{i,S}\) 表示考虑 \(i\) 及以 \(i\) 为根的子树。已经考虑的点已经用掉了 \(S\) 中为 \(1\) 的编号（\(S\) 是 \(0/1\) 串）。然后就会得到一个复杂度爆炸的做法。
考虑绕一个弯子。
所以我们先想编号如果可以重复的话，怎么计算这个问题。
显然 \(n^3\) 随便算（不知道有没有更优的做法）。然后考虑怎么由编号重复计算出编号不重复的。
所以考虑容斥，答案为：
其中 \(Q_i\) 表示编号只能在 \(i\) （看作二进制 \(0/1\) 串）中选择的方案数。
然后就差不多了。
Code
#include <bits/stdc++.h>
using namespace std;
#define int long long
int n, m, x, y;
int cn[20], Can, Ans, Res, Cnt;
int firs[20], nex[40], to[40], tot;
int f[20][20];
void Add (int u, int v){
++ tot;
nex[tot] = firs[u];
firs[u] = tot;
to[tot] = v;
}
void Solve (int u, int father){
for (int i = 0;i < n;++ i)
if (Can >> i & 1)
f[u][i] = 1;
for (int e = firs[u];e;e = nex[e]){
int v = to[e];
if (v == father)
continue;
Solve (v, u);
int Sum;
for (int i = 0;i < n;++ i){
Sum = 0;
if (Can >> i & 1)
for (int j = 0;j < n;++ j)
if (Can >> j & 1)
if (cn[i] >> j & 1)
Sum += f[v][j];
f[u][i] *= Sum;
}
}
}
signed main (){
scanf ("%lld%lld", &n, &m);
for (int i = 0;i < m;++ i){
scanf ("%lld%lld", &x, &y);
-- x;
-- y;
cn[x] |= 1ll << y;
cn[y] |= 1ll << x;
}
for (int i = 1;i < n;++ i){
scanf ("%lld%lld", &x, &y);
-- x;
-- y;
Add (x, y);
Add (y, x);
}
for (Can = 1;Can < (1 << n);++ Can){
Solve (0, - 1);
Res = Cnt = 0;
for (int i = 0;i < n;++ i){
Cnt += Can >> i & 1;
Res += f[0][i] * (Can >> i & 1);
}
Ans += Res * ((n - Cnt & 1) ? - 1 : 1);
}
printf ("%lld\n", Ans);
return 0;
}