A
代码
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
bool solve() {
int n, m;
cin >> n >> m;
ll suma = 0, sumb = 0;
for (int i = 1, x;i <= n;i++) cin >> x, suma += x;
for (int i = 1, x;i <= m;i++) cin >> x, sumb += x;
if (suma > sumb) cout << "Tsondu" << '\n';
else if (suma < sumb) cout << "Tenzing" << '\n';
else cout << "Draw" << '\n';
return true;
}
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--) {
if (!solve()) cout << -1 << '\n';
}
return 0;
}
B
代码
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
bool solve() {
int n, x;
cin >> n >> x;
int sum = 0;
for (int i = 0;i < 3;i++) {
bool ok = 1;
for (int j = 1;j <= n;j++) {
int val;
cin >> val;
ok &= (x | val) == x;
if (ok) sum |= val;
}
}
if (sum == x) cout << "YES" << '\n';
else cout << "NO" << '\n';
return true;
}
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--) {
if (!solve()) cout << -1 << '\n';
}
return 0;
}
C
题目
给定一个长为 \(n\) 的数组 \(a\) ，其中元素 \(a_i \in[1,n]\) 代表颜色。
现在有一种操作：选择两个颜色相同的不同位置 \(i,j\) ，然后删除 \([i,j]\) 这一段，删除操作会影响下标。
问最多能删除多少元素。
题解
知识点：线性dp。
设 \(f_{i}\) 表示 \([1,i]\) 最多能删除的元素个数，有转移方程：
\[f_i = \max\limits_{j:a_j = a_i} \{ f_{j-1} + i-j+1 \} \]我们要优化这个转移，实际上我们只需要维护 \(\max\limits_{j:a_j = a_i} \{ f_{j-1} -j+1 \}\) 即可。
设 \(mx_j\) 表示在 \([1,i-1]\) 中颜色为 \(j\) 的所有位置 \(f_{j-1}-j+1\) 的最大值，每次求完 \(f_i\) 更新 \(mx_{a_i}\) 即可。
时间复杂度 \(O(n)\)
空间复杂度 \(O(n)\)
代码
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int a[200007];
int mx[200007];
int f[200007];
bool solve() {
int n;
cin >> n;
for (int i = 1;i <= n;i++) cin >> a[i], mx[i] = -1e9;
for (int i = 1;i <= n;i++) {
f[i] = max(f[i - 1], mx[a[i]] + i);
mx[a[i]] = max(mx[a[i]], f[i - 1] - i + 1);
}
cout << f[n] << '\n';
return true;
}
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--) {
if (!solve()) cout << -1 << '\n';
}
return 0;
}
D
题目
有 \(n\) 个朋友，编号为 \(1\) 到 \(n\) ，我们需要和他们玩最多 \(n^2\) 轮游戏，每轮游戏需要选择其中的一些人一起玩，并选择要玩多久，要求是：
- \(1\) 号朋友必须被选中。
- \(n\) 号朋友不能被选中。
- 所有人玩的时间需要遵守 \(m\) 条约束。
一条约束描述为三个整数 \(u,v,y\) ，表示朋友 \(u\) 或朋友 \(v\) 单独被选中玩的时间的总和不能超过 \(y\) 。
问在如此约束下，最多能玩多久，构造一个满足的方案，并给出这个方案要玩几轮，以及每轮游戏选中了哪些人玩了多久。
题解
知识点：差分约束，构造。
由于 \(n\) 一定不会被选中，而 \(1\) 必须被选中。因此我们考虑将点分成两个集合：
- 集合 \(A\) 表示能和 \(1\) 一起玩的。
- 集合 \(B\) 表示不能和 \(1\) 一起玩的。
初始时，集合 \(B\) 只有 \(n\) ，剩下的都在集合 \(A\) 。
显然，集合 \(A\) 的朋友是可以一起玩的，但玩到一定时间会因为和 \(n\) 的约束，有一些朋友就不能继续玩了，于是从集合 \(A\) 中移出放入集合 \(B\) ，剩下的继续玩。这个过程会逐步将朋友从 \(A\) 移到 \(B\) 。
实际上，我们考虑每个朋友 \(u\) 移入 \(B\) 的时间 \(T_u\) ，那么对于任意两个有约束的朋友 \(u,v\) 需要满足 \(|T_u -T_v| \leq y\) 。对于这个问题，我们将朋友看作点，约束看作带权无向边，那么就构造了一个差分约束系统，用最短路即可解决，起点是 \(n\) 。
我们在最短路过程中， \(dis_u\) 即为 \(T_u\) 。点一旦被确定距离，意味着这个时刻将点移出 \(A\) ，一旦 \(1\) 被确定就立刻结束。我们需要记录点被移出 \(A\) 的顺序，顺序上相邻的两个点的距离差，就是这轮还未被放进集合 \(B\) 的点玩的时间。
时间复杂度 \(O((n+m)\log m)\)
空间复杂度 \(O(n+m)\)
代码
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
vector<pair<int, int>> g[107];
int n, m;
ll dis[107];
bool vis[107];
struct node {
int v;
ll w;
friend bool operator<(const node &a, const node &b) { return a.w > b.w; }
};
priority_queue<node> pq;
vector<int> ord;
void dijkstra() {
for (int i = 1;i <= n;i++) dis[i] = 2e18, vis[i] = 0;
dis[n] = 0;
pq.push({ n,0 });
while (!pq.empty()) {
int u = pq.top().v;
pq.pop();
if (vis[u]) continue;
ord.push_back(u);
vis[u] = 1;
if (vis[1]) break;
for (auto [v, w] : g[u]) {
if (vis[v]) continue;
if (dis[u] + w < dis[v]) {
dis[v] = dis[u] + w;
pq.push({ v,dis[v] });
}
}
}
}
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n >> m;
for (int i = 1;i <= m;i++) {
int u, v, w;
cin >> u >> v >> w;
g[u].push_back({ v,w });
g[v].push_back({ u,w });
}
dijkstra();
if (!vis[1]) {
cout << "inf" << '\n';
return 0;
}
cout << dis[1] << ' ' << ord.size() - 1 << '\n';
for (int i = 1;i < ord.size();i++) {
string s(n, '1');
for (int j = 0;j < i;j++) s[ord[j] - 1] = '0';
cout << s << ' ' << dis[ord[i]] - dis[ord[i - 1]] << '\n';
}
return 0;
}
E
题目
给定 \(k\) ，确定了平面直角坐标系中一条直线 \(x+y = k\) 。
给出 \(n\) 个点 \((x_i,y_i)\) ，满足坐标是整数且 \(0 \leq x_i,y_i,x_i+y_i <k\) ，每个点有一个权值 \(c_i\) 。
现在有两个操作：
- 删除一个点，花费其权值。
- 选择一个整数坐标位置 \((a,b)\) ，画出等腰直角三角形 \(x=a,y=b,x+y=k\) ，设其直角边长是 \(l\) ，以及一个常数 \(A\) ，那么删除这个等腰直角三角形内所有点，花费 \(lA\) 。
问删掉所有点最少花费是多少。
题解
知识点：线性dp，线段树。
容易发现，我们选择删除的三角形区域最终是不相交的，否则可以合并。同时，三角形可以通过其左上角和右下角的纵坐标唯一确定，那么一个三角形就可以映射到纵坐标上的一个线段。现在，问题就变成在纵坐标上选择一些不相交的线段，使得线段对应的三角形位置删除、其他位置单点删除后，花费最小。这是一个类似最小多个子段和的问题，因此我们可以从上到下dp解决。
为了方便，我们先将 \(y\) 坐标处理为 \(k-y\) ，这样点的坐标就从 \(0 \sim k-1\) 映射到 \(k\sim 1\) 。
设 \(f_{i}\) 表示删除纵坐标 \(\leq i\) 的点的最小花费，那么有转移方程：
\[f_i = \min\left\{ iA,f_{i-1} + \sum_{j:y_j = i}c_j ,\min\limits_{1 \leq j \leq i-1} \left\{ f_{j} + \sum_{k:\substack{0 \leq x_k \leq j-1\\ j+1 \leq y_k\leq i}}c_k + (i-j)A \right\}\right\} \]其中：
-
第一项表示，从 \(i\) 行往上都用一个三角形删除。
-
第二项表示，第 \(i\) 行全都单点删除。
-
第三项表示，从 \(i\) 行往上到 \(j+1\) 行用一个三角形删除，从 \(j\) 行往上不变。
但这导致了，坐标满足 \(0 \leq x \leq j-1, j+1 \leq y\leq i\) 的点没有考虑到，而这些点不可能被三角形覆盖，因此全都选择单点删除的花费。
考虑优化第三项。我们用线段树维护 \(j \in[1,i-1]\) 的
\[f_{j} + \sum_{k:\substack{0 \leq x_k \leq j-1\\ j+1 \leq y_k\leq i}}c_k - jA \]最小值。其中，求和项可以每层区间加递推。因为区间 \([1,i-1]\) 可能是导致 \([1,0]\) 不合法区间，取默认值为 \(0\) 即可，此时第三项结果为 \(iA\) ，不会产生错误答案。
每次最后我们需要将 \(f_[i]-iA\) 加到线段树位置 \(i\) 上。
最后，答案即为 \(f[k]\) 。
当然，为了避免不合法区间的出现，可以选择将第二项放到线段树的位置 \(i\) 上，最后更新的时候取 \(f[i]\) 和线段树位置 \(i\) 的最小值更新即可。实际上，线段树也能维护整个第三项，默认值设为无穷大即可，但更新的时候会有点麻烦，要把新的值覆盖无穷大的值。
这两个实现虽然不会产生不合法的区间，但区间加实现常数会大一点，可以选择专门写一个函数操作。
另一个类似的思路：假设都用单点删除，去dp将一部分改为三角形删除的贡献改变量的最小值（是负的），最后用单点删除的总和加上这个最小值即可。
时间复杂度 \(O((n+k) \log k)\)
空间复杂度 \(O(n+k)\)
代码
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template<class T, class F>
class SegmentTreeLazy {
int n;
vector<T> node;
vector<F> lazy;
void push_down(int rt) {
node[rt << 1] = lazy[rt](node[rt << 1]);
lazy[rt << 1] = lazy[rt](lazy[rt << 1]);
node[rt << 1 | 1] = lazy[rt](node[rt << 1 | 1]);
lazy[rt << 1 | 1] = lazy[rt](lazy[rt << 1 | 1]);
lazy[rt] = F();
}
void update(int rt, int l, int r, int x, int y, F f) {
if (r < x || y < l) return;
if (x <= l && r <= y) return node[rt] = f(node[rt]), lazy[rt] = f(lazy[rt]), void();
push_down(rt);
int mid = l + r >> 1;
update(rt << 1, l, mid, x, y, f);
update(rt << 1 | 1, mid + 1, r, x, y, f);
node[rt] = node[rt << 1] + node[rt << 1 | 1];
}
T query(int rt, int l, int r, int x, int y) {
if (r < x || y < l) return T();
if (x <= l && r <= y) return node[rt];
push_down(rt);
int mid = l + r >> 1;
return query(rt << 1, l, mid, x, y) + query(rt << 1 | 1, mid + 1, r, x, y);
}
public:
SegmentTreeLazy(int _n = 0) { init(_n); }
SegmentTreeLazy(const vector<T> &src) { init(src); }
void init(int _n) {
n = _n;
node.assign(n << 2, T());
lazy.assign(n << 2, F());
}
void init(const vector<T> &src) {
init(src.size() - 1);
function<void(int, int, int)> build = [&](int rt, int l, int r) {
if (l == r) return node[rt] = src[l], void();
int mid = l + r >> 1;
build(rt << 1, l, mid);
build(rt << 1 | 1, mid + 1, r);
node[rt] = node[rt << 1] + node[rt << 1 | 1];
};
build(1, 1, n);
}
void update(int x, int y, F f) { update(1, 1, n, x, y, f); }
T query(int x, int y) { return query(1, 1, n, x, y); }
};
struct T {
int mi = 0;
friend T operator+(const T &a, const T &b) { return { min(a.mi,b.mi) }; }
};
struct F {
int add = 0;
T operator()(const T &x) { return { x.mi + add }; }
F operator()(const F &g) { return { g.add + add }; }
};
vector<pair<int, int>> pos[200007];
int f[200007];
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n, k, A;
cin >> n >> k >> A;
for (int i = 1;i <= n;i++) {
int x, y, c;
cin >> x >> y >> c;
pos[k - y].push_back({ x,c });
}
SegmentTreeLazy<T, F> sgt(k);
for (int i = 1;i <= k;i++) {
f[i] = f[i - 1];
for (auto [x, c] : pos[i]) sgt.update(x + 1, i - 1, { c }), f[i] += c;
f[i] = min({ f[i],i * A, sgt.query(1, i - 1).mi + i * A });
sgt.update(i, i, { f[i] - i * A });
}
cout << f[k] << '\n';
return 0;
}