题目大意：
给定区间 l r
求得区间中有多少个数 数的各个数位里出现最多次的数>=数的长度的一半 如2233 3334
枚举k在数中出现次数在一半以上 那么求出的所有方案数中应该减去 两个数各占一半的情况
#include <bits/stdc++.h> using namespace std; #define LL long long #define INF 0x3f3f3f3f #define mem(i,j) memset(i,j,sizeof(i)) #define inc(i,l,r) for(int i=l;i<=r;i++) #define dec(i,r,l) for(int i=r;i>=l;i--) #define gcd(i,j) __gcd(i,j); const int N=55; const int mod=1e9+7; const double eps=1e-8; LL dp[N][N][2][2]; // dp[i][j][b1][b2] // i为数的第i位 j作为枚举的k出现次数的相对计数器 // b1=1当前位小于上界 =0则是等于上界 // b2=1到当前位之前全是前导0 =0则不是前导0 LL DP(char t[],int n,int k1,int k2) { mem(dp,0); dp[0][25][0][1]=1; // 初始设25 防止负数 inc(i,0,n-1) inc(j,0,N-1) inc(b1,0,1) inc(b2,0,1) { LL cur=dp[i][j][b1][b2]; inc(nxt,0,9) { // 枚举下一位 if(k2!=-1) { // 说明枚举的是2233这种被两个数各占一半的情况 if(b2==0 || nxt!=0) // 下一位不是前导0 if(nxt!=k1 && nxt!=k2) continue; // 但又不是这两种数 } if(b1==0 && nxt>t[i]-'0') continue; // 当前位已经是上界 那么下一位不能超过上界 bool nb2= b2&(nxt==0); // 当前位是0b2为1 下一位为0nxt==0为1 则nb2为1 int nj=j; if(nb2==0) { // 下一位不是前导0 if(nxt==k1) nj--; else nj++; } // 是k1就+ 不是就- 最后j=25说明k1刚好一半 如果j<25说明k1超过半数 bool nb1= b1|(nxt<t[i]-'0'); // 当前位之前均为上界b1=0 下一位为上界nxt<t[i]-'0'=0 则nb1为0 dp[i+1][nj][nb1][nb2]+=cur; } } LL res=dp[n][25][1][0]+dp[n][25][0][0]; if(k2==-1) inc(j,0,24) res+=dp[n][j][1][0]+dp[n][j][0][0]; return res; } LL ANS(char t[],int n) { LL res=0; inc(k,0,9) res+=DP(t,n,k,-1); // k出现次数超过一半 如2223 inc(k1,0,9) inc(k2,k1+1,9) // k1 k2各占一半的 如2323 res-=DP(t,n,k1,k2); return res; } int main() { LL ta,tb; while(~scanf("%lld%lld",&ta,&tb)) { ta--; char a[20],b[20]; int lena=0,lenb=0; while(ta) a[lena++]=ta%10+'0', ta/=10; while(tb) b[lenb++]=tb%10+'0', tb/=10; reverse(a,a+lena); reverse(b,b+lenb); printf("%lld ",ANS(b,lenb)-ANS(a,lena)); } return 0; }