http://acm.hdu.edu.cn/showproblem.php?pid=6899
比賽的時候死磕了兩個小時，想得都是上次在哪少了1，然后這次進位要進到哪個位置，，，然而越寫越亂，0406都沒看
據說是個old題，cometoj和以前dls出過的題都有對|x-y|的討論，就是把上一位傳向下一位的當成-1 0 1，這樣就可以保證減法的進位了，詳見這題題解https://cometoj.com/contest/71/problem/D?problem_id=4019
感謝hduoj提供admin賬號，去比賽ac代碼里學習了一下
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int a,b,k,w;ll ans;
ll dp[35][3][3][2][2][2];
inline void prework()
{
scanf("%d%d%d%d",&a,&b,&k,&w);
}
inline ll dfs(int ind,int v1,int v2,bool fa,bool fb,bool fw)
{
v1=min(v1,1);v2=min(v2,1);
if(v1<-1 || v2<-1)
return 0;
if(ind<0)
return v1>=0 && v2>=0;
if(dp[ind][v1+1][v2+1][fa][fb][fw]>=0)
return dp[ind][v1+1][v2+1][fa][fb][fw];
ll ret=0;
int upa=fa?(a>>ind&1):1;
int upb=fb?(b>>ind&1):1;
int upw=fw?(w>>ind&1):1;
int t=k>>ind&1;
for(int i=0;i<=upa;i++)
for(int j=0;j<=upb;j++)
{
if((i^j)>upw)
continue;
ret+=dfs(ind-1,v1*2+i-j+t,v2*2+j-i+t,fa&&i==upa,fb&&j==upb,fw&&(i^j)==upw);
}
return dp[ind][v1+1][v2+1][fa][fb][fw]=ret;
}
inline void mainwork()
{
memset(dp,-1,sizeof(dp));
ans=dfs(30,0,0,1,1,1);
}
inline void print()
{
printf("%lld\n",ans);
}
int main()
{
int t;
scanf("%d",&t);
for(int i=1;i<=t;i++)
{
prework();
mainwork();
print();
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/116366.html
標籤：其他
上一篇：HDU 6889 Graph Theory Class （Min25篩）
下一篇：Python石頭剪刀布完整代碼