题目大意:

给定区间 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=;
const int mod=1e9+;
const double eps=1e-; LL dp[N][N][][];
// 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,);
dp[][][][]=; // 初始设25 防止负数
inc(i,,n-) inc(j,,N-)
inc(b1,,) inc(b2,,) {
LL cur=dp[i][j][b1][b2];
inc(nxt,,) { // 枚举下一位
if(k2!=-) { // 说明枚举的是2233这种被两个数各占一半的情况
if(b2== || nxt!=) // 下一位不是前导0
if(nxt!=k1 && nxt!=k2) continue; // 但又不是这两种数
}
if(b1== && nxt>t[i]-'') continue;
// 当前位已经是上界 那么下一位不能超过上界
bool nb2= b2&(nxt==); // 当前位是0b2为1 下一位为0nxt==0为1 则nb2为1
int nj=j;
if(nb2==) { // 下一位不是前导0
if(nxt==k1) nj--;
else nj++;
} // 是k1就+ 不是就- 最后j=25说明k1刚好一半 如果j<25说明k1超过半数
bool nb1= b1|(nxt<t[i]-''); // 当前位之前均为上界b1=0 下一位为上界nxt<t[i]-'0'=0 则nb1为0
dp[i+][nj][nb1][nb2]+=cur;
}
}
LL res=dp[n][][][]+dp[n][][][];
if(k2==-) inc(j,,)
res+=dp[n][j][][]+dp[n][j][][];
return res;
} LL ANS(char t[],int n) {
LL res=;
inc(k,,) res+=DP(t,n,k,-); // k出现次数超过一半 如2223
inc(k1,,) inc(k2,k1+,) // 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[],b[];
int lena=,lenb=;
while(ta) a[lena++]=ta%+'', ta/=;
while(tb) b[lenb++]=tb%+'', tb/=;
reverse(a,a+lena); reverse(b,b+lenb);
printf("%lld\n",ANS(b,lenb)-ANS(a,lena));
} return ;
}

最新文章

  1. Azure Deploy
  2. c#画正弦波
  3. 初始化css样式的原因
  4. 【CentOS】阿里云CentOS安装php环境
  5. Java-IO之FileReader和FileWriter
  6. 机器学习之KNN原理与代码实现
  7. POJChallengeRound2 Tree 【数学期望】
  8. C++二维数组、指针、对象数组、对象指针
  9. HbuilderX 常用快捷键
  10. 《CSS世界》读书笔记(七)
  11. mybatis逆向工程之动态web项目
  12. Java调用使用SSL/HTTPS协议来传输的axis webservice服务
  13. Compile、Make和Build的区别
  14. c++中对应java ShutdownHook的退出处理器
  15. [转]Shared——探究react-native通信机制
  16. 【ASP.NET】#001 获取服务器IP
  17. sqlalchemy常用语法
  18. Distributed transactions in Spring, with and without XA
  19. Configure Always On Availability Group for SQL Server on Ubuntu——Ubuntu上配置SQL Server Always On Availability Group
  20. kernel cmdline

热门文章

  1. 请列举出JS对象的几种创建方式?
  2. 解决WordPress设置错误的url网站不能访问
  3. windows server 2008R2 配置tomcat服务开机自启动
  4. systemd:在service文件中给Exec传入多个参数
  5. loj2542 「PKUWC2018」随机游走 MinMax 容斥+树上高斯消元+状压 DP
  6. 太恐怖了!黑客正在GPON路由器中利用新的零日漏洞
  7. python 的set定义
  8. 前端-个人网页开发最常用的插件Superslide 与 swiper
  9. Linux服务的安装与使用
  10. OpenCV—Python 轮廓检测 绘出矩形框(findContours\ boundingRect\rectangle