数位dp——牛客多校H
2024-10-07 19:46:58
/*
x[1,A]
y[1,B]
x^y<C 或 x&y>C
把ABC拆成二进制后按位进行数位dp
dp[pos][s1][s2][f1][f2]
表示从高到低第pos位,条件一状态为s1,条件2状态为s2,x在pos为的限制状态为f1,y在pos的限制状态为f2的方案数
条件状态s=0|1|2表示前pos位数运算结果<C前pos位数,=C前pos位数,>C前pos位数
dp时枚举下一位的所有可能情况,如果当前状态已经确定(满足或不满足),那么下一位取什么都可以,即下一位的条件状态可以直接继承当前位
反之当前状态不确定,即前pos位的值和C相等,那么需要通过当前为来进行判断下一位的条件状态 终止条件:pos==30
s1==2||s2==0,值为1,反之为0 考虑要减去的情况
x=0,y=[1,min(C-1,B)]都可行
y=0,x=[1,min(C-1,A)]都可行
x=0,y=0也可行
*/
#include<bits/stdc++.h>
using namespace std;
#define maxn 35
#define ll long long
ll A,B,C,dp[maxn][][][][];
vector<int>v1,v2,v3; ll dfs(int pos,int S1,int S2,int f1,int f2){
ll &res=dp[pos][S1][S2][f1][f2];
if(res!=-)return res;
if(pos==){//边界条件
if(S1==||S2==)return res=;
else return res=;
}
res=;
int newS1,newS2,lim1,lim2;
lim1=f1?v1[pos]:;//x下一位的上界
lim2=f2?v2[pos]:;//y下一位的上界
for(int i=;i<=lim1;i++)//枚举xy的下一位
for(int j=;j<=lim2;j++){
int tmp1=i&j,tmp2=i^j;
if(S1==){//先处理条件1
if(tmp1==v3[pos])newS1=;
else if(tmp1<v3[pos])newS1=;
else newS1=;
}
else newS1=S1;
if(S2==){
if(tmp2==v3[pos])newS2=;
else if(tmp2<v3[pos])newS2=;
else newS2=;
}
else newS2=S2;
res=res+dfs(pos+,newS1,newS2,f1&&(i==lim1),f2&&(j==lim2));
}
return res;
}
void calc(ll x,vector<int> & v){
v.clear();
for(int i=;i>;i--){
v.push_back(x&);
x>>=;
}
reverse(v.begin(),v.end());//把数组倒置后就可以正常数位dp了
}
int main(){
int t;cin>>t;
while(t--){
memset(dp,-,sizeof dp);
cin>>A>>B>>C;
calc(A,v1);calc(B,v2);calc(C,v3);
ll res=dfs(,,,,);//进入搜索时的状态
res-=min(C-,A)+min(C-,B)+;//0取不到,但数位dp时算了
cout<<res<<'\n';
}
}
最新文章
- JavaScript 字符串处理详解
- 【LeetCode】Counting Bits(338)
- MYSQL外键(Foreign Key)的使用
- DateUtil工具类
- PostgreSQL的case when
- python模块介绍- collections(5)-OrderedDict 有序字典
- DirectUI 收集资料
- [专题汇总]AC自动机
- HDUOJ 2672---god is a girl 《斐波那契数》
- JavaWeb项目开发案例精粹-第3章在线考试系统-005action层
- SignalR Supported Platforms -摘自网络
- struts2自己定义拦截器
- ProgressBar样式总结与自己主动填充方法(代码)
- Spring Security 入门详解(转)
- SQL点滴16—SQL分页语句总结
- 使用图片地图减少HTTP请求数量
- c语言,文件操作总结
- j2ee中spring的分布式事务实现及解决方案
- Android 插件化技术窥探
- 虚拟机上安装django链接Pycharm(版本差异有所差异)
热门文章
- oracle入门学习之oracle数据库结构
- ubuntu颜色配置
- Java中基本类型的包装类
- PHP FILTER_VALIDATE_FLOAT 过滤器
- 对Map的key按升序进行排序
- 出现Warning: date(): It is not safe to rely on the system&#39;s timezone settings的解决办法
- docker镜像管理和dockerfile详解(8)
- artTemplate性能卓越的 js 模板引擎
- Jquery的Ready方法加载为什么两次?
- C#基础-->;cookie和session