USACO 2019-2020 Platinum 题解
Visits: 410
2019 December Contest
Greedy Pie Eaters
区间 dp。
考虑最后放上去的区间，必有一个位置被新覆盖了。
枚举这个位置即可，时间复杂度 $\mathcal O(n^3)$。
const int N = 307;
int n, m, a[N][N][N], f[N][N];
int main() {
rd(n), rd(m);
for (int i = 1, x, l, r; i <= m; i++) {
rd(x), rd(l), rd(r);
for (int k = l; k <= r; k++) a[l][r][k] = x;
}
for (int k = 1; k <= n; k++)
for (int l = 1, r = l + k - 1; r <= n; l++, r++) {
for (int i = l; i <= r; i++)
f[l][r] = max(f[l][r], f[l][i-1] + f[i+1][r] + (a[l][r][i] = max(a[l][r][i], max(a[l+1][r][i], a[l][r-1][i]))));
}
print(f[1][n]);
return 0;
}
Bessie’s Snow Cow
对每种颜色开一个 set，维护树上有这种颜色的 dfs 序区间。
根据势能分析，时间复杂度为 $\mathcal O(n \log n)$。
最后只需要用一个树状数组/线段树支持区间加区间求和，总时间复杂度 $\mathcal O(n \log n)$。
const int N = 1e5 + 7;
int n, m, l[N], r[N], k;
vi e[N];
set< pi > s[N];
struct T {
int l, r;
ll x, z;
} t[N<<2];
void dfs(int x) {
l[x] = ++k;
for (ui i = 0; i < e[x].size(); i++) {
int y = e[x][i];
if (l[y]) continue;
dfs(y);
}
r[x] = k;
}
void build(int p, int l, int r) {
t[p].l = l, t[p].r = r;
if (l == r) return;
build(ls, l, md), build(rs, md + 1, r);
}
inline void add(int p, ll x) {
t[p].x += x * (t[p].r - t[p].l + 1), t[p].z += x;
}
inline void spd(int p) {
if (t[p].z) add(ls, t[p].z), add(rs, t[p].z), t[p].z = 0;
}
inline void upd(int p) {
t[p].x = t[ls].x + t[rs].x;
}
void add(int p, int l, int r, ll x) {
if (t[p].l >= l && t[p].r <= r) return add(p, x);
spd(p);
if (l <= md) add(ls, l, r, x);
if (r > md) add(rs, l, r, x);
upd(p);
}
void ins(int c, int l, int r) {
auto itl = s[c].lower_bound(mp(l, 0)), itr = s[c].lower_bound(mp(r + 1, 0));
if (itl != s[c].begin()) {
--itl;
if ((*itl).se >= r) return;
++itl;
}
while (itl != itr) add(1, (*itl).fi, (*itl).se, -1), s[c].erase(itl++);
add(1, l, r, 1), s[c].insert(mp(l, r));
}
ll ask(int p, int l, int r) {
if (t[p].l >= l && t[p].r <= r) return t[p].x;
spd(p);
ll ret = 0;
if (l <= md) ret += ask(ls, l, r);
if (r > md) ret += ask(rs, l, r);
return ret;
}
int main() {
rd(n), rd(m);
for (int i = 1, x, y; i < n; i++) rd(x), rd(y), e[x].pb(y), e[y].pb(x);
dfs(1), build(1, 1, n);
while (m--) {
int o, x, c;
rd(o), rd(x);
if (o == 1) rd(c), ins(c, l[x], r[x]);
else print(ask(1, l[x], r[x]));
}
return 0;
}
Tree Depth
我们要求的是每个位置在所有 $k$ 对逆序对的排列构造的笛卡尔树上的深度和。
稍微转化一下，对于位置 $i$，答案即是所有合法的笛卡尔树上 $i$ 的祖先数量之和，再加上合法排列数。
那么我们可以枚举所有 $j$，求出有多少合法的笛卡尔树上 $j$ 是 $i$ 的祖先，把结果加到 $i$ 的答案上。
而在排列 $p$ 中，$j$ 是 $i$ 的祖先的充要条件是 $p_j$ 是 $[i,j]$ 或 $[j,i]$ 的 $\min$。
另一方面，设 $f_{n,k}$ 表示 $1\sim n$ 的排列有 $k$ 对逆序对的个数，其生成函数为
$$
F_{n}(x) = \prod_{i=0}^{n-1} \sum_{j=0}^i x^j
$$
原因是从左到右考虑每个数，第 $i$ 个数与前面构成的逆序对可以从 $0 \sim i – 1$ 中任选。
如果我们钦定 $j$ 是 $i$ 的祖先，那么我们可以先从 $i$ 考虑到 $j$，再考虑剩下的数，则当考虑 $j$ 的时候 $p_j$ 必须为当前最小的，即：
- 若 $i < j$，$F(x) = \frac{F_n(x)}{\sum_{k=0}^{j-i} x^k} x^{j-i}$。
- 若 $i > j$，$F(x) = \frac{F_n(x)}{\sum_{k=0}^{j-i} x^k} x^{0}$。
那么答案就是 $[x^K]F(x)$。
注意到不同的 $F(x)$ 只有 $\mathcal O(n)$ 个，因为只与 $j-i$ 有关。
暴力计算出 $F_n(x)$ 是 $\mathcal O(n^4)$ 的，求出每一个 $F(x)$ 是 $\mathcal O(n^3)$ 的，因此总时间复杂度为 $\mathcal O(n^4)$。
前缀和可以在乘法和除法的时候优化掉一个 $\mathcal O(n)$，最后的时间复杂度为 $\mathcal O(n^3)$。
const int N = 307;
int n, m, k;
modint f[N*N], g[N*N], ans[N];
void mul(int x) {
m += x, g[0] = f[0];
for (int i = 1; i <= m; i++) g[i] = g[i-1] + f[i];
for (int i = 0; i <= m; i++)
f[i] = g[i] - (i - x - 1 >= 0 ? g[i-x-1] : 0);
}
void div(int x) {
modint s = 0;
for (int i = m - x; ~i; i--) {
if (i + x + 1 <= m - x) s -= g[i+x+1];
s += g[i] = f[i+x] - s;
}
for (int i = 0; i <= m; i++) f[i] = 0;
m -= x;
for (int i = 0; i <= m; i++) f[i] = g[i];
}
int main() {
rd(n, k, P);
f[0] = 1;
for (int i = 1; i < n; i++) mul(i);
for (int i = 1; i < n; i++) {
div(i);
for (int j = i + 1; j <= n; j++) ans[j] += f[k];
if (k >= i) for (int j = 1; i + j <= n; j++) ans[j] += f[k-i];
mul(i);
}
for (int i = 1; i <= n; i++) ans[i] += f[k];
printa(ans, n);
return 0;
}
2020 January Contest
Cave Paintings
借助并查集抽离出森林，然后树形 DP 一下即可。
const int N = 1e3 + 7;
int n, m;
char s[N][N];
int f[N*N], p[N*N];
modint c[N*N], ans = 1;
int get(int x) {
return x == f[x] ? x : (f[x] = get(f[x]));
}
inline void merge(int x, int y) {
f[get(x)] = get(y);
}
int get(int x, int y) {
return (x - 1) * m + (y - 1) + 1;
}
void get(int &x, int &y, int z) {
x = (z - 1) / m + 1, y = (z - 1) % m + 1;
}
int main() {
rd(n, m);
for (int i = 1; i <= n; i++) rds(s[i], m);
for (int i = 1; i <= n * m; i++) f[i] = i, c[i] = 1;
for (int i = n - 1; i > 1; i--) {
vector<pi> e;
for (int j = 2; j < m; j++) {
if (s[i][j] == '.' && s[i][j+1] == '.')
merge(get(i, j), get(i, j + 1));
if (s[i][j] == '.' && s[i+1][j] == '.')
e.pb(mp(get(get(i + 1, j)), get(i, j)));
}
sort(e.begin(), e.end());
for (ui j = 1; j < e.size(); j++)
if (e[j].fi == e[j-1].fi)
merge(e[j].se, e[j-1].se);
for (ui j = 0; j < e.size(); j++)
if (!j || e[j].fi != e[j-1].fi)
p[get(e[j].fi)] = get(e[j].se);
}
for (int i = n * m; i; i--) {
if (get(i) != i) continue;
int x, y;
get(x, y, i);
if (s[x][y] == '#') continue;
c[i] += 1;
if (p[i]) c[p[i]] *= c[i];
else ans *= c[i];
}
print(ans);
return 0;
}
Non-Decreasing Subsequences
DP 显然可以写成矩阵乘法，记转移矩阵与其逆矩阵的前缀积为 $a,ia$，则 $l,r$ 的答案为
$$
\sum_{i=1}^k (ia[l-1] \cdot a[r])[1][i]
$$
由于只有 $\mathcal O(k)$ 个位置有值，矩阵乘法的复杂度为 $\mathcal O(k^2)$。
直接做复杂度为 $\mathcal O((n+q)k^2)$，将前缀积再前缀和一下就是 $\mathcal O(nk^2 + qk)$。
const int N = 5e4 + 7, K = 21, i2 = (P + 1) >> 1;
int n, k, q;
modint a[K][K], ia[K][K], s[N][K], is[N][K], ans;
int main() {
rd(n, k);
for (int i = 1; i <= k; i++)
a[i][i] = ia[i][i] = s[0][i] = 1;
is[0][1] = 1;
for (int o = 1, x; o <= n; o++) {
rd(x);
for (int i = 1; i <= x; i++)
for (int j = x; j >= i; j--)
a[i][x] += a[i][j];
for (int i = 1; i < x; i++)
for (int j = x; j <= k; j++)
ia[i][j] -= i2 * ia[x][j];
for (int i = x; i <= k; i++)
ia[x][i] *= i2;
for (int i = 1; i <= k; i++) {
is[o][i] = ia[1][i];
for (int j = i; j <= k; j++)
s[o][i] += a[i][j];
}
}
rd(q);
for (int i = 1, l, r; i <= q; i++) {
rd(l, r), ans = 0;
for (int j = 1; j <= k; j++)
ans += s[r][j] * is[l-1][j];
print(ans);
}
return 0;
}
Falling Portals
把图象画出来 $f_i(x) = -ix + a_i$，问的就是允许走交点的情况下从 $f_i(x)$ 走到 $f_{q_i}(x)$ 的最小横坐标。
根据 $a_{i}$ 和 $a_{q_i}$ 的大小关系，判断是向上走还是向下走。
每次显然是贪心地能走则走，因此决策是唯一的，预处理之后倍增即可。
预处理大概是个凸包，代码不写了。
2020 February Contest
Delegation
跟 P5021 赛道修建 差不多，二分 + 贪心 + 树形 dp。
const int N = 1e5 + 7;
int n, m;
vi e[N];
inline int dp(int x, int f) {
multiset<int> s;
for (int y : e[x])
if (y != f) {
int k = dp(y, x);
if (!~k) return -1;
s.insert(k + 1);
}
int p = 0, q = 0;
while (s.size()) {
int t = *s.begin();
s.erase(s.begin());
if (t >= m) p = t;
else {
auto o = s.lower_bound(m - t);
if (o == s.end()) {
if (p) return -1;
p = t;
} else {
if (*o >= m) q = t;
s.erase(o);
}
}
}
return x != 1 ? p ? p : q : p;
}
int main() {
rd(n);
for (int i = 1, x, y; i < n; i++)
rd(x), rd(y), e[x].pb(y), e[y].pb(x);
int l = 1, r = n - 1;
while (l < r) {
m = (l + r + 1) >> 1;
int k = dp(1, 0);
if (!k || k >= m) l = m;
else r = m - 1;
}
print(l);
return 0;
}
Equilateral Triangles
曼哈顿距离转成切比雪夫距离，可以发现满足要求的三角形在新的坐标下一定是一个平行与坐标轴的正方形的两个相邻的顶点和对面的边上的任意一点连接而成。
那么前缀和计数一下即可，显然要横着和竖着各算一次，时间复杂度 $\mathcal O(n^3)$。
如果出现三个点都是正方形的顶点的情况，会被横着竖着各计算一次，需要去掉这样的情况，在后一次计算的时候不算到即可。
const int N = 307;
int n, a[N*2][N*2], b[N*2][N*2];
char s[N];
ll ans;
int main() {
rd(n);
for (int i = 1; i <= n; i++) {
rds(s, n);
for (int j = 1; j <= n; j++)
if (s[j] == '*') a[i+j-1][i-j+n] = 1;
}
n *= 2;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
b[i][j] = a[i][j] + b[i][j-1];
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (a[i][j])
for (int k = j + 1; k <= n; k++)
if (a[i][k]) {
if (i - (k - j) >= 1)
ans += b[i-(k-j)][k] - b[i-(k-j)][j-1];
if (i + (k - j) <= n)
ans += b[i+(k-j)][k] - b[i+(k-j)][j-1];
}
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
b[i][j] = a[i][j] + b[i-1][j];
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (a[j][i])
for (int k = j + 1; k <= n; k++)
if (a[k][i]) {
if (i - (k - j) >= 1)
ans += b[k-1][i-(k-j)] - b[j][i-(k-j)];
if (i + (k - j) <= n)
ans += b[k-1][i+(k-j)] - b[j][i+(k-j)];
}
print(ans);
return 0;
}
Help Yourself
$$
\begin{aligned}Ans &= \sum_{s} ans(s)^k \\&= \sum_{s} \sum_{i=0}^k S_2(k, i) ans(s)^{\underline{k}} \\&= \sum_{i=0}^k S_2(k,i) i! \sum_s \binom{ans(s)}{i}\end{aligned}
$$
将区间按 $l$ 排序，每次加入一个区间做 DP。
设 $f_i$ 表示最右边的端点为 $i$ 的集合的答案，分 $i<l$，$l \le i \le r$，$i>r$ 三种情况转移，线段树优化，时间复杂度 $\mathcal O(nk\log n)$。
本题中常幂转下降幂的 Trick 非常重要。
2020 US Open Contest
Sprinklers 2: Return of the Alfalfa
设 $f_{i,j}$ 表示考虑前 $i$ 行，第 $i$ 行中，第 $1\sim j-1$ 列为 C，第 $j\sim n$ 列为 A，且第 $i+1$ 行的第 $j$ 列为 C 的方案数。
这个定义要求我们从 $f_{i_1,j_1}$ 转移到 $f_{i_2,j_2}$ 的条件为：
- $i_1 < i_2$，$j_1 < j_2$。
- $s_{i_1+1, j_2-1},s_{i_2,j_2}$ 都为
.或不存在。
设第 $i_1+1 \sim i_2$ 行中 . 的个数为 $c$，则转移系数为 $2^{c-k}$，其中 $k$ 是固定必须放的个数。
边界为 $f_{0,0} = 1$，目标为 $\sum_{j=1}^{n+1} f_{n,j}$。
直接做是 $\mathcal O(n^4)$ 的，二维前缀和优化一下就是 $\mathcal O(n^2)$ 的了。
const int N = 2e3 + 7;
int n;
char s[N][N];
modint f[N][N], h[N][N], g[N], vg[N], v2, ans;
int main() {
rd(n), v2 = (modint)1 / 2, g[0] = vg[0] = 1;
for (int i = 1; i <= n; i++) {
rds(s[i], n);
g[i] = g[i-1];
for (int j = 1; j <= n; j++)
if (s[i][j] == '.') g[i] *= 2;
vg[i] = 1 / g[i];
}
f[0][0] = 1;
for (int j = 0; j <= n; j++)
h[0][j] = !j || s[1][j] == '.';
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n + 1; j++) {
if (j == n + 1 || s[i][j] == '.')
f[i][j] += h[i-1][j-1] * g[i] * (j - 1 == 0 ? (modint)1 : v2) * (j == n + 1 ? (modint)1 : v2);
h[i][j] = h[i][j-1] + f[i][j];
}
if (i == n) continue;
for (int j = 0; j <= n; j++)
if (!j || s[i+1][j] == '.') h[i][j] = h[i][j] * vg[i] + h[i-1][j];
else h[i][j] = h[i-1][j];
}
print(h[n][n+1]);
return 0;
}
Exercise
题目太神仙了，先咕咕咕着。
Circus
题目太神仙了，先咕咕咕着。
