AtCoder Beginner Contest 369
A - 369 (abc369 A)
题目大意
给定两个数\(a,b\)，问有多少个整数\(x\)，使得 \(a,b,x\)经过某种排列后成为等差数列，
解题思路
就三种情况：\(xab\)，\(axb\)， \(abx\)，三种情况都求出来，然后放到 set去重即为答案。中间的情况要判断是否是实数。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int a, b;
cin >> a >> b;
if (a > b)
swap(a, b);
set<int> ans{a - (b - a), b + (b - a)};
if ((b - a) % 2 == 0)
ans.insert(a + (b - a) / 2);
cout << ans.size() << '\n';
return 0;
}
B - Piano 3 (abc369 B)
题目大意
谈钢琴，给出左右手依次要弹奏的键，问左右手移动的距离数。
解题思路
模拟即可，用一个map记录左右手当前位置，然后移动到下一个位置时计算距离，累计求和集合。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
int ans = 0;
map<char, int> pos;
while (n--) {
int p;
string s;
cin >> p >> s;
if (pos.find(s[0]) != pos.end()) {
ans += abs(pos[s[0]] - p);
}
pos[s[0]] = p;
}
cout << ans << '\n';
return 0;
}
C - Count Arithmetic Subarrays (abc369 C)
题目大意
给定一个数组\(a\)，问有多少个 \(l,r\)，使得 \(a[l..r]\)是一个等差数列。
解题思路
等差数列即公差相等。从\(a\)的差分数组\(b\)来看， \(a[l..r]\)是等差数列，意味着差分数组的对应区间的数是相等的，那就是说，对于\(a[l..r]\)是等差数列的 \(l,r\)对数，等价于 \(b[i..j]\)是相同数的对数。（特判下\(a[l..r]\)长度是 \(1\)的情况）
那先求 \(a\)的差分数组\(b\)，然后对该差分数组的相同数的区间，比如 \(b[i..j] = c\)，那么对于\(a\)数组符合条件的 \(l,r\) 就有 \(\frac{(j - i + 1)(j - 1)}{2}\)种取法。
对每个这样的区间累计求和即为答案。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
vector<int> a(n);
for (auto& i : a)
cin >> i;
vector<int> l(n);
int la = -1;
int cnt = 0;
LL ans = n;
for (int i = 1; i < n; ++i) {
if (a[i] - a[i - 1] != la) {
ans += 1ll * cnt * (cnt - 1) / 2;
cnt = 2;
la = a[i] - a[i - 1];
} else {
++cnt;
}
}
ans += 1ll * cnt * (cnt - 1) / 2;
cout << ans << '\n';
return 0;
}
D - Bonus EXP (abc369 D)
题目大意
\(n\)个怪兽，你要依次打他们。
对于第 \(i\)只怪兽，要么与它战斗，要么放走他。
如果与它战斗，你会获胜，且会获得 \(x_i\)经验。如果它是你第偶数只打败的怪兽，则还可以额外获得 \(x_i\)经验，即共获得双倍经验。
问获得的经验数的最大值。
解题思路
比较朴素的\(dp\)，很显然对于每只怪兽考虑打或不打，如果选择打，其结果会受到 是否是第偶数只打败这一状态的影响，因此我们的\(dp\)状态，除了包含基本状态 考虑前$i$只怪兽外，还要加上状态打败了奇数/偶数只怪兽这一\(0/1\)状态。
有了这一状态后，就可以写出关于经验的转移式子了。即 \(dp[i][0/1]\)表示考虑前 \(i\)只怪兽，已经打败了偶数只/奇数只怪兽时，获得的最大经验值。
然后考虑第\(i\)只打或不打 ，得到对应的经验值，转移到后续状态即可。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
LL inf = 1e18;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
vector<int> a(n);
for (auto& x : a)
cin >> x;
array<LL, 2> dp = {0, -inf};
for (int i = 0; i < n; i++) {
array<LL, 2> dp2 = {0, 0};
dp2[0] = max(dp[0], dp[1] + a[i] + a[i]);
dp2[1] = max(dp[1], dp[0] + a[i]);
dp2.swap(dp);
}
cout << max(dp[0], dp[1]) << '\n';
return 0;
}
E - Sightseeing Tour (abc369 E)
题目大意
给定一张无向图，边有边权。
回答\(q\)个询问。
每个询问给定 \(k \leq 5\)条边，表示从\(1 \to n\)，必须经过至少一次这些边，的最短路径。
解题思路
这里给的边数很少。
考虑最简单的情况，即\(k=1\)，给的边是\(u,v\)，那么很显然答案就是 \(1 \to u \to v \to n\)或者 \(1 \to v \to u \to n\)， 即考虑从\(1\)节点出发，以最短路先到 \(u\)还是先到 \(v\)。
这里 \(k=5\)，但情况数仍然不多，我们仍然枚举中途经过的点，共有\(O(k! 2^k)\)种情况（枚举遍历边的顺序，对于每条边再枚举访问端点的顺序）， \(k=5\)的话就是 \(3e3\)，情况数不大，有了经过的点之后，剩下的就是以最短路径依次遍历每个点。由于 \(n\leq 400\)，可以事先用 \(floyd\)求出任意两点的距离，然后对于每个询问，花费 \(O(k! 2^k)\)枚举遍历点的顺序，然后用 \(O(2k)\)计算该顺序对应的最短路长度，所有情况取最小即为答案。
总的时间复杂度为\(O(n^3 + q(k! 2^k + k))\)
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const LL inf = 1e18;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, m;
cin >> n >> m;
vector<array<int, 3>> edge(m);
vector<vector<LL>> dis(n, vector<LL>(n, inf));
for (int i = 0; i < n; i++)
dis[i][i] = 0;
for (int i = 0; i < m; i++) {
int u, v, w;
cin >> u >> v >> w;
--u, --v;
dis[u][v] = min(dis[u][v], (LL)w);
dis[v][u] = min(dis[v][u], (LL)w);
edge[i] = {u, v, w};
}
for (int k = 0; k < n; ++k) {
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
}
}
}
int q;
cin >> q;
auto calc = [&](vector<int>& p) -> LL {
LL sum = 0;
int st = 0;
for (int i = 0; i < p.size(); i += 2) {
int u = p[i], v = p[i + 1];
sum += dis[st][u];
st = v;
}
sum += dis[st][n - 1];
return sum;
};
while (q--) {
int k;
cin >> k;
vector<int> b(k);
for (auto& x : b) {
cin >> x;
--x;
}
int up = (1 << k);
LL ans = inf;
do {
for (int i = 0; i < up; ++i) {
vector<int> p;
LL sumb = 0;
for (int j = 0; j < k; ++j) {
auto [u, v, w] = edge[b[j]];
sumb += w;
if ((i >> j) & 1) {
swap(u, v);
}
p.push_back(u);
p.push_back(v);
}
LL sum = calc(p) + sumb;
ans = min(ans, sum);
}
} while (next_permutation(b.begin(), b.end()));
cout << ans << '\n';
}
return 0;
}
F - Gather Coins (abc369 F)
题目大意
\(h\times w\)网格，有些格子有金币。
从左上走到右下，只能向右走和向下走。
问取得金币的最大值。
解题思路
朴素\(dp\)就是 \(dp[i][j] = \max(dp[i - 1][j], dp[i][j - 1]) + (coin[i][j] == 1)\)，但\(h \times w\)可达 \(1e10\)，整不动。但金币数最多只有 \(10^5\)，我们知道 \(dp\)的值只有在有金币的格子才会变动，实际有效的格子只有 \(10^5\)个。我们仅考虑这些格子的 \(dp\)值怎么计算。
考虑 \(dp[i][j]\)表示当前处于有金币的格子 \((i,j)\)时的最大金币数，考虑能够转移到此的状态，即 $dp[i][j] = \max_{x \leq i, y \leq j, coin[i][j]}(dp[x][y]) + 1。
这个转移条件其实就是个二维偏序，因此对金币的位置\((x,y)\)从小到大排序，然后依次枚举这些金币，当考虑到第 \(i\)个金币时， \(j \leq i\)的金币 一定满足\(x_j \leq x_i\)，因此我们只需找到 \(y_j \leq y_i\)的最大的 \(dp[x_j][y_j]\)值即可，这是一个区间最值查询，用线段树维护即可。
即对金币的位置\((x,y)\)从小到大排序，然后依次枚举这些金币，用线段树维护枚举过的金币关于y_j下标的dp最大值。考虑上述的转移条件，在线段树查询时，由于枚举顺序的缘故，天然满足\(x \leq i\)的条件，而线段树的区间查询找到满足 \(y < j\)的 \(\max(dp[x][y])\)，因此上述的二维偏序的最值问题就可以用线段树解决了。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int N = 2e5 + 8;
const int inf = 1e9 + 7;
class segment {
#define lson (root << 1)
#define rson (root << 1 | 1)
public:
int val[N << 2];
int id[N << 2];
void pushup(int root) {
if (val[lson] > val[rson]) {
val[root] = val[lson];
id[root] = id[lson];
} else {
val[root] = val[rson];
id[root] = id[rson];
}
}
void build(int root, int l, int r) {
if (l == r) {
val[root] = -inf;
return;
}
int mid = (l + r) >> 1;
build(lson, l, mid);
build(rson, mid + 1, r);
pushup(root);
}
void update(int root, int l, int r, int pos, int v, int i) {
if (l == r) {
if (val[root] < v) {
val[root] = v;
id[root] = i;
}
return;
}
int mid = (l + r) >> 1;
if (pos <= mid)
update(lson, l, mid, pos, v, i);
else
update(rson, mid + 1, r, pos, v, i);
pushup(root);
}
pair<int, int> query(int root, int l, int r, int L, int R) {
if (L <= l && r <= R) {
return {val[root], id[root]};
}
int mid = (l + r) >> 1;
pair<int, int> resl{}, resr{};
if (L <= mid)
resl = query(lson, l, mid, L, R);
if (R > mid)
resr = query(rson, mid + 1, r, L, R);
return max(resl, resr);
}
} seg;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int h, w, n;
cin >> h >> w >> n;
vector<array<int, 2>> pos(n + 2);
for (int i = 1; i <= n; ++i)
cin >> pos[i][0] >> pos[i][1];
pos[0] = {1, 1};
pos[n + 1] = {h, w};
sort(pos.begin(), pos.end());
seg.build(1, 1, w);
seg.update(1, 1, w, 1, 0, 0);
vector<int> tr(n);
for (int i = 1; i <= n + 1; ++i) {
auto& [x, y] = pos[i];
auto res = seg.query(1, 1, w, 1, y);
int dp = res.first + 1;
tr[i] = res.second;
seg.update(1, 1, w, y, dp, i);
}
auto [ans, p] = seg.query(1, 1, w, w, w);
cout << ans - 1 << '\n';
string op;
while (p != 0) {
auto [x1, y1] = pos[p];
p = tr[p];
auto [x2, y2] = pos[p];
auto dx = abs(x1 - x2);
auto dy = abs(y1 - y2);
if (dx) {
op += string(dx, "UD"[x1 > x2]);
}
if (dy) {
op += string(dy, "LR"[y1 > y2]);
}
}
reverse(op.begin(), op.end());
cout << op << '\n';
return 0;
}
G - As far as possible (abc369 G)
题目大意
给定一棵树，边有边权。
对于\(k=1,2,...,n\)，要求选 \(k\)个点，使得从 \(1\)号点出发，遍历每个点，最终回到 \(1\)号点的距离的最小值最大。
解题思路
如果我给定了\(k\)个点，怎么求这个的最小值呢。
容易发现答案其实就是这 \(k\)个点到根的路径的并的长度的两倍。
当 \(k=1\)时，很显然我们选择距离根最远的点。
然后当 \(k=2\)时，由于先前的选择，会导致一些点对答案的贡献发生了变化——其到根的路径有一部分与之前选择的点到根的路径有交集，那交集的部分不会有额外的贡献。因此当我们选择一个点后，除了一路沿父亲节点更新贡献外，还要更新父亲兄弟节点及其子树的贡献改变。这个贡献改变自然是一棵子树，通过树的\(dfs\) 序来维护这个贡献改变，其实就是一个区间操作，可以用线段树维护，其复杂度只有\(O(\log)\)，而贡献改变会发生多少次呢？一个点最多只会带来一次贡献改变，因此最多区间操作 \(O(n)\)次，因此总的复杂度只有 \(O(n \log n)\)次。
即\(val[i]\)表示\(dfs\)序里的第 \(i\)个节点，如果我选择它，它对答案贡献（增加）了多少。每次我们肯定选择最大的 \(val\)，选择这个 \(val\)后，会使得一些子树内的节点对答案的贡献减少（减去交集路径长度），每个子树内的节点在 \(dfs\)序里面对应了一个区间，因此我们用线段树维护这个 \(val\)数组，每次查询就是个区间最值，每次更新贡献就是个区间操作。
但如果从另一个角度来看，考虑对这棵树进行长链剖分，容易发现答案就是最长的 \(k\)个长链的长度的两倍。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
vector<vector<array<int, 2>>> edge(n);
for (int i = 0; i < n - 1; ++i) {
int u, v, w;
cin >> u >> v >> w;
--u, --v;
edge[u].push_back({v, w});
edge[v].push_back({u, w});
}
vector<int> mxson(n, -1);
vector<LL> deep(n, 0), maxdeep(n, 0);
function<void(int, int)> dfs1 = [&](int u, int fa) {
maxdeep[u] = deep[u];
for (auto [v, w] : edge[u]) {
if (v == fa)
continue;
deep[v] = deep[u] + w;
dfs1(v, u);
maxdeep[u] = max(maxdeep[u], maxdeep[v]);
if (mxson[u] == -1 || maxdeep[mxson[u]] < maxdeep[v]) {
mxson[u] = v;
}
}
};
dfs1(0, -1);
vector<LL> lian;
function<void(int, int, LL)> dfs2 = [&](int u, int fa, LL dis) {
for (auto [v, w] : edge[u]) {
if (v == fa)
continue;
if (v == mxson[u])
dfs2(v, u, dis + w);
else
dfs2(v, u, w);
}
if (mxson[u] == -1) {
lian.push_back(dis);
}
};
dfs2(0, -1, 0);
sort(lian.begin(), lian.end(), greater<LL>());
int up = 0;
LL ans = 0;
for (int i = 0; i < lian.size(); ++i) {
ans += lian[i];
cout << ans * 2 << '\n';
}
for (int i = lian.size(); i < n; ++i) {
cout << ans * 2 << '\n';
}
return 0;
}