CF244B Undoubtedly Lucky Numbers 题解

题目简述

给定一个 $n$，问有多少个小于等于 $n$ 的数只由两个不同的数字 $x$ 和 $y$ 组成。

题目分析

直接枚举肯定不行，我们考虑枚举 $x$ 和 $y$，再利用深搜，生成所有不大于 $n$ 且只由 $x$ 和 $y$ 组成的数字，利用 map 去重，统计答案即可。

代码

#include<iostream>
#include<map>
using namespace std;
#define int long long
int n,ans;
map<int,bool> vis;
inline int read()
{
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
	    if(ch=='-')
		{
			f=-1;
		}
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
	    x=(x<<1)+(x<<3)+ch-48;
	    ch=getchar();
	}
	return x*f;
}
inline void write(int x)
{
    if(x<0)
	{
    	putchar('-');
		x=-x;
	}
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
void check(int a,int x,int y,int cnt)
{
	if(cnt>10||a>n) return;
	if(a<=n&&a!=0&&!vis[a])
	{
		ans++;
		vis[a]=1;
	}
	check(a*10+x,x,y,cnt+1);
	check(a*10+y,x,y,cnt+1);
}
signed main()
{
	n=read();
	for(int i=0;i<=9;i++)
	{
		for(int j=i+1;j<=9;j++)
		{
			check(0,i,j,0);
		}
	}
	cout<<ans;
	return 0;
}