首页 > 代码库 > hdu 5798 Stabilization(dfs+巧妙利用二进制位)
hdu 5798 Stabilization(dfs+巧妙利用二进制位)
题目链接:hdu 5798 Stabilization
题意:
给出一个序列Ai,可以让每个Ai异或上一个x使得最小,问最小值以及使得该值最小的最小x值
题解:
首先枚举x,然后如何来算得出的价值呢,巧妙的利用A[i]与A[i-1]的二进制位关系。
详细题解传送门
1 #include<bits/stdc++.h> 2 #define mst(a,b) memset(a,b,sizeof(a)) 3 #define F(i,a,b) for(int i=(a);i<=(b);++i) 4 using namespace std; 5 typedef long long ll; 6 7 const int N=1e5+7; 8 int t,n,a[N],x,mx; 9 ll dp[22][22],ans; 10 11 void dfs(int pos,ll sum,int now) 12 { 13 if(pos>mx) 14 { 15 if(sum<ans)ans=sum,x=now; 16 else if(sum==ans)x=min(x,now); 17 return; 18 } 19 F(i,0,1) 20 { 21 ll tmp=sum+dp[pos][pos]; 22 F(j,0,pos-1)if(((now>>j)&1)==i)tmp+=dp[pos][j]; 23 else tmp-=dp[pos][j]; 24 dfs(pos+1,tmp,now+(i<<pos)); 25 } 26 } 27 28 int main(){ 29 scanf("%d",&t); 30 while(t--) 31 { 32 mst(dp,0),mx=0,ans=0,x=0; 33 scanf("%d",&n); 34 F(i,1,n)scanf("%d",a+i); 35 F(i,2,n) 36 { 37 int ta=max(a[i],a[i-1]),tb=min(a[i],a[i-1]); 38 int pos=19;ans+=ta-tb; 39 while(pos>=0&&!(((ta^tb)>>pos)&1))pos--; 40 mx=max(mx,pos); 41 for(int j=pos;j>=0;j--) 42 dp[pos][j]+=((ta>>j)&1)-((tb>>j)&1); 43 } 44 F(i,0,mx)F(j,0,i)dp[i][j]<<=j; 45 dfs(0,0,0); 46 printf("%d %lld\n",x,ans); 47 } 48 return 0; 49 }
hdu 5798 Stabilization(dfs+巧妙利用二进制位)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。