AtCoder Beginner Contest 327
A - ab (abc327 A)
题目大意
给定一个字符串\(s\)，问是否包含 ab或ba。
解题思路
遍历判断即可。
神奇的代码
#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;
string s;
cin >> n >> s;
bool ok = false;
for (int i = 1; i < n; ++i) {
ok |= (s[i] == 'a' && s[i - 1] == 'b');
ok |= (s[i - 1] == 'a' && s[i] == 'b');
}
if (ok)
cout << "Yes" << '\n';
else
cout << "No" << '\n';
return 0;
}
B - A^A (abc327 B)
题目大意
给定\(b\)，问是否存在 \(a\)使得 \(a^a = b\)。
解题思路
由于指数爆炸的缘故，\(a\)的范围不会很大，枚举\(a\)，看\(b \% a\)是否为 \(0\)，然后用\(b\)不断除以 \(a\) ，看最后除的次数是否等于\(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);
LL b;
cin >> b;
int ans = -1;
for (int i = 2; i <= 20; ++i) {
if (b % i != 0)
continue;
LL x = b;
int cnt = 0;
while (x > 1) {
x /= i;
++cnt;
}
if (cnt == i) {
ans = i;
break;
}
}
if (b == 1)
ans = 1;
cout << ans << '\n';
return 0;
}
C - Number Place (abc327 C)
题目大意
给定一个\(9 \times 9\)的网格，问是否符合数独局面。
数独局面，即每行 \(1-9\)，每列 \(1-9\)，每个 \(3 \times 3\)的格子有 \(1-9\)。
解题思路
按照条件，逐行、逐列、逐格子分别判断即可。
神奇的代码
#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);
array<array<int, 9>, 9> a;
for (auto& i : a)
for (auto& j : i)
cin >> j;
auto ok = [&]() {
for (auto& i : a) {
if (set<int>(i.begin(), i.end()).size() != 9)
return false;
}
for (int i = 0; i < 9; ++i) {
set<int> cnt;
for (int j = 0; j < 9; ++j) {
cnt.insert(a[j][i]);
}
if (cnt.size() != 9)
return false;
}
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < 3; ++j) {
set<int> cnt;
for (int x = 0; x < 3; ++x)
for (int y = 0; y < 3; ++y) {
cnt.insert(a[i * 3 + x][j * 3 + y]);
}
if (cnt.size() != 9)
return false;
}
}
return true;
};
if (ok())
cout << "Yes" << '\n';
else
cout << "No" << '\n';
return 0;
}
D - Good Tuple Problem (abc327 D)
题目大意
给定两个数组长度为\(m\)，仅包含\(1-n\)的\(a,b\)，问它们是否是一对好数组。
若两个数组是一对好数组，则存在一个长度为\(n\)的\(01\)数组 \(x\)，使得 \(x_{a_i} \neq x_{b_i}, \forall i \in [1, m]\)。
解题思路
将条件抽象成图，相当于是点\(a_i\)和点\(b_i\)连一条边，它们的颜色不能相同。
即最后是否是一张二分图，黑白染色即可。
神奇的代码
#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, m;
cin >> n >> m;
vector<int> a(m), b(m);
for (auto& i : a) {
cin >> i;
--i;
}
for (auto& i : b) {
cin >> i;
--i;
}
vector<vector<int>> edge(n);
for (int i = 0; i < m; ++i) {
edge[a[i]].push_back(b[i]);
edge[b[i]].push_back(a[i]);
}
vector<int> col(n, -1);
bool ok = true;
auto BFS = [&](int st) {
queue<int> team;
team.push(st);
col[st] = 0;
while (!team.empty()) {
int u = team.front();
team.pop();
int target = (col[u] ^ 1);
for (auto& v : edge[u]) {
if (col[v] == -1) {
col[v] = target;
team.push(v);
} else if (col[v] != target) {
ok = false;
return;
}
}
}
};
for (int i = 0; i < n && ok; ++i) {
if (col[i] == -1)
BFS(i);
}
if (ok)
cout << "Yes" << '\n';
else
cout << "No" << '\n';
return 0;
}
E - Maximize Rating (abc327 E)
题目大意
给定\(n\)场比赛的表现分\(p_i\)，现在选择一些场比赛，使得这些场比赛的 \(rating\)最大。
如果选择了 \(k\)场比赛 \((q_1, q_2, ..., q_k)\)，则 \(rating\)为
注意这里的\(q\)要按照原来的顺序排列。
解题思路
枚举\(k\)，有几项就变成常数，唯一的变数就是最大化\(\sum_{i=1}^{k}(0.9)^{k-i}q_i\)，这其实就是个经典的背包问题。
设\(dp[i][j]\)表示前 \(i\)场比赛，我选择了\(j\)场的\(\sum_{i=1}^{k}(0.9)^{k-i}q_i\)的最大值。
转移就是考虑当前比赛选或不选，则\(dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1] * 0.9 + p_i)\)
初始条件就是\(dp[0][0] = 0\)。
答案就是\(\max(\frac{dp[n][k]}{\sum_{i=1}^{k}(0.9)^{k-i}} - \frac{1200}{\sqrt{k}})\)
时间复杂度是\(O(n^2)\)
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const double inf = numeric_limits<double>::max();
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
vector<double> dp(n + 1, -inf);
dp[0] = 0;
for (int i = 0; i < n; ++i) {
vector<double> dp2 = dp;
int p;
cin >> p;
for (int j = 1; j <= i + 1; ++j) {
dp2[j] = max(dp2[j], dp[j - 1] * 0.9 + p);
}
dp2.swap(dp);
}
double ans = -inf;
double bottom = 1;
for (int i = 1; i <= n; ++i) {
ans = max(ans, dp[i] / bottom - 1200 / sqrt(i));
bottom = bottom * 0.9 + 1;
}
cout << fixed << setprecision(10) << ans << '\n';
return 0;
}
F - Apples (abc327 F)
题目大意
二维平面，给定若干个点，问一个长宽为\(d \times w\)的矩形所能覆盖的点的数量的最大值。
解题思路
枚举一个维度\(i\)（时间），问题就是在\([i, i + d)\)的范围内的另一维度（地点）的宽度为\(w\)的点数的最大值。
设数组\(a[i]\)表示 \(sum[i, i + w)\)，即当前时间范围内的一个区间的点数，随着时间的流逝，会有新的点加入，会有旧的点删去。其影响的都是一个长度为 \(w\)的\(a\)区间，用线段树维护这个数组 \(a\)即可。
时间复杂度为\(O(n\log n)\)
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int N = 2e5 + 8;
class segtree {
#define lson (root << 1)
#define rson (root << 1 | 1)
int max[N << 2], lazy[N << 2];
inline void pushdown(int root) {
if (lazy[root]) {
lazy[lson] += lazy[root];
max[lson] += lazy[root];
lazy[rson] += lazy[root];
max[rson] += lazy[root];
lazy[root] = 0;
}
}
void update(int root, int l, int r, int L, int R, LL val) {
if (L <= l && r <= R) {
lazy[root] += val;
max[root] += val;
return;
}
pushdown(root);
int mid = (l + r) >> 1;
if (L <= mid)
update(lson, l, mid, L, R, val);
if (R > mid)
update(rson, mid + 1, r, L, R, val);
max[root] = std::max(max[lson], max[rson]);
}
int query(int root, int l, int r) { return max[root]; }
public:
int n;
void update(int L, int R, LL val) { update(1, 1, n, L, R, val); }
int query() { return query(1, 1, n); }
};
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, d, w;
cin >> n >> d >> w;
vector<array<int, 2>> apple(n);
for (auto& i : apple)
cin >> i[0] >> i[1];
vector<int> id(n);
iota(id.begin(), id.end(), 0);
ranges::sort(id, [&](int a, int b) { return apple[a][0] < apple[b][0]; });
segtree seg;
seg.n = N - 8;
auto it = id.begin();
int ans = 0;
for (auto& i : id) {
while (it != id.end() && apple[*it][0] + d <= apple[i][0]) {
seg.update(max(1, apple[*it][1] - w + 1), apple[*it][1], -1);
it = next(it);
}
seg.update(max(1, apple[i][1] - w + 1), apple[i][1], 1);
ans = max(ans, seg.query());
}
cout << ans << '\n';
return 0;
}
G - Many Good Tuple Problems (abc327 G)
题目大意
若两个数组是一对好数组，则存在一个长度为\(n\)的\(01\)数组 \(x\)，使得 \(x_{a_i} \neq x_{b_i}, \forall i \in [1, m]\)。
问所有的长度为\(m\)，仅包含 \(1-n\)的共 \(n^{2m}\)对数组中，好数组的数量。
解题思路
注意到一对数组是好数组，我们将每一位的数字连一条边，这意味着它们所形成的图是一张二分图。
考虑对这个二分图计数。
首先枚举左边部分的点的数量\(k\)，注意到点取值多少不影响结果，因此方案数有 \(C_n^k\)。
然后考虑连边情况，每一条边都是从左边\(k\)个点选一个点，右边 \(n-k\)个点选一个点，然后连边。
但这里要考虑到边的顺序——因为数组有下标顺序，如果不考虑这个顺序的话，方案数就是 \(O((k(n-k))^m)\)，但是这里面有很多重复的情况。考虑如何不计重。然后来写题解了
神奇的代码