傳送門(mén)

文章目錄

• 題意：
• 思路：

題意：

思路：

考慮數(shù)位$dp$，設(shè)計(jì)狀態(tài)$f[pos][flag1][flag2][flag3][flag4]$，其中$flag1:x\ge L_{x}flag2:y\le R_x,flag3:z\ge L_y,flag4:w\le R_y$，控制一下上下界即可。
但是可能會(huì)有重復(fù)的情況，比如當(dāng)前$i,j$都為$1$的時(shí)候，那么答案當(dāng)前位也是$1$，此時(shí)只有一種情況。當(dāng)$i\&j=0$時(shí)，會(huì)有三種情況$(0,0),(1,0),(0,1)$，這個(gè)時(shí)候答案的當(dāng)前位都是$1$，我們對(duì)這三種情況取一個(gè)$max$即可，因?yàn)橛幸环N情況肯定包含了其他的情況。
所以直接套個(gè)板子即可。

// Problem: #6274. 數(shù)字 // Contest: LibreOJ // URL: https://loj.ac/p/6274 // Memory Limit: 512 MB // Time Limit: 1000 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=110,mod=1e9+7,INF=0x3f3f3f3f; const double eps=1e-6;LL t,l1,l2,r1,r2; int L1[N],L2[N],R1[N],R2[N],T[N]; LL f[N][2][2][2][2]; //flag1:>=l1 flag2<=r1 flag3>=l2 flag4<=r2LL dp(int pos,int flag1,int flag2,int flag3,int flag4) {if(pos==-1) return 1;if(f[pos][flag1][flag2][flag3][flag4]!=-1) return f[pos][flag1][flag2][flag3][flag4];int x=flag1? 0:L1[pos];int y=flag2? 1:R1[pos];int z=flag3? 0:L2[pos];int w=flag4? 1:R2[pos];LL ans1=0,ans2=0;for(int i=x;i<=y;i++) {for(int j=z;j<=w;j++) {if((i|j)!=T[pos]) continue;if((i&j)==0) ans1=max(ans1,dp(pos-1,flag1||i>x,flag2||i<y,flag3||j>z,flag4||j<w));else ans2+=dp(pos-1,flag1||i>x,flag2||i<y,flag3||j>z,flag4||j<w);}}return f[pos][flag1][flag2][flag3][flag4]=ans1+ans2; }LL solve() {memset(f,-1,sizeof(f));for(int i=60;i>=0;i--) {L1[i]=l1>>i&1;L2[i]=l2>>i&1;R1[i]=r1>>i&1;R2[i]=r2>>i&1;T[i]=t>>i&1;}return dp(60,0,0,0,0); }int main() { // ios::sync_with_stdio(false); // cin.tie(0);cin>>t>>l1>>r1>>l2>>r2;printf("%lld\n",solve());return 0; } /**/

總結(jié)

以上是生活随笔為你收集整理的Loj #6274. 数字 数位dp + 去重的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。