A - ストーブ (Stove)
有 \(n\) 个客人将要来访，第 \(i\) 个客人的来访时间为 \([a_i, a_i + 1]\)，保证 \(\forall i \in [1, n), a_i < a_{i + 1}\)。
在每个客人来访时，你都需要保证暖炉是亮着的（初始时暖炉为熄灭状态）。你可以在任意时刻熄灭暖炉，但每次点亮都需要消耗一根火柴，且你只有 \(k\) 根火柴，求最小的暖炉点亮时间。
\(n \le 10^5, a_i \le 10^9\)。
首先使用一根火柴点亮初始时刻的暖炉，接下来你有 \(k - 1\) 次熄灭暖炉的机会。
考虑在第 \(i\) 个人到第 \(i + 1\) 个人的时间间隙中熄灭暖炉的收益为 \(a_{i + 1} - a_i - 1\)，将这个收益排序并取前 \(k\) 大即可。时间复杂度 \(O(n \log n)\)。
Code
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 5;
int n, k;
int a[N], b[N];
int main () {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> k;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
}
for (int i = 1; i < n; ++i) {
b[i] = a[i + 1] - a[i] - 1;
}
int ans = a[n] - a[1] + 1;
sort(b + 1, b + n, greater<int>());
for (int i = 1; i < k; ++i) {
ans -= b[i];
}
cout << ans << '\n';
return 0;
}
B - 美術展 (Art Exhibition)
有 \(n\) 件美术品，每件美术品有尺寸 \(A_i\) 与价值 \(B_i\)，现在要选择若干美术品作为展览，设选择的美术品集合为 \(S\)，最大化 \(\sum\limits_{i \in S} B_i - (\max\limits_{i \in S} A_i - \min\limits_{i \in S} A_i)\)、
\(1 \le n \le 5 \times 10^5, 1 \le A_i \le 10^{15}, 1 \le B_i \le 10^9\)。
首先将所有美术品按照 \(A_i\) 排序，由于所有美术品价值为正，多选一定更优，所以选择的美术品是一段区间。
对 \(B\) 做前缀和。设选择的区间为 \([l, r]\)，则价值为 \(B_r - B_{l - 1} - A_r + A_l\)。考虑设一个左端点 \(l\) 的权值为 \(A_l - B_{l - 1}\)，设一个右端点 \(r\) 的权值为 \(B_r - A_r\)，线性扫一遍即可。时间复杂度 \(O(n \log n)\)。
Code
#include <iostream>
#include <algorithm>
using namespace std;
using LL = long long;
using Pii = pair<LL, LL>;
const int N = 5e5 + 5;
int n;
Pii a[N];
int main () {
cin.tie(0)->sync_with_stdio(0);
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> a[i].first >> a[i].second;
}
sort(a + 1, a + n + 1);
for (int i = 1; i <= n; ++i) {
a[i].second += a[i - 1].second;
}
LL mxl = 0, ans = 0;
for (int i = 1; i <= n; ++i) {
mxl = max(mxl, a[i].first - a[i - 1].second);
ans = max(ans, mxl + a[i].second - a[i].first);
}
cout << ans << '\n';
return 0;
}
C - 団子職人 (Dango Maker)
有一个 \(n \times m\) 的网格，每个团子被放在一个格子里，每个团子的颜色是
R,G, 'W' 中的一种。
现在你可以从上到下，或从左到右选一个 \(1 \times 3\) 的矩形，并将其中的团子按顺序做成一个团子串，要求三个团子的颜色必须依次是R,G,W。
求最大的可以制作的团子数。
\(1 \le n, m \le 3 \times 10^3\)。
对于所有团子，考虑在 G 处计算贡献，那么两个团子如果冲突，则它们一定在同一条从左上到右下的对角线上。
所以我们对于每个对角线独立地 \(\text{dp}\)。考虑当前某个对角线的一个格子，设 \(f_0\) 为该团子不做团子串的方案数，\(f_1\) 表示该团子横着串的方案数，\(f_2\) 表示该团子竖着串的方案数。则 \(f_1\) 和 \(f_2\) 之间不能相互转移。
时间复杂度 \(O(nm)\)。
Code
#include <iostream>
using namespace std;
const int N = 3e3 + 5;
int n, m, f[3], g[3];
char s[N][N];
int main () {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> m;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
cin >> s[i][j];
}
}
int ans = 0;
for (int sum = 2; sum <= n + m; ++sum) {
f[0] = 0, f[1] = f[2] = -N;
for (int i = max(1, sum - m), j = sum - i; i <= n && j; ++i, --j) {
copy(f, f + 3, g);
fill(f, f + 3, -N);
f[0] = max(max(g[0], g[1]), g[2]);
if (s[i][j] == 'G' && s[i - 1][j] == 'R' && s[i + 1][j] == 'W') {
f[1] = max(g[0], g[1]) + 1;
}
if (s[i][j] == 'G' && s[i][j - 1] == 'R' && s[i][j + 1] == 'W') {
f[2] = max(g[0], g[2]) + 1;
}
}
ans += max(max(f[0], f[1]), f[2]);
}
cout << ans << '\n';
return 0;
}
D - 定期券 (Commuter Pass)
给定一张 \(n\) 个结点 \(m\) 条边的无向图，边有边权。
现在你可以选择一条 \(s\) 到 \(t\) 的最短路，并将这条路径上的边的权值全部设为 \(1\)，求操作后 \(u\) 到 \(v\) 最短路的最小值。
\(1 \le n \le 10^5, 1 \le m \le 2 \times 10^5\)。
首先考虑如何刻画“\(s\) 到 \(t\) 的最短路”，我们从 \(s\) 开始跑一遍 \(\text{Dijkstra}\)，求出 \(d_i\) 表示 \(s\) 到 \(i\) 的最短路，对于原图上的无向边拆成两条有向边，如果一条有向边 \((u, v)\) 不满足 \(d_v = d_u + w(u, v)\)，则将其从图中删去。那么我们将得到一张 \(\text{DAG}\)，此时在新图上每一条 \(s\) 到 \(t\) 的路径都是最短路。
然后我们发现答案要么不经过修改权值的边，此时就是 \(dis(u, v)\)，要么形如 \(u \rightarrow a \rightarrow b \rightarrow v\)，其中 \(a\) 和 \(b\) 在 \(s\) 到 \(t\) 的一条最短路上。则此时答案为 \(dis(u, a) + dis(v, b)\) 或 \(dis(u, b) + dis(v, a)\)。
考虑在 \(\text{DAG}\) 上 \(\text{dp}\)，设 \(r_i\) 表示 \(i\) 是否能到 \(t\)，\(f_{i, 0}\) 表示 \(i\) 能到达的，且满足 \(r_x = 1\) 的点中最小的 \(dis(v, x)\)，\(f_{i, 1}\) 类似，直接 \(\text{dp}\) 即可。对于所有 \(i\)，\(dis(s, i), dis(t, i)\) 可以 \(\text{Dijkstra}\) 预处理。
时间复杂度 \(O(n \log n)\)。
Code
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
using LL = long long;
using Pii = pair<LL, LL>;
const int N = 1e5 + 5;
const LL Inf = 1e18;
int n, m, gs, gt, s, t, deg[N];
vector<Pii> e[N];
vector<int> g[N];
LL dis[3][N], f[N][2];
bool r[N];
void Dijkstra (int st, LL *dis) {
priority_queue<Pii, vector<Pii>, greater<Pii>> q;
q.push({0, st});
fill(dis + 1, dis + n + 1, Inf);
while (!q.empty()) {
Pii tp = q.top();
q.pop();
LL d = tp.first;
int u = tp.second;
if (d < dis[u]) {
dis[u] = d;
for (auto i : e[u]) {
int v = i.first, w = i.second;
q.push({d + w, v});
}
}
}
}
int main () {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> m >> gs >> gt >> s >> t;
for (int i = 1, u, v, w; i <= m; ++i) {
cin >> u >> v >> w;
e[u].push_back({v, w});
e[v].push_back({u, w});
}
Dijkstra(s, dis[0]), Dijkstra(t, dis[1]), Dijkstra(gs, dis[2]);
for (int i = 1; i <= n; ++i) {
for (auto j : e[i]) {
if (dis[2][j.first] == dis[2][i] + j.second) {
g[j.first].push_back(i), ++deg[i];
}
}
}
queue<int> q;
for (int i = 1; i <= n; ++i) {
if (!deg[i]) {
q.push(i);
}
}
fill(f[1], f[n] + 2, Inf);
LL ans = dis[0][t];
for (; !q.empty(); q.pop()) {
int u = q.front();
if (u == gt) {
r[u] = 1;
}
if (r[u]) {
f[u][0] = min(f[u][0], dis[1][u]);
f[u][1] = min(f[u][1], dis[0][u]);
ans = min(ans, min(dis[0][u] + f[u][0], dis[1][u] + f[u][1]));
}
for (auto v : g[u]) {
if (r[u]) {
f[v][0] = min(f[v][0], f[u][0]);
f[v][1] = min(f[v][1], f[u][1]);
r[v] = 1;
}
if (!--deg[v]) {
q.push(v);
}
}
}
cout << ans << '\n';
return 0;
}
E - 毒蛇の脱走 (Snake Escaping)
给定 \(n\)，对于一个长度为 \(n\) 的二进制数 \(x\)，定义其权值为 \(a_x\)。接下来进行 \(q\) 次询问，每次询问格式如下：
- 给定一个长度为 \(n\) 字符串 \(s\)，\(s\) 中的每个字符是 \(\texttt{0, 1, ?}\) 三者之一，对于所有将
?填写成0或1的方案组成的数字，求它们的权值和，此处允许前导 \(\texttt{0}\)。\(1 \le n \le 20, 1 \le q \le 10^6\)。
记 \(s_0, s_1, s_2\) 分别为 \(\texttt{0, 1, ?}\) 在 \(s\) 中的出现位置，\(cnt_0 = |s_0|, cnt_1 = |s_1|, cnt_2 = |s_2|\) 分别为这三种字符在原串中的出现次数。
考虑类似根号分治，因为 \(cnt_0 + cnt_1 + cnt_2 \le 20\)，所以 \(\min(cnt_0, cnt_1, cnt_2) \le 6\)。我们 \(\forall i \in [0, 2]\)，对于 \(cnt_i \le 6\) 的情况分别处理。
对于 \(cnt_2 \le 6\)
由于 \(\texttt{?}\) 不超过 \(6\) 个，所以我们枚举每个 \(\texttt{?}\) 填什么，对于所有可能的方案求和即可。
时间复杂度 \(O(2^{cnt_2})\)。
对于 \(cnt_0 \le 6\)
考虑只有 \(\texttt{1}\) 和 \(\texttt{?}\) 时怎么做，我们将 \(\text{?}\) 看成 \(\texttt{0}\)，那么所有方案的权值和相当于高维后缀和。具体地，设 \(f_s = \sum\limits_{t \supseteq s} a_t\)，则一个转化后的集合 \(s\) 权值和为 \(f_s\)。
现在加入 \(\texttt{0}\)，由于 \(\texttt{0}\) 的个数很少，所以我们对 \(\texttt{0}\) 容斥，它可以看作 \(\texttt{?}\) 的方案数减去 \(\texttt{1}\) 的方案数，所以我们枚举每个 \(\texttt{0}\) 是变成 \(\texttt{1}\) 还是 \(\texttt{?}\)，得到答案为
\[ \sum\limits_{t \subseteq s_0} f_{s_1 \cup t} (-1)^{|t|} \]时间复杂度 \(O(2^{cnt_0})\)
对于 \(cnt_1 \le 6\)
类似地考虑只有 \(\texttt{1}\) 和 \(\texttt{?}\) 的情况，我们将 \(\texttt{?}\) 看成 \(\texttt{1}\)，设 \(g_s = \sum\limits_{t \subseteq s} a_t\)，则一个转化后的集合 \(s\) 权值和为 \(g_{A - s}\)，其中 \(A\) 为全集。
还是类似地将 \(\texttt{1}\) 容斥为 \(\texttt{?}\) 的方案减去 \(\texttt{0}\) 的方案，枚举每个 \(\texttt{1}\) 变 \(\texttt{0}\) 还是变 \(\texttt{?}\)，可得答案为
\[ \sum\limits_{t \subseteq s_1} g_{A - (s_0 \cup t)}(-1)^{|t|} \]时间复杂度 \(O(2^{cnt_1})\)。
最后 \(f, g\) 分别相当于高维后、前缀和，直接上 \(\text{And-FWT}\) 和 \(\text{Or-FWT}\) 即可。
总时间复杂度 \(O(2^nn + q 2^{\lfloor \frac{n}{3} \rfloor})\)。
Code
#include <iostream>
using namespace std;
const int N = 20, S = (1 << N);
int n, q, all;
int a[S], f[S], g[S];
void FWT_And (int *a) {
for (int k = 1; k <= all; k <<= 1) {
for (int i = 0; i <= all; i += (k << 1)) {
for (int j = 0; j < k; ++j) {
a[i + j] += a[i + j + k];
}
}
}
}
void FWT_Or (int *a) {
for (int k = 1; k <= all; k <<= 1) {
for (int i = 0; i <= all; i += (k << 1)) {
for (int j = 0; j < k; ++j) {
a[i + j + k] += a[i + j];
}
}
}
}
int main () {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> q, all = (1 << n) - 1;
for (int s = 0; s <= all; ++s) {
char c;
cin >> c;
a[s] = f[s] = g[s] = c - '0';
}
FWT_And(f), FWT_Or(g);
for (string str; q--; ) {
cin >> str;
int s[3] = {0, 0, 0}, cnt[3];
for (int i = 0; i < n; ++i) {
if (str[i] == '0')
s[0] |= (1 << (n - i - 1));
else if (str[i] == '1')
s[1] |= (1 << (n - i - 1));
else if (str[i] == '?')
s[2] |= (1 << (n - i - 1));
}
for (int i = 0; i < 3; ++i) {
cnt[i] = __builtin_popcount(s[i]);
}
if (cnt[2] <= 6) {
int ans = 0;
for (int t = s[2]; ; t = (t - 1) & s[2]) {
ans += a[t | s[1]];
if (!t) break;
}
cout << ans << '\n';
}
else if (cnt[0] <= 6) {
int ans = 0;
for (int t = s[0]; ; t = (t - 1) & s[0]) {
ans += f[t | s[1]] * (__builtin_popcount(t) & 1 ? -1 : 1);
if (!t) break;
}
cout << ans << '\n';
}
else if (cnt[1] <= 6) {
int ans = 0;
for (int t = s[1]; ; t = (t - 1) & s[1]) {
ans += g[(t | s[0]) ^ all] * (__builtin_popcount(t) & 1 ? -1 : 1);
if (!t) break;
}
cout << ans << '\n';
}
}
return 0;
}