AtCoder Beginner Contest 300
A - N-choice question (abc300 a)
题目大意
给定一个元素互不相同的数组\(c\)和 \(a,b\)，找到 \(i\)使得 \(c_i = a + b\)
解题思路
直接for循环寻找即可。
神奇的代码
#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, a, b;
cin >> n >> a >> b;
for(int i = 0; i < n; ++ i){
int c;
cin >> c;
if (c == a + b){
cout << i + 1 << '\n';
return 0;
}
}
return 0;
}
B - Same Map in the RPG World (abc300 b)
题目大意
给定两个矩阵\(A,B\)，问能否对 \(A\)进行若干次变换操作得到 \(B\)。
变换分两种，一种是将第一列放到最后一列，另一种是将第一行放到最后一行。
解题思路
范围不大，直接枚举所有变换操作判断即可。
如果我们将左右连通，上下连通，那么变换操作实际上不改变每个点的上下左右点。即变换操作可以看成将矩形左上角的点移动。
时间复杂度为\(O(H^2W^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 h, w;
cin >> h >> w;
vector<string> a(h), b(h);
for(auto &i : a){
cin >> i;
}
for(auto &i : b){
cin >> i;
}
auto equal = [&](int x, int y){
for(int i = 0; i < h; ++ i)
for(int j = 0; j < w; ++ j){
int X = (x + i) % h;
int Y = (y + j) % w;
if (a[X][Y] != b[i][j]){
return false;
}
}
return true;
};
auto check = [&](){
for(int i = 0; i < h; ++ i)
for(int j = 0; j < w; ++ j)
if (equal(i, j))
return true;
return false;
};
if (check()){
cout << "Yes" << '\n';
}
else
cout << "No" << '\n';
return 0;
}
C - Cross (abc300 c)
题目大意
给定一个包含.#的矩形，问由#组成的形如X的最长长度，每个长度的数量。
解题思路
范围不大，枚举X的位置和大小判断即可。
时间复杂度为\(O(HW\min(HW))\)
神奇的代码
#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 h, w;
cin >> h >> w;
vector<string> s(h);
for(auto &i : s)
cin >> i;
int sz = min(h, w);
vector<int> ans(sz + 1);
auto check = [&](int x, int y){
if (s[x][y] != '#')
return 0;
for(int i = 0; i <= sz; ++ i){
for(int dx = -1; dx <= 1; dx += 2)
for(int dy = -1; dy <= 1; dy += 2){
int nx = x + i * dx, ny = y + i * dy;
if (nx >= h || nx < 0 || ny < 0 || ny >= w)
return i - 1;
if (s[nx][ny] != '#')
return i - 1;
}
}
return sz;
};
for(int i = 0; i < h; ++ i)
for(int j = 0; j < w; ++ j)
ans[check(i, j)] ++;
for(int i = 1; i <= sz; ++ i)
cout << ans[i] << " \n"[i == sz];
return 0;
}
D - AABCC (abc300 d)
题目大意
问\(1 \sim n\)中能表示成 \(a^2 \times b \times c^2(a < b < c)\)且 \(a,b,c\)为质数的数的个数。
解题思路
由于\(n \leq 10^{12}\)，预处理\(1 \to 10^6\)的质数，然后枚举\(c\)和 \(a\)，计算得到乘积小于等于 \(n\)的最大的 \(b\)，此时符合条件的数量就是 \(1 \sim b\)中的质数个数，这个事先预处理即可。
时间复杂度是 \(O(\sqrt{n} \log n)\)
神奇的代码
#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 LL p_max = 1E6 + 100;
LL pr[p_max], p_sz;
int cnt[p_max];
void get_prime() {
static bool vis[p_max];
FOR (i, 2, p_max) {
if (!vis[i]) {
pr[p_sz++] = i;
cnt[i] = 1;
}
FOR (j, 0, p_sz) {
if (pr[j] * i >= p_max) break;
vis[pr[j] * i] = 1;
if (i % pr[j] == 0) break;
}
}
FOR(i, 2, p_max)
cnt[i] += cnt[i - 1];
}
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
LL n;
cin >> n;
LL ans = 0;
get_prime();
for(int i = 0; i < p_sz; ++ i){
for(int j = 0; j < i; ++ j){
LL sum = 1ll * pr[i] * pr[i] * pr[j] * pr[j];
if (sum > n)
break;
LL maxb = min(n / sum, pr[i] - 1);
if (maxb <= pr[j])
break;
ans += cnt[maxb] - cnt[pr[j]];
}
}
cout << ans << '\n';
return 0;
}
E - Dice Product 3 (abc300 e)
题目大意
六面骰子，每面等概率出现。
现在不断掷骰子，直到掷出来的数的乘积大于等于\(N\)。
问恰好为 \(N\)的概率。对 \(998244353\)取模。
解题思路
显然\(n\)的质因数只能有 \(2,3,5\)。
设\(dp[n]\)表示最终是 \(n\)的概率，根据定义， \(dp[n] = \frac{1}{6}dp[\frac{n}{1}] + \frac{1}{6}dp[\frac{n}{2}] + \frac{1}{6}dp[\frac{n}{3}] + \frac{1}{6}dp[\frac{n}{4}] + \frac{1}{6}dp[\frac{n}{5}] + \frac{1}{6}dp[\frac{n}{6}]\)，即掷出\(n\)的概率，应当是先掷出 \(\frac{n}{1}\) ，然后再以\(\frac{1}{6}\)的概率掷出 \(1\)，或者先掷出 \(\frac{n}{2}\) ，然后再以\(\frac{1}{6}\)的概率掷出 \(2\)，依次类推。
当然，如果不整除就没有这部分的概率贡献。
化简一下就是\(dp[n] = \frac{1}{5}dp[\frac{n}{2}] + \frac{1}{5}dp[\frac{n}{3}] + \frac{1}{5}dp[\frac{n}{4}] + \frac{1}{5}dp[\frac{n}{5}] + \frac{1}{5}dp[\frac{n}{6}]\)
因为每次转移状态大小都会除以一个数，所以最终的状态数量应该不会超过\(O(n \log n)\)，写个记忆化就可以了。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int mo = 998244353;
long long qpower(long long a, long long b){
long long qwq = 1;
while(b){
if (b & 1)
qwq = qwq * a % mo;
a = a * a % mo;
b >>= 1;
}
return qwq;
}
long long inv(long long x){
return qpower(x, mo - 2);
}
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
LL n, ba;
cin >> n;
ba = n;
int cnt2 = 0, cnt3 = 0, cnt5 = 0;
while (n % 2 == 0){
++ cnt2;
n /= 2;
}
while (n % 3 == 0){
++ cnt3;
n /= 3;
}
while (n % 5 == 0){
++ cnt5;
n /= 5;
}
if (n != 1)
cout << 0 << '\n';
else{
map<LL, int> cache;
LL inv5 = inv(5);
function<LL(LL)> dfs = [&](LL n){
if (n == 1)
return 1;
if (cache.find(n) != cache.end())
return cache[n];
LL ans = 0;
for(int i = 2; i <= 6; ++ i)
if (n % i == 0){
ans = (ans + dfs(n / i));
if (ans >= mo)
ans -= mo;
}
cache[n] = ans * inv5 % mo;
return cache[n];
};
cout << dfs(ba) << '\n';
}
return 0;
}
F - More Holidays (abc300 f)
题目大意
给定一个包含xo的字符串\(t\)，它由一个长度为\(n\)的串\(s\)重复 \(m\)次拼接得到。要求将恰好 \(k\)个 x变成o，问连续o的最大长度。
解题思路
把x的位置都记录下来，容易发现我们进行变换的x肯定是一组连续的x。
我们枚举进行变化的第一个x，然后找到之后的第 \(k\)个 x，之间的长度取个最大值即可。
虽然这个x有\(nm = 10^{14}\)个，但由于串是重复拼接得到的，第二部分的串的 x实际上跟第一个串的情况一致（并且不会更优），因此我们只需要枚举第一个串x和第二个串的第一个x（注意这个情况，会利用第一个串最后一个x和第二个串的第一个x之间的o，可能从第一个串的第一个x更优）。
神奇的代码
#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;
LL k;
cin >> n >> m >> k;
string s;
cin >> s;
vector<int> pos;
LL cnt = 0;
for(int i = 0; i < n; ++ i){
cnt += (s[i] == 'x');
if (s[i] == 'x')
pos.push_back(i);
}
LL ans = 0;
LL la = -1;
auto solve = [&](int st){
LL left = pos.size() - st;
LL minn = min(left, k);
left = k - minn;
if (left == 0){
if (st + k == pos.size()){
return 1ll * n + pos[0] * (m > 1);
}else {
return 1ll * pos[st + k];
}
}
LL shift = left / cnt + 1;
LL remain = left % cnt;
if (remain == 0 && shift == m){
return shift * n;
}else if (shift > m || shift == m && remain > 0)
return 0ll;
else{
return shift * n + pos[remain];
}
};
for(int i = 0; i < pos.size(); ++ i){
LL r = solve(i);
ans = max(ans, r - la - 1);
la = pos[i];
}
if (m > 1){
m -= 1;
LL r = solve(0);
ans = max(ans, n + r - pos.back() - 1);
}
cout << ans << '\n';
return 0;
}
求第\(k\)个 x可能有些情况要讨论，官方题解采用的二分法就可以以\(\log\)的代价避免这个讨论。
且x的数量和串\(s\)的长度是同一个数量级，我们也可以枚举答案的左端点，然后二分找到恰好包含\(k\)个x的最右端点，长度取个最大值。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const LL inf = 1e18;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n, m;
LL k;
cin >> n >> m >> k;
string s;
cin >> s;
vector<int> sum(n);
LL cnt = 0;
for(int i = 0; i < n; ++ i){
if (s[i] == 'x'){
sum[i] = 1;
}
}
partial_sum(sum.begin(), sum.end(), sum.begin());
LL ans = 0;
LL la = -1;
auto count = [&](LL pos){
LL shift = pos / n, remain = pos % n;
return shift * sum.back() + sum[remain] * (shift != m);
};
auto solve = [&](int st){
LL l = st, r = 1ll * n * m;
LL down = st == 0 ? 0 : sum[st - 1];
while(l + 1 < r){
LL mid = (l + r) >> 1;
if (count(mid) - down <= k)
l = mid;
else
r = mid;
};
return r;
};
for(int i = 0; i < n; ++ i){
LL r = solve(i);
ans = max(ans, r - i);
}
cout << ans << '\n';
return 0;
}
G - P-smooth number (abc300 g)
题目大意
<++>
解题思路
<++>
神奇的代码
Ex - Fibonacci: Revisited (abc300 h)
题目大意
<++>
解题思路
<++>
神奇的代码