2026夏个人训练赛第二十四场
A. 贪吃巧克力
直接两边同时模拟。
cpp
#include <iostream>
using namespace std;
typedef long long LL;
const int N = 1000010;
LL a[N];
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int _; cin >> _;
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
}
int l = 1, r = n;
for (int i = 1; i <= m; ++i) {
LL p, x;
int j, k = r - l + 1;
cin >> p >> x;
bool f = false;
for (j = 0; j <= r - l; ++j) {
LL lx = a[l + j] * (a[l + (j + p) % k]);
LL rx = a[l + k - j - 1] * a[l + (k - j - 1 + p) % k];
if (lx == x) {
cout << "L " << j + 1 << '\n';
l += j + 1;
f = true;
break;
}
else if (rx == x) {
cout << "R " << j + 1 << '\n';
r -= j + 1;
f = true;
break;
}
}
if (!f) cout << "F\n";
}
return 0;
}B. 好串串
考虑从左到右枚举当前位置为结尾的好串，发现只能是一种包含两个以上不同字符的串，和所有相邻的相同字符的串。对于第一个预处理一个左侧的下标（极大的好串是一定不会互相包含，而且即使重叠重叠的部分分给哪边都是一样的，所以可以 O(n) 预处理），对于第二个 DP 的时候按段维护一下前缀 min.
cpp
#include <iostream>
using namespace std;
const int N = 5000010;
int f[N], g[N];
int tr[N * 4];
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int _, T;
cin >> _ >> T;
while (T--) {
string s;
cin >> s;
int n = s.length();
s = " " + s;
fill(f, f + n + 1, n);
fill(g, g + n + 1, n + 1);
f[0] = 0;
for (int i = 1; i <= n; ) {
int j = i;
while (j <= n && s[j + 1] == s[i]) j++;
int l = i - 1, r = j + 1;
while (l >= 1 && r <= n && s[l] == s[r] && s[l] <= s[l + 1]) {
g[r] = min(g[r], l);
l--, r++;
}
i = r;
}
int pre = 0;
for (int i = 1; i <= n; ++i) {
if (s[i] == s[i - 1]) pre = min(pre, f[i - 1]);
else pre = f[i - 1];
f[i] = pre + 1;
if (g[i] < i) f[i] = min(f[i], f[g[i] - 1] + 1);
}
cout << f[n] << '\n';
}
return 0;
}C. 行走
暴力所有的约数。
cpp
#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 1010;
bool vis[N][N];
int a[N][N];
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int n, v, res = 1;
cin >> n >> v;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) cin >> a[i][j];
}
v = a[1][1];
int l = sqrt(v);
vector<int> s = {v};
for (int i = 2; i <= l; ++i) {
if (v % i == 0) {
s.emplace_back(i);
if (i * i != v) s.emplace_back(v / i);
}
}
sort(s.begin(), s.end(), greater<int>());
for (int t : s) {
fill(vis[0], vis[0] + N * N, false);
queue<pair<int, int>> q;
q.emplace(1, 1);
vis[1][1] = true;
while (!q.empty()) {
auto [x, y] = q.front();
q.pop();
if (x == n && y == n) {
res = t;
break;
}
if (x < n && a[x + 1][y] % t == 0 && !vis[x + 1][y]) vis[x + 1][y] = true, q.emplace(x + 1, y);
if (y < n && a[x][y + 1] % t == 0 && !vis[x][y + 1]) vis[x][y + 1] = true, q.emplace(x, y + 1);
}
if (res == t) break;
}
cout << res << '\n';
return 0;
}E. 真实排名
特判一下 0，因为翻倍也无效。对于任意一个
- 不翻倍，那么比他大的和严格小于
的里面任选 k 个即可。 - 翻倍，那么
都需要翻倍，假设固定要翻倍 t 个，在剩下的里面再任选 k - t 个即可。
cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long LL;
const int MOD = 998244353;
const int N = 100010;
LL fac[N], inv[N];
LL power(LL n, LL p) {
LL res = 1, base = n;
while (p) {
if (p & 1) res = res * base % MOD;
base = base * base % MOD;
p >>= 1;
}
return res;
}
void init() {
int n = 100000;
fac[0] = inv[0] = 1;
for (int i = 1; i <= n; ++i) fac[i] = fac[i - 1] * i % MOD;
inv[n] = power(fac[n], MOD - 2);
for (int i = n - 1; i; --i) inv[i] = inv[i + 1] * (i + 1) % MOD;
}
LL comb(LL n, LL m) {
if (n < m) return 0;
return fac[n] * inv[m] % MOD * inv[n - m] % MOD;
}
vector<LL> values;
LL a[N], s[N], res[N], m;
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
init();
int n, k;
cin >> n >> k;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
values.emplace_back(a[i]);
}
sort(values.begin(), values.end());
values.erase(unique(values.begin(), values.end()), values.end());
m = values.size();
for (int i = 1; i <= n; ++i) {
s[lower_bound(values.begin(), values.end(), a[i]) - values.begin() + 1] ++;
}
for (int i = 1; i <= m; ++i) {
s[i] += s[i - 1];
}
for (int i = 1; i <= m; ++i) {
if (values[i - 1] == 0) {
res[i] = comb(n, k);
continue;
}
LL cur = 0;
// no
int big = s[m] - s[i - 1] - 1, small = s[upper_bound(values.begin(), values.end(), values[i - 1] - 1 >> 1) - values.begin()];
cur = comb(big + small, k);
// yes
int t = s[lower_bound(values.begin(), values.end(), values[i - 1] * 2) - values.begin()] - s[i - 1];
if (k >= t) cur = (cur + comb(n - t, k - t)) % MOD;
res[i] = cur;
}
for (int i = 1; i <= n; ++i) {
cout << res[lower_bound(values.begin(), values.end(), a[i]) - values.begin() + 1] << '\n';
}
return 0;
}F. 甲苯先生的字符串
只有相邻两位有约束，而且是线性的，直接矩阵快速幂
cpp
#include <iostream>
#include <cstring>
using namespace std;
typedef long long LL;
const int N = 26;
const int MOD = 1000000007;
LL a[N][N], b[N][N];
LL v1[N], v2[N];
void mul1() {
memset(v2, 0, sizeof(v2));
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
v2[i] = (v2[i] + v1[j] * a[j][i]) % MOD;
}
}
memcpy(v1, v2, sizeof(v1));
}
void mul2() {
memset(b, 0, sizeof(b));
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
for (int k = 0; k < N; ++k) {
b[i][j] = (b[i][j] + a[i][k] * a[k][j]) % MOD;
}
}
}
memcpy(a, b, sizeof(a));
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
LL p;
string s;
cin >> p >> s;
fill(a[0], a[0] + N * N, 1);
fill(v1, v1 + N, 1);
for (int i = 1; i < s.length(); ++i) {
a[s[i - 1] - 'a'][s[i] - 'a'] = 0;
}
p--;
while (p) {
if (p & 1) mul1();
mul2();
p >>= 1;
}
LL res = 0;
for (int i = 0; i < N; ++i) res = (res + v1[i]) % MOD;
cout << res << '\n';
return 0;
}其他没做的题
- 构造题
- Eddy Walker
- Eddy Walker 2
- Go on Strike!
- Kth Minimum Clique
- MAZE