第45届ICPC济南站L.Bit Sequence 数位DP+记忆化搜索

（数位DP+记忆化搜索）

题意简述：

给定一个长度为m的01数组与L, 求[0,L]中val值为m的数的个数

一个数x的val值定义为 x到x+m-1的按位1的个数序列

首先手玩规律观察什么样的数有相同的val序列，会发现后7位可以固定下来，这是因为我们发现后7位只会进一次位，且这次进位对前面位的影响取决于从第8位开始连续1串的长度奇偶性。

那么我们用后7位来拟合m序列，同时做好前面位的奇偶性处理，就可以做了。

反思：

写完代码是超时的。

手玩后发现了可以固定后几位，通过计算m来确定固定几位，但是没有考虑好进制的影响，应直接按最坏情况（7位）暴力处理

同时由于本题状态比较复杂，应使用记忆化搜索降低编程难度。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int f[110];//m数组，结果最后7位应与之相同
int b[300];
int lit[110];
ll dp[110][2][2][2];
ll m,k;
ll cal(int pre1,int par,int lim){
int p=127;
if(lim) {
p=k&((1<<7)-1);
}
int cnt=0;
for(int i=0;i<=min(127,p);i++){
bool ff=1;
for(int j=0;j<m;j++){
if(i+j<=127&&f[j] != (b[i+j]^par)) ff=0;
else if(i+j>127&&f[j]!=(b[i+j]^par^pre1)) ff=0;
}
if(ff) cnt++;
}
return cnt;
}
ll dfs(int x,int pre1,int par,int lim){
if(dp[x][pre1][par][lim]!=-1) return dp[x][pre1][par][lim];
if(x<=6) return dp[x][pre1][par][lim]=cal(pre1,par,lim);
ll res=0;
if(lim==0){
res+=dfs(x-1,pre1^1,par^1,0);
res+=dfs(x-1,0,par,0);
} else {
if(lit[x]==1){
res+=dfs(x-1,0,par,0);
res+=dfs(x-1,pre1^1,par^1,1);
}else {
res+=dfs(x-1,0,par,1);
}
}
return dp[x][pre1][par][lim]=res;
}
void solve(){
cin>>m>>k;
memset(dp,-1,sizeof(dp));
for(int i=0;i<m;i++) cin>>f[i];
int len;
for(int i=0;i<=60;i++){
if((1L<<i)&k) lit[i]=1;
else lit[i]=0;
if((1L<<i)>k) {
len=i;
break;
}
}
len=max(len,1);
//
cout<<len<<"n";
cout<<dfs(len-1,0,0,1)<<"n";
}
int cal_1(int x){
int cnt=0;
while(x){
if(x&1) cnt++;
x>>=1;
}
return cnt;
}
void init(){
for(int i=1;i<=250;i++){
b[i]=cal_1(i)%2;
}
}
int main(){
init();
int t;
cin>>t;
while(t--){
solve();
}
return 0;
}

最后

以上就是高挑抽屉为你收集整理的第45届ICPC济南站L.Bit Sequence 数位DP+记忆化搜索的全部内容，希望文章能够帮你解决第45届ICPC济南站L.Bit Sequence 数位DP+记忆化搜索所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。