当前位置: 首页 > news >正文

16 LCA模拟赛1T1 密码 题解

密码

题面

给定两个由字符 \(0 \sim 9\) 组成的字符串 \(s, t\)\(t\) 是由 \(s\) 中的一段非空连续子串替换为其各个字符的和得到的

现在要求这一段非空连续子串的左右端点,下标从 1 开始

例如

input:
2148
213
output:
2 4

\(1 \le |s| \le 10^5\)

题解

这道题其实还算比较简单,不过我码力太弱,导致赛时写了1.5h

一个关键的观察:替换后的字符和长度不会超过 6 ,因为最多 \(10^5\) 个数,每个数最大是 \(9\) 那么最大数字和就是 \(9 \times 10^5\) 也就是 6 位

那么我们将 \(t\) 分成三段,前面不变的一段,中间被替换的段,后面不变的一段

假如我们知道了中间段的长度,那么也就能够推出 \(s\) 中的左右端点

我们只需要判断前面、后面两个字符串是否相等,以及 \(s\) 中被替换的一段替换后是否和我们枚举的这一段匹配即可

判断前后缀是否相等,可以预处理。快速求 \(s\) 中某一段的区间和,可以用前缀和算

时间复杂度 \(O(36 n)\) 如果交换一下枚举顺序,先枚举左端点,再枚举 \(len\) ,就可以省去一个 6 的常数

code

优化后代码,要注意前导零问题

namespace solution_a {const int N = 1e5 + 10;int n, m;char s[N], t[N];bool pre[N], suc[N];int sum[N];void solve () {scanf ("%s%s", s + 1, t + 1);n = strlen (s + 1), m = strlen (t + 1);for (int i = 1; i <= n; i ++) {sum[i] = sum[i - 1] + s[i] - '0';}// 预处理 pre & sucint p = 1;while (p <= m && s[p] == t[p]) pre[p ++] = 1;p = 1;while (p <= m && s[n - p + 1] == t[m - p + 1]) suc[p ++] = 1;pre[0] = suc[0] = 1;// 枚举,计算for (int l = 1; l <= m; l ++) {int sm = 0;for (int r = l; r <= min (l + 5, m); r ++) {if (r > l && !sm) break; // t 中被替换的这段数不能含有前导零sm = sm * 10 + t[r] - '0';if (suc[m - r] && pre[l - 1] && sm == sum[n - (m - r)] - sum[l - 1]) {cout << l << ' ' << n - (m - r) << endl;return;}}}}}

赛时代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>using namespace std;const int N = 1e5 + 10;int n, m;
char s[N], t[N];
bool pre[N], suc[N];
int sum[N];int main () {// freopen ("password.in", "r", stdin);// freopen ("password.out", "w", stdout);scanf ("%s%s", s + 1, t + 1);n = strlen (s + 1), m = strlen (t + 1);for (int i = 1; i <= n; i ++) {sum[i] = sum[i - 1] + s[i] - '0';}for (int i = 1; i <= m; i ++) {if (s[i] == t[i]) pre[i] = 1;else {break;}}for (int i = n, j = m, cnt = 1; j >= 1 && i >= 1; i --, j --, cnt ++) {if (s[i] == t[j]) suc[cnt] = 1;else {break;}}pre[0] = suc[0] = 1;for (int len = 1; len <= 10; len ++) {for (int l = 1; l + len - 1 <= m; l ++) {int r = l + len - 1;int pw = 0;char tmp[20];int x = sum[n - (m - r)] - sum[l - 1];if (!x) {tmp[ ++ pw] = '0';} else {while (x) {tmp [ ++ pw] = x % 10 + '0';x /= 10;}reverse (tmp + 1, tmp + 1 + pw);}if (!suc[m - r] || !pre[l - 1]) continue;bool ok = 1;for (int j = 1; j <= pw; j ++) {if (tmp[j] != t[l + j - 1]) {ok = 0;break;}}if (ok) {cout << l << ' ' << n - (m - r) << endl;return 0;}}        }return 0;
}
http://www.hskmm.com/?act=detail&tid=25005

相关文章:

  • 吴恩达深度学习课程一:神经网络和深度学习 第二周:神经网络基础(一)
  • 阿里开源规则引擎QLExpress
  • QOJ7411 Bitwise Xor
  • 完整教程:SOC-ESP32S3部分:25-HTTP请求
  • 为什么要采用“接口 - 抽象类 - 实现类”这种三层结构? - 浪矢
  • 对外提供 AI 服务的风险:合规视角与 AI 安全围栏落地指南
  • VScode C/C++ 汉化 竞赛版 只需下载扩展 (超简单)
  • 网络安全工具与社区讨论月报
  • 机器人运动未来与人机交互研究
  • 欧拉路径 欧拉图 小记
  • OI 笑传 #16
  • cf296b
  • 第一次使用Ttpora
  • Apache反向代理
  • 原版 Sunshine+虚拟显示器实现熄屏串流
  • 2025国庆Day4
  • gis坐标计算
  • day17 课程()
  • NKOJ全TJ计划——NP11744
  • ROIR 2025
  • trick 小记
  • python编写AI生常用匡架及使用指令集
  • 123123
  • 1005模拟赛总结
  • 2025.10.5 2024CCPC郑州
  • 20250531MATLAB三维绘图 - 教程
  • 概率期望dp 复习笔记
  • 2025.10
  • PCIe扫盲——物理层逻辑部分基础(一)
  • 仅需3%训练数据的文本归一化技术