给定一个数，要给出小于等于这个数的所有非负数中，各个数位上的数字重复不超过两次的数的个数。
比如111，110，112，121，1211都是，102，120，1200就不是。
YY 的幸运数字是......，是什么数字我也不知道，但是已知这个数字的十进制表示（不含前导零）中只包含不超过两个不同的数字。
给定一个数 nn ，请计算出不超过 nn 的所有正整数中，有可能是 YY 的幸运数字的个数。
输入一行，包含一个正整数 nn。
对于 60% 的数据：
1≤n≤10的5次方，
对于 100% 的数据：
1≤n≤10的9次方。
输出一个整数，表示不超过 nn 的所有正整数中，有可能是 YY 的幸运数字的个数。
不超过103的所有正整数中，只有102、103不可能是 YY 的幸运数字。
代码:
#include<iostream> #include<stdio.h> using namespace std; #define sc scanf #define ci cin #define co cout #define e endl #define Maxx(a,b) (a>b?a:b) #define Minn(a,b) (a<b?a:b) #define lld long long int int getLen(int n){ if(n==0) return 1; int len=0; while(n){ n/=10; len++; } return len; } int cal(lld n){ int dict[10] = {0,9,99,351,927,2151,4671,9783,20079,40743}; lld dig[10] = {0,1,10,100,1000,10000,100000,1000000,10000000,100000000}; int mon[9] = {1,2,4,8,16,32,64,128,256};//与以下的binary数组相配合，记录操作次数用的 int len,highest,value; len = getLen(n);//取得位数 highest = n/dig[len];//取得最高位 value += dict[len-1] + (dict[len]-dict[len-1])/9*(highest-1);//len-1位的情况全部包括进来，最高位从1到highest-1的情况全部包括进来 //对最高位为highest的数进行枚举 lld res; for(int j=0;j<=9;j++){//从左往右数第二位 从0到9枚举 //co<<j<<e; int binary[9] = {0,0,0,0,0,0,0,0,0};//二进制位类似于状态位 if(j!=highest){//只取和最高位不相同的数，因为相同的数必然会包含在这些不同的数中 //220: 枚举 0: 四类情况 200 202 220 222 // 枚举 1: 四类情况 211 212 221 222 // 枚举 2: 四类情况 222 222 222 222 // 枚举 3: 四类情况 233 232 223 222 // 枚举 4: 四类情况 244 242 224 222 // 枚举 5: 四类情况 255 252 225 222 // 枚举 6: 四类情况 266 262 226 222 // 枚举 7: 四类情况 277 272 227 222 // 枚举 8: 四类情况 288 282 228 222 // 枚举 9: 四类情况 299 292 229 222 //只需跳过枚举2并且第四列的数据删到只剩一个，剩下的就是可能出现的枚举，在和数据比大小，最后一列全部相同的情况总共出现9次 //先挑出所有的比220小的数，再判断222是否小于220，大于就不操作，小于等于就要减掉多加上的8次 int cnt = 0; while(1){//不论与N的大小全部枚举出来,暴力解法 res=highest*dig[len]; for(int i=8;i>=10-len;i--){ if(binary[i]==0) res += dig[9-i]*j; else res += dig[9-i]*highest; } if(res<=n){ value++;//只要res小于等于n就加进来 } for(int i=8;i>=10-len;i--){//+1操作 if(binary[i]==0){ binary[i] = 1; break; }else{ binary[i] = 0; } } cnt++; if(cnt==mon[len-1]) break; //操作2^（len-1）方停止 } } }//最后的res是全1的类型 if(res<=n) value -= 8; return value; } int main(){ lld n; int dict[10] = {0,9,99,351,927,2151,4671,9783,20079,40743}; while(sc("%lld",&n)!=EOF){ if(n==1000000000){ co<<dict[9]+1<<e; }else if(n<=100){ co<<n<<e; }else{ co<<cal(n)<<e; } } return 0; }dict数组是通过推导得来，因为1位数的情况下，从一开始，就有9种符合条件，2位数以下的情况就包括10-->99再加上一位数的情况，总共99种，
3位数就应该是100-->999：分两类情况讨论
1类：各个数位都只用到1位相同的数字=9种
2类：各个数位恰好都用到了两个数字{罗列一下
100 101 110 112 113 114 115 116 117 118 119 121 122 131 133 141 144 151 155 161 166 171 177 181 188 191 199//27个
200 202 211 212 220 221 223 224 225 226 227 228 229 ------------------------------//也是27个
}
这样子算出来就是=9+27*9 = 9 + 81*3 = 252 再加上2位数的情况 = 252 +99 = 351；
以此类推4位数 = 351 + 9 + 81*7 = 927.....
8位数 = 【7位数情况的个数】 + 9 + 81*（2的8次方-1）；
打出dict的代码:
int dict[9];//创建字典存储对应位数可能有的情况,上限9位数就是1000000000 dict[1] = 9;//1位数9种 //co<<dict[1]<<e; for(int i=2;i<=8;i++){//n位数可能的情况是 n-1位数可能的情况加上9（恰好1个数字重复）再加上81*(2^(n-1)-1)【恰好两个数字重复】 cnt*=2; dict[i] = dict[i-1] + 9 + 81*(cnt-1); co<<dict[i]<<e; }算法里面是用binary数组来表示对应位置上的情况，比如说第八位数就是binary[8]，存储0和1的表示方式来控制对应位置上可能存在的情况，因为之前最高位highest已被记录，那binary[8]=1就意味着第八位现在的状态是和最高位一致.
