ABC359(A-G)
A - Count Takahashi¶
题目大意
给你 \(N\) 个字符串，求出有多少个字符串等于 Takahashi。
参考代码
#include <iostream>
using namespace std;
int main()
{
int n, ans = 0;
cin >> n;
string s;
while(n--)
{
cin >> s;
if(s == "Takahashi")
ans++;
}
cout << ans << endl;
return 0;
}
B - Couples¶
题目大意
有 \(2N\) 个人站成一行，每个人身上都穿着一件颜色为 \(A_i\) 的衣服，一共有 \(N\) 种颜色的衣服，每种颜色都恰好有两个人穿。
对于 \(i = 1, 2, \cdots, N\)，统计满足以下条件的 \(i\) 的数量：
- 穿着颜色为 \(i\) 衣服的两个人中间恰好只有一个其他人。
参考代码
#include <iostream>
#include <vector>
using namespace std;
int main()
{
int n;
cin >> n;
vector<vector<int>> col(n + 1);
for (int i = 0, x; i < 2 * n; i++)
{
cin >> x;
col[x].push_back(i);
}
int ans = 0;
for (int i = 1; i <= n; i++)
if (abs(col[i][0] - col[i][1]) == 2)
ans++;
cout << ans << endl;
return 0;
}
C - Tile Distance 2¶
题目大意
在二维平面上铺满了很多 \(2 \times 1\) 的瓷砖，如下图所示。
瓷砖放置的规则是：设某个 \(1 \times 1\) 方格的左下角坐标为 \((x, y)\)，如果 \(x + y\) 是偶数，则 \((x, y)\) 是 \(2 \times 1\) 瓷砖的左下角。否则，\((x, y)\) 是 \(2 \times 1\) 瓷砖的左下角再往右 \(1\) 单位的位置。
你的初始坐标是 \((S_x + 0.5, S_y + 0.5)\)，目的地是 \((T_x + 0.5, T_y + 0.5)\)，你可以移动无数次，每一次移动时，从上下左右选择一个方向，朝着这个方向移动 \(1\) 单位的距离。在同一个瓷砖中的移动不需要支付费用，进入另一个瓷砖需要支付 \(1\) 的费用，问：移动到目的地最少需要花费多少费用？
解题思路
观察样例 1 的过程：
可以发现在移动过程对于 \(x\) 轴坐标差应该优先利用 \(2 \times 1\) 瓷砖的特性进行移动，这样是不需要支付花费的。因此，先将位置移动到和目标位置相同的 \(x\) 坐标，假设我们向左（右）移动了 \(a\) 步，相应的 \(y\) 坐标也向上（下）移动了 \(a\) 步。剩下的 \(y\) 坐标差就只能一直向上（下）移动了。
实际写的时候要分类讨论一下，好在并不复杂。
参考代码
#include <iostream>
using namespace std;
int main()
{
using LL = long long;
LL sx, sy, tx, ty;
cin >> sx >> sy >> tx >> ty;
if (sx == tx)
cout << abs(sy - ty);
else if (sx > tx)
{
if ((sx + sy) % 2 == 1)
sx--;
if ((tx + ty) % 2 == 1)
tx--;
LL dx = abs(tx - sx), dy = abs(ty - sy);
if (dx <= dy)
cout << dy << endl;
else
{
dx -= dy;
cout << dy + dx / 2 << endl;
}
}
else
{
if ((sx + sy) % 2 == 0)
sx++;
if ((tx + ty) % 2 == 0)
tx++;
LL dx = abs(tx - sx), dy = abs(ty - sy);
if (dx <= dy)
cout << dy << endl;
else
{
dx -= dy;
cout << dy + dx / 2 << endl;
}
}
return 0;
}
D - Avoid K Palindrome¶
题目大意
给你一个长度为 \(N(2 \le N \le 1000)\) 的字符串 \(S\)，\(S\) 由 A，B 和 ? 三种字符组成。其中 ? 字符需要替换成 A 或 B，假设有 \(q\) 个 ? 字符，则替换后一共有 \(2^q\) 种可能的字符串。问：在这 \(2^q\) 种字符串中，有多少字符串满足 不存在 长度为 \(K(2 \le K \le 10)\) 的回文子串？答案对 \(998244353\) 取模。
解题思路
考虑到 \(K \le 10\)，我们可以状态压缩，将 A 看作 \(0\)，B 看作 1。
定义 \(dp[i][s]\) 表示在前 \(i\) 个字符中，不包含长度为 \(K\) 的回文子串，且最后 \(K\) 位的字符状态为 \(s\) 的子串数量。
首先处理出初始状态，可以单独取出字符串的前 \(K\) 位，跑一遍 \(2^K\) 的枚举，枚举出来的字符串的数量就是 \(dp[k][s] = 1\)。
接下来从第 \(K+1\) 位开始转移，假设 \(K = 4\)，\(s = 1010\)，显然只有当 \(S_i\) 是 ? 或者 A 才可以转移到这个状态（因为最后一位必须是 \(0\)），那么 \(s = 1010\) 有可能从上一轮的 \(0101\) 或者 \(1101\) 转移过来，因此我们有 \(dp[i][1010] = dp[i-1][0101] + dp[i-1][1101]\)。
当然，有一些回文子串的状态是应该排除的，我们可以预先将 \(2^K\) 个状态中的回文子串除，在 dp 的时候就不会访问到不合法的状态了。
参考代码
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int mod = 998244353;
int main()
{
int n, k;
string s;
cin >> n >> k;
cin >> s;
int len = 1 << k;
vector<int> v[2];
vector<bool> is_palindrome(len);
for (int st = 0; st < len; st++)
{
auto check = [k](int st) -> bool
{
for (int i = 0, j = k-1; i < j; i++, j--)
{
int x = st >> i & 1, y = st >> j & 1;
if (x != y)
return false;
}
return true;
};
is_palindrome[st] = check(st);
if (!is_palindrome[st])
v[st & 1].push_back(st);
}
vector<int> dp[2] = {vector<int>(len), vector<int>(len)};
vector<int> &pre = dp[0], now = dp[1];
auto dfs = [&s, &now, &k, &is_palindrome](auto &&self, int cur, int st) -> void
{
if (cur == k)
{
if (!is_palindrome[st])
now[st] = 1;
return;
}
if (s[cur] == 'A')
self(self, cur + 1, st << 1);
else if (s[cur] == 'B')
self(self, cur + 1, st << 1 | 1);
else
{
self(self, cur + 1, st << 1);
self(self, cur + 1, st << 1 | 1);
}
};
dfs(dfs, 0, 0);
for (int i = k; i < n; i++)
{
swap(now, pre);
fill(now.begin(), now.end(), 0);
if (s[i] != 'B')
for (auto st : v[0])
now[st] = (pre[st >> 1] + pre[1 << (k - 1) | st >> 1]) % mod;
if (s[i] != 'A')
for (auto st : v[1])
now[st] = (pre[st >> 1] + pre[1 << (k - 1) | st >> 1]) % mod;
}
int ans = 0;
if (s[n - 1] != 'B')
for (auto st : v[0])
ans = (ans + now[st]) % mod;
if (s[n - 1] != 'A')
for (auto st : v[1])
ans = (ans + now[st]) % mod;
cout << ans << endl;
return 0;
}
E - Water Tank¶
题目大意
有 \(N+1\) 个水槽被 \(N(1 \le N \le 2 \times 10 ^5)\) 个木板挡住，其中第 \(i\) 个木板的高度是 \(H_i(1 \le H_i \le 10^9)\)。用 \(A_i\) 表示第 \(i\) 个水槽当前有高度为 \(A_i\) 的水，初始的时候，所有的水槽都没有水，即 \(A_0 = A_1 = \cdots = A_N = 0\)。
重复的执行以下操作：
- 给 \(A_0\) 的值加 \(1\)。
- 接下来，按照 \(i = 1, 2, \cdots, N\) 的顺序，执行以下操作：
- 如果 \(A_{i-1} > A_i\) 且 \(A_i > H\)，则 \(A_{i-1}\) 的值减 \(1\)，\(A_i\) 的值加 \(1\)。
问：对于水槽 \(i = 1, 2, \cdots, N\)，需要经过至少多少次操作才能让 \(A_i > 0\)？
解题思路
观察样例：
可以发现，上图中最后一次操作之后水槽 \(1\) 和 \(2\) 高度一样，已经合并起来了。之后我们继续推演：
- 要想给 \(3\) 号水槽注水，前提是让 \(2\) 号水槽的高度到达 \(4\)。
- 要想让 \(2\) 号水槽有水，由于 \(1\) 和 \(2\) 已经合并，所以必须同时给这两个水槽加水。
- 当 \(1\) 和 \(2\) 水槽高度到达 \(3\)，此时高度和 \(0\) 号水槽一样高，再次合并，这意味着后续的注水操作是 \(0-2\) 水槽同时进行的。
- 当 \(0-2\) 号水槽高度到达 \(4\)，此时下一次注水就会进入 \(3\) 号水槽。
- \(\cdots\cdots\)
因此，我们可以通过这种合并水槽的操作同时给多个水槽注水。每一次注水的目标是到达左边界或者右边界的高度，如果到达左边界的高度，则与左边界的水槽合并，如果到达右边界，则表示下一个水槽的答案已经计算出来。
显然这种合并的操作可以用并查集维护，并查集可以增加一个大小的信息。不过更好的做法是，规定并查集代表点为编号较小的水槽，这样只需要用编号相减就能得到当前合并了多少个水槽。
参考代码
#include <iostream>
using namespace std;
using LL = long long;
const int maxn = 2E5 + 10;
int p[maxn], a[maxn], h[maxn];
int find(int x)
{
return x == p[x] ? x : p[x] = find(p[x]);
}
// 要求 u > v
int merge(int u, int v)
{
u = find(u);
v = find(v);
p[u] = v;
return v;
}
int main()
{
int n;
cin >> n;
h[0] = 2E9;
for (int i = 1; i <= n; i++)
{
cin >> h[i];
p[i] = i;
}
LL t = 0;
for (int i = 1; i <= n; i++)
{
int left = find(i-1);
int len = i - 1 - left + 1;
while (a[left] < h[i])
{
if(h[left] < h[i])
{
LL d = h[left] - a[left];
t += d * len;
left = merge(left, left-1);
len = i - 1 - left + 1;
}
else
{
LL d = h[i] - a[left];
t += d * len;
a[left] = h[i];
}
}
cout << t + 1 << ' ';
}
return 0;
}
F - Tree Degree Optimization¶
题目大意
给你一个长度为 \(N(2 \times 10^5)\) 的序列 \(A = (A_1, A_2, \cdots, A_N)\)。对于一棵有 \(N\) 个节点的树 \(T\)，设 \(d_i\) 表示点 \(i\) 的度数。
定义 \(f(T) = \sum\limits_{i = 1}^Nd_i^2A_i\)。
问：对于给定的 \(N\) 和序列 \(A\)，最小的 \(f(T)\) 是多少？
解题思路
一棵树合法的度序列 \(d = (d_1, d_2, \cdots, d_N)\) 需要满足以下条件：
现在我们要最小化 \(f(T) = \sum\limits_{i = 1}^Nd_i^2A_i\)，从第一个限制条件看很容易想到一个类似背包的 \(O(N^2)\) dp，但其实完全没必要这样。
只需要简简单单来一个贪心：首先，所有点的度数设置成 \(1\)，接下来还有 \(N-2\) 的度数没有使用，考虑每一个点增加度数所带来的代价，选择一个最小的代价就可以了。把下一度的代价存放到堆里即可，时间复杂度 \(O(NlogN)\)
参考代码
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
using LL = long long;
LL sq(LL x) {return x * x;}
struct Node
{
LL x, a, d;
bool operator > (const Node &other) const {return d > other.d;}
};
int main()
{
int n;
cin >> n;
LL ans = 0;
priority_queue<Node, vector<Node>, greater<Node>> heap;
for(int i = 0; i < n; i++)
{
Node t;
cin >> t.a;
ans += t.a;
t.x = 1;
t.d = 3 * t.a;
heap.push(t);
}
n -= 2;
while(n--)
{
Node t = heap.top();
heap.pop();
ans += t.d;
t.x++;
t.d = (sq(t.x + 1) - sq(t.x)) * t.a;
heap.push(t);
}
cout << ans << endl;
return 0;
}
G - Sum of Tree Distance¶
题目大意
给你一个棵 \(N(2 \le N \le 2 \times 10 ^ 5)\) 个节点的树，树上每个节点都有一个颜色，第 \(i\) 个节点的颜色是 \(A_i\)。
对于树上的两个节点 \(i\) 和 \(j\) ，定义 \(f(i, j)\) 如下：
- 如果 \(A_i \neq A_j\)，则 \(f(i, j) = 0\)
- 否则，\(f(i, j)\) 表示点 \(i\) 到点 \(j\) 的距离。
求出 \(\sum\limits_{i = 1}^{N-1}\sum\limits_{j = i+1}^{N} f(i, j)\) 的值。
解题思路
本题的正解是使用点分治和虚树。。不过效率稍微慢一点的做法是分块。
我们设置一个阈值 \(B\)，根据同种颜色的数量是否大于 \(B\)，执行两种算法：
-
小于 \(B\)
由于数量较少，直接两两枚举求出 \(f(i, j)\)，而求出树上两点的距离需要求出 \(lca(i, j)\)，如果使用倍增或者树剖这种在线算法的话，算一下时间复杂度：首先，单次 \(lca(i, j)\) 需要 \(O(logN)\)，一种颜色至多有 \(B\) 个点，也就是 \(B^2\) 对点，而至多有 \(\frac{N}{B}\) 组颜色，那么时间复杂度就是 \(BNlogN\)，代入 \(B = sqrt(N)\)，则 \(O(N\sqrt{N}logN) \approx 1.6 \times 10^9\)，非常极限的计算量，要极限卡常才能过去。
于是我们不得不优化计算 \(lca(i, j)\) 的效率，无外乎就是几种方法：
- 使用 tarjan 算法离线处理所有 \(lca(i, j)\) 请求，这个算法预处理的时间是线性的，但麻烦，之前学 lca 的时候写过，非常复杂。
- 将 lca 转化成 RMQ 问题，也就是将序列变成欧拉序，然后用 ST 表预处理出静态区间的最值，需要花费 \(O(NlogN)\) 的时间进行预处理，然后每一次查询都是 \(O(1)\) 的，最终的时间复杂度就是 \(O(NlogN + N\sqrt{N}) \approx 10^8\)
- ps：还存在一种 \(O(N)\) 时间预处理 RMQ 的 Four russian 算法，但由于瓶颈不在预处理的时间，所以实际效率差别不大。
因此，最终选择的是第二种算法。
-
大于等于 \(B\)
先考虑极端的情况，也就是所有点都是同一种颜色，那么我们需要求出一棵 \(N\) 个节点的树中两两节点的距离之和。实际上这可以通过一遍 dfs 实现，在 dfs 中我们统计每个点的子树大小，接下来对于节点 \(u\) 的子节点 \(v\)，在回溯时，我们知道了子节点 \(v\) 的子树大小（记为 \(son[v]\)），考虑连边 \((u, v)\) 对答案的贡献，这条连边的一侧是 \(v\) 及其子树的所有节点，有 \(son[v]\) 个，另一侧是其他所有节点 \(N - son[v]\)，对于这两侧的节点想要到达对方都需要经过这条边，一共会经过这条边 \(son[v](N-son[v])\) 次。dfs 结束后所有的边都被计入贡献，于是答案就统计出来了，一次统计的时间复杂度为 \(O(N)\)
考虑另一种极端的情况，即每种颜色点的数量都等于 \(B\)，这样的颜色至多有 \(\frac{N}{B}\) 组，也就是 \(O(\frac{N^2}{B} = N\sqrt{N})\)。
综上，选取 \(B = sqrt(N)\)，总的时间复杂度为 \(O(NlogN + N\sqrt{N}) = O(N\sqrt{N})\)
参考代码
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
using LL = long long;
const int maxn = 2E5 + 10;
const int maxm = 2 * maxn;
const int maxp = 20;
int n;
int head[maxn], edge[maxm], ne[maxm], idx = 1;
void add(int u, int v)
{
edge[idx] = v;
ne[idx] = head[u];
head[u] = idx++;
}
int fir[maxn], ord[maxm], dep[maxn], ti = 0;
void dfs(int u)
{
fir[u] = ++ti;
ord[ti] = u;
for (int i = head[u]; i; i = ne[i])
{
int v = edge[i];
if (fir[v])
continue;
dep[v] = dep[u] + 1;
dfs(v);
ord[++ti] = u;
}
}
int st[maxm][maxp], lg[maxm];
void build_st()
{
lg[0] = -1;
for (int i = 1; i <= ti; i++)
{
st[i][0] = ord[i];
lg[i] = lg[i >> 1] + 1;
}
for (int i = 1; i <= ti; i++)
st[i][0] = ord[i];
for (int k = 1; k <= lg[ti]; k++)
{
int len = 1 << k;
int half = len >> 1;
for (int i = 1; i + len - 1 <= ti; i++)
{
int x = st[i][k - 1], y = st[i + half][k - 1];
st[i][k] = dep[x] < dep[y] ? x : y;
}
}
}
int lca(int u, int v)
{
u = fir[u];
v = fir[v];
if (u > v)
swap(u, v);
int k = lg[v - u + 1];
int len = 1 << k;
int x = st[u][k], y = st[v - len + 1][k];
return dep[x] < dep[y] ? x : y;
}
int distance(int u, int v)
{
int c = lca(u, v);
return dep[u] + dep[v] - 2 * dep[c];
}
int color[maxn];
LL ans = 0;
vector<int> col_set[maxn];
LL dp(int u, int fa, const int col, const int total)
{
LL son = color[u] == col;
for (int i = head[u]; i; i = ne[i])
{
int v = edge[i];
if (v == fa)
continue;
LL sv = dp(v, u, col, total);
son += sv;
ans += sv * (total - sv);
}
return son;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
for (int i = 1, u, v; i < n; i++)
{
cin >> u >> v;
add(u, v);
add(v, u);
}
dfs(1);
build_st();
for (int u = 1; u <= n; u++)
{
cin >> color[u];
col_set[color[u]].push_back(u);
}
int B = sqrt(n);
for (int col = 1; col <= n; col++)
{
const vector<int> &v = col_set[col];
int total = v.size();
if (total <= B)
{
for (int i = 0; i < total; i++)
for (int j = i + 1; j < total; j++)
ans += distance(v[i], v[j]);
}
else
dp(v[0], 0, col, total);
}
cout << ans << endl;
return 0;
}
创建日期: 2024-07-13