A - First Player (abc304 a)
题目大意
依次给定每个人的姓名和年龄，排成一圈。从年龄最小的人依次输出姓名。
解题思路
找到年龄最小的，依次输出就好了。
神奇的代码
#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<pair<int, string>> p(n);
for(auto &i : p)
cin >> i.second >> i.first;
int st = min_element(p.begin(), p.end()) - p.begin();
for(int i = 0; i < n; ++ i){
cout << p[st].second << '\n';
st = (st + 1) % n;
}
return 0;
}
B - Subscribers (abc304 b)
题目大意
给定一个数字，如果其超过三位数，则仅保留其最高三位，低位数字全部置为0。
解题思路
读一个string，直接赋值即可。
神奇的代码
#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);
string s;
cin >> s;
if (s.size() > 3)
fill(s.begin() + 3, s.end(), '0');
cout << s << '\n';
return 0;
}
C - Virus (abc304 c)
题目大意
给定\(n\)个人的坐标，第一个人阳了，若两人的欧式距离\(\leq d\)，其中有一个阳了，则另一个也会阳。然后继续传染。
问最终每个人是否阳了。
解题思路
从第一个人直接\(BFS\)即可。时间复杂度为 \(O(n^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, d;
cin >> n >> d;
d *= d;
vector<array<int, 2>> p(n);
for(auto &i : p)
cin >> i[0] >> i[1];
vector<int> ans(n, 0);
ans[0] = 1;
queue<int> team;
team.push(0);
auto dis = [&](int x, int y){
return (p[x][0] - p[y][0]) * (p[x][0] - p[y][0]) + (p[x][1] - p[y][1]) * (p[x][1] - p[y][1]);
};
while(!team.empty()){
int u = team.front();
team.pop();
for(int i = 0; i < n; ++ i){
if (ans[i])
continue;
if (dis(i, u) <= d){
ans[i] = 1;
team.push(i);
}
}
}
for(int i = 0; i < n; ++ i)
if (ans[i])
cout << "Yes" << '\n';
else
cout << "No" << '\n';
return 0;
}
D - A Piece of Cake (abc304 d)
题目大意
一个\(h \times w\)的蛋糕，给定 \(n\)个草莓的位置，然后竖切 \(a\)刀，横切 \(b\)刀，给定切的位置，问切出来的 \((a+1)(b+1)\)块蛋糕中，草莓数量最少和最多分别是多少。不会把草莓切成两半。
解题思路
\(a \times b \leq 4e10\)，因此不能考虑每块蛋糕。但我们可以考虑每个草莓对蛋糕的贡献。
根据草莓的位置，每个草莓仅对一块蛋糕有贡献，因此我们就遍历每块草莓，令其对应蛋糕的草莓数加一。而求是哪块蛋糕，其实就看它位于哪一刀的右边和上边（左下坐标原点）即可，二分就可以找到。
最后看最大值和最小值即可。因为蛋糕的草莓数量是稀疏的，我们可以用 map记录，最后看map里的元素个数是否等于\((a+1)(b+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 w, h, n, a, b;
cin >> w >> h >> n;
vector<array<int, 2>> s(n);
for(auto &i : s)
cin >> i[0] >> i[1];
cin >> a;
vector<int> vec(a);
for(auto &i : vec)
cin >> i;
cin >> b;
vector<int> hor(b);
for(auto &i : hor)
cin >> i;
map<LL, int> cnt;
int minn = n + 1, maxx = 0;
auto check = [&](int x, int y){
int pos1 = upper_bound(vec.begin(), vec.end(), x) - vec.begin();
int pos2 = upper_bound(hor.begin(), hor.end(), y) - hor.begin();
return 1ll * (a + 1) * pos2 + pos1;
};
for(auto &[x, y]: s){
LL id = check(x, y);
cnt[id] ++;
}
for(auto &[_, v] : cnt){
minn = min(minn, v);
maxx = max(maxx, v);
}
if (cnt.size() < 1ull * (a + 1) * (b + 1))
minn = 0;
cout << minn << ' ' << maxx << '\n';
return 0;
}
E - Good Graph (abc304 e)
题目大意
给定一张无向图，有\(k\)个限制，第 \(i\)个限制表示 点\(x_i\)和 点\(y_i\) 不能相互到达。原图满足这\(k\)条限制。
依次回答\(q\)个独立的询问，每个询问添加一条边\((u,v)\)后，是否还满足这 \(k\)个限制。
解题思路
题意相当于给了若干个连通块，然后要求一些连通块之间不能相互到达，然后问增加的边，是否导致两个不该连通的连通块连通。
那就给每个连通块标个号，然后把不能连通的连通块编号用set存起来，每个询问就问这条边的两个点所在的连通块标号是否在这个set里即可。
连通块标号、查点所在的连通块，用并查集即可。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
class dsu {
public:
vector<int> p;
int n;
dsu(int _n) : n(_n) {
p.resize(n);
iota(p.begin(), p.end(), 0);
}
inline int get(int x) {
return (x == p[x] ? x : (p[x] = get(p[x])));
}
inline bool unite(int x, int y) {
x = get(x);
y = get(y);
if (x != y) {
p[x] = y;
return true;
}
return false;
}
};
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n, m;
cin >> n >> m;
dsu d(n);
for(int i = 0; i < m; ++ i){
int u, v;
cin >> u >> v;
-- u, -- v;
d.unite(u, v);
}
int k;
cin >> k;
set<array<int, 2>> forbid;
for(int i = 0; i < k; ++ i){
int u, v;
cin >> u >> v;
-- u, -- v;
int fu = d.get(u), fv = d.get(v);
assert(fu != fv);
if (fu > fv)
swap(fu, fv);
forbid.insert({fu, fv});
}
int q;
cin >> q;
while(q--){
int u, v;
cin >> u >> v;
-- u, -- v;
int fu = d.get(u), fv = d.get(v);
if (fu > fv)
swap(fu, fv);
if (forbid.find({fu, fv}) == forbid.end()){
cout << "Yes" << '\n';
}else{
cout << "No" << '\n';
}
}
return 0;
}
F - Shift Table (abc304 f)
题目大意
给定高桥的\(n\)天值班情况\(s\)。
问满足下述条件的青木的\(n\)天值班情况\(t\)数量，满足每天他俩至少有一人值班，且青木的值班情况是关于\(m\)的循环，其中 \(m | n,m < n\)。
解题思路
考虑枚举\(m\)，判断有多少种方案数满足上述要求。
考虑青木的前\(m\)天，对于第\(i\)天来说，青木肯定是可以值班的，那就考虑能否不值班。容易发现需要满足 \(s[j] = 1(j \% m == i)\)，即第 \(i\)天所涉及到的每一天（ \(i, i + m, i + 2m, i + 3m...\)）高桥都要值班，青木才可以不值班。
直观上来讲就是将高桥的值班情况\(s\)每长度为\(m\)切一份，每一份按位与，结果是\(1\)的那些天可以值班或不值班，其他天则必须要值班。设\(1\)的个数为\(x\)个，那青木的方案数就是 \(2^{x}\)。
如果不考虑算重，我们只需要将所有枚举的\(m\) 计算的情况数加起来，就是答案。
但问题是这样会算重，题意里也温馨提示不同的周期可能会生成相同的情况。比如我枚举\(m=2\)，计算了情况数，然后枚举\(m=4\)时，属于\(m=2\)的情况会再算一次，因为周期为 \(2\)的也是周期为\(4\)的。因此这里我们需要容斥。
如何容斥呢？上述情况我们之所以不能普通的相加，是因为大的循环情况会包含小的循环情况，我们得把\(m=4\)中满足\(m=2\)的情况剔除，也就是说\(m=4\)应该意味着 该情况关于\(4\)循环，但不关于 \(2\)的循环，即\(4\)是它的最小循环节。
为了想清楚如何容斥，最好把式子写出来。
设\(a_i\) 表示值班情况关于\(i\)的循环，满足题意条件的情况数，即上述我们求的结果， \(b_i\)表示值班情况关于\(i\)的循环，且不存在更小的循环节。
根据定义，我们有\(a_i = \sum_{j | i} b_j\)， 即\(a_i\)包括了循环节为 \(i\)，也包括循环节更小的情况。上述方法可以求出 \(a_i\)，这里我们就需要容斥求出 \(b_j\)。
发现可以直接容斥，\(b_i = a_i - \sum_{j < i, j | i} b_j\)，因为\(b_i\)已经是最小的循环节数量，所以我们就把\(a_i\)中包含的比\(i\)还小的循环节剔除就可以了。然后答案就是\(\sum_{i|n, i \neq n}b_i\)
时间复杂度是\(O(nd(n))\)，其中 \(d(n)\)表示 \(n\)的因数个数，因为 \(n \neq 2e5\)，而\(2 * 3 * 5 * 7 * 11 * 13 * 17 = 5e5\)，也就最多\(7\)个质数，这 \(7\)个质数组合最多也就 \(2^7 = 128\)个因数，其余质数情况只会更少因数，因此复杂度不大。
如果右式减去的是关于\(a_j\)的话就需要像下面的莫比乌斯反演的容斥。
神奇的代码
#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;
string s;
cin >> n >> s;
vector<int> p2(n + 1, 1);
for(int i = 1; i <= n; ++ i)
p2[i] = p2[i - 1] * 2 % mo;
vector<int> cnt(n);
for(int i = 1; i < n; ++ i){
if (n % i != 0)
continue;
vector<int> ok(i, 1);
for(int j = 0; j < n; ++ j)
ok[j % i] &= (s[j] == '#');
cnt[i] = p2[count(ok.begin(), ok.end(), 1)];
for(int j = 1; j < i; ++ j)
if (i % j == 0){
cnt[i] -= cnt[j];
if (cnt[i] < 0)
cnt[i] += mo;
}
}
int ans = accumulate(cnt.begin(), cnt.end(), 0ll) % mo;
cout << ans << '\n';
return 0;
}
容易发现这是个狄利克雷卷积\(a_i = \sum_{j | i} 1(\frac{i}{j})b_j\)，其中\(1(x)=1\)是常函数，可以直接莫比乌斯反演（其实就是等式两边卷积一个\(1\)的逆函数，即\(\mu\)）得到 \(b_i = \sum_{j|i} \mu(\frac{i}{j})a_j\)，然后答案就是
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define FOR(i, x, y) for (decay<decltype(y)>::type i = (x), _##i = (y); i < _##i; ++i)
#define FORD(i, x, y) for (decay<decltype(x)>::type i = (x), _##i = (y); i > _##i; --i)
const int mo = 998244353;
const LL p_max = 1E5 + 100;
LL mu[p_max];
void get_mu() {
mu[1] = 1;
static bool vis[p_max];
static LL prime[p_max], p_sz, d;
FOR (i, 2, p_max) {
if (!vis[i]) {
prime[p_sz++] = i;
mu[i] = -1;
}
for (LL j = 0; j < p_sz && (d = i * prime[j]) < p_max; ++j) {
vis[d] = 1;
if (i % prime[j] == 0) {
mu[d] = 0;
break;
}
else mu[d] = -mu[i];
}
}
}
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n;
string s;
cin >> n >> s;
vector<int> p2(n + 1, 1);
for(int i = 1; i <= n; ++ i)
p2[i] = p2[i - 1] * 2 % mo;
get_mu();
vector<int> a(n);
vector<int> b(n);
for(int i = 1; i < n; ++ i){
if (n % i != 0)
continue;
vector<int> ok(i, 1);
for(int j = 0; j < n; ++ j)
ok[j % i] &= (s[j] == '#');
a[i] = p2[count(ok.begin(), ok.end(), 1)];
for(int j = i; j < n; j += i){
b[j] += (mu[j / i] * a[i] % mo + mo) % mo;
if (b[j] >= mo)
b[j] -= mo;
}
}
int ans = 0;
for(int i = 1; i < n; ++ i)
if (n % i == 0){
ans += b[i];
if (ans >= mo)
ans -= mo;
}
cout << ans << '\n';
return 0;
}
这里还可以继续化简，交换两个求和顺序，得到（第二个求和式\(i = k \cdot j | n, i \neq n\),故 \(k | \frac{n}{j}, k \neq \frac{n}{j}\)）
而\(\sum_{k | \frac{n}{j}, k \neq \frac{n}{j}}\mu(k) + \mu(\frac{n}{j}) = \sum_{k | \frac{n}{j}}\mu(k) = \varepsilon(\frac{n}{j}) = 0(j \neq n)\)，其中\(\varepsilon(n)\)是狄利克雷卷积的单位函数，\(\varepsilon(1) = 1\)，其余取值为 \(0\)。
因此\(\sum_{k | \frac{n}{j}, k \neq \frac{n}{j}}\mu(k) = -\mu(\frac{n}{j})\)，故最终答案化简为
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define FOR(i, x, y) for (decay<decltype(y)>::type i = (x), _##i = (y); i < _##i; ++i)
#define FORD(i, x, y) for (decay<decltype(x)>::type i = (x), _##i = (y); i > _##i; --i)
const int mo = 998244353;
const LL p_max = 1E5 + 100;
LL mu[p_max];
void get_mu() {
mu[1] = 1;
static bool vis[p_max];
static LL prime[p_max], p_sz, d;
FOR (i, 2, p_max) {
if (!vis[i]) {
prime[p_sz++] = i;
mu[i] = -1;
}
for (LL j = 0; j < p_sz && (d = i * prime[j]) < p_max; ++j) {
vis[d] = 1;
if (i % prime[j] == 0) {
mu[d] = 0;
break;
}
else mu[d] = -mu[i];
}
}
}
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n;
string s;
cin >> n >> s;
vector<int> p2(n + 1, 1);
for(int i = 1; i <= n; ++ i)
p2[i] = p2[i - 1] * 2 % mo;
get_mu();
vector<int> a(n);
vector<int> b(n);
int ans = 0;
for(int i = 1; i < n; ++ i){
if (n % i != 0)
continue;
vector<int> ok(i, 1);
for(int j = 0; j < n; ++ j)
ok[j % i] &= (s[j] == '#');
a[i] = p2[count(ok.begin(), ok.end(), 1)];
ans += (-mu[n / i] * a[i] % mo + mo) % mo;
if (ans >= mo)
ans -= mo;
}
cout << ans << '\n';
return 0;
}
不过虽然题意提到不同的\(m\)可以导出相同的情况，上述讨论基于一个假设就是，如果 \(x\)和 \(y\)都能导出同一种情况，其中\(x\)是该情况中循环节最小的 ，那么一定有 \(x|y\) ，当时就想着这个\(x | y\)是否一定成立，然后就没敢容斥了。
G - Max of Medians (abc304 g)
题目大意
<++>文章来源地址https://www.toymoban.com/news/detail-470044.html
解题思路
<++>
神奇的代码
Ex - Constrained Topological Sort (abc304 h)
题目大意
<++>文章来源：https://www.toymoban.com/news/detail-470044.html
解题思路
<++>
神奇的代码
到了这里，关于AtCoder Beginner Contest 304的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
