NowCoder.Number

题目描述

链接:https://ac.nowcoder.com/acm/contest/884/K

One day he got a string consisted of numbers. He wants to know how many substrings in the string are multiples of 300 when considered as decimal integers.

Note that leading and trailing zeros are allowed (both in original string and substrings you chose) and the same substring appearing in different places can be counted multiple times.

输入描述:

A single line consisting a string consisted of characters ‘0’ to ‘9’.

输出描述:

The number of substrings that are multiples of 300 when considered as decimal integers.

样例输入:

600

样例输出:

4

说明:

‘600’, ‘0’, ‘0’, ‘00’ are multiples of 300. (Note that ‘0’ are counted twice because it appeared two times)

备注:

let the string in the input be s, 1≤∣s∣≤10^5 .

问题分析:

因为n^2复杂度在10^5条件下肯定会T,所以排除朴素的求前缀和。

想到二分去做,但是因为要保证子串的有序性,也不可以。

Solve A: O(n)复杂度

这里想到正序和逆序,人工筛选的办法肯定是从后向前筛选,例如333300会先筛选0、0、00、300、3300,33300,333300,在保证00的条件下3333筛了四遍,推广到前缀和的N^2复杂度是肯定不可行的,所以考虑正序——保存前 i 个数正确顺序的条件下,在求第 i + 1 项时直接引用第 i 项的数。

w[i]为前 i 项的和 mod 3的值,对于长度 >=2 的区间 [l,r] 内 只要 w[ l - 1 ] = w[ r ] 且 w [ r - 1 ] , w [ r ]为 0 即满足

也就是说,当 s [i] = 0 时,ans+1,当 s [ i - 1 ] == s [ i ]时,ans+= ( i 之前有多少能满足的条件数目)其中 cn [x] 数组代表出现了多少次 mod3 = x的情况,即 i 时刻 cn [ 0 ] 为 i 之前有多少 满足能被300整除的组合数。

你可能会问,为什么不直接写 ans += cn[0]? 形如78900 w[i]为22222,也就是说不满足前面一串能形成300的倍数的条件时这一串是不被二次计算的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define maxx 100005
char s[maxx]; int n,w[maxx],cn[3];
int main()
{
scanf("%s",s+1); n=strlen(s+1);
for(int i=1;i<=n;++i)
w[i]=(w[i-1]+s[i])%3;

ll ans=0;

for(int i=1;i<=n;++i)
{
if(s[i]=='0')
{
++ans;
if(s[i-1]=='0')
ans+=cn[w[i]];
}
cn[w[i-1]]++;
}
printf("%lld\n",ans);
return 0;
}

Solve B:前缀和+剪枝

Solve C:动态规划