USACO 2020 January Contest, Platinum Problem 2. Non-Decreasing Subsequences
这个题目有两种做法，一种是矩阵，一种是 CDQ 分治。矩阵我只大概口胡了一下，没仔细想，这里主要介绍一下 CDQ 分治的做法。
CDQ 分治。考虑到一般不下降子序列的做法，对左右分别维护一个 DP数组 \(f(x,i)\) ：
- 若 \(l\leq i\leq mid\)，则表示以 \(i\) 为左端点，所有 \(k\in[i,mid]\) 且 \(A_k=x\) 的 \(k\) 为右端点，不下降子序列的个数。
- 若 \(mid<i\leq r\)，则表示以 \(i\) 为右端点，所有 \(k\in[mid+1,i]\) 且 \(A_k=x\) 的 \(k\) 为左端点，不下降子序列的个数。
考虑跨过左右两半的询问 \([ql,qr]\)，显然答案就是 \(\displaystyle\sum_{i=l}^{mid}\sum_{j=mid+1}^r\sum_{x=1}^K\sum_{y=x}^{K}f(x,i)\times f(y,j)\)，用前/后缀合优化即可通过。
时间复杂度 \(\mathcal{O}(NK\log N\log K+QK)\)。
点击查看代码
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9+7;
const int MAXN = 5e4 + 5, MAXK = 25, MAXQ = 2e5 + 5;
void setIO(string name) {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
freopen((name + ".in").c_str(), "r", stdin);
freopen((name + ".out").c_str(), "w", stdout);
}
int N, K, Q;
int A[MAXN], qL[MAXQ], qR[MAXQ], ans[MAXQ];
int f[MAXK][MAXN];
struct FenwickTree {
int tree[MAXK];
void init() { memset(tree, 0, sizeof (tree)); }
void modify(int x, int v) {
while (x <= K) {
(tree[x] += v) %= MOD;
x += x & -x;
}
}
int query(int x) {
int res = 0;
while (x > 0) {
(res += tree[x]) %= MOD;
x -= x & -x;
}
return res;
}
} T;
void solve(int L, int R, vector<int> Queries) {
if (L == R) {
for (auto id : Queries) ans[id] = 2;
return;
}
int mid = (L + R) >> 1;
for (int i = 1; i <= K; i++) {
T.init();
for (int j = mid; j >= L; j--) {
f[i][j] = ((A[j] == i) + T.query(K + 1 - A[j])) % MOD;
T.modify(K + 1 - A[j], f[i][j]);
}
for (int j = mid - 1; j >= L; j--) (f[i][j] += f[i][j + 1]) %= MOD;
}
for (int i = L; i <= mid; i++) (f[1][i] += 1) %= MOD;
for (int i = 1; i <= K; i++) {
T.init();
for (int j = mid + 1; j <= R; j++) {
f[i][j] = ((A[j] == i) + T.query(A[j])) % MOD;
T.modify(A[j], f[i][j]);
}
for (int j = mid + 2; j <= R; j++) (f[i][j] += f[i][j - 1]) %= MOD;
}
for (int i = mid + 1; i <= R; i++) (f[K][i] += 1) %= MOD;
vector<int> QueriesL, QueriesR;
QueriesL.clear();
QueriesR.clear();
for (auto id : Queries) {
if (qR[id] <= mid) QueriesL.emplace_back(id);
else if (qL[id] > mid) QueriesR.emplace_back(id);
else {
int sum = 0;
for (int i = K; i >= 1; i--) {
(sum += f[i][qR[id]]) %= MOD;
(ans[id] += 1LL * f[i][qL[id]] * sum % MOD) %= MOD;
}
}
}
solve(L, mid, QueriesL);
solve(mid + 1, R, QueriesR);
}
int main() {
// setIO("nondec");
cin >> N >> K;
for (int i = 1; i <= N; i++) cin >> A[i];
cin >> Q;
vector<int> oriQ;
for (int i = 1; i <= Q; i++) {
cin >> qL[i] >> qR[i];
oriQ.emplace_back(i);
}
solve(1, N, oriQ);
for (int i = 1; i <= Q; i++) cout << ans[i] << "\n";
return 0;
}
USACO 2020 January Contest, Platinum Problem 3. Falling Portals
首先可以发现一个贪心的策略：如果 \(A_{Q_i}<A_i\)，则希望下落地越快越好，知道到达 \(Q_i\)，反之是对称的，故下只考虑这种情况。
显然可以把图像画出来，发现行走的是一个上凸壳，那就维护一个凸包，每次询问在上面二分即可。细节见代码。
时间复杂度 \(\mathcal{O}(N\log N)\)。
点击查看代码
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 10;
void setIO(string name) {
freopen((name + ".in").c_str(), "r", stdin);
freopen((name + ".out").c_str(), "w", stdout);
}
int N;
int A[MAXN], Q[MAXN], id[MAXN];
int stk[MAXN], top = 0;
int resx[MAXN], resy[MAXN];
bool check(int x, int y, int k) { return 1LL * (A[x] - A[k]) * (y - k) < 1LL * (A[y] - A[k]) * (x - k); }
void ins(int id, bool op) {
while((top > 0 && (op ^ (stk[top] < id))) || (top > 1 && check(stk[top - 1], stk[top], id))) top--;
stk[++top] = id;
if(op ^ (A[Q[id]] < A[id])) {
if(op ^ (Q[id] > stk[1])) return;
int l = 1, r = top;
while(l < r) {
int mid = (l + r + 1) >> 1;
if((op ^ (Q[id] < stk[mid])) && check(stk[mid], stk[mid - 1], Q[id])) l = mid;
else r = mid - 1;
}
resx[id] = A[stk[l]] - A[Q[id]]; resy[id] = stk[l] - Q[id];
}
}
int main() {
// setIO("falling");
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> N;
for (int i = 1; i <= N; i++) cin >> A[i];
for (int i = 1; i <= N; i++) cin >> Q[i];
for (int i = 1; i <= N; i++) id[i] = i;
sort(id + 1, id + N + 1, [&](int x, int y) { return A[x] > A[y]; });
for (int i = 1; i <= N; i++) ins(id[i], 0);
top = 0;
for (int i = N; i >= 1; i--) ins(id[i], 1);
for (int i = 1; i <= N; i++) {
if(!resx[i]) {
cout << "-1\n";
continue;
}
int g = __gcd(resx[i], resy[i]);
resx[i] /= g, resy[i] /= g;
cout << resx[i] << "/" << resy[i] << "\n";
}
return 0;
}
USACO 2020 Feburary Contest, Platinum Problem 1. Delegation
和 NOIP2018 赛道修建 非常相似。
显然二分答案。考虑 check() 就是 DFS 一遍，每次上传一个当前往上传的没删掉的边权。用 multiset 维护删边，每次贪心地删边即可。
注意：如果 \(u=1\)，则强制儿子个数偶数，不满补 \(0\)；否则强制奇数，不满补 \(0\)。
时间复杂度 \(\mathcal{O}(N\log^2 N)\)。
点击查看代码
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5+5;
void setIO(string name) {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
freopen((name + ".in").c_str(), "r", stdin);
freopen((name + ".out").c_str(), "w", stdout);
}
int N;
vector<int> G[MAXN];
bool res;
int dfs(int u, int p, int lim) {
multiset<int> S;
for (auto v : G[u]) {
if (v == p) continue;
S.insert(dfs(v, u, lim) + 1);
if(!res) return 0;
}
if(u == 1 && ((int)S.size() & 1)) S.insert(0);
if(u != 1 && !((int)S.size() & 1)) S.insert(0);
bool flag = 0;
int ret;
while(!S.empty()) {
int cur = *S.begin();
S.erase(S.begin());
auto it = S.lower_bound(lim - cur);
if (it == S.end()) {
if (u == 1 || flag) {
res = 0;
return 0;
}
flag = 1;
ret = cur;
continue;
}
S.erase(it);
}
return ret;
}
bool check(int lim) {
res = 1;
dfs(1, 0, lim);
return res;
}
int main() {
// setIO("deleg");
cin >> N;
for (int i = 1; i < N; i++) {
int u, v;
cin >> u >> v;
G[u].push_back(v);
G[v].push_back(u);
}
int l = 1, r = N - 1;
while (l < r) {
int mid = (l + r + 1) >> 1;
if (check(mid)) l = mid;
else r = mid - 1;
}
cout << l << '\n';
return 0;
}
USACO 2020 Feburary Contest, Platinum Problem 3. Help Yourself
先考虑 \(K=1\) 的情况咋做。
首先按区间左端点将区间排序。每次考虑加入一个区间 \([l,r]\)。设 \(f(x)\) 表示当前区间集合右端点最大的那个右端点是 \(r\) 的方案数，转移分 3 类：
- 将 \(f_0+1,f_1+1,\cdots,f_{l-1}+1\) 加到 \(f_r\) 上。
- 将 \(f_l,f_{l+1},\cdots,f_r\) 加到 \(f_r\) 上。
- 将 \(f_{r+1},f_{r+2},\cdots,f_{2N}\) 都 \(\times 2\)。
线段树维护单点加，区间乘 \(2\)，区间求和即可。
然后考虑 \(K>1\) 其实是类似的，只不过需要维护 \((f_i+1)^K\)，这个可以用二项式定理展开成有关 \(f_i^0,f_i^1,\cdots,f_i^K\) 的一些东西，所以维护 \(K\) 棵线段树，第 \(x\) 棵维护 \(f_i^x\) 即可。
时间复杂度 \(\mathcal{O}(NK\log N)\)。
点击查看代码
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
const int MAXN = 1e5 + 5;
const int MAXK = 10 + 5;
const int MOD = 1e9 + 7;
void setIO(string name) {
freopen((name + ".in").c_str(), "r", stdin);
freopen((name + ".out").c_str(), "w", stdout);
}
void mulMOD(int &x, int y) { x = 1LL * x * y % MOD; }
int N, K;
pii a[MAXN];
int C[MAXK][MAXK];
struct SegmentTree {
int val[MAXN << 3], tag[MAXN << 3]; // range sum, multiple tag
void pushup(int x) { val[x] = (val[x << 1] + val[x << 1 | 1]) % MOD; }
void pushdown(int x) {
if (tag[x] == 1) return;
mulMOD(val[x << 1], tag[x]);
mulMOD(val[x << 1 | 1], tag[x]);
mulMOD(tag[x << 1], tag[x]);
mulMOD(tag[x << 1 | 1], tag[x]);
tag[x] = 1;
}
void modifyMul(int x, int l, int r, int ql, int qr) {
if(ql > qr) return ;
if (l >= ql && r <= qr) {
mulMOD(val[x], 2);
mulMOD(tag[x], 2);
return;
}
pushdown(x);
int mid = (l + r) >> 1;
if (ql <= mid) modifyMul(x << 1, l, mid, ql, qr);
if (qr > mid) modifyMul(x << 1 | 1, mid + 1, r, ql, qr);
pushup(x);
}
void modifyPoint(int x, int l, int r, int p, int v) {
if (l == r) {
(val[x] += v) %= MOD;
return;
}
pushdown(x);
int mid = (l + r) >> 1;
if (p <= mid) modifyPoint(x << 1, l, mid, p, v);
else modifyPoint(x << 1 | 1, mid + 1, r, p, v);
pushup(x);
}
int query(int x, int l, int r, int ql, int qr) {
if (l >= ql && r <= qr) return val[x];
pushdown(x);
int mid = (l + r) >> 1, res = 0;
if (ql <= mid) res = query(x << 1, l, mid, ql, qr);
if (qr > mid) (res += query(x << 1 | 1, mid + 1, r, ql, qr)) %= MOD;
return res;
}
} T[MAXK];
int v[MAXK];
int main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> N >> K;
for (int i = 0; i <= K; i++) {
C[i][0] = 1;
for (int j = 1; j <= i; j++) {
C[i][j] = C[i - 1][j] + C[i - 1][j - 1];
}
}
for (int i = 1; i <= N; i++) cin >> a[i].first >> a[i].second;
sort(a + 1, a + N + 1);
for (int i = 0; i <= K; i++) {
memset(T[i].val, 0, sizeof(T[i].val));
memset(T[i].tag, 1, sizeof(T[i].tag));
}
T[0].modifyPoint(1, 0, (N << 1), 0, 1);
for (int i = 1; i <= N; i++) {
for (int j = 0; j <= K; j++) T[j].modifyPoint(1, 0, (N << 1), a[i].second, T[j].query(1, 0, (N << 1), a[i].first, a[i].second));
for (int j = 0; j <= K; j++) v[j] = T[j].query(1, 0, (N << 1), 0, a[i].first - 1);
for (int j = 0; j <= K; j++) {
int sum = 0;
for (int k = 0; k <= j; k++) (sum += 1LL * v[k] * C[j][k] % MOD) %= MOD;
T[j].modifyPoint(1, 0, (N << 1), a[i].second, sum);
}
for (int j = 0; j <= K; j++) T[j].modifyMul(1, 0, (N << 1), a[i].second + 1, (N << 1));
}
cout << T[K].query(1, 0, (N << 1), 0, (N << 1)) << "\n";
return 0;
}