AtCoder Beginner Contest 359
A - Count Takahashi (abc359 A)
题目大意
给定\(n\)个字符串，问有多少个字符串是Takahashi
解题思路
注意判断比较即可。
神奇的代码
#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;
while (n--) {
string s;
cin >> s;
ans += s == "Takahashi";
}
cout << ans << '\n';
return 0;
}
B - Couples (abc359 B)
题目大意
给定\(n\)个数字，问有多少个数字，其左右两个数字相同。
解题思路
枚举中间的数字，然后判断其左右俩数字是否相同即可。
神奇的代码
#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;
n *= 2;
vector<int> a(n);
for (auto& x : a)
cin >> x;
int ans = 0;
for (int i = 1; i < n - 1; ++i) {
ans += a[i - 1] == a[i + 1];
}
cout << ans << '\n';
return 0;
}
C - Tile Distance 2 (abc359 C)
题目大意
给定一个坐标系，有格子，如下：
给定起点和终点，问从起点到终点，要穿过多少次蓝线。
解题思路
观察上述格子，可以发现在\(y\)轴移动，每移动一次，必定穿过一次蓝线。
由于每行格子交错排列的，每往上走一个，我左右可走的区间都扩大了\(1\)。比如我在\((5,0)\)，我可以左边往上走到\((3,1) \to (5,1)\)的格子，也可以右边往上走到\((5,1) \to (7,1)\)。
这样，原本我左右走的横坐标区间是\([4,6)\)，往上走一格后，横坐标区间扩大为\([3,7)\)，往上走\(n\)格，可到达的横坐标区间范围为\([4-n, 6+n)\)，只要我终点的横坐标在这区间，那我就可以只花费\(y\)轴移动的代价就抵达终点了。而如果不在这个区间，那就再左右移动，每移动一次，横坐标区间就变动\(2\)。
容易发现这样移动一定是最优的。\(y\)轴移动的蓝线穿过不可避免，然后\(x\)轴的蓝线穿过已经尽可能在移动\(y\)轴时避免了。
神奇的代码
#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);
LL sx, sy, tx, ty;
cin >> sx >> sy >> tx >> ty;
LL dy = abs(sy - ty);
LL odd = (sx & 1);
LL l = sx - odd + (sy & 1) * (odd ? 1 : -1);
LL r = l + 2;
l -= dy, r += dy;
LL ans = dy + max(0ll, l - tx + 1) / 2 + max(0ll, tx - r + 2) / 2;
cout << ans << '\n';
return 0;
}
D - Avoid K Palindrome (abc359 D)
题目大意
给定一个包含AB?的字符串\(s\)，将?变成A或B，问有多少种情况，使得\(s\)没有长度为\(k\)的回文子串。
解题思路
注意\(k \leq 10\)
从左到右考虑每个字符，如果当前是?，则考虑其变为A,B，是否出现长度为\(k\)的回文串。
我们需要知道该?前\(k-1\)位的情况，加上该字母，就可以判断出新增的子串是不是回文串。
即设\(dp[i][j]\)表示考虑前\(i\)位字符，其中?都已经替换成A或B后，且后\(9\)位的字符状态为\(j\)(因为只有AB两种，可以编码成01，用二进制压缩表示)。
然后考虑当前位的情况，如果取值为A即\(0\)，则判断\(j << 1\)状态是不是回文串，不是的话则有\(dp[i+1][(j<<1) \& mask] += dp[i][j]\)，否则就状态非法，不转移。因为\(j<<1\)是后\(10\)个字符的状态信息，而\(j\)的含义是后\(9\)位，所以\(\& mask\)是把第\(10\)位去掉。
同理，取值为\(B\)的话，即\(1\)，则判断\((j << 1) | 1\)是不是回文串，不是的话就转移，否则不转移。
可以事先预处理每个状态是否是回文串，然后当\(i \geq k\)时再考虑转移的合法性。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int mo = 998244353;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, k;
string s;
cin >> n >> k >> s;
int up = (1 << k);
vector<int> p(up);
for (int i = 0; i < up; i++) {
vector<int> bit(k);
int num = i;
for (int j = 0; j < k; j++) {
bit[j] = (num & 1);
num >>= 1;
}
auto rev = bit;
reverse(rev.begin(), rev.end());
p[i] = rev == bit;
}
up = 1 << (k - 1);
int mask = up - 1;
vector<int> dp(up, 0);
dp[0] = 1;
for (int i = 0; i < n; ++i) {
int chr = s[i];
vector<int> dp2(up, 0);
for (int j = 0; j < up; j++) {
if (chr == '?') {
if (i + 1 < k || !p[j << 1]) {
int nxt = (j << 1) & mask;
dp2[nxt] = (dp2[nxt] + dp[j]) % mo;
}
if (i + 1 < k || !p[j << 1 | 1]) {
int nxt = (j << 1 | 1) & mask;
dp2[nxt] = (dp2[nxt] + dp[j]) % mo;
}
} else {
if (i + 1 < k || !p[j << 1 | (chr - 'A')]) {
int nxt = (j << 1 | (chr - 'A')) & mask;
dp2[nxt] = (dp2[nxt] + dp[j]) % mo;
}
}
}
dp.swap(dp2);
}
LL ans = 0;
for (int i = 0; i < up; i++) {
ans = (ans + dp[i]) % mo;
}
cout << ans << '\n';
return 0;
}
E - Water Tank (abc359 E)
题目大意
给定柱子长度。然后如下如所示。
每一时刻，\(0\)位会多一高度的水，如果该水高度高过柱子，且高过\(1\)位的水高度，则该高度的水会跑到\(1\)位，同理继续判断\(1\)位，该水是否跑到\(2\)位。
问每一位出现水的最早时刻。
解题思路
-
考虑\(1\)位，其答案就是第一根柱子高度\(3(a_1)+1\)
-
考虑\(2\)位，需要\(0\)位水高\(3\)，\(1\)位水高\(1\)，答案就是\(3+1+1\)
-
考虑\(3\)位，则需要\(0,1,2\)的水高均为\(4\)，答案就是\(4+4+4+1\)
-
考虑\(4\)位，则需要\(0,1,2\)水高\(4\)，\(3\)位水高\(1\)，答案就是\(4+4+4+1+1\)
-
考虑\(5\)位，则需要\(0,1,2,3,4,\)位水高\(5\)，答案就是\(5+5+5+5+5+1\)。
观察上述例子的求解过程，如果要求第\(i\)位的答案，则要求第\(i-1\)位装满，装满的意思就是和柱子\(a_i\)高度同高，而同高会连带着\(i-2,i-3,...\)位同高，但需要多少位呢？观察上述会发现，假设前面比柱子\(a_i\)还高的柱子是\(a_j\)，那么\(j,j+1,...,i-1\)位的水高都必须是\(a_i\)。
因此，求解第\(i\)位的答案，则需要\(i-1,i-2,...,j\)位与\(a_i\)同高，然后\(j-1,j-2,...,k\)与\(a_j\)同高，然后\(k-1,k-2,...\)与\(a_k\)同高，其中\(a_i \leq a_j \leq a_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<int> h(n + 1);
for (int i = 1; i <= n; ++i)
cin >> h[i];
h[0] = 1e9 + 8;
vector<int> hei;
hei.push_back(0);
LL ans = 0;
for (int i = 1; i <= n; ++i) {
while (!hei.empty() && h[hei.back()] <= h[i]) {
ans -= h[hei.back()] * (LL)(hei.back() - hei[hei.size() - 2]);
hei.pop_back();
}
ans += h[i] * (LL)(i - hei.back());
hei.push_back(i);
cout << ans + 1 << " \n"[i == n];
}
return 0;
}
F - Tree Degree Optimization (abc359 F)
题目大意
给定\(n\)个点的点权\(a_i\)，构造一棵树，使得\(\sum_{i=1}^{n} d_i^2a_i\)最小，其中\(d_i\)表示点\(i\)的度。
解题思路
由于是一棵树，则有\(\sum d_i = 2n-2, 1 \leq d_i \leq n - 1\)。
对于任意满足上述条件的\(d_i\)，都可以构造出对应的树，使得每个点的度数都是\(d_i\)。（构造方法为，每次选择度数为1和非1的点连边，然后更新剩余度数，归纳可证）
那剩下就是如何分配这些度数。
如果给点\(1\)分配一个度，是其\(d_1 = 1 \to 2\)，则代价是\(4a_1 - a_1\)，而如果是\(d_1 = 2 \to 3\)，则代价是\(9a_1 - 4a_1\)。
这可以把问题抽象成每个点起始度数为\(1\)，然后把剩下的\(n-2\)个度分配给每个点，使得代价最小，每次仅分配\(1\)的度，那我肯定是贪心的分配给代价最小的点。
用优先队列维护上述代价即可。
神奇的代码
#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& x : a)
cin >> x;
priority_queue<pair<LL, int>, vector<pair<LL, int>>, greater<pair<LL, int>>>
q;
LL ans = accumulate(a.begin(), a.end(), 0ll);
for (int i = 0; i < n; i++) {
q.push({a[i] * 3ll, 2});
}
for (int i = 0; i < n - 2; i++) {
auto [x, y] = q.top();
q.pop();
ans += x;
if (y < n - 1) {
LL ori = x / (2 * y - 1);
LL nxt = ori * (2 * y + 1);
q.push({nxt, y + 1});
}
}
cout << ans << '\n';
return 0;
}
G - Sum of Tree Distance (abc359 G)
题目大意
给定一棵树，点有点权\(a_i\)。求\(\sum_i \sum_j f(i,j)\)，其中\(a_i == a_j\)。\(f(i,j)\)表示点\(i \to j\)的距离，边权为\(1\)。
解题思路
距离的最终来源是边数，考虑每条边被算入了多少次，即对答案贡献的次数。
即\(\sum_i \sum_j f(i,j) = \sum_e sum_e\)，其中\(sum_e\)表示边\(e\)对答案贡献的次数，考虑该次数怎么算。
考虑边\((u,v)\)，将该树分成了两个连通块，如果这两个连通块各有一点\(i,j\)，其\(a_i == a_j\)，那么从点\(i \to j\)必定经过该边，因此需要统计每个点权，在两个连通块的出现次数，其乘积的和则是该边的贡献。
问题就变成了统计一个子树里，各个点权的出现次数\(cc_i\)，事先预处理每个点权的出现次数\(cnt_i\)，对点权求和，即\(\sum cc_i \times (cnt_i - cc_i)\)就是该边对答案的贡献。
由于点权是稀疏的，用map来维护出现次数，合并儿子之间的map，采用启发式合并，即用数量少的合并到数量大的，这样每次合并最坏的复杂度是\(O(\frac{n}{2})\)，而最坏的情况最多只有\(O(\log n)\)次（每一次最坏情况，合并后的点数会翻倍，最多翻倍\(O(\log n)\)次。
合并的时候，计算边贡献的式子，\(\sum cc_i \times (cnt_i - cc_i)\)只有一项发生变化，可以动态\(O(1)\)维护出更新后的贡献\(sum\)。
最终的时间复杂度就是\(O(n \log^2 n)\)，一个\(\log\)是启发式合并，另一个\(\log\)是map。
代码里的\(sum\)是考虑父亲边\(u \to fa\)对答案的贡献。由于返回类型是\(pair\)，用\(map\)构造\(pair\)会复制构造造成巨大的性能损失，用\(move\)函数进行移动构造。或者返回值仅为\(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;
vector<vector<int>> edge(n);
for (int i = 0; i < n - 1; i++) {
int u, v;
cin >> u >> v;
u--;
v--;
edge[u].push_back(v);
edge[v].push_back(u);
}
vector<int> a(n);
vector<int> cnt(n);
for (auto& x : a) {
cin >> x;
--x;
cnt[x]++;
}
LL ans = 0;
auto dfs = [&](auto& dfs, int u, int fa) -> pair<map<int, int>, LL> {
map<int, int> cc;
LL sum = 0;
for (auto v : edge[u]) {
if (v == fa)
continue;
auto&& [son_ret, son_sum] = dfs(dfs, v, u);
if (son_ret.size() > cc.size()) {
swap(son_ret, cc);
swap(son_sum, sum);
}
for (auto& [k, v] : son_ret) {
sum -= 1ll * cc[k] * (cnt[k] - cc[k]);
cc[k] += v;
sum += 1ll * cc[k] * (cnt[k] - cc[k]);
}
}
sum -= 1ll * cc[a[u]] * (cnt[a[u]] - cc[a[u]]);
cc[a[u]]++;
sum += 1ll * cc[a[u]] * (cnt[a[u]] - cc[a[u]]);
ans += sum;
return {move(cc), sum};
};
dfs(dfs, 0, 0);
cout << ans << '\n';
return 0;
}