Description
给定一个奇数n，可得到一个由从1到n的所有奇数所组成的数列，求这一数列中数字3所出现的总次数。例如当n=3时，可得到奇数列：1,3，其中有一个数字3，故可得1
Solution
\(f_{i,0/1}\)表示当前位是或者不是3, 后面有i位的时候答案是多少.
这个东西可以转移出来, 我是直接记忆化搜索的.然后就是怎么把\(n\)拆成若干个\(f_{i,0/1}\)的和,
这个东西比较复杂, 分成三种情况讨论,- 当前位大于3
- 当前位小于3
- 当前位等于3
其中当前为等于3的情况是最难处理的, 所以数据中特意有一个\(30033\)
然后又因为stringstream(字符串转整数, 因为要求出n的一个后缀的大小) 的语法问题debug了好长时候. 当然细节是非常非常多的.
Code
#include#include #include #include #include #include long long f[15][2];long long p10[15] = { 1, 5, 50, 500, 5000, 50000, 500000, 5000000, 50000000, 500000000, 50000000000ll};long long Get(int i, bool is) { if (i < 1) return is; if (f[i][is]) return f[i][is]; f[i][is] = 1ll * p10[i] * is + 9ll * Get(i - 1, 0) + Get(i - 1, 1); return f[i][is];}long long Get(long long num) { if (num >= 10 and num < 100) return num / 10; int p = 1; while (num > 2 * p10[p]) p += 1; p -= 1; while (num >= 2 * p10[p]) num -= 2 * p10[p]; return num;}int main () { long long n = 0, res = 0; while(std:: cin >> n) { std:: string str; str = std:: to_string(n); int siz = str.size() - 1; res = 0; int nn; for (int i = 0; i < str.size(); i += 1) { int p = i + 1; std:: stringstream sstr; std:: string sxs = str.substr(p, str.size() - p); sstr.str(sxs); sstr >> nn; if (str[i] > '3') res += (str[i] - '1') * Get(siz, 0) + Get(siz, 1); else if (str[i] < '3') res += (str[i] - '0') * Get(siz, 0); else res += 3 * Get(siz, 0) + (sxs.size() ? (nn / 2) + (nn % 2) : 1); siz -= 1; sstr.clear(); } std:: cout << res << '\n'; } return 0;}