比赛链接:https://atcoder.jp/contests/abc215/tasks
如果一个字符串是 Hello,World!
,输出 AC
,否则输出 WA
。
模拟。
#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); string s; cin >> s; cout << (s == "Hello,World!" ? "AC" : "WA") << "\n"; return 0; }
输出 \(2\) 不超过 \(n\) 的最大幂次方。
模拟。
#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); long long n; cin >> n; cout << __lg(n) << "\n"; return 0; }
给出一个字符串,输出相关字母所对应的字典序第 \(k\) 小的字符串。
模拟。
#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); string s; int k; cin >> s >> k; sort(s.begin(), s.end()); int cnt = 0; do { if (++cnt == k) { cout << s << "\n"; break; } } while (next_permutation(s.begin(), s.end())); return 0; }
给出一个大小为 \(n\) 的数组 \(a\) ,找出 \([1, m]\) 中与每个 \(a_i\) 都 \(gcd=1\) 的数。
把每个 \(a_i\) 做一下质因子分解然后用这些质因子筛一下 \([1, m]\) 即可。
#include <bits/stdc++.h> using namespace std; constexpr int N = 1e5 + 10; int p[N]; void Init() { for (int i = 2; i < N; i++) { if (p[i]) { continue; } for (int j = i; j < N; j += i) { p[j] = i; } } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); Init(); int n, m; cin >> n >> m; vector<int> a(n); set<int> st; for (int i = 0; i < n; i++) { cin >> a[i]; for (int j = a[i]; j != 1; j /= p[j]) { st.insert(p[j]); } } vector<bool> is(N, true); for (auto i : st) { if (not is[i] or i == 1) { continue; } for (int j = i; j < N; j += i) { is[j] = false; } } vector<int> ans; for (int i = 1; i <= m; i++) { if (is[i]) { ans.push_back(i); } } cout << ans.size() << "\n"; for (auto i : ans) { cout << i << "\n"; } return 0; }
将字符逐个考虑,每次它需要加上之前所有不含它或以它结尾的字符串。
模拟代码即:
#include <bits/stdc++.h> using namespace std; constexpr int MOD = 998244353; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; string s; cin >> n >> s; map<string, int> mp; mp[""] = 1; for (auto ch : s) { auto next_mp(mp); for (auto [x, y] : mp) { if (x.find(ch) == string::npos) { next_mp[x + ch] += mp[x]; } else if (x.back() == ch) { next_mp[x] += mp[x]; } } mp = next_mp; } int ans = 0; for (auto [x, y] : mp) { if (x != "") { ans = (ans + y) % MOD; } } cout << ans << "\n"; return 0; }
最多有 \(2^{|s| = 1000}\) 种子串,考虑利用题目条件压缩。
因为最多有 \(10\) 个字母,所以可以枚举字母的所有排列组合方式,同时相邻连续的同种字母都可以看作一个字母,所有最终共可能有 \(\sum \limits _{i = 1}^{10} C_{10}^i \cdot A_i^i \approx 10^7\) 种字符串。
但 \(|s| \cdot 10^7 = 10^{10}\) 的复杂度仍难以接受(事实上这份代码跑了 \(20s\) ),考虑进一步压缩。
因为只需要知道一个字符串是否含有 \(ch\) 或以 \(ch\) 结尾,所以可以只保存字符串的字母集和结尾字母,此时复杂度为 \(|s| \cdot 2^{10} \cdot 10 \approx 10^7\) 。
设 \(dp_{ij}\) 为字母集为 \(i\) ,以字母 \(j\) 结尾的字符串个数,将上部分代码改写一下即可。
#include <bits/stdc++.h> using namespace std; constexpr int N = 1 << 10; 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; string s; cin >> n >> s; vector<vector<Z>> dp(N, vector<Z> (10)); for (auto ch : s) { auto next_dp(dp); int id = ch - 'A'; for (int i = 0; i < N; i++) { if ((i & (1 << id)) == 0) { next_dp[i | (1 << id)][id] += (i == 0 ? 1 : accumulate(dp[i].begin(), dp[i].end(), Z(0))); } else { next_dp[i][id] += dp[i][id]; } } dp = next_dp; } Z ans = 0; for (auto vec : dp) { for (auto x : vec) { ans += x; } } cout << ans.val() << "\n"; return 0; }
给出平面上的 \(n\) 个整数点,定义两点间的距离为 \(\mathrm{min} (|x_i-x_j|,|y_i-y_j|)\) ,找出两个不同点间的最大距离。
The maximization problem of a minimum value can often be solved with a binary search.
——Editorial
考虑二分最终答案,将所有点按 \(x\) 坐标从小到大排序,然后记录满足 \(x - pre_x \ge mid\) 时 \(pre_y\) 的最值,若存在 \(y - pre_{y\_{min}}\) 或 \(pre_{y\_{max}} - y \ge mid\) ,则该二分值可行,设为下界。
#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector<pair<int, int>> a(n); for (auto& [x, y] : a) { cin >> x >> y; } sort(a.begin(), a.end()); int l = 0, r = 1e9; while (l < r) { int mid = (l + r + 1) / 2; bool ok = false; queue<pair<int, int>> que; int mi = 1e9, mx = 0; for (auto [x, y] : a) { while (not que.empty() and x - que.front().first >= mid) { mi = min(mi, que.front().second); mx = max(mx, que.front().second); que.pop(); } if (y - mi >= mid or mx - y >= mid) { ok = true; } que.emplace(x, y); } if (ok) { l = mid; } else { r = mid - 1; } } cout << l << "\n"; return 0; }
https://atcoder.jp/contests/abc215/editorial/2514
https://atcoder.jp/contests/abc215/editorial/2515