USACO 2014 US Open Odometer /// 数位DP
2024-10-07 13:40:23
题目大意:
给定区间 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 ;
}
最新文章
- Azure Deploy
- c#画正弦波
- 初始化css样式的原因
- 【CentOS】阿里云CentOS安装php环境
- Java-IO之FileReader和FileWriter
- 机器学习之KNN原理与代码实现
- POJChallengeRound2 Tree 【数学期望】
- C++二维数组、指针、对象数组、对象指针
- HbuilderX 常用快捷键
- 《CSS世界》读书笔记(七)
- mybatis逆向工程之动态web项目
- Java调用使用SSL/HTTPS协议来传输的axis webservice服务
- Compile、Make和Build的区别
- c++中对应java ShutdownHook的退出处理器
- [转]Shared——探究react-native通信机制
- 【ASP.NET】#001 获取服务器IP
- sqlalchemy常用语法
- Distributed transactions in Spring, with and without XA
- Configure Always On Availability Group for SQL Server on Ubuntu——Ubuntu上配置SQL Server Always On Availability Group
- kernel cmdline
热门文章
- 请列举出JS对象的几种创建方式?
- 解决WordPress设置错误的url网站不能访问
- windows server 2008R2 配置tomcat服务开机自启动
- systemd:在service文件中给Exec传入多个参数
- loj2542 「PKUWC2018」随机游走 MinMax 容斥+树上高斯消元+状压 DP
- 太恐怖了!黑客正在GPON路由器中利用新的零日漏洞
- python 的set定义
- 前端-个人网页开发最常用的插件Superslide 与 swiper
- Linux服务的安装与使用
- OpenCV—Python 轮廓检测 绘出矩形框(findContours\ boundingRect\rectangle