题目链接：https://ac.nowcoder.com/acm/contest/338/F
题意：就是让你统计1~n中包含520的数的个数，n<= 1e18
思路：数位DP中比较简单的了，dp[pos][pre1][pre2]代表着第pos位，前缀是pre1和pre2的不包含520的个数，最后用总数减去包含520的个数就是答案。
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; typedef long long ll; #define ls rt << 1 #define rs rt << 1|1 #define mid ((l + r) >> 1) #define lson l, mid, ls #define rson mid + 1, r, rs const int maxn = 20; const int mod = 1e9 + 7; ll dp[maxn][12][12]; int a[maxn]; ll dfs(int pos, int pre1, int pre2, int lead, int limit) { if(pos == 0) return 1; if(!limit && ! lead && dp[pos][pre1][pre2] != -1) return dp[pos][pre1][pre2]; int up = limit ? a[pos] : 9; ll ret = 0; for(int i = 0; i <= up; ++i) { if(pre1 == 5 && pre2 == 2 && i == 0) continue; ret += dfs(pos - 1, pre2, i, lead && (i == 0), limit && (i == up)); } if(!limit && !lead) dp[pos][pre1][pre2] = ret; return ret; } ll slove(ll x) { int tot = 0; while(x) { a[++tot] = x % 10; x /= 10; } memset(dp, -1, sizeof(dp)); return dfs(tot, 0, 0, 1, 1); } int main() { int t; scanf("%d", &t); while(t--) { ll n; scanf("%lld", &n); ll ans = n - slove(n) + 1; printf("%lld\n", ans); } return 0; }
