题解
知识点：模拟
时间复杂度 \(O(1)\)
空间复杂度 \(O(1)\)
代码
#include <bits/stdc++.h>
#define ll long long
using namespace std;
bool solve() {
int a, b, c;
cin >> a >> b >> c;
int x = a - 1;
int y = abs(b - c) + c - 1;
if (x > y) cout << 2 << '\n';
else if (x < y) cout << 1 << '\n';
else cout << 3 << '\n';
return true;
}
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--) {
if (!solve()) cout << -1 << '\n';
}
return 0;
}
B
题解
知识点：模拟。
倒着来，很方便。
时间复杂度 \(O(n)\)
空间复杂度 \(O(n)\)
代码
#include <bits/stdc++.h>
#define ll long long
using namespace std;
bool solve() {
int n;
cin >> n;
string T;
cin >> T;
string S;
for (int i = T.length() - 1;i >= 0;i--) {
if (T[i] == '0') {
S = (char)((T[i - 1] - '0') + (T[i - 2] - '0') * 10 + 'a' - 1) + S;
i -= 2;
}
else {
S = (char)(T[i] - '0' + 'a' - 1) + S;
}
}
cout << S << '\n';
return true;
}
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--) {
if (!solve()) cout << -1 << '\n';
}
return 0;
}
C
题解
知识点：贪心，枚举。
显然最小花费是 \(|s[n]-a[1]|\) ，最大化路线的方式是按序走过 \(s[1]\) 到 \(s[n]\) 的所有字母。
把每个字母的下标放进桶中 ， \(s[1]\) 比 \(s[n]\) 小则从 \(s[1]\) 正序，否则从 \(s[1]\) 倒序。
时间复杂度 \(O(n)\)
空间复杂度 \(O(n)\)
代码
#include <bits/stdc++.h>
#define ll long long
using namespace std;
bool solve() {
string s;
cin >> s;
int n = s.length();
s = "?" + s;
vector<vector<int>> v(26);
for (int i = 1;i <= n;i++) {
v[s[i] - 'a'].push_back(i);
}
int x = s[1] - 'a', y = s[n] - 'a';
if (x < y) {
int cnt = 0;
for (int i = x;i <= y;i++) {
cnt += v[i].size();
}
cout << abs(s[n] - s[1]) << ' ' << cnt << '\n';
for (int i = x;i <= y;i++)
for (auto j : v[i]) cout << j << ' ';
}
else {
int cnt = 0;
for (int i = x;i >= y;i--) {
cnt += v[i].size();
}
cout << abs(s[n] - s[1]) << ' ' << cnt << '\n';
for (int i = x;i >= y;i--)
for (auto j : v[i]) cout << j << ' ';
}
cout << '\n';
return true;
}
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--) {
if (!solve()) cout << -1 << '\n';
}
return 0;
}
D
题解
知识点：贪心，枚举，双指针。
处理出 \(y-x\) 得到每个成员的贡献，从小到大排序，最小的和最大的两人一组即可最大化分组数量，不能分配就跳过较小的。
时间复杂度 \(O(n)\)
空间复杂度 \(O(n)\)
代码
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int diff[100007];
bool solve() {
int n;
cin >> n;
for (int i = 1;i <= n;i++) cin >> diff[i];
for (int i = 1;i <= n;i++) {
int y;
cin >> y;
diff[i] = y - diff[i];
}
sort(diff + 1, diff + n + 1);
int ans = 0;
int l = 1, r = n;
while (l < r) {
if (diff[l] + diff[r] >= 0) ans++, r--;
l++;
}
cout << ans << '\n';
return true;
}
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--) {
if (!solve()) cout << -1 << '\n';
}
return 0;
}
E
题解
知识点：贪心。
\(i\) 从 \(2\) 开始依次询问。先询问 \((1,i)\) ，如果结果 \(-1\) 则输出 \(i-1\) ；否则，再询问一次 \((i,1)\) ，如果答案和 \((1,i)\) 不同则输出两个答案之和，否则继续下一个 \(i\) 。除去特判 \(n \in [3,25]\) 会因为询问到 \(-1\) 结束的情况，其他情况只需要一组答案不同即可，概率很高。
时间复杂度 \(O(1)\)
空间复杂度 \(O(1)\)
代码
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll query(ll a, ll b) {
cout << "? " << a << ' ' << b << endl;
ll ans;
cin >> ans;
return ans;
}
void answer(ll x) {
cout << "! " << x << endl;
exit(0);
}
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
for (int i = 2;i;i++) {
ll ans1 = query(1, i);
if (!~ans1) answer(i - 1);
ll ans2 = query(i, 1);
if (ans1 != ans2) answer(ans1 + ans2);
}
return 0;
}
F
题解
知识点：枚举，前缀和，数论。
注意到一个数字 \(\mod 9\) 的答案和所有数位加起来 \(\mod 9\) 的答案相同，因此先对 \(s\) 数位预处理模意义前缀和。
然后处理出所有 \(w\) 长度的串的余数，把串首坐标放进桶中对应余数的位置，只需要存两个最左边的即可。
对于每组询问，遍历余数 \(a,b\) 满足 \(a \cdot re + b \equiv k \pmod 9\) ，其中 \(re\) 为 \([l,r]\) 的余数。将余数 \(a,b\) 对应的串下标更新一下答案即可，答案可以用 pair 存，方便更新。注意特判 \(a = b\) 的情况，需要同一个余数的前两个下标。
时间复杂度 \(O(n+m)\)
空间复杂度 \(O(n)\)
代码
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int a[200007];
bool solve() {
string s;
cin >> s;
int n = s.length();
s = "?" + s;
for (int i = 1;i <= n;i++) a[i] = (s[i] - '0' + a[i - 1]) % 9;
int w, m;
cin >> w >> m;
vector<vector<int>> pos(9);
for (int i = w;i <= n;i++) {
int re = (a[i] - a[i - w] + 9) % 9;
if (pos[re].size() < 2) pos[re].push_back(i - w + 1);
}
while (m--) {
int l, r, k;
cin >> l >> r >> k;
int re = (a[r] - a[l - 1] + 9) % 9;
pair<int, int> ans = { n + 1,n + 1 };
for (int i = 0;i <= 8;i++) {
if (pos[i].empty()) continue;
for (int j = 0;j <= 8;j++) {
if (pos[j].empty()) continue;
if ((i * re + j) % 9 == k) {
if (i != j) ans = min(ans, { pos[i][0],pos[j][0] });
else if (i == j && pos[i].size() == 2) ans = min(ans, { pos[i][0],pos[i][1] });
}
}
}
if (ans > pair<int, int>{n, n}) cout << -1 << ' ' << -1 << '\n';
else cout << ans.first << ' ' << ans.second << '\n';
}
return true;
}
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--) {
if (!solve()) cout << -1 << '\n';
}
return 0;
}
G
题解
知识点：线性dp。
预处理出 \(s\) 中所有能删除 \(t\) 的下标，暴力 \(O(n^2)\) 处理即可，存进 vector 。随后dp一下前 \(i\) 个能删除位置的最小删除次数。
设 \(f[i]\) 为考虑到第 \(i\) 个能删除的位置，删除 \([1,v[i]]\) 所有能删除的段，且一定删除第 \(i\) 段的最小删除次数。设 \(tot[i]\) 为能够达成 \(f[i]\) 删除次数的对应的方案数。
对于 \(v[i]\) ，我们枚举上一个删除的位置 \(v[j]\) ，先保证 \(i,j\) 不重合即 \(v[i]-v[j]\geq m\) ，然后保证 \(i,j\) 中间没有别的能删除的段即 $v[k] - v[j] < m $ 以及 $ v[i] - v[k] < m$ 。于是可以转移：
if (f[i] > f[j] + 1) {
f[i] = f[j] + 1;
tot[i] = tot[j];
}
else if (f[i] == f[j] + 1) {
tot[i] = (tot[i] + tot[j]) % mod;
}
最后统计末尾重合的一段的最小删除次数，以及对应的总方案数。
时间复杂度 \(O(nm^2)\)
空间复杂度 \(O(n)\)
代码
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int mod = 1e9 + 7;
bool solve() {
string s, t;
cin >> s >> t;
int n = s.size(), m = t.size();
s = "?" + s;
vector<int> v;
v.push_back(0);
for (int i = m;i <= n;i++)
if (s.substr(i - m + 1, m) == t) v.push_back(i);
vector<int> f(507, 0x3f3f3f3f), tot(507, 0);
f[0] = 0, tot[0] = 1;
for (int i = 1;i < v.size();i++) {
for (int j = i - 1;j >= 0;j--) {
if (v[i] - v[j] < m) continue;
bool ok = 1;
for (int k = j + 1;k < i;k++) ok &= v[k] - v[j] < m || v[i] - v[k] < m;
if (!ok) break;
if (f[i] > f[j] + 1) {
f[i] = f[j] + 1;
tot[i] = tot[j];
}
else if (f[i] == f[j] + 1) {
tot[i] = (tot[i] + tot[j]) % mod;
}
}
}
int mi = n, ans = 0;
for (int i = 0;i < v.size();i++) if (v.back() - v[i] < m) mi = min(mi, f[i]);
for (int i = 0;i < v.size();i++) if (v.back() - v[i] < m && f[i] == mi) ans = (ans + tot[i]) % mod;
cout << mi << ' ' << ans << '\n';
return true;
}
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--) {
if (!solve()) cout << -1 << '\n';
}
return 0;
}