odd-even number
Problem Description
For a number,if the length of continuous odd digits is even and the length of continuous even digits is odd,we call it odd-even number.Now we want to know the amount of odd-even number between L,R(1<=L<=R<= 9*10^18).
Input
First line a t,then t cases.every line contains two integers L and R.
Output
Print the output for each case on one line in the format as shown below.
Sample Input
2 1 100 110 220
Sample Output
Case #1: 29 Case #2: 36
Source
Solution
题意:给出一段区间,求其中符合条件:【所有连续的奇数位(那一位的数字是奇数,而不是那一位的序号为奇数)的长度要是偶数,所有连续的偶数位的长度要是奇数】的数的个数。2,4,6,8这种满足条件;11也满足条件。
思路:难。一开始想三维,就是不行。参考了一下要这样开:LL dp[20][2][20][2];//第i位,上一位奇偶,连续位数,当前数是否有前导零
思路:难。一开始想三维,就是不行。参考了一下要这样开:LL dp[20][2][20][2];//第i位,上一位奇偶,连续位数,当前数是否有前导零
#include <set> #include <map> #include <list> #include <cmath> #include <stack> #include <queue> #include <ctime> #include <string> #include <cstdio> #include <vector> #include <cctype> #include <climits> #include <sstream> #include <cstring> #include <cstdlib> #include <iostream> #include <algorithm> #include <functional> #define ms(a) memset(a,0,sizeof(a)) typedef long long LL; const LL LINF = LLONG_MAX / 2; const int INF = INT_MAX / 2; const int MAXN = 150 + 10; const int MOD = 100000; int gcd(int a, int b) { if (!b)return a; return gcd(b, a%b); } using namespace std; //or2..or2..or2..or2..// int dig[20], len; LL dp[20][2][20][2];//第i位,上一位奇偶,连续位数,前导零 LL dfs(int pos, int pre = 0, int ln = 0, bool inf = 1, bool ze = 1)//pre 1为奇,0为偶 { if (!pos)//处理完最后一位 { if (pre)//最后一位是奇数,如果连续位数为偶数,则可行 return (ln & 1) == 0; //最后一位是偶数,如果连续位数为奇数,则可行 else return ln & 1; } //已经搜索过 if (!inf&&dp[pos][pre][ln][ze] != -1)return dp[pos][pre][ln][ze]; int en = inf ? dig[pos] : 9;//如果前面的位数小于dig[pos],inf就会为0,后面的数字可以任取 LL ans = 0; for (int i = 0; i <= en;i++) { if (i & 1)//奇数 { if (ze)//有前导零 { //如果还是放0,还是有前导零 if (!i)ans += dfs(pos - 1, 0, 0, inf&&i == en, 1); //如果放非0,而且是奇数,连续位数为1,没有前导零 else ans += dfs(pos - 1, 1, 1, inf&&i == en, 0); } else if (!pre)//上一位是偶数 { //连续位数为奇数的情况下满足条件 if (ln & 1)ans += dfs(pos - 1, 1, 1, inf&&i == en, ze); } //上一位是奇数 else ans += dfs(pos - 1, 1, ln + 1, inf&&i == en, ze); } else//偶数 { if (ze)//有前导零 { //如果还是放0,还是有前导零 if (!i)ans += dfs(pos - 1, 0, 0, inf&&i == en, 1); //如果放非0,而且是偶数,连续位数为1,没有前导零 else ans += dfs(pos - 1, 0, 1, inf&&i == en, 0); } //上一位是偶数 else if (!pre)ans += dfs(pos - 1, 0, ln + 1, inf&&i == en, ze); else { //上一位是奇数,连续位数为偶数时满足条件 if (!(ln & 1))ans += dfs(pos - 1, 0, 1, inf&&i == en, ze); } } } if (!inf)dp[pos][pre][ln][ze] = ans;//记录 return ans; } int main() { int T, cas = 1; LL l, r; cin >> T; while (T--) { memset(dp, -1, sizeof(dp)); scanf("%lld%lld", &l, &r), l--; for (len = 0; l; l /= 10)dig[++len] = l % 10; LL tp = dfs(len); for (len = 0; r; r /= 10)dig[++len] = r % 10; printf("Case #%d: %lld\n", cas++, dfs(len) - tp); } return 0; }
欢迎转载,请保留出处与链接。Ocrosoft » HDU 5898 odd-even number