https://blog.csdn.net/wust_zzwh/article/details/52100392
讲的好的博客。
https://cn.vjudge.net/contest/302933#problem/B
这道题要用减法，
前导零不排除的模板
题目给了个f(x)的定义：F(x) = An * 2n-1 + An-1 * 2n-2 + ... + A2 * 2 + A1 * 1，Ai是十进制数位，然后给出a,b求区间[0,b]内满足f(i)<=f(a)的i的个数。
常规想：这个f(x)计算就和数位计算是一样的，就是加了权值，所以dp[pos][sum]，这状态是基本的。a是题目给定的，f(a)是变化的不过f(a)最大好像是4600的样子。如果要memset优化就要加一维存f(a)的不同取值，那就是dp[10][4600][4600]，这显然不合法。
这个时候就要用减法了，dp[pos][sum]，sum不是存当前枚举的数的前缀和(加权的)，而是枚举到当前pos位，后面还需要凑sum的权值和的个数，
也就是说初始的是时候sum是f(a),枚举一位就减去这一位在计算f(i)的权值，那么最后枚举完所有位 sum>=0时就是满足的，后面的位数凑足sum位就可以了。
仔细想想这个状态是与f(a)无关的(新手似乎很难理解)，一个状态只有在sum>=0时才满足，如果我们按常规的思想求f(i)的话，那么最后sum>=f(a)才是满足的条件。
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N = 12; int dp[N][5000]; int pw[N]; int num[N]; int ans; int ca = 0; void init() { pw[0] = 1; for(int i = 1; i < 12; i++) { pw[i] = pw[i - 1] * 2; } } int dfs(int pos, int sum, bool lim) { if(pos == -1) { return ans - sum >= 0; } if(sum > ans) return 0; int up = lim ? num[pos] : 9; int res = 0; if(!lim && dp[pos][ans - sum] != -1) return dp[pos][ans - sum]; for(int i = 0; i <= up; i++) { res += dfs(pos - 1, sum + i * pw[pos], lim && i == num[pos]); } if(!lim) dp[pos][ans - sum] = res; return res; } void solve(int n, int m) { ans = 0; int cnt = 0; while(n) { ans += (n % 10) * pw[cnt++]; // printf("%d %d ", pw[cnt - 1], n % 10); n /= 10; } // printf("%d ", ans); cnt = 0; while(m) { num[cnt++] = m % 10; m /= 10; } printf("Case #%d: %d ", ++ca, dfs(cnt - 1, 0, 1)); } int t; int n, m; int main() { scanf("%d", &t); memset(dp, -1, sizeof(dp)); init(); while(t--) { scanf("%d%d", &n, &m); solve(n, m); } return 0;
}
https://cn.vjudge.net/contest/302933#problem/C
前导零排除的模板
找区间中有多少个二进制中0的个数大于1的个数的数。
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N = 35; int dp[N][70]; int a[N]; int dfs(int pos, int sta, int lead, int lim) { if(pos == -1) return sta >= 35; int ans = 0; if(!lim && !lead && dp[pos][sta] != -1) return dp[pos][sta]; int up = lim ? a[pos] : 1; for(int i = 0; i <= up; i++) {
//如果前面全是零的话，这个零就不需要算 if(lead && i == 0) ans += dfs(pos - 1, sta, 1, lim && i == a[pos]); else ans += dfs(pos - 1, sta + (i == 0 ? 1 : -1), 0, lim && i == a[pos]); } if(!lim && !lead) dp[pos][sta] = ans; return ans; } int solve(int x) { int cnt = 0; while(x) { a[cnt++] = x & 1; x >>= 1; } return dfs(cnt - 1, N, 1, 1); } int n, m; int main() { memset(dp, -1, sizeof(dp)); while(~scanf("%d%d", &n, &m)) { printf("%d ", solve(m) - solve(n - 1)); } return 0; }
https://ac.nowcoder.com/acm/contest/887/H
给出A,B,C,然后求有多少组0-A的数与0-B的数满足x & y > c, x ^ y < c.
数位dp
解法：首先与和异或都不可能导致进位，所以可以一位一位的比，如果高位的大那个后面无论怎样肯定都是大的，小的话同理。
数位dp的复杂度为dp数组的总维度乘以一次dfs里的循环数。
这一题把lim也加进了dp数组，因为这一题边界情况可能不止访问一次，因为他有两个数，以前基本上边界都只会访问一次，所以不必要保存状态，而这个题目边界会访问多次，
所以需要保存状态。
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N = 35; int numa[N], numb[N], numc[N]; ll dp[35][3][3][2][2]; ll dfs(int pos, int ca, int cb, int lima, int limb) { if(pos == -1) return ca == 2 || cb == 0; if(ca == 0 && cb == 2) return 0; if(dp[pos][ca][cb][lima][limb] != -1) return dp[pos][ca][cb][lima][limb]; int ea = lima ? numa[pos] : 1; int eb = limb ? numb[pos] : 1; ll ans = 0; for(int i = 0; i <= ea; i++) { for(int j = 0; j <= eb; j++) { int x = i & j; int y = i ^ j; int cca = ca, ccb = cb; if(ca == 1) { if(x == numc[pos]) cca = 1; else if(x < numc[pos]) cca = 0; else cca = 2; } if(cb == 1) { if(y == numc[pos]) ccb = 1; else if(y < numc[pos]) ccb = 0; else ccb = 2; } ans += dfs(pos - 1, cca, ccb, lima && i == ea, limb && j == eb); } } dp[pos][ca][cb][lima][limb] = ans; return ans; } ll solve(ll a, ll b, ll c) { memset(numa, 0, sizeof(numa)); memset(numb, 0, sizeof(numb)); memset(numc, 0, sizeof(numc)); ll aa = a, bb = b, cc = c; int cnta = 0, cntb = 0, cntc = 0; while(a) numa[cnta++] = a % 2, a /= 2; while(b) numb[cntb++] = b % 2, b /= 2; while(c) numc[cntc++] = c % 2, c /= 2; int ma = max(cnta, max(cntb, cntc)); ll ans = dfs(ma - 1, 1, 1, 1, 1);
//这里是排除0的情况。 return ans - min(bb, cc - 1) - min(aa, cc - 1) - 1; } int main() { int t; scanf("%d", &t); ll a, b, c; while(t--) { scanf("%lld%lld%lld", &a, &b, &c); memset(dp, -1, sizeof(dp)); printf("%lld ", solve(a, b, c)); } return 0; }