【PNR#2 Div1 A】恰钱(数位 DP)
DP 数位
2023-09-27 14:28:28 时间
恰钱
题目链接:PNR#2 Div1 A
题目大意
给你一个区间,要你判断里面是否有数满足二进制 1 个数等于末尾 0 个数,如果有就找出一个。
思路
考虑直接上数位 DP,就用二进制来 DP 即可。
维护是否在碰左边界右边界,
1
1
1 的个数,末尾连续
0
0
0 的个数,以及当前形成的数。
然后分 0 , 1 0,1 0,1 讨论一下,具体看代码。
代码
#include<cstdio>
using namespace std;
int q, l, r;
int slove(int now, bool ld, bool rd, int num1, int lst0, int val) {
if (now < 0 && val && lst0 == num1) return val;
if (lst0 + now + 1 < num1) return -1;
if (!ld && !rd) {
if (!val) return -1;
if (((num1 + 1) + 1 <= now + 1) || (num1 == lst0 + now + 1)) {
if (((num1 + 1) + 1 <= now + 1)) return val | (1 << (num1 + 1));
else return val;
}
return -1;
}
for (int i = (ld ? ((l >> now) & 1) : 0); i <= (rd ? ((r >> now) & 1) : 1); i++) {
if (i == 0) {
int x = slove(now - 1, ld & (i == ((l >> now) & 1)), rd & (i == ((r >> now) & 1)), num1, lst0 + 1, val);
if (x != -1) return x;
}
else {
int x = slove(now - 1, ld & (i == ((l >> now) & 1)), rd & (i == ((r >> now) & 1)), num1 + 1, 0, val | (1 << now));
if (x != -1) return x;
}
}
return -1;
}
int main() {
// freopen("ex_data3.in", "r", stdin);
// freopen("write.txt", "w", stdout);
scanf("%d", &q);
while (q--) {
scanf("%d %d", &l, &r);
printf("%d\n", slove(31, 1, 1, 0, 1, 0));
}
return 0;
}
相关文章
- 【BZOJ】1090: [SCOI2003]字符串折叠(dp)
- 【BZOJ】1010: [HNOI2008]玩具装箱toy(dp+斜率优化)
- 【UVa】Headmaster's Headache(状压dp)
- CodeForces 146E - Lucky Subsequence DP+扩展欧几里德求逆元
- android px转换为dip/dp
- 划分问题(dp)
- Codeforces 86C Genetic engineering (AC自己主动机+dp)
- SPOJ 130 - Rent your airplane and make money(dp+优化)
- hdu 2859 (二维dp)
- poj-3898 Software Industry Revolution DP
- HDU 4562 守护雅典娜(dp)
- ZOJ 3822 Domination(概率dp)
- 数位DP【模板】
- 树形dp——覆盖所有边的最少费用(Protecting Zonk)
- 数位DP模板
- 【YBT2023寒假Day14 B】二进制数(数位DP)(数学)
- 【luogu P5363】移动金币(博弈论)(DP)(数位DP)(MTT)
- 【PE806】Nim on Towers of Hanoi(DP)(生成函数)
- 【ybt高效进阶5-3-2】【luogu P6218】区间圆数 / Round Numbers S(数位DP)