傳送門

文章目錄

• 題意：
• 思路：

題意：

問你有多少對$x,y$滿足以下條件：
$(1)x\in [0,A],y\in [0,B]$
$(2)|x?y|\le K$
$(3)xxory\le W$

其中$A,B,K,W\le 1e9$。

思路：

明顯的數位$dp$了，考慮怎么設計狀態。
眾嗦粥汁，數位$dp$的狀態是要能表現出數的狀態和結構的，分別分析一下這三個條件就好啦。
對于第一個條件，我們維護兩個變量$flag1,flag2$表示能否達到上界就好啦，很套路。
對于第二個條件，我們自然的想到拆掉絕對值，變成$x?y+K\ge 0,y?x+K\ge 0$，由于我們需要按照二進制來考慮(因為有異或)， 所以我這兩個式子的值域都為$[?1,2]$，所以我們分別用兩個變量$k1,k2$表示這兩個式子是多少。考慮是否每個狀態都有意義呢？這里只考慮$k1$，當$k1\le ?2$的時候，由于我們加上當前位的$[?1,2]$中某一個數之前需要乘$2$(因為從高位到低位)，那么無論如何，這個值只會越來越小，所以如果$k\le ?2$的時候直接返回$0$即可。對于大于$0$的狀態，無論如何都不會變小，我們為了節省空間將其與$2$取一個$min$即可。
對于第三個條件，記一個變量為$flag3$，表示$W$是否達到上界，也就是說$x,y$的異或值可以任意。

分析完之后就是數位$dp$裸題辣。

// Problem: Xor // Contest: HDOJ // URL: http://acm.hdu.edu.cn/showproblem.php?pid=6899 // Memory Limit: 524 MB // Time Limit: 2000 ms // // Powered by CP Editor (https://cpeditor.org)//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math") //#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native") //#pragma GCC optimize(2) #include<cstdio> #include<iostream> #include<string> #include<cstring> #include<map> #include<cmath> #include<cctype> #include<vector> #include<set> #include<queue> #include<algorithm> #include<sstream> #include<ctime> #include<cstdlib> #include<random> #include<cassert> #define X first #define Y second #define L (u<<1) #define R (u<<1|1) #define pb push_back #define mk make_pair #define Mid ((tr[u].l+tr[u].r)>>1) #define Len(u) (tr[u].r-tr[u].l+1) #define random(a,b) ((a)+rand()%((b)-(a)+1)) #define db puts("---") using namespace std;//void rd_cre() { freopen("d://dp//data.txt","w",stdout); srand(time(NULL)); } //void rd_ac() { freopen("d://dp//data.txt","r",stdin); freopen("d://dp//AC.txt","w",stdout); } //void rd_wa() { freopen("d://dp//data.txt","r",stdin); freopen("d://dp//WA.txt","w",stdout); }typedef long long LL; typedef unsigned long long ULL; typedef pair<int,int> PII;const int N=1000010,mod=1e9+7,INF=0x3f3f3f3f; const double eps=1e-6;int a,b,k,w; int A[210],B[210],K[210],W[210]; LL f[100][2][2][2][10][10]; //pos a<=A,b<=B,a^b<=W,x-y+k>=0,y-x+k>=0LL dp(int pos,int flag1,int flag2,int flag3,int k1,int k2) {if(pos==-1) return k1>=0&&k2>=0;if(k1<-1||k2<-1) return 0;k1=min(2,k1); k2=min(2,k2);if(f[pos][flag1][flag2][flag3][k1+1][k2+1]!=-1) return f[pos][flag1][flag2][flag3][k1+1][k2+1];int x=flag1? 1:A[pos];int y=flag2? 1:B[pos];int z=flag3? 1:W[pos];LL ans=0;for(int i=0;i<=x;i++) {//afor(int j=0;j<=y;j++) {//bif((i^j)>z) continue;ans+=dp(pos-1,flag1||i<x,flag2||j<y,flag3||((i^j)<z),k1*2+i-j+K[pos],k2*2+j-i+K[pos]);}}return f[pos][flag1][flag2][flag3][k1+1][k2+1]=ans; }LL solve() {for(int i=30;i>=0;i--) {A[i]=a>>i&1;B[i]=b>>i&1;K[i]=k>>i&1;W[i]=w>>i&1;}return dp(30,0,0,0,0,0); }int main() { // ios::sync_with_stdio(false); // cin.tie(0);int _; scanf("%d",&_);while(_--) {memset(f,-1,sizeof(f));scanf("%d%d%d%d",&a,&b,&k,&w);printf("%lld\n",solve());}return 0; } /**/

總結

以上是生活随笔為你收集整理的hdu 6899 Xor 数位dp的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。