首页 > 试题广场 >

小苯的子串删除

[编程题]小苯的子串删除
  • 热度指数：515 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
\,\,\,\,\,\,\,\,\,\,小苯有一个长度为 n 的数字串 s，他想要将 s 变为 3 的倍数。为此，他可以进行最多一次操作：
\,\,\,\,\,\,\,\,\,\,\,\,\,\,\bullet\,选择一段区间 [l, r]\ (1 \leq l \leq r \leq n)，删除 s_l, s_{l+1}, \dots, s_r 这一段数位。
\,\,\,\,\,\,\,\,\,\,他想知道有多少种不同的删除区间方案，使得 s 是 3 的倍数。请你帮帮他吧。

输入描述:
\,\,\,\,\,\,\,\,\,\,第一行输入一个整数 n\left(1 \leq n \leq 2\times 10^5\right)，表示字符串长度。
\,\,\,\,\,\,\,\,\,\,第二行输入一个长度为 n 且仅包含数字的字符串 s 。


输出描述:
\,\,\,\,\,\,\,\,\,\,在一行上输出输出一个整数，表示不同的删除方案数。
示例1

输入

4
1233

输出

7

说明

\,\,\,\,\,\,\,\,\,\,如果选择进行操作，则可能删除的区间有：
\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,● [1, 2]，则剩余 "\tt 33" ，满足是 3 的倍数。
\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,● [3, 3]，剩余 "\tt 123" ，满足是 3 的倍数。
\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,● [1, 3]，剩余 "\tt 3" ，满足是 3 的倍数。
\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,● [4, 4]，剩余 "\tt 123" ，满足是 3 的倍数。
\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,● [3, 4]，剩余 "\tt 12" ，满足是 3 的倍数。
\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,● [1, 4]（全部删除）则剩余 "\tt 0" ，也满足是 3 的倍数。
\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,● 不进行操作，则剩余 "\tt 1233" ，也是 3 的倍数。
\,\,\,\,\,\,\,\,\,\,则共有七种删除方案（注意，不删除/全删除也是删除方案）。
算法知识视频讲解
开通博客
头像 丨阿伟丨
发表于 2025-09-12 17:54:03
题目链接 https://www.nowcoder.com/practice/40de22ffa68740cca2193b3c9aa8fc7a 思路分析 1. 问题转换与核心性质 题目要求我们计算有多少种删除连续子串的方案，使得剩余数字串代表的数是 3 的倍数。 一个众所周知的数学性质是：一个数是 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

数组 前缀和 基础数学 阿里云
难度：
4条回答 946浏览

热门推荐

相关试题

小苯的子串删除

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号