A – N-choice question (abc300 a)题目大意
给定一个元素互不相同的数组\(c\)和 \(a,b\)，找到 \(i\)使得 \(c_i = a + b\)
解题思路
直接for循环寻找即可。
神奇的代码
#include 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 > 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 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 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 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 s(h); for(auto &i : s) cin >> i; int sz = min(h, w); vector 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 = h || nx < 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 using namespace std;using LL = long long;#define FOR(i, x, y) for (decay::type i = (x), _##i = (y); i < _##i; ++i)#define FORD(i, x, y) for (decay::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 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 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 cache; LL inv5 = inv(5); function 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 = 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 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 pos; LL cnt = 0; for(int i = 0; i 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 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 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 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 > 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)题目大意
解题思路
神奇的代码