对于复杂二进制数位DP问题考虑朴素思想：agc015d
对于复杂二进制数位dp问题考虑朴素思想：agc015d
本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133643686
https://atcoder.jp/contests/agc015/tasks/agc015_d
我一开始考虑的是直接上二进制数位dp，但发现这很难做
然后其实可以从最朴素的二进制+分类讨论角度考虑
同样是那么几个套路，考虑最高位
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 zhangxixi的博客！
相关推荐
2023-09-12
二进制、数位DP：0912T3
二进制、数位dp：0912T3 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132840291 考虑题目转化，二进制下满足 i⊆j,(i+x)⊆(j+y)i\subseteq j,(i+x)\subseteq (j+y)i⊆j,(i+x)⊆(j+y) 这显然是个数位dp形式 考虑枚举每一位与进位， dpk,p1,p2dp_{k,p_1,p_2}dpk,p1,p2 表示第 k−1k-1k−1 位向第 kkk 位，分别进位 p1,p2p_1,p_2p1...
2023-12-20
二进制下传优化AND连边：UOJ176
二进制下传优化AND连边：UOJ176 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135106721 https://vj.imken.moe/contest/600665#problem/E 一个朴素思路是枚举 ppp ，然后再枚举 x&y=px\&y=px&y=p ，如果 x,yx,yx,y 不在一起，则连一条边。 考虑优化。如果 x,yx,yx,y 的交集更大，则不是 ppp 。所以一个思路是取出 ppp 所有0的位置，然后...
2023-09-22
二进制位运算相关的计数问题——巧用高维前缀和：0922T2
二进制位运算相关的计数问题——巧用高维前缀和：0922T2 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133183403 http://cplusoj.com/d/senior/p/SS230922B 在 https://blog.csdn.net/zhangtingxiqwq/article/details/133176573 当中，我们大致对题目进行了转化。 对于询问 kkk ，我们现在要求所有 a(i,j)a(i,j)a(i,j) 的异或和，满足 ...
2023-10-10
popcount相关性质+从低往高的数位DP：CF1734F
popcount相关性质+从低往高的数位dp：CF1734F 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133749334 https://www.luogu.com.cn/problem/CF1734F popcount有个性质： popcount(x)^popcount(y)=popcount(x^y) 考虑数位dp，发现很难 然后我们发现可以从低往高dp（当做套路） 只不过是否达到上界变成是否超出去 12345678910111213141516...
2023-11-04
涉及多种位运算操作混合类题目——通过加转三进制（扩大状态，不变枚举量）：CF1033F
涉及多种位运算操作混合类题目——通过加转三进制（扩大状态，不变枚举量）：CF1033F 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/134219227 https://www.luogu.com.cn/problem/CF1033F 我们发现直接用二进制来做很难做，但我们可以观察其给的表 我们发现如果表示成和的形式是容易进行一一对应的 对于询问的时候，我们直接枚举每位有的和是多少，虽然状态是三次的，但是对于每个填法最多对应两个 所以我们通过 扩大状态，不...
2026-06-16
DP之双DP前后互补加类二进制均摊思想：SS221109D
dp之双dp前后互补加类二进制均摊思想：SS221109D 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/162037356 https://cplusoj.com/d/senior/p/SS221109D 首先可以推一下性质，不难发现，一个数只会进行如此变换： 先除至多 log2(n)\log_2(n)log2(n) 次 再乘至多 nnn 次 所以一个明显的dp是可以设计的： f(i,x,y)f(i,x,y)f(i,x,y) 表示第 iii...