[牛客暑期多校第四场][思维]K-Number

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

签到题 本场就做出来这一道题 菜的一比

zzq给的题解中的第二种做法并不能看懂
网上搜的题解的思路感觉比较好 在这里写一下

这是题解给的做法 下面那个做法的确是最快的
思路看一下注释吧

拿样例二模拟一下试试看
123000321013200987000789
先求mod
100000020011000020000100
遇到两个连续0更新答案
遇到第一个连续0时 num数组值分别为 3 1 0
ans=3
遇到第二个连续0时 num数组值分别为 4 1 0
ans=7
第三次 10 3 1
ans=17
第四次 14 3 2
ans=31
第五次 15 3 2
ans=46
加上9个0 答案是55

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 5;
char s[maxn];
int num[3], n, mod;
ll ans;
int main() {
scanf(“%s”, s + 1);
ans = 0;
n = strlen(s + 1);
num[0] = 1;//初始值 如果是3的倍数 那么就能贡献一个答案
num[1] = num[2] = 0;//不是三的倍数就不能贡献答案
mod = 0;
for (int i = 1; i <= n; i++) {
mod = (mod * 10 + (s[i] - ‘0’)) % 3;//求总和是不是3的倍数
if (s[i] == ‘0’ && s[i + 1] == ‘0’) {//如果碰到两个连续0 更新答案
ans += num[mod];
}
num[mod]++;
if (s[i] == ‘0’) ans++;//如果是‘0’ 答案要加1
}
printf(“%lld\n”, ans);
return 0;
}

uncategorized > 牛客竞赛
[牛客暑期多校第四场][思维]K-Number
https://47.97.0.163/2019/07/29/牛客暑期多校第四场思维k-number/
作者
John Doe
发布于
2019年7月29日
许可协议