洛谷 P6218 [USACO06NOV] Round Numbers S

原题链接

数位dp

一道小清新数位dp题。

乍一看,诶,这不就是个板子嘛。

但是写着写着就发现还是有蛮多细节的,下面我们来分析一下:

直接来看核心代码(即 \(dfs\) 部分)

ll dfs(ll len, ll cha, ll flag, ll lim){
	if(!len) return cha >= 30;
	if(dp[len][cha][flag][lim] != -1) return dp[len][cha][flag][lim];
	ll res = lim ? num[len] : 1;
	ll ans = 0;
	for(ll i = 0; i <= res; i++)
		ans += dfs(len - 1, cha + (!i ? (flag ? 0 : 1) : -1), flag && (!i), lim && (i == res));
	return dp[len][cha][flag][lim] = ans;
}

变量解释:

\(len:\) 倒着查找到了第几位

\(cha:\) 0 比 1 多几个,注意可能 1 比 0 多,即 \(cha < 0\),作为数组下标的话会 \(RE\),(酱紫一点都不好哇QWQ),所以我们深搜时,令 \(cha\) 初值为 30,就解决问题了

\(flag:\) 当前位是否为前导 0 (1:是 $\ $ 0:否)

\(lim:\) 当前位是否有上界限制(1:有 $\ $ 0:无)

再来看

cha + (!i ? (flag ? 0 : 1) : -1)

如果当前位是 0,但是是前导 0,那么 \(cha\) 不变,如果不是是前导0,那么 \(cha++\);

如果当前位是 1,那么 \(cha--\)。

其余的就没什么难点啦,不要忘记开 \(long \ long\)

上完整代码

#include <iostream>
#include <cstdio>
#include <cstring>

#define ll long long

using namespace std;

ll l, r, len;
ll num[100];
ll dp[100][100][2][2];

ll dfs(ll len, ll cha, ll flag, ll lim){
	if(!len) return cha >= 30;
	if(dp[len][cha][flag][lim] != -1) return dp[len][cha][flag][lim];
	ll res = lim ? num[len] : 1;
	ll ans = 0;
	for(ll i = 0; i <= res; i++)
		ans += dfs(len - 1, cha + (!i ? (flag ? 0 : 1) : -1), flag && (!i), lim && (i == res));
	return dp[len][cha][flag][lim] = ans;
}

ll solve(ll x){
	len = 0;
	while(x){
		num[++len] = x % 2;
		x /= 2;
	}
	memset(dp, -1, sizeof(dp));
	return dfs(len, 30, 1, 1);
}

signed main(){
	scanf("%lld%lld", &l, &r);
	printf("%lld\n", solve(r) - solve(l - 1));
	return 0;
}

完结撒花~

上一篇:Python做一个查Q绑脚本


下一篇:2021-09-23