Educational Codeforces Round 50(Rated for Div.2)C.Classy Numbers(dfsまたはデジタルdp)

数字の中で0以外の数字が3より少ない数をClassy numberと呼び、区間l,rを与え、この区間内のclassy numberテーマリンクを出力する.http://codeforces.com/contest/1036/problem/C 考え方:2つ:1つはdfsを用いて1 e 18未満のclassy numberをすべて探し出し、2分法で範囲内の数を検索することです.2つ目は、デジタルdpのテンプレートを使用して、コードバーc++コード:dfs+二分:

#include 
#include 
#include 

using namespace std;

typedef long long LL;


vector <LL> v;

void dfs(LL cur,LL cnt,LL len) {
	v.push_back(cur);
	if(len==18)return;
	dfs(cur*10,cnt,len+1);//    len  0    
	for(int i=1;i<=9;i++)
	     if(cnt<3) {
	     	dfs(cur*10+i,cnt+1,len+1);
		 }
}

int main() {
    int T;
	for(LL i=1;i<=9;i++)
	    dfs(i,1,1);
	v.push_back(1e18);
	sort(v.begin(),v.end());
	cin >> T;
	while(T--) {
		LL l,r;
		cin >> l >> r;
		int x=lower_bound(v.begin(),v.end(),l)-v.begin();
		int y=upper_bound(v.begin(),v.end(),r)-v.begin();
		cout << y-x <<endl;
	}
	return 0;
}

デジタルdp:

#include 
#include 
#include 
#include 

using namespace std;

typedef long long LL;
//     1,2,3   4    
LL dp[20][4];//                              
LL a[20];


LL dfs(int pos,int sta,bool lim) {
	if(sta>3)return 0;
	if(pos==-1)return 1;
	if(!lim&&dp[pos][sta]!=-1)return dp[pos][sta];//                    
	//               
	LL up=lim?a[pos]:9;//           
	LL ans=0;
	for(LL i=0;i<=up;i++) {
		ans+=dfs(pos-1,sta+(i>0),lim&&(up==i));
	}
	if(!lim)dp[pos][sta]=ans;//       
	//              ，          
	return ans; 
}

LL solve(LL x) {
	 int pos=0;
	memset(dp,-1,sizeof(dp));
	while(x) {
		a[pos++]=x%10;
		x/=10;
	}
	//cout <
	//LL y;
	//cout << (y=) <
	return dfs(pos-1,0,1);
}




int main() {
    int T;
	cin >> T;
	while(T--) {
		LL l,r;
		cin >> l >> r;
		memset(a,0,sizeof(a));
		cout << solve(r)-solve(l-1)<<endl;
	}
	return 0;
}