题目

\(\texttt{[USACO06NOV] Round Numbers S}\)

分析

数位 \(dp\) 入门题

一般我们需要当前位置 \(pos\)，有无前导零 \(lead\)，高位标记 \(limit\)

然后就依题弄

\(Code\)

#include<cstdio>

#include<cstring>

using namespace std;

int l , r , f[40][40][40] , a[40] , len;

int dfs(int pos , int s0 , int s1 , int lead , int limit)

{

	if (!pos) return s0 >= s1;

	if (f[pos][s0][s1] != -1 && !lead && !limit) return f[pos][s0][s1];

	int res = 0;

	for(register int i = 0; i <= (limit ? a[pos] : 1); i++)

	{

		if (!i && lead) res += dfs(pos - 1 , s0 , s1 , 1 , limit && (i == a[pos]));

		else res += dfs(pos - 1 , s0 + (i == 0) , s1 + (i == 1) , 0 , limit && (i == a[pos]));

	}

	if (!lead && !limit) f[pos][s0][s1] = res;

	return res;

}

int solve(int x)

{

	len = 0;

	while (x) a[++len] = x & 1 , x >>= 1;

	memset(f , 255 , sizeof f);

	return dfs(len , 0 , 0 , 1 , 1);

}

int main()

{

	scanf("%d%d" , &l , &r);

	printf("%d\n" , solve(r) - solve(l - 1));

}

巴特西

[USACO06NOV] Round Numbers S

题目

分析

\(Code\)

最新文章

热门文章