Div. 3 Codeforces Round #820 A-G( 二 ) _生活百科

pair存，方便更新。注意特判 $a = b$ 的情况，需要同一个余数的前两个下标。
时间复杂度 $O(n+m)$
空间复杂度 $O(n)$
代码#include <bits/stdc++.h>#define ll long longusing 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 longusing 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;}

Div. 3 Codeforces Round #820 A-G( 二 )

推荐阅读

【健康知识】10斤大蒜放多少糖和醋糖醋蒜可以用塑料瓶腌制吗!

查违章电话12580 查询违章电话号码

2022年做啥生意好挣钱未来最挣钱的十大行业排行榜

社会学对当今中国的作用有哪些社会学对当今中国的作用

中山泉林欢乐世界大门票是多少钱中山泉林欢乐世界游玩指南

减肥是先做器械还是先跑步慢跑多快速度可以减肥

伪装微信地理位置会不会封号

华为nova5怎么拍慢动作视频

这些建议要留心下眼袋有细纹怎么办

cad制图如何标注尺寸公差 cad制图如何标注尺寸

什么叫创业创业意识是什么怎么进行创业？创业又是什么？

2023东莞松山湖园区第二轮补录民办学校名单

科三考试项目介绍科目三步骤技巧

糕粉糕粉馅料做法

cp在游戏里是什么意思呀 cp在游戏里是什么意思

男生会陪没兴趣的人聊天吗，聊天聊久了会动情吗

无线经常掉线怎么回事-手机无线老是掉线怎么回事-一览大全

红豆小米红枣粥的营养价值丰富,经常食用后可有补血益气的功效红豆小米红枣粥的功效与作用

邻居噪音扰民怎么办？噪音扰民怎么处理

如何知道自己的姻缘何时到，请问我的姻缘何时到？