比赛链接

A

题解

知识点:模拟

时间复杂度 \(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;
}

最新文章

  1. LR破解版录制手机脚本(一)模拟器录制
  2. Git版本库
  3. SegmentControl的多选项实现(标题栏)
  4. 深入研究C语言 第一篇
  5. js 函数声明方式以及javascript的历史
  6. arcgis地图操作的资料URL,以供以后查阅
  7. 【原创】tcp协议那块一些点(想到了再加)
  8. poj2594 (最小路径覆盖 + floyd)
  9. IS-IS完整笔记
  10. I/P/B/SI/SP帧和PTS/DTS的关系
  11. APP瘦身绝技(快速减少包大小)
  12. Linux查看日志方法总结(1)
  13. hdu4811-Ball(2013ACM/ICPC亚洲区南京站现场赛)
  14. 将.rpm转换为.tar.gz
  15. K-DTree学习
  16. 外网訪问XAMPP失败 解决方式 XAMPP1.8.3
  17. 锯齿状优惠券css绘制
  18. 温度转换-python
  19. search 重要文件路径 搜索【原】
  20. javascript随笔和常见的知识点

热门文章

  1. Java SE 11 新增特性
  2. RabbitMQ 入门系列:2、基础含义理解:链接、通道、队列、交换机
  3. 从零开始Blazor Server(15)--总结
  4. C#基础_XML文件介绍
  5. 记录一次数据库CPU被打满的排查过程
  6. 第五十三篇:Vue安装Element ui
  7. 第二十四篇:对于dom的理解
  8. 【设计模式】Java设计模式 - 动态代理
  9. C/C++ Capstone 引擎源码编译
  10. 使用docker-compose.yml安装rabbitmq集群