省流：A、B、C、E、H、K、L。
D 和 I 之后可能会看心情补，剩下的题大概这辈子都不会做了。
A. Points
有两个由二维平面上的点组成的可重点集 \(U,V\)。如下定义 \(D(U,V)\)：
- 当 \(U,V\) 中存在一个为空时，\(D(U,V) = -1\)。
- 否则 \(D(U,V) = \min\limits_{(u_x,u_y) \in U, (v_x,v_y) \in V} \max(u_x+v_x,u_y+v_y)\)。
初始时 \(U,V\) 均为空。\(q\) 次操作，每次操作对 \(U\) 或 \(V\) 插入或删除一个元素，在每次操作后求出 \(D(U,V)\) 的值。
\(1 \leq q \leq 2.5 \times 10^5\)，\(0 \le x,y \le 2.5 \times 10^5\)。
先讲个一开始想的愚笨做法：线段树分治一下，每次加入元素 \(u\) 的时候二分 \(mid\)，判定另一侧是否所有 \(v\) 都满足 \(\max(u_x+v_x,u_y+v_y) \geq mid\)。考虑将元素按照 \(v_x\) 排序，那么满足 \(u_x+v_x \ge mid\) 的部分是一个后缀，对剩下的前缀部分而言，必须满足 \(u_y + v_y \geq mid\)。以 \(v_x\) 为下标建立线段树，每次二分出这个前缀查区间 \(\min\) 即可，但这样是 \(\mathcal{O}(q \log q \log^2 V)\) 的，很没救。
考虑把 \(\max\) 拆掉。讨论一下，容易得出当 \(u_x - u_y \ge v_y - v_x\) 时，\(\max\) 由 \(u_x + v_x\) 提供，反之则由 \(u_y + v_y\) 提供。这样做的好处是，在新的判断方式中，\(u\) 和 \(v\) 是独立的，这给我们的维护带来了很大的便利。
我们使用线段树来维护答案，每个节点存区间内 \(u_x,u_y,v_x,v_y\) 的最小值和区间内的答案。对于 \(u\)，我们将它的信息在下标 \(u_x - u_y\) 处更新，对于 \(v\) 则将它的信息在 \(v_y - v_x\) 处更新，这样合并的时候更新答案是容易的。需要注意对于同一个 \(d\)，可能存在多个点的 \(u_x - u_y = d\)，因此对线段树的每个叶子我们还需要开一个 \(\tt{multiset}\) 维护对应的点集，同时不要漏掉 \(u_x - u_y = v_y - v_x\) 的情况。总时间复杂度 \(\mathcal{O}(q \log V)\)。
code
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair <int, int> pi;
#define fi first
#define se second
constexpr int N = 5e5 + 5, inf = 1e9;
bool Mbe;
int n = 250000, q;
multiset <int> sux[N], suy[N], svx[N], svy[N];
#define m ((l + r) >> 1)
int tr[N << 2], ux[N << 2], uy[N << 2], vx[N << 2], vy[N << 2];
void push_up(int x) {
tr[x] = min(tr[x << 1], tr[x << 1 | 1]);
int val = min(uy[x << 1] + vy[x << 1 | 1], ux[x << 1 | 1] + vx[x << 1]);
tr[x] = min(tr[x], val);
ux[x] = min(ux[x << 1], ux[x << 1 | 1]);
uy[x] = min(uy[x << 1], uy[x << 1 | 1]);
vx[x] = min(vx[x << 1], vx[x << 1 | 1]);
vy[x] = min(vy[x << 1], vy[x << 1 | 1]);
}
void build(int x, int l, int r) {
tr[x] = ux[x] = uy[x] = vx[x] = vy[x] = inf;
if (l == r) return;
build(x << 1, l, m), build(x << 1 | 1, m + 1, r);
}
pi cur;
void mdf(int x, int l, int r, int p, int v, int ty) { // v1 ins v2 del ty1 u ty2 v
if (l == r) {
int pos = l + n, nx = cur.fi, ny = cur.se;
assert(pos >= 0);
if (v == 1) {
if (ty == 1) {
sux[pos].insert(nx);
suy[pos].insert(ny);
ux[x] = *sux[pos].begin();
uy[x] = *suy[pos].begin();
} else {
svx[pos].insert(nx);
svy[pos].insert(ny);
vx[x] = *svx[pos].begin();
vy[x] = *svy[pos].begin();
}
} else {
if (ty == 1) {
auto it = sux[pos].find(nx);
sux[pos].erase(it);
it = suy[pos].find(ny);
suy[pos].erase(it);
if (sux[pos].empty()) ux[x] = inf;
else ux[x] = *sux[pos].begin();
if (suy[pos].empty()) uy[x] = inf;
else uy[x] = *suy[pos].begin();
} else {
auto it = svx[pos].find(nx);
svx[pos].erase(it);
it = svy[pos].find(ny);
svy[pos].erase(it);
if (svx[pos].empty()) vx[x] = inf;
else vx[x] = *svx[pos].begin();
if (svy[pos].empty()) vy[x] = inf;
else vy[x] = *svy[pos].begin();
}
}
tr[x] = min(ux[x] + vx[x], uy[x] + vy[x]);
return;
}
if (p <= m) mdf(x << 1, l, m, p, v, ty);
else mdf(x << 1 | 1, m + 1, r, p, v, ty);
push_up(x);
}
#undef m
bool Med;
int main() {
// fprintf(stderr, "%.9lf\n", 1.0 * (&Mbe - &Med) / 1048576.0);
ios :: sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> q;
build(1, -n, n);
while (q--) {
int op, s, x, y;
cin >> op >> s >> x >> y;
cur = make_pair(x, y);
if (s == 1) mdf(1, -n, n, x - y, op, s);
else mdf(1, -n, n, y - x, op, s);
if (tr[1] >= inf) cout << "-1\n";
else cout << tr[1] << "\n";
}
// cerr << 1e3 * clock() / CLOCKS_PER_SEC << "ms\n";
return 0;
}
/*
6
1 1 100 100
1 2 30 130
1 1 120 170
2 1 100 100
1 2 70 100
2 1 120 170
*/
B. Bingo
构造一个 \(n \times n\) 的矩形，里面恰有 \(k\) 个 #，且不存在任意一行、一列或一条对角线上全是 #，或报告无解。
\(1 \leq n \leq 100\)。
显然，我们只需要求出最多能放多少个 # 并构造方案。
-
当 \(n\) 为奇数时，\(k\) 的最大值为 \(n^2 - n\)，留出一条对角线即可。
-
当 \(n\) 为偶数时：
- 若 \(n=2\)，则 \(k\) 的最大值为 \(2\)。
- 否则有 \(n>2\)，此时 \(k\) 的最大值也是 \(n^2-n\)，留出一条对角线，再把最中间 \(2 \times 2\) 的方阵旋转一下即可。
时间复杂度 \(\mathcal{O}(n^2)\)。
code
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair <int, int> pi;
#define fi first
#define se second
constexpr int N = 1e2 + 5, mod = 1e9 + 7;
bool Mbe;
int n, k;
char a[N][N];
bool Med;
int main() {
// fprintf(stderr, "%.9lf\n", 1.0 * (&Mbe - &Med) / 1048576.0);
ios :: sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n >> k;
if (n == 1) {
if (k == 0) cout << "YES\n.\n";
else cout << "NO\n";
return 0;
} if (n == 2) {
if (k == 0) cout << "YES\n..\n..\n";
if (k == 1) cout << "YES\n#.\n..\n";
if (k >= 2) cout << "NO\n";
return 0;
}
if (k > n * n - n) {
cout << "NO\n";
return 0;
}
cout << "YES\n";
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
a[i][j] = '.';
int c = 0;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++) {
if (n % 2 == 1) {
if (i != j) {
if (c == k) goto out;
a[i][j] = '#';
c++;
}
} else {
if (i != j) {
if (i == n / 2 && j == n / 2 + 1) continue;
if (i == n / 2 + 1 && j == n / 2) continue;
if (c == k) goto out;
a[i][j] = '#';
c++;
} else if (i == n / 2 || i == n / 2 + 1) {
if (c == k) goto out;
a[i][j] = '#';
c++;
}
}
}
out :
for (int i = 1; i <= n; i++) cout << a[i] + 1 << "\n";
// cerr << 1e3 * clock() / CLOCKS_PER_SEC << "ms\n";
return 0;
}
C. AND PLUS OR
给定一个长为 \(2^n\) 的序列 \(a\)，给出一组 \(i,j\) 满足 \(a_{i} + a_{j} < a_{i \operatorname{and} j} + a_{i \operatorname{or} j}\)，或报告无解。
\(1 \leq n \leq 20\)。
考虑改写一下式子，将 \(i,j\) 看成集合，令 \(x = i \cap j\)，\(y = i - x\)，\(z = j - x\)，则原式可改写成：\(a(x+y) + a(x+z) < a(x) + a(x+y+z)\)，即 \(a(x+y) - a(x) < a(x+y+z) - a(x+z)\)。我们将其看成一个关于集合的函数 \(f(S) = a(x+y+S) - a(x+S)\)，那么上式等价于 \(f(\emptyset) < f(S)\)。
当 \(x,y\) 固定时，假设我们已经找到了一个 \(z\) 满足条件，我们可以尝试在空集中逐位加入 \(z\) 的每一位，观察函数的变化。令 \(z_j\) 表示只包含 \(z\) 中前 \(j\) 个 \(1\) 的集合。我们发现，由于最后 \(f(\emptyset) < f(z)\)，那么在 \(j\) 在 \(0 \sim |z|\) 变化的过程中，一定存在一个位置 \(j\)，使得 \(f(z_{j-1}) < f(z_j)\)。此时令 \(x \gets x + z_j\)，\(z \gets z_{j+1 \sim |z|}\)，我们就得到了一个新的解。
反复上述操作，最后一定能够得到一个 \(|z|=1\) 的解。对于 \(y\) 同理。于是我们只需要枚举 \(x\)，再枚举两个不在 \(x\) 中的元素即可，时间复杂度 \(\mathcal{O}(n^2 2^n)\)。
code
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair <int, int> pi;
#define fi first
#define se second
constexpr int N = 2e6 + 5, inf = 1e9;
bool Mbe;
int n, a[N];
void solve() {
cin >> n;
for (int i = 0; i < 1 << n; i++) cin >> a[i];
int x = -1, y = 0;
for (int s = 0; s < 1 << n; s++)
for (int i = 0; i < n; i++)
if (!((s >> i) & 1))
for (int j = 0; j < n; j++)
if ((i != j) && !((s >> j) & 1)) {
int v1 = a[s | (1 << i)] + a[s | (1 << j)];
int v2 = a[s] + a[s | (1 << i) | (1 << j)];
if (v1 < v2) {
x = s | (1 << i), y = s | (1 << j);
goto end;
}
}
end :
if (x == -1) cout << "-1\n";
else cout << x << " " << y << "\n";
}
bool Med;
int main() {
// fprintf(stderr, "%.9lf\n", 1.0 * (&Mbe - &Med) / 1048576.0);
ios :: sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t; t = 1;
while (t--) solve();
// cerr << 1e3 * clock() / CLOCKS_PER_SEC << "ms\n";
return 0;
}
完全不理解为什么场上过这题的队比过 A 的多那么多，难道大家都是猜结论大师吗
。
E. Yet Another Interval Graph Problem
给定 \(n\) 条线段 \([l_i,r_i]\)，新建一张图 \(G\)，点 \(i\) 和点 \(j\) 之间有连边当且仅当 \(i,j\) 两条线段有交。删除第 \(i\) 个点有代价 \(c_i\)，求最小代价使得图中所有连通块的大小都不超过 \(k\)。
\(1 \leq k \leq n \leq 2500\)，\(1 \leq l_i \leq r_i \le 10^9\)，\(1 \le c_i \le 10^9\)。
考虑 DP。但我们发现删点难以处理，改为考虑保留哪些点并最大化价值。显然每个连通块会形成一个区间，设 \(f_i\) 表示 \(i\) 位置之前的答案，转移时枚举 \(f_j\) 并钦定 \([j+1,i]\) 连通，这样我们只需要取所有被 \([j+1,i]\) 包含的区间 \(l\) 的前 \(k\) 大的 \(c_l\) 即可。使用优先队列维护，时间复杂度 \(\mathcal{O}(n^2 \log k)\)。
code
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair <int, int> pi;
#define fi first
#define se second
constexpr int N = 5e5 + 5, inf = 1e9;
int n, k; LL ans, f[N];
struct seg {
int l, r, val;
};
vector <int> t;
vector <seg> tmp, add[N], del[N];
LL sum;
priority_queue <int> q;
void ins(int x) {
if (q.size() < k) {
sum += x;
q.push(-x);
} else if (-q.top() < x) {
sum -= -q.top();
sum += x;
q.pop();
q.push(-x);
}
}
bool Med;
int main() {
// fprintf(stderr, "%.9lf\n", 1.0 * (&Mbe - &Med) / 1048576.0);
ios :: sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n >> k;
for (int i = 1; i <= n; i++) {
int l, r, w;
cin >> l >> r >> w;
t.emplace_back(l);
t.emplace_back(r);
ans += w;
tmp.emplace_back((seg){ l, r, w });
}
sort(t.begin(), t.end());
t.erase(unique(t.begin(), t.end()), t.end());
for (auto it : tmp) {
it.l = lower_bound(t.begin(), t.end(), it.l) - t.begin() + 1;
it.r = lower_bound(t.begin(), t.end(), it.r) - t.begin() + 1;
// cerr << it.l << " " << it.r << "\n";
add[it.r].emplace_back(it);
}
n = t.size();
for (int i = 1; i <= n; i++) {
sum = 0;
while (q.size()) q.pop();
for (auto it : add[i]) del[it.l].emplace_back(it);
for (int j = i; j >= 1; j--) {
for (auto it : del[j]) ins(it.val);
f[i] = max(f[i], f[j - 1] + sum);
}
}
ans -= f[n];
cout << ans << "\n";
// cerr << 1e3 * clock() / CLOCKS_PER_SEC << "ms\n";
return 0;
}
/*
5 2
1 4 1
3 6 2
5 8 5
7 10 2
9 12 1
*/
H. Endless Road
给定 \(n\) 个区间 \([l_i,r_i)\)。进行 \(n\) 轮如下操作：
- 设区间 \(i\) 当前的权值 \(v_i\) 为区间内未被染色的位置数量。找到 \(v_i\) 最小的区间 \(I\)（若有多个则取编号最小的一个）。
- 将区间 \(I\) 内的所有位置染色。
请你依次输出每轮选择的区间编号。
\(1 \le n \leq 2.5 \times 10^5\)，\(0 \le l_i < r_i \le 10^9\)。
先离散化一下，顺便把区间改成闭区间。这样每个位置带权但是只有 \(\mathcal{O}(n)\) 个。
对于两个区间 \(I,J\)，若 \(I \subseteq J\)，那么 \(J\) 被删除的时间显然一定会在 \(I\) 之后。因此我们先考虑区间不互相包含的情况。
考虑直接维护每个区间的权值 \(v_i\)，用 \(\tt{set}\) 维护当前剩下的位置集合，操作区间 \(I\) 时拿出所有 \(I\) 中未被删除的位置。对每个位置而言，包含它的线段都是一段区间，于是只需要维护区间加，区间最小值及最小值对应的位置即可。因为每个位置只会被删一次，因此时间复杂度为 \(\mathcal{O}(n \log n)\)。
接下来考虑相互包含的情况如何处理。此时我们需要在删除区间 \(I\) 之后加入所有不包含其他区间的区间。注意到如果将区间 \([l_i,r_i]\) 放在位置 \(l_i\)，这样的区间一定是后缀 \(r_i\) 的最小值，用另一颗支持单点修改，区间最小值及最小值位置的线段树维护即可。注意到每个 \(l_i\) 可能有多个区间，因此对每个位置我们需要开一个 \(\tt{multiset}\) 维护区间集合。同时加入线段时我们需要知道它当前的权值，这可以用一个树状数组简单维护。
实现细节见代码。总时间复杂度 \(\mathcal{O}(n \log n)\)。
code
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair <int, int> pi;
#define fi first
#define se second
constexpr int N = 5e5 + 5, inf = 2e9;
bool Mbe;
int n, l[N], r[N], m, b[N];
vector <int> tmp;
struct BIT {
int c[N];
void add(int x, int v) {
for (int i = x; i <= m; i += i & -i) c[i] += v;
}
int qry(int x) {
int res = 0;
for (int i = x; i; i -= i & -i) res += c[i];
return res;
}
int qry(int l, int r) {
return qry(r) - qry(l - 1);
}
} bit;
set <pi> s[N], curL, curR;
set <int> rest;
struct SGT1 {
#define m ((l + r) >> 1)
int mi[N << 2], id[N << 2];
void build(int x, int l, int r) {
mi[x] = inf;
if (l == r) return;
build(x << 1, l, m), build(x << 1 | 1, m + 1, r);
}
void push_up(int x) {
if (mi[x << 1] < mi[x << 1 | 1]) mi[x] = mi[x << 1], id[x] = id[x << 1];
else mi[x] = mi[x << 1 | 1], id[x] = id[x << 1 | 1];
}
void upd(int x, int l, int r, int p, pi v) {
if (l == r) return mi[x] = v.fi, id[x] = v.se, void();
if (p <= m) upd(x << 1, l, m, p, v);
else upd(x << 1 | 1, m + 1, r, p, v);
push_up(x);
}
pi qry(int x, int l, int r, int ql, int qr) {
if (ql > qr) return make_pair(0, 0);
if (ql <= l && qr >= r) return make_pair(mi[x], id[x]);
if (qr <= m) return qry(x << 1, l, m, ql, qr);
if (qr > m) return qry(x << 1 | 1, m + 1, r, ql, qr);
pi p = qry(x << 1, l, m, ql, qr);
pi q = qry(x << 1 | 1, m + 1, r, ql, qr);
return p.fi < q.fi ? p : q;
}
#undef m
} sgt1;
struct SGT2 {
#define m ((l + r) >> 1)
int mi[N << 2], id[N << 2], tag[N << 2];
void build(int x, int l, int r) {
mi[x] = inf;
if (l == r) return;
build(x << 1, l, m), build(x << 1 | 1, m + 1, r);
}
void push_up(int x) {
if (mi[x << 1] == mi[x << 1 | 1]) {
mi[x] = mi[x << 1];
id[x] = min(id[x << 1], id[x << 1 | 1]);
} else {
if (mi[x << 1] < mi[x << 1 | 1]) mi[x] = mi[x << 1], id[x] = id[x << 1];
else mi[x] = mi[x << 1 | 1], id[x] = id[x << 1 | 1];
}
}
void push_tag(int x, int v) {
mi[x] += v;
tag[x] += v;
}
void push_down(int x) {
if (tag[x]) push_tag(x << 1, tag[x]), push_tag(x << 1 | 1, tag[x]), tag[x] = 0;
}
void upd(int x, int l, int r, int p, pi v) {
if (l == r) return mi[x] = v.fi, id[x] = v.se, void();
push_down(x);
if (p <= m) upd(x << 1, l, m, p, v);
else upd(x << 1 | 1, m + 1, r, p, v);
push_up(x);
}
void mdf(int x, int l, int r, int ql, int qr, int v) {
if (ql > qr) return;
if (ql <= l && qr >= r) return push_tag(x, v);
push_down(x);
if (ql <= m) mdf(x << 1, l, m, ql, qr, v);
if (qr > m) mdf(x << 1 | 1, m + 1, r, ql, qr, v);
push_up(x);
}
#undef m
} sgt2;
bool Med;
int main() {
// fprintf(stderr, "%.9lf\n", 1.0 * (&Mbe - &Med) / 1048576.0);
ios :: sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> l[i] >> r[i];
tmp.emplace_back(l[i]);
tmp.emplace_back(r[i]);
}
sort(tmp.begin(), tmp.end());
tmp.erase(unique(tmp.begin(), tmp.end()), tmp.end());
static int suf[N];
m = tmp.size() - 1;
for (int i = 1; i <= m; i++) b[i] = tmp[i] - tmp[i - 1];
for (int i = 1; i <= n; i++) {
l[i] = lower_bound(tmp.begin(), tmp.end(), l[i]) - tmp.begin();
r[i] = lower_bound(tmp.begin(), tmp.end(), r[i]) - tmp.begin();
l[i]++;
}
// for (int i = 1; i <= m; i++) cout << b[i] << " \n"[i == m];
// for (int i = 1; i <= n; i++) cout << "["<< l[i] << ", " << r[i] << "]\n";
for (int i = 1; i <= n; i++) s[l[i]].insert(make_pair(r[i], i));
for (int i = 1; i <= m; i++) rest.insert(i);
l[0] = r[0] = 0;
l[n + 1] = r[n + 1] = m + 1;
curL.insert(make_pair(0, 0));
curR.insert(make_pair(0, 0));
curL.insert(make_pair(m + 1, n + 1));
curR.insert(make_pair(m + 1, n + 1));
sgt1.build(1, 1, m);
sgt2.build(1, 1, m);
for (int i = 1; i <= m; i++) {
if (s[i].empty()) continue;
auto it = s[i].begin();
sgt1.upd(1, 1, m, i, *it);
}
for (int i = 1; i <= m; i++) bit.add(i, b[i]);
int lst = m + 1;
for (int i = m; i >= 1; i--) {
if (s[i].empty()) continue;
auto it = s[i].begin();
int nr = it -> fi;
if (nr < lst) {
// cout << "[" << i << ", " << nr << "]\n";
curL.insert(make_pair(i, it -> se));
curR.insert(make_pair(nr, it -> se));
int val = bit.qry(i, nr);
sgt2.upd(1, 1, m, i, make_pair(val, it -> se));
s[i].erase(it);
if (!s[i].empty()) sgt1.upd(1, 1, m, i, *s[i].begin());
else sgt1.upd(1, 1, m, i, make_pair(inf, 0));
lst = nr;
}
}
vector <int> ans;
for (int i = 1; i <= n; i++) {
int u = sgt2.id[1];
ans.emplace_back(u);
sgt2.upd(1, 1, m, l[u], make_pair(inf, 0));
auto it = curL.find(make_pair(l[u], u));
curL.erase(it);
it = curR.find(make_pair(r[u], u));
curR.erase(it);
auto L = rest.lower_bound(l[u]);
auto R = L;
for (auto it = L; *it <= r[u]; it++, R = it) {
if (it == rest.end()) break;
int p = *it;
bit.add(p, -b[p]);
auto itL = curR.lower_bound(make_pair(p, 0));
int nl = itL -> se;
nl = l[nl];
auto itR = curL.upper_bound(make_pair(p, n + 1));
itR--;
int nr = itR -> fi;
sgt2.mdf(1, 1, m, nl, nr, -b[p]);
}
rest.erase(L, R);
auto itR = curL.upper_bound(make_pair(l[u], 0));
auto itL = itR;
itL--;
int l1 = itL -> fi, r1 = r[itL -> se];
int l2 = itR -> fi, r2 = r[itR -> se];
int lst = l1;
while (true) {
int id = sgt1.qry(1, 1, m, lst + 1, l2 - 1).se;
if (!id) break;
int nl = l[id], nr = r[id];
if (nr >= r2) break;
int val = bit.qry(nl, nr);
sgt2.upd(1, 1, m, nl, make_pair(val, id));
curL.insert(make_pair(nl, id));
curR.insert(make_pair(nr, id));
s[nl].erase(make_pair(nr, id));
if (!s[nl].empty()) sgt1.upd(1, 1, m, nl, *s[nl].begin());
else sgt1.upd(1, 1, m, nl, make_pair(inf, 0));
lst = nl;
}
}
for (auto x : ans) cout << x << " ";
// cerr << 1e3 * clock() / CLOCKS_PER_SEC << "ms\n";
return 0;
}
/*
4
3 7
10 14
1 6
6 11
*/
K. Fake Plastic Trees 2
给定一棵 \(n\) 个点的树，点编号从 \(1\) 到 \(n\) 。每个点有一个非负权值 \(a_i\)。你需要把树上的一些边删掉，并保证删掉之后，每个连通块的权值之和在区间 \([L,R]\) 中。
给定非负整数 \(K\)，对于每个 \(0≤i≤K\)，判断能否恰好删去 \(i\) 条边。
\(1 \leq n \le 1000\)，\(0 \le K \le 50\)，\(0 \le L \le R \le 10^{15}\)，\(0 \le a_i \le 10^{15}\)。
考虑一个暴力 DP：设 \(dp_{x,i,w}\) 表示在 \(x\) 子树内断掉 \(i\) 条边，且现在 \(x\) 所在的连通块的权值之和为 \(w\)，是否可行。用树形背包容易得到一个 \(\mathcal{O}(nKR^2)\) 的做法。
注意到 \(i\) 固定时除了 \(x\) 所在的连通块以外的连通块的权值之和都在 \([L,R]\) 中，这只有 \(R−L+1\) 种。而 \(x\) 子树内的权值和固定，所以 \(w\) 只有 \(\mathcal{O}(K(R−L))\) 种取值。这样容易得到一个 \(\mathcal{O}(nK^3(R−L)^2)\) 的做法。使用 \(\tt{bitset}\) 维护可以做到 \(\mathcal{O}(nK^3(R-L)^2 / \omega)\)。
想要进一步优化则需要发型一些更好的性质。
引理 \(1\)：如果 \(dp_{x,i,w_1}=dp_{x,i,w_2}=dp_{x,i,w_3}=1\)，且 \(w_1<w_2<w_3\) ，且 \(w_3−w_1≤R−L\)，那么将 \(dp_{x,i,w_2}\) 置为 \(0\) 也不会改变最终答案。
证明：设 \(x\) 所在连通块最终的权值为 \(W\) 。考虑如果使用了 \((x,i,w_2)\) 这个组合，那么把它换成 \((x,i,w_1)\) 或 \((x,i,w_3)\)，则可以获得 \(W−(w_2−w_1)\) 或 \(W+(w_3−w_2)\)。由于 \(w_3−w_1≤R−L\)，这两者也必然有至少一个是合法的，所以总是可以不考虑 \((x,i,w_2)\) 这个组合。
由引理 \(1\)，在 \(w\) 的 \(\mathcal{O}(K(R−L))\) 种取值中，只需要保留 \(\mathcal{O}(K)\) 个为 \(1\) 的位置。所以时间复杂度为 \(O(nK^3)\)。
code
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
constexpr int N = 1e3 + 5, K = 55;
bool Mbe;
int n, k; LL L, R, a[N];
vector <int> e[N];
vector <LL> f[N][K], g[K];
int sz[N];
bool chk(LL x) {
return L <= x && x <= R;
}
void dfs(int u, int ff) {
sz[u] = 1;
for (int i = 0; i <= k; i++) f[u][i].clear();
f[u][0].emplace_back(a[u]);
for (auto v : e[u]) {
if (v == ff) continue;
dfs(v, u);
for (int i = 0; i <= k; i++) g[i].clear();
for (int i = 0; i <= min(sz[u] - 1, k); i++)
for (int j = 0; j <= min(sz[v] - 1, k - i); j++)
for (LL p : f[u][i]) {
bool ok = false;
for (LL q : f[v][j]) {
if (p + q <= R) g[i + j].emplace_back(p + q);
if (chk(q)) ok = 1;
}
if (ok && i + j + 1 <= k) g[i + j + 1].emplace_back(p);
}
sz[u] += sz[v];
for (int i = 0; i <= min(sz[u] - 1, k); i++) {
sort(g[i].begin(), g[i].end());
f[u][i].clear();
int c = 0;
for (LL v : g[i]) {
while (c > 1 && v - f[u][i][c - 2] < R - L) c--, f[u][i].pop_back();
f[u][i].emplace_back(v);
c++;
}
}
}
}
void solve() {
cin >> n >> k >> L >> R;
for (int i = 1; i <= n; i++) cin >> a[i], e[i].clear();
for (int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
e[u].emplace_back(v);
e[v].emplace_back(u);
}
dfs(1, 0);
for (int i = 0; i <= k; i++) {
bool ok = false;
for (LL j : f[1][i]) ok |= chk(j);
if (ok) cout << "1";
else cout << "0";
}
cout << "\n";
}
bool Med;
int main() {
// fprintf(stderr, "%.9lf\n", 1.0 * (&Mbe - &Med) / 1048576.0);
ios :: sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t; cin >> t;
while (t--) solve();
// cerr << 1e3 * clock() / CLOCKS_PER_SEC << "ms\n";
return 0;
}
/*
3
4 3 1 2
1 1 1 1
1 2
2 3
3 4
4 3 1 2
1 1 1 1
1 2
1 3
1 4
4 3 0 0
1 1 1 1
1 2
1 3
1 4
*/
L. Curly Racetrack
你是一个水管工。有一个 \(n \times m\) 的长方形网格，每一个格子的水管可以为以下这几种类型之一：
注意上述水管可以旋转。我们称第四种蓝色高亮标识的水管为高级的。如果一个局面中每个位置都放置了如上六种水管之一，并且所有水管都连起来了（每条水管接口都与相邻的水管相连），那么就称这个局面是合法的。注意不能朝向边界外。
目前有一些格子中放置了高级水管，你能在若干个其他格子中放置一些高级水管。在此之后，另一个水管工会尝试在剩余未被放置水管的格子中放置水管，使得最终变成一个合法的局面。注意你和你的同伴不能旋转那些提前放置的水管。此外，对某些格子，你不能够在其中放入高级水管，并且对另外某些格子，你必须要在其中放入一种高级水管。
你需要求出在你放完高级水管之后最多有多少个格子中为高级水管，并使得你的同伴能完成工作。无解输出 \(\tt{-1}\)。
\(1 \le n,m \le 100\)。
给每条边赋一个状态，表示有没有水管通过这条边相连。考虑一个高级水管即为要求一个格子中相对的两条边状态不同。题目即为给定一些边的状态，给定一些格子能否或者必须为好格子，求最多有几个格子为好格子。
注意到行和列几乎独立，对于一行竖着的边，如果相邻两个有要求的边奇偶性不对，即不能满足中间的格子均为好格子，则说明中间的格子中至少一个为坏格子。对于列类似。
进一步发现，我们仅有形如这样的限制。即，如果我们选择一些格子不一定为好格子，使得上述要求（即一行或一列中某些格子至少一个被选择）均被满足，那么一定能够构造出一种方案使得其他格子均为好格子。
这样就可以建立一个二分图，左侧点为所有行限制，右侧点为所有列限制，对于两个相交的限制，如果交点所在格子可以被选择为坏格子，那么在两个限制间连一条边。问题变成选择最少的边，使得每个点周围的边中都至少一个被选择了。即为最小边覆盖，跑 \(\tt{dinic}\) 求最大流即可。
一年前在模拟赛碰到过这题，所以代码是一年前的。
code
/*
最黯淡的一个 梦最为炽热
万千孤单焰火 让这虚构灵魂鲜活
至少在这一刻 热爱不问为何
存在为将心声响彻
*/
#include <bits/stdc++.h>
#define pii pair<int, int>
#define mp(x, y) make_pair(x, y)
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define int long long
#define mem(x, v) memset(x, v, sizeof(x))
#define mcpy(x, y, n) memcpy(x, y, sizeof(int) * (n))
#define lob lower_bound
#define upb upper_bound
using namespace std;
inline int read() {
int x = 0, w = 1;char ch = getchar();
while (ch > '9' || ch < '0') { if (ch == '-')w = -1;ch = getchar(); }
while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
return x * w;
}
const int MN = 1e2 + 5;
const int Mod = 998244353;
const int inf = 1e9;
inline int qPow(int a, int b = Mod - 2, int ret = 1) {
while (b) {
if (b & 1) ret = ret * a % Mod;
a = a * a % Mod, b >>= 1;
}
return ret;
}
// #define dbg
int N, M, cnt, S, T, c[MN], idL[MN][MN], idR[MN][MN];
char a[MN][MN];
vector <int> L, R;
namespace Dinic {
const int MN = 2e4 + 5, MM = 1e5 + 5;
int N, S, T, mxf;
int fr[MN], cur[MN], v[MN], f[MN], nxt[MN], tot;
int q[MN], hd, tl, d[MN];
inline void add(int x, int y, int z) {
v[++tot] = y, f[tot] = z, nxt[tot] = fr[x], fr[x] = tot;
v[++tot] = x, f[tot] = 0, nxt[tot] = fr[y], fr[y] = tot;
}
inline bool BFS() {
for (int i = 1; i <= N; i++) d[i] = 0;
hd = tl = 0, q[tl++] = S, d[S] = 1;
while (hd != tl) {
int x = q[hd++];
for (int i = fr[x]; i; i = nxt[i]) {
int y = v[i], z = f[i];
if (d[y] || !z) continue;
d[y] = d[x] + 1, q[tl++] = y;
if (y == T) return true;
}
}
return false;
}
inline int DFS(int x, int now) {
if (x == T) return now;
int rest = now;
for (int &i = cur[x]; i; i = nxt[i]) {
int y = v[i], z = f[i];
if (d[y] != d[x] + 1 || !z) continue;
int k = DFS(y, min(z, rest));
if (!k) d[y] = 0;
else f[i] -= k, f[i ^ 1] += k, rest -= k;
if (!rest) break;
}
return now - rest;
}
inline void work() {
while (BFS()) {
for (int i = 1; i <= N; i++) cur[i] = fr[i];
int cur;
while (cur = DFS(S, inf)) mxf += cur;
}
}
inline void init(int _N, int _S, int _T) {
N = _N, S = _S, T = _T, mxf = 0, tot = 1;
for (int i = 1; i <= N; i++) fr[i] = 0;
}
}
signed main(void) {
N = read(), M = read();
for (int i = 1; i <= N; i++) scanf("%s", a[i] + 1);
int fl = 1;
auto chk = [&](int x, int k) {
if (c[x] == -1) c[x] = k;
else if (c[x] != k) fl = 0;
};
for (int i = 1; i <= N; i++) {
mem(c, -1);
c[0] = c[M] = 0;
for (int j = 1; j <= M; j++) {
if (a[i][j] == '1' || a[i][j] == '2') {
chk(j - 1, 1), chk(j, 0);
}
if (a[i][j] == '3' || a[i][j] == '4') {
chk(j - 1, 0), chk(j, 1);
}
}
for (int j = 0, k = 1; j < M; j = k++) {
while (!~c[k]) k++;
if (((j - k) & 1) == (c[j] ^ c[k])) continue;
int o = 0;
for (int p = j + 1; p <= k; p++) if (a[i][p] == 'x') o = 1;
if (o) continue;
++cnt, L.pb(cnt);
for (int p = j + 1; p <= k; p++) {
idL[i][p] = cnt;
if (a[i][p] == '.') o = 1;
}
if (!o) fl = 0;
}
}
for (int i = 1; i <= M; i++) {
mem(c, -1);
c[0] = c[N] = 0;
for (int j = 1; j <= N; j++) {
if (a[j][i] == '1' || a[j][i] == '3') {
chk(j - 1, 1), chk(j, 0);
}
if (a[j][i] == '2' || a[j][i] == '4') {
chk(j - 1, 0), chk(j, 1);
}
}
for (int j = 0, k = 1; j < N; j = k++) {
while (!~c[k]) k++;
if (((j - k) & 1) == (c[j] ^ c[k])) continue;
int o = 0;
for (int p = j + 1; p <= k; p++) if (a[p][i] == 'x') o = 1;
if (o) continue;
++cnt, R.pb(cnt);
for (int p = j + 1; p <= k; p++) {
idR[p][i] = cnt;
if (a[p][i] == '.') o = 1;
}
if (!o) fl = 0;
}
}
if (!fl) return puts("-1"), 0;
S = cnt + 1, T = S + 1, Dinic :: init(T, S, T);
for (int o : L) Dinic :: add(S, o, 1);
for (int o : R) Dinic :: add(o, T, 1);
int ans = N * M;
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++) {
if (a[i][j] == 'x') ans--;
else if (a[i][j] == '.' && idL[i][j] && idR[i][j]) Dinic :: add(idL[i][j], idR[i][j], 1);
}
}
Dinic :: work(), ans -= cnt - Dinic :: mxf;
printf("%lld\n", ans);
return 0;
}