比赛链接：https://atcoder.jp/contests/abc220/tasks
A - Find Multiple
题意
判断 ([a, b]) 中是否有 (c) 的倍数。
- (1 le a le b le 1000)
- (1 le c le 1000)
题解
模拟。
代码
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int a, b, c;
cin >> a >> b >> c;
for (int i = a; i <= b; i++) {
if (i % c == 0) {
cout << i << "
";
return 0;
}
}
cout << -1 << "
";
return 0;
}
B - Base K
题意
给出 (k) 进制下的 (a, b) ，将它们转换为十进制。
- (2 le k le 10)
- (1 le a, b le 10^5) （十进制下）
题解
模拟。
代码
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int k;
cin >> k;
string a, b;
cin >> a >> b;
int ta = 0, tb = 0;
for (auto ch : a) {
ta = ta * k + (ch - '0');
}
for (auto ch : b) {
tb = tb * k + (ch - '0');
}
cout << 1LL * ta * tb << "
";
return 0;
}
C - Long Sequence
题意
将长为 (n) 的序列 (a) 重复拼接无数次，计算前缀和第一次大于 (x) 时的位置。
- (1 le n le 10^5)
- (1 le a_i le 10^9)
- (1 le x le 10^{18})
题解
取余。
代码
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<long long> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
for (int i = 1; i < n; i++) {
a[i] += a[i - 1];
}
long long x;
cin >> x;
long long ans = 0;
ans = x / a.back() * n;
x %= a.back();
for (int i = 0; i < n; i++) {
if (a[i] > x) {
ans += i + 1;
break;
}
}
cout << ans << "
";
return 0;
}
D - FG operation
题意
有一个长为 (n) 的序列 (a) ，每次有两种可选操作：
- 移去最左端的两个元素 (x, y) ，并在最左端插入 ((x + y) \% 10)
- 移去最左端的两个元素 (x, y) ，并在最左端插入 ((x imes y) \% 10)
问在 (2^{n - 1}) 种可能情况中，最后余下的数为 (0,1,dots,9) 的情况数，答案对 (998244353) 取模。
- (2 le n le 10^5)
- (0 le a_i le 9)
题解
设 (dp[i][j]) 为前 (i) 个数余下 (j) 的情况数。
代码
#include <bits/stdc++.h>
using namespace std;
constexpr int MOD = 998244353;
int norm(int x) { if (x < 0) { x += MOD; } if (x >= MOD) { x -= MOD; } return x; }
template<class T> T binpow(T a, int b) { T res = 1; for (; b; b /= 2, a *= a) { if (b % 2) { res *= a; } } return res; }
struct Z {
int x;
Z(int x = 0) : x(norm(x)) {}
int val() const { return x; }
Z operator-() const { return Z(norm(MOD - x)); }
Z inv() const { assert(x != 0); return binpow(*this, MOD - 2); }
Z &operator*=(const Z &rhs) { x = 1LL * x * rhs.x % MOD; return *this; }
Z &operator+=(const Z &rhs) { x = norm(x + rhs.x); return *this; }
Z &operator-=(const Z &rhs) { x = norm(x - rhs.x); return *this; }
Z &operator/=(const Z &rhs) { return *this *= rhs.inv(); }
friend Z operator*(const Z &lhs, const Z &rhs) { Z res = lhs; res *= rhs; return res; }
friend Z operator+(const Z &lhs, const Z &rhs) { Z res = lhs; res += rhs; return res; }
friend Z operator-(const Z &lhs, const Z &rhs) { Z res = lhs; res -= rhs; return res; }
friend Z operator/(const Z &lhs, const Z &rhs) { Z res = lhs; res /= rhs; return res; }
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
vector<vector<Z>> dp(n, vector<Z> (10));
dp[0][a[0]] = 1;
for (int i = 1; i < n; i++) {
for (int j = 0; j < 10; j++) {
dp[i][j * a[i] % 10] += dp[i - 1][j];
dp[i][(j + a[i]) % 10] += dp[i - 1][j];
}
}
for (int i = 0; i < 10; i++) {
cout << dp[n - 1][i].val() << "
";
}
return 0;
}
E - Distance on Large Perfect Binary Tree
题意
在一个 (n) 层满二叉树中，计算距离为 (d) 的结点二元组个数， ((i, j) e (j, i)) ，答案对 (998244353) 取模。
- (2 le n le 10^6)
- (1 le d le 2 imes 10^6)
题解
枚举路径所经最高层结点的左右子路径长度。
假设分别为 (l, d - l) ，那么前 (n - max(l, d - l)) 层的结点都可以作为路径所经的最高层结点。
易知在满二叉树中与根节点距离为 (i) 的结点的个数为 (2^i) ，且左右子树各占一半。
所以长为 (d) 的路径个数为：
[sum limits _{l = 0} ^{d} (2^{n - max(l, d - l)} - 1) imes 2^{max(0, l - 1)} imes 2^{max(0, d - l - 1)}
]
最后因为问的是二元组个数，所以需要再 ( imes 2) 。
代码
#include <bits/stdc++.h>
using namespace std;
constexpr int MOD = 998244353;
int norm(int x) { if (x < 0) { x += MOD; } if (x >= MOD) { x -= MOD; } return x; }
template<class T> T binpow(T a, int b) { T res = 1; for (; b; b /= 2, a *= a) { if (b % 2) { res *= a; } } return res; }
struct Z {
int x;
Z(int x = 0) : x(norm(x)) {}
int val() const { return x; }
Z operator-() const { return Z(norm(MOD - x)); }
Z inv() const { assert(x != 0); return binpow(*this, MOD - 2); }
Z &operator*=(const Z &rhs) { x = 1LL * x * rhs.x % MOD; return *this; }
Z &operator+=(const Z &rhs) { x = norm(x + rhs.x); return *this; }
Z &operator-=(const Z &rhs) { x = norm(x - rhs.x); return *this; }
Z &operator/=(const Z &rhs) { return *this *= rhs.inv(); }
friend Z operator*(const Z &lhs, const Z &rhs) { Z res = lhs; res *= rhs; return res; }
friend Z operator+(const Z &lhs, const Z &rhs) { Z res = lhs; res += rhs; return res; }
friend Z operator-(const Z &lhs, const Z &rhs) { Z res = lhs; res -= rhs; return res; }
friend Z operator/(const Z &lhs, const Z &rhs) { Z res = lhs; res /= rhs; return res; }
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
int d;
cin >> d;
Z ans = 0;
for (int i = 0; i <= d; i++) {
int dep = n - max(i, d - i);
if (dep >= 1) {
ans += (binpow(Z(2), dep) - 1) * binpow(Z(2), max(0, i - 1)) * binpow(Z(2), max(0, d - i - 1));
}
}
ans *= 2;
cout << ans.val() << "
";
return 0;
}
F - Distance Sums 2
题意
给出一棵有 (n) 个结点的树，对于每个结点 (i) ，计算 (sum limits _{j = 1} ^{n} dis(i, j)) 。
- (2 le n le 10^5)
题解
换根 (dp) ，当根节点由父结点 (p) 转移到子结点 (u) 时，路径总和的变化量为 (-sz[u] + (n - sz[u])) ，即子结点所在子树的结点距离都 (-1) ，其余结点距离都 (+1) 。
代码
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<vector<int>> G(n);
for (int i = 0; i < n - 1; i++) {
int u, v;
cin >> u >> v;
--u, --v;
G[u].push_back(v);
G[v].push_back(u);
}
vector<int> sz(n), dis(n);
function<void(int, int)> dfs1 = [&](int u, int p) {
sz[u] = 1;
if (p != -1) {
dis[u] = dis[p] + 1;
}
for (auto v : G[u]) {
if (v != p) {
dfs1(v, u);
sz[u] += sz[v];
}
}
};
dfs1(0, -1);
vector<long long> ans(n);
ans[0] = accumulate(dis.begin(), dis.end(), 0LL);
function<void(int, int)> dfs2 = [&](int u, int p) {
if (p != -1) {
ans[u] = ans[p] - sz[u] + (n - sz[u]);
}
for (auto v : G[u]) {
if (v != p) {
dfs2(v, u);
}
}
};
dfs2(0, -1);
for (int i = 0; i < n; i++) {
cout << ans[i] << "
";
}
return 0;
}
G - Isosceles Trapezium
题意
给出平面中 (n) 个不同点的整数坐标 ((x_i, y_i)) 及其权值 (c_i) ，计算可能由 (4) 个点组成的等腰梯形的最大权值。
- (4 le n le 1000)
- (-10^9 le x_i, y_i le 10^9)
- (1 le c_i le 10^9)
题解
注意到，等腰梯形由上下两底确定，且上下两底的中点在同一条中垂线上，所以可以枚举所有的边并对其中垂线及中点建立映射。
方便起见，采用法向式来表示每条边所对应的中垂线，即：
[a(x - x_0) + b(y - y_0) = 0
]
表示过点 ((x_0, y_0)) 且与向量 ((a, b)) 垂直的直线。
对于 ((x_i, y_i), (x_j, y_j)) 两点所在边的中垂线，易知其过中点 ((frac{x_i + x_j}{2}, frac{y_i + y_j}{2})) ，且与向量 ((x_j - x_i, y_j - y_i)) 垂直。
为避免误差，可将整体坐标扩大 (2) 倍。
至此，用法向式表示出了每条边的中垂线，为了便于映射，将向量进行规范化，约分后统一转为 (x ge 0) 或 (x = 0, y ge 0) 的形式，之后将法向式化为一般式，即：
[Ax + By + C = ax + by - (ax_0 + by_0)
]
这样，对 ((A, B, C)) 进行映射，便确定了每条边的中垂线，之后再对中垂线所经不同点的权值进行映射即可。
Tips
可能存在多条边中点及中垂线相同，此时取所有点权值中的最大值。
代码
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<int> x(n), y(n), c(n);
for (int i = 0; i < n; i++) {
cin >> x[i] >> y[i] >> c[i];
x[i] *= 2, y[i] *= 2;
}
map<tuple<int, int, long long>, map<pair<int, int>, int>> mp;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
int dx = x[j] - x[i], dy = y[j] - y[i];
int g = gcd(dx, dy);
dx /= g, dy /= g;
if (dx < 0 or (dx == 0 and dy < 0)) {
dx *= -1, dy *= -1;
}
auto line = make_tuple(dx, dy, -(1LL * dx * (x[i] + x[j]) + 1LL * dy * (y[i] + y[j])));
auto point = make_pair((x[i] + x[j]) / 2, (y[i] + y[j]) / 2);
mp[line][point] = max(mp[line][point], c[i] + c[j]);
}
}
long long ans = -1;
for (auto [line, point] : mp) {
vector<long long> v;
for (auto [ord, c] : point) {
v.push_back(c);
}
sort(v.begin(), v.end(), greater<>());
if ((int)v.size() >= 2) {
ans = max(ans, v[0] + v[1]);
}
}
cout << ans << "
";
return 0;
}
参考
https://atcoder.jp/contests/abc220/editorial/2706