明明是很容易的题模拟赛却没注意到。
数学、模拟
题意
略。
思路
不妨从 \(5\) 下手。一数仅当最后一位是 \(0\) 或 \(5\) 时，该数才是 \(5\) 的倍数。因此如果第 \(i\) 位是 \(0\) 或 \(5\)，所有最后一位是 \(5\) 的连续子串都满足条件，子串数量 \(+i\)。
同理，由于 \(100\) 是 \(4\) 的倍数，所以一数只需后两位是 \(4\) 的倍数，该数就是 \(4\) 的倍数。因此如果第 \(i\) 与 \(i-1\) 位构成了 \(4\) 的倍数，则所有以此两位结尾的子串也都满足条件，子串数量 \(+i-1\)。特别地，当第 \(i\) 位或第 \(i-1\) 位是 \(4\) 或 \(8\) 时，这两位也应参与计数。
考虑一个更优化的做法。一个两位数是 \(4\) 的倍数有两种情况：末位为 \(2\)、\(6\) 和末位为 \(4\)、\(8\)。通过观察不难得出，第一种情况仅十位是奇数时成立，第二种情况仅十位是偶数时成立。这样在代码求解时会更简洁。
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#define int long long
using namespace std;
const int N=1e6+10;
int n,ans;
char s[N];
signed main(){scanf("%s",s+1);n=strlen(s+1);for(int i=1;i<=n;i++){if(s[i]=='0'||s[i]=='5') ans+=i;else if(s[i]=='4'||s[i]=='8'){if((s[i-1]-'0')%2) ans+=1;else ans+=i;}else if(s[i]=='2'||s[i]=='6'){if((s[i-1]-'0')%2) ans+=i-1;} }printf("%lld\n",ans);return 0;
}
时间复杂度 \(O(n)\)。