ABC362(A-G)
A - Buy a Pen¶
题目大意
有三种颜色的笔，Red 卖 \(R\) 元，Green 卖 \(G\) 元，Blue 卖 \(B\) 元。你不想购买颜色为 \(C\) 的笔，问：买一只笔最小需要多少钱？
参考代码
#include <iostream>
using namespace std;
int main()
{
int r, g, b;
string s;
cin >> r >> g >> b;
cin >> s;
if(s == "Red")
cout << min(g, b) << endl;
else if(s == "Green")
cout << min(r, b) << endl;
else
cout << min(r, g) << endl;
return 0;
}
B - Right Triangle¶
题目大意
平面上有三个点 \(A(x_A, y_A)\)，\(B(x_B, y_B)\) 和 \(C(x_C, y_C)\)，问：这三个点能否构成直角三角形？
参考代码
#include <iostream>
using namespace std;
struct Vector {
int x, y;
Vector(int x1, int y1, int x2, int y2) : x(x1-x2), y(y1-y2) {}
int operator * (const Vector &other) const
{return x * other.x + y * other.y;}
};
int main()
{
int xa, xb, xc, ya, yb, yc;
cin >> xa >> ya >> xb >> yb >> xc >> yc;
Vector ab(xa, ya, xb, yb), ac(xa, ya, xc, yc), bc(xb, yb, xc, yc);
if(ab * ac == 0 || ab * bc == 0 || ac * bc == 0)
cout << "Yes" << endl;
else
cout << "No" << endl;
return 0;
}
C - Sum = 0¶
题目大意
给你 \(N(1 \le N \le 2 \times 10 ^ 5)\) 个区间 \([L_1, R_1], [L_2, R_2], \cdots, [L_N, R_N]\)，判断是否存在 \(N\) 个数的序列 \(X = (X_1, X_2, \cdots, X_N)\) 满足以下条件：
- \(L_i \le X_i \le R_i\)
- \(\sum\limits_{i = 1} ^ N X_i = 0\)
如果存在这样的序列则输出，否则输出 No
解题思路
把所有区间的上界和下界加起来，如果 \(\sum\limits_{i = 1} ^ N L_i \le 0 \le \sum\limits_{i = 1} ^ N R_i\) 说明有解，下面考虑如何构造答案。
预处理一个后缀和 \(SL_i = SL_{i+1} + L_i\)，\(SR_i = SR_{i+1} + R_i\)，同时用 \(sum\) 表示当前已经构造出来的 \(X_i\) 的和。
考虑一种解的方案：当某个 \(X_i\) 存在多个可以凑成 \(0\) 的解时，选最小的一个，因此，遵循以下规则构造解：
- 如果 \(SL_i + sum \le 0 \le SR_i + sum\)，此时令 \(X_i = L_i\) 即可。
- 否则，我们需要让 \(SL_{i+1} + sum + X_i \le 0 \le SR_{i+1} + sum + X_i\)，解得 \(-SR_{i+1} - sum \le X_i \le -SL_{i+1} - sum\)，选择最小的解，令 \(X_i = -SR_{i+1} - sum\) 即可。
参考代码
#include <iostream>
#include <vector>
using namespace std;
using LL = long long;
int main()
{
int n;
cin >> n;
vector<LL> L(n), R(n);
for(int i = 0; i < n; i++)
cin >> L[i] >> R[i];
vector<LL> SL(n), SR(n);
SL[n-1] = L[n-1];
SR[n-1] = R[n-1];
for(int i = n - 2; i >= 0; i--)
{
SL[i] = SL[i+1] + L[i];
SR[i] = SR[i+1] + R[i];
}
if(SL[0] > 0 || SR[0] < 0)
{
cout << "No" << endl;
return 0;
}
cout << "Yes" << endl;
LL sum = 0;
for(int i = 0; i < n - 1; i++)
{
if(SL[i+1] + sum + L[i] <= 0 && 0 <= SR[i + 1] + sum + L[i])
{
cout << L[i] << ' ';
sum += L[i];
}
else
{
LL x = -sum - SR[i+1];
cout << x << ' ';
sum += x;
}
}
cout << -sum << endl;
return 0;
}
D - Shortest Path 3¶
题目大意
给你一个无向图，图中有点权和边权，定义一条路径的距离为路径上所有点权和边权的和。求点 \(1\) 到所有其他点的最短路、
参考代码
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
using LL = long long;
const int maxn = 2E5 + 10;
const int maxm = maxn * 2;
int head[maxn], edge[maxm], ne[maxm], cost[maxm], A[maxn], idx = 1;
void add(int u, int v, int w)
{
edge[idx] = v;
ne[idx] = head[u];
cost[idx] = w;
head[u] = idx++;
}
struct Node
{
int u;
LL dis;
bool operator > (const Node &other) const
{return dis > other.dis;}
};
LL dis[maxn];
void dijkstra()
{
memset(dis, 0x3f, sizeof dis);
priority_queue<Node, vector<Node>, greater<Node>> heap;
dis[1] = A[1];
heap.push({1, A[1]});
while(!heap.empty())
{
auto [u, d] = heap.top();
heap.pop();
if(d > dis[u])
continue;
for(int i = head[u]; i; i = ne[i])
{
int v = edge[i];
LL nd = d + cost[i] + A[v];
if(nd < dis[v])
{
dis[v] = nd;
heap.push({v, nd});
}
}
}
}
int main()
{
int n, m;
cin >> n >> m;
for(int i = 1; i <= n; i++)
cin >> A[i];
while(m--)
{
int u, v, w;
cin >> u >> v >> w;
add(u, v, w);
add(v, u, w);
}
dijkstra();
for(int i = 2; i <= n; i++)
cout << dis[i] << ' ';
return 0;
}
E - Count Arithmetic Subsequences¶
题目大意
给你 \(N(1 \le N \le 80)\) 个数 \(A = (A_1, A_2, \cdots, A_N)\)，对于每个 \(k = 1, 2, \cdots, N\)，求出 \(A\) 中有多少个长度为 \(k\) 的等差数列。
解题思路
注意到 \(N \le 80\)，考虑动态规划。
定义 \(dp[i][x][y]\) 为长度为 \(i\) ，且最后两个数是 \(A_x\) 和 \(A_y\) 的等差数列的个数，转移的时候，只需要在 \(A_x\) 之前遍历所有的 \(A_j\)，使得 \(A_y - A_x = A_x - A_j\) 就可以了，这样就可以将 \(A_y\) 接在 \(A_j, A_x\) 的后边。那么 \(dp[i][x][y] = \sum\limits_{j = 1}^{x-1} dp[i-1][j][x]\)，时间复杂度 \(O(N^4)\)，是能过的。
下面考虑优化。为了计算 \(dp[i][x][y]\)，我们实际上要找的是长度为 \(i-1\) ，结尾是 \(A_x\) ，且公差为 \(d = A_y-A_x\) 的等差数列的个数之和，这启发我们把相同的公差 \(d\) 存放在一起。定义 \(d[i][y]\) 表示长度为 \(i\)，结尾是 \(A_y\) 的等差数列的哈希表，其中哈希表的 key 是公差 \(d\)，value 是数量。这样我们实际只需要在 dp 的过程中维护 \(d[i][y]\) 即可，枚举 \(x\)，算出 \(d = A_y-A_x\)，在 \(d[i-1][x]\) 的哈希表中查找出公差 \(d\) 的数量即可。时间复杂度 \(O(N^3)\)
参考代码
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
using LL = long long;
const LL mod = 998244353;
int main()
{
int n;
cin >> n;
vector<int> A(n);
for(int i = 0; i < n; i++)
cin >> A[i];
if(n == 1)
{
cout << 1 << endl;
return 0;
}
cout << n << ' ' << n * (n-1) / 2;
vector<vector<unordered_map<int, LL>>> dp(n+1, vector<unordered_map<int, LL>>(n));
for(int y = 0; y < n; y++)
for(int x = 0; x < y; x++)
{
int d = A[y] - A[x];
dp[2][y][d]++;
}
for(int i = 3; i <= n; i++)
{
LL sum = 0;
for(int y = 2; y < n; y++)
for(int x = 0; x < y; x++)
{
int d = A[y] - A[x];
if(auto it = dp[i-1][x].find(d); it != dp[i-1][x].end())
{
sum += it->second;
sum %= mod;
dp[i][y][d] += it->second;
dp[i][y][d] %= mod;
}
}
cout << ' ' << sum;
}
return 0;
}
F - Perfect Matching on a Tree¶
题目大意
给你一棵 \(N(1 \le N \le 2 \times 10^5)\) 个节点的树。对于树上的两点 \(x\) 和 \(y\)，定义 \(w(x, y)\) 表示两点之间的距离。
求出树上的 \(\lfloor \frac{N}{2} \rfloor\) 对点 \((x_1, y_1), (x_2, y_2), \cdots, (x_{\lfloor \frac{N}{2} \rfloor}, y_{\lfloor \frac{N}{2} \rfloor})\)，满足树上的点最多在其中出现一次，且最大化 \(\sum\limits_{i=1}^{\lfloor \frac{N}{2} \rfloor} w(x_i, y_i)\) 的值。
解题思路
考虑一条边能对答案产生的贡献，假设移除掉某条边 \((u, v)\) 之后，\(u\) 所在的子树有 \(c\) 个点，则 \(v\) 所在的子树有 \(N-c\) 个点，那么，这条边最多能对答案产生 \(\min(c, N-c)\) 次贡献。因此，如果每一条边的贡献都达到了 \(\min(c, N-c)\) ，那么答案就一定是最大的。
不失一般性的，不妨设 \(c \le N-c\)，即点 \(u\) 所在的子树的点数量更少，那么我们需要让点 \(u\) 所在的子树的所有点都穿过边 \((u, v)\)，也就是和 \(v\) 所在的子树进行匹配。这样可以让边 \((u, v)\) 的贡献最大。此外，这种方式还可以让 \(u\) 子树中所有的边的贡献最大化（因为子树中所有的点都必须穿过边 \((u, v)\) ）。
这种方式实际上不需要考虑每个点究竟和哪个点匹配，只需要让点穿过边，让边的贡献达到最大即可。
这启发我们按照树的重心（如果不会树的重心请看 树的重心 - OI Wiki (oi-wiki.org)）进行切分，假设树的重心是 \(G\)，\(G\) 的所有子树有 \(T_1, T_2, \cdots, T_k\)，同时设 \(E_i\) 表示 \(G\) 和子树 \(T_i\) 的根节点的连边。根据刚刚推导出来的性质，只需要考虑让每条边 \(E_i\) 的贡献最大即可，也就是让所有子树的点都和其他子树的点匹配（一个简短的证明：试想一下，如果 \(G\) 不是重心，那么存在一个子树的点的数量超过了 \(\frac{N}{2}\)，这棵子树就会出现内部的匹配，这样就一定会有一些边的贡献没有最大化。）。
如何构造答案？一种方式是每次从最大和次大的子树中选择两个点，然后删掉这两个点继续选择。不过还有一种更简单的做法，依次遍历子树 \(T_1, T_2, \cdots, T_k\)，按照访问的顺序把节点放到一个数组 \(v\) 中，然后让 \(v[i]\) 和 \(v[i+\lfloor \frac{N}{2} \rfloor]\) 匹配，根据重心的性质，这种匹配方式可以保证两个点一定不是同一个子树。
如果 \(N\) 是偶数的话，最后剩下的点和 \(G\) 进行匹配即可（相当于把 \(G\) 加进数组 \(v\) 的末尾）。否则 \(N\) 是奇数，则 \(G\) 不参与匹配。
参考代码
#include <iostream>
#include <vector>
using namespace std;
const int maxn = 2E5 + 10;
const int maxm = maxn * 2;
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 n, c;
int dfs(int u, int fa)
{
int son = 1;
int M = 0;
for (int i = head[u]; i; i = ne[i])
{
int v = edge[i];
if (v == fa)
continue;
int sonv = dfs(v, u);
son += sonv;
M = max(M, sonv);
}
M = max(M, n - son);
if (M <= n / 2)
c = u;
return son;
}
vector<int> dfn;
void dfs2(int u, int fa)
{
dfn.emplace_back(u);
for (int i = head[u]; i; i = ne[i])
{
int v = edge[i];
if (v == fa)
continue;
dfs2(v, u);
}
}
int main()
{
cin >> n;
for (int i = 1, u, v; i < n; i++)
{
cin >> u >> v;
add(u, v);
add(v, u);
}
dfs(1, 1);
if (n % 2 == 0)
dfn.emplace_back(c);
for (int i = head[c]; i; i = ne[i])
{
int u = edge[i];
dfs2(u, c);
}
for(int i = 0; i < n / 2; i++)
cout << dfn[i] << ' ' << dfn[i + n / 2] << '\n';
return 0;
}
G - Count Substring Query¶
题目大意
有一个字符串 \(S(1 \le |S| \le 5 \times 10^5)\) 和 \(Q(1 \le Q \le 5 \times 10^5)\) 个询问，每次询问给你一个字符串 \(T_i\)，其中 \(\sum\limits_{i=1}^Q|T_i| \le 5 \times 10^5\)。对于每一次询问，回答出 \(T_i\) 在 \(S\) 中出现了几次。
解题思路
AC 自动机 板子题。
参考代码
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int maxn = 5E5 + 10;
int cnt[maxn];
struct Trie
{
int ne[maxn][26], fail[maxn], vis_cnt[maxn], node_cnt;
vector<int> pattern_id[maxn];
int next_pattern_id;
vector<int> edge[maxn];
void insert(string s)
{
int u = 0;
for (auto ch : s)
{
int c = ch - 'a';
if (!ne[u][c])
ne[u][c] = ++node_cnt;
u = ne[u][c];
}
pattern_id[u].emplace_back(next_pattern_id++);
}
void build()
{
queue<int> q;
for (int c = 0; c < 26; c++)
if (ne[0][c])
q.push(ne[0][c]);
while (!q.empty())
{
int u = q.front();
q.pop();
for (int c = 0; c < 26; c++)
{
int v = ne[u][c], f = fail[u];
if (v)
{
fail[v] = ne[f][c];
q.push(v);
}
else
ne[u][c] = ne[f][c];
}
}
}
void dfs(int u)
{
for(auto v : edge[u])
{
dfs(v);
vis_cnt[u] += vis_cnt[v];
}
for(auto i : pattern_id[u])
cnt[i] += vis_cnt[u];
}
void fail_tree()
{
for(int u = 1; u <= node_cnt; u++)
edge[fail[u]].push_back(u);
dfs(0);
}
void query(string s)
{
int now = 0;
for (auto ch : s)
{
int c = ch - 'a';
now = ne[now][c];
vis_cnt[now]++;
}
fail_tree();
}
} ac;
int main()
{
string s;
cin >> s;
int q;
cin >> q;
string t;
for(int i = 0; i < q; i++)
{
cin >> t;
ac.insert(t);
}
ac.build();
ac.query(s);
for(int i = 0; i < q; i++)
cout << cnt[i] << '\n';
return 0;
}
创建日期: 2024-07-25