CF2276E.Good Substrings
普及+/提高
通过率:0%
时间限制:2.00s
内存限制:512MB
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
You are given a string s of length n, consisting only of digits.
A substring of s is a contiguous subsequence of its characters. A substring sl…r is bad if it contains the string 2025 as a subsequence and doesn't contain the string 2026 as a subsequence. Otherwise, the substring is good. For example, the strings 2025, 72707275, 20625 are bad, but the strings 20256, 2026, 777, 1290723576 are good.
For each index i from 1 to n, calculate the number of good substrings that contain it. In other words, for each index i from 1 to n, calculate the number of pairs of integers l,r such that 1≤l≤i≤r≤n and the substring sl…r is good.
给你一个长度为 n 的字符串 s,其中仅包含数字字符。
s 的一个子串是指其字符的一个连续子序列。若子串 sl…r 包含字符串 2025 作为子序列,且不包含字符串 2026 作为子序列,则称该子串为坏的;否则,该子串为好的。例如,字符串 2025、72707275、20625 是坏的,而字符串 20256、2026、777、1290723576 是好的。
对每个从 1 到 n 的下标 i,计算包含位置 i 的好子串的个数。换言之,对每个从 1 到 n 的下标 i,计算满足 1≤l≤i≤r≤n 且子串 sl…r 为好的整数对 (l,r) 的个数。
输入格式
The first line contains a single integer t (1≤t≤104) — the number of test cases.
The first line of each test case contains a single integer n (1≤n≤3⋅105).
The second line contains a string s of length n, consisting of digits.
Additional constraint on the input: the sum of n across all test cases does not exceed 3⋅105.
第一行包含一个整数 t(1≤t≤104)——测试用例的数量。
每个测试用例的第一行包含一个整数 n(1≤n≤3⋅105)。
第二行包含一个长度为 n 的字符串 s,由数字组成。
输入的额外约束:所有测试用例的 n 之和不超过 3⋅105。
输出格式
For each test case, print n integers. The i-th integer should be equal to the number of good substrings that contain index i.
对于每个测试用例,输出 n 个整数。其中第 i 个整数应等于包含下标 i 的“好”子串的数量。
输入输出样例
输入#1
2 6 202516 5 20265
输出#1
4 8 10 10 9 6 5 8 9 8 5
说明/提示
null
输入解题思路,AI测评打分。不知道怎么写?