第 45 届国际大学生程序设计竞赛（ICPC）亚洲区域赛（济南）L Bit Sequence —

第 45 届国际大学生程序设计竞赛（ICPC）亚洲区域赛（济南）L Bit Sequence —— 记忆化搜索

本文主要是介绍第 45 届国际大学生程序设计竞赛（ICPC）亚洲区域赛（济南）L Bit Sequence —— 记忆化搜索，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

This way

题意：

定义f(x)表示x的二进制上1的个数
给你m个数，问你有多少个数在0~L之间，满足f(x+i)=a[i](0<=i<m)

题解：

我L都写出来了…我还是没有拿金
那么可以猜测到这是一个记忆化搜索
枚举最后被m影响的几位，然后记忆化前面的部分。
因为会有进位，所以需要特殊地考虑。
ad表示非进位的时候需要的前面的位数是奇数还是偶数，adf表示进位后需要奇数还是偶数。
由于会有进位那么我们需要知道进位影响了多少个1
dp[i][j][k]表示到了第i位，连续最后1的个数是j个，当前有奇数个1还是偶数个1
那么到了边界的时候，是否进位需要分别考虑
在这里插入图片描述
上面是0的情况，下面是1的情况
并且到了上限的时候，也需要考虑非进位能否满足条件：

上面表示只能取0。
做完之后我们可以发现，其实在枚举最后几位的时候，去dfs会超过L的限制，比如L是
100001010
那么比如我们枚举的是最后4位，在情况为1111的时候，前面的位数照常枚举，所以最大会举到
100001111，超过了L
因此需要for一遍将额外的值删掉。同时额外的值不会超过2^7，可以直接暴力枚举
在这里插入图片描述
这个就是查看一个长整型二进制有多少个1。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=65,M=105;
ll dp[N][N][2];
int a[M],f,b[N],ad,adf,low;
ll dfs(int pos,int len,int even,int lim){if(pos==low){ll ans=0;if(f){if(ad==even&&adf==even)ans++;if(!lim||(lim&&b[pos])){if(adf==((even+len)&1)&&ad==((even+1)&1))ans++;}}else{if(lim&&b[pos]==0){if(ad==even)ans=1;}elseans=1;}return ans;}if(!lim&&~dp[pos][len][even])return dp[pos][len][even];ll ans=0;int top=lim?b[pos]:1;for(int i=0;i<=top;i++)ans+=dfs(pos-1,i==0?0:len+1,(even+i)&1,lim&&i==top);if(!lim)dp[pos][len][even]=ans;return ans;
}
int main()
{int t;scanf("%d",&t);while(t--){int m;ll l;scanf("%d%lld",&m,&l);for(int i=1;i<=m;i++)scanf("%d",&a[i]);low=0;int vv=m;while(vv)low++,vv>>=1;int mx=(1<<low)-1;ll ans=0;for(int i=0;i<=mx;i++){if(i>l)break;ad=(a[1]^__builtin_popcount(i))&1;adf=2;for(int j=2;j<=m;j++){int v=(a[j]^__builtin_popcount(i+j-1))&1;if(i+j-1>mx){if(adf==2)adf=v;if(adf!=v){adf=-1;break;}continue;}if(v!=ad){ad=-1;break;}}if(ad==-1||adf==-1)continue;if(mx>=l){if(!ad)ans++;continue;}if(i+m-1>mx)f=1;else f=0;memset(dp,-1,sizeof(dp));int top=0;ll x=l;while(x)top++,x>>=1;top--;for(int j=top;~j;j--)b[j]=(l>>j)&1;ans+=dfs(top,0,0,1);}if(mx<l){ll v=l|mx;//v--;while(v>l){int del=0;for(int i=1;i<=m;i++){ll now=v+i-1;int num=__builtin_popcount(now);ll mm=1ll<<32;if(now>mm){now>>=32;num+=__builtin_popcount(now);}if(num%2!=a[i]){del=1;break;}}if(!del)ans--;v--;}}printf("%lld\n",ans);}return 0;
}