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; }

總結

以上是生活随笔為你收集整理的2049 : 压死骆驼的最后一根稻草 （规律）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。