include dfs bit ont ios sstream 限制 digi
题意:求 1~N 中含有 49 的数字个数。
- #include < cstdio > #include < cstring > #include < cstdlib > #include < cctype > #include < cmath > #include < iostream > #include < sstream > #include < iterator > #include < algorithm > #include < string > #include < vector > #include < set > #include < map > #include < stack > #include < deque > #include < queue > #include < list > #define lowbit(x)(x & ( - x)) const double eps = 1e-8;
- inline int dcmp(double a, double b) {
- if (fabs(a - b) < eps) return 0;
- return a > b ? 1 : -1;
- }
- typedef long long LL;
- typedef unsigned long long ULL;
- const int INT_INF = 0x3f3f3f3f;
- const int INT_M_INF = 0x7f7f7f7f;
- const LL LL_INF = 0x3f3f3f3f3f3f3f3f;
- const LL LL_M_INF = 0x7f7f7f7f7f7f7f7f;
- const int dr[] = {
- 0,
- 0,
- -1,
- 1,
- -1,
- -1,
- 1,
- 1
- };
- const int dc[] = { - 1,
- 1,
- 0,
- 0,
- -1,
- 1,
- -1,
- 1
- };
- const int MOD = 1e9 + 7;
- const double pi = acos( - 1.0);
- const int MAXN = 10000 + 10;
- const int MAXT = 10000 + 10;
- using namespace std;
- int digit[30];
- LL dp[30][2];
- LL dfs(int len, bool state, bool limit) { //len--当前位,从高到低枚举,state--上一位的状态,limit--当前位的数字是否有限制
- if (!len) return 1;
- if (!limit && dp[len][state] != -1) return dp[len][state]; //!limit--记录重复枚举的数的个数,以便记忆化搜索
- LL ans = 0,
- up = limit ? digit[len] : 9;
- for (int i = 0; i <= up; ++i) {
- if (state && i == 9) continue;
- ans += dfs(len - 1, i == 4, limit && i == up);
- }
- if (!limit) dp[len][state] = ans; //记录截止到当前位且当前位无限制时满足条件的数的个数
- return ans;
- }
- LL solve(LL x) {
- int cnt = 0;
- while (x) {
- digit[++cnt] = x % 10;
- x /= 10;
- }
- return dfs(cnt, false, true);
- }
- int main() {
- int T;
- scanf("%d", &T);
- memset(dp, -1, sizeof dp);
- while (T--) {
- LL N;
- scanf("%lld", &N);
- printf("%lld\n", N - (solve(N) - solve(0)));
- }
- return 0;
- }
HDU - 3555 Bomb(数位 dp)
来源: http://www.bubuko.com/infodetail-2164510.html