2025.2.17——1400

2025.2.17——1400

---

A 1400 B 1400 C 1400 ------------------------------------------------ 二分+构造+字符串/贪心/思维。CF的题就得多看透几层表面发掘本质。

---

A 一眼单调性。分析后可以二分答案。

---

B 本质是： ( j − i ) ∣ n , s [ i ] ! = s [ j ] (j-i)|n,s[i]!=s[j] (j−i)∣n,s[i]!=s[j] 。设想一个周期为 T T T 。设最小的不能被 n n n 整除的数为 t t t 。必要性： T > = t T>=t T>=t 。充分性： T = = t T==t T==t 时， s [ i ] = = s [ j ] s[i]==s[j] s[i]==s[j]的距离为 t t t 的倍数，不能被 n n n 整除，满足题意。绝妙的构造…

---

C 字符串贪心匹配。看着题解想了好久，值得多几次回味。解法和优化亦多样，正难则反/搜索/动态规划…

---

------------------------代码------------------------ A #include <bits/stdc++.h> #define int long long using namespace std; #define bug(BUG) cout << "bug:# " << (BUG) << endl #define bug2(BUG1, BUG2) cout << "bug:# " << (BUG1) << " " << (BUG2) << endl #define bug3(BUG1, BUG2, BUG3) cout << "bug:# " << (BUG1) << ' ' << (BUG2) << ' ' << (BUG3) << endl #define bugv(VEC) \ { \ for (auto Vec : VEC) \ cout << Vec << ' '; \ cout << '\n'; \ } void _(); signed main() { ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); cout << fixed << setprecision(10); int T = 1; cin >> T; while (T--) _(); return 0; } void _() { int n; cin >> n; vector<int> a(n + 1); for (int i = 1; i <= n; i++) cin >> a[i]; sort(begin(a) + 1, end(a)); // bugv(a); auto ok = [&](int x) { int cnt = 0; // bug2(1, x); for (int i = 1; i <= n;) { int j = i; cnt++; for (; j <= n && a[j] - a[i] <= x << 1; j++) ; i = j; // bug(i); } // bug2(2, cnt); return cnt <= 3; }; // ok(2); int l = -1, r = 1e9; while (r - l - 1) { int mid = l + r >> 1; if (ok(mid)) r = mid; else l = mid; } cout << r << '\n'; }

---

B #include <bits/stdc++.h> #define int long long using namespace std; #define bug(BUG) cout << "bug:# " << (BUG) << endl #define bug2(BUG1, BUG2) cout << "bug:# " << (BUG1) << " " << (BUG2) << endl #define bug3(BUG1, BUG2, BUG3) cout << "bug:# " << (BUG1) << ' ' << (BUG2) << ' ' << (BUG3) << endl #define bugv(VEC) \ { \ for (auto Vec : VEC) \ cout << Vec << ' '; \ cout << '\n'; \ } void _(); signed main() { ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); cout << fixed << setprecision(10); int T = 1; cin >> T; while (T--) _(); return 0; } void _() { int n; cin >> n; int st = 1; while (n % st == 0) st++; for (int i = 0; i < n; i++) cout << (char)('a' + i % st); cout << '\n'; }

---

C #include <bits/stdc++.h> #define int long long using namespace std; #define bug(BUG) cout << "bug:# " << (BUG) << endl #define bug2(BUG1, BUG2) cout << "bug:# " << (BUG1) << " " << (BUG2) << endl #define bug3(BUG1, BUG2, BUG3) cout << "bug:# " << (BUG1) << ' ' << (BUG2) << ' ' << (BUG3) << endl #define bugv(VEC) \ { \ for (auto Vec : VEC) \ cout << Vec << ' '; \ cout << '\n'; \ } void _(); signed main() { ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); cout << fixed << setprecision(10); int T = 1; cin >> T; while (T--) _(); return 0; } void _() { string s; cin >> s; int m; cin >> m; string l, r; cin >> l >> r; int st = 0; int n = s.size(); s = ' ' + s; for (int i = 0; i < m; i++) { int mx = st + 1; for (int j = l[i] - '0'; j <= r[i] - '0'; j++) { int t = st + 1; while (t <= n && j != s[t] - '0') t++; mx = max(mx, t); } st = mx; } cout << (st > n ? "YES" : "NO") << '\n'; }

---