I got that power
题目描述
每个人 都有自己独有的计数方式 比如以下 字符串111123455可以表示为4个1,1个2,1个3,1个4,2个5.为了方便记忆就表示为4–1,1–2,1–3,1–4,2–5当然顺序肯定不能变换 计数方式可以表示为“a–b”的形式 在计数方式中相连的b互不相等且a与b不为0 独有的计数方式 如果转化为字符串 字符串的长度小于10的9次方
给你下面的计数方式 例如5–4也就是字符串44444,10–4也就是字符串4444444444
给你这样的计数方式 判断这个字符串中有多少连续子串所构成的整数是4的倍数
例如5–4可表示为字符串44444里面共有(4,4,4,4,4,44,44,44,44,444,444,444,4444,4444,44444)15个是4的倍数;
输入
第一行是数字T(T<1000)
每一行一个独有的计数方式 长度小于100
输出
输出字符串中有多少个是4的倍数 占一行
样例输入
4
5–4
1–1,1–2
2–4,2–2,2–3
1–4,1–3,1–2,1–1
样例输出
15
1
3
3
思路
能被4整除的的数字分两种,个位数个多位数
个位数:4,8
多位数:只要个位加十位的数可以被4整除
可以判断每一位数字,如果本身可以被4整除ans++,如果加上前一个数可以被4整除,ans+=i如果数字过长,MLE,TLE。
所以可以有pre记录前面的数
判断能被N整除的字符串
看这里
AC
#include<bits/stdc++.h>#define ll long long#define mem(a, b) memset(a, b, sizeof(a)) #define N 100005#define P pair<ll, int>using namespace std;ll a[N], b[N];int main() {// freopen("in.txt", "r", stdin);ios::sync_with_stdio(false);string s;int n;cin >> n;while (n--) {cin >> s;int len = s.length();int now = 0; for (int i = 0; i < len; i++) {// int t = s[i] - '0';// t <= 9 && t >= 0if (isdigit(s[i])) {int sum = 0, num;while (i < len && s[i] != '-') {//手残 sum += sum * 10 + s[i] - '0';//一直WA sum = sum * 10 + s[i] - '0';i++;}i += 2;num = s[i] - '0';a[now] = sum;b[now] = num;now++;}}ll ans = 0, pre = a[0];if (b[0] % 4 == 0) ans += a[0];if (b[0] % 4 == 0 && a[0] > 1) {ans += (a[0] * a[0] - a[0]) / 2;}for (int i = 1; i < now; i++) {if (b[i] % 4 == 0) ans += a[i];if (b[i] % 4 == 0 && a[i] > 1) {ans += (2 * pre + a[i]) * (a[i] - 1) / 2;} if ((b[i] + 10 * (b[i - 1] - '0')) % 4 == 0) ans += pre;pre += a[i];}cout << ans << endl;} return 0;}