注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[BZOJ1879][Sdoi2009]Bill的挑战  

2015-01-25 21:44:51|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

1879: [Sdoi2009]Bill的挑战

好久没发blog了……过来除除草
主要原因是自己太弱,遇到难题不会做只好去看题解,水题发出来没啥意思……
最近各种手残+脑残+被虐
这道题其实也是大裸题TxT
本题题目里说的M指的是N

题解在代码下方

#include<cstdio>
#include<cstdlib>
#include<queue>
#include<cstring>
using namespace std;
const int MOD = 1000003;
const int N = 20;
const int LEN = 50+10;
const int BIT = 1<<15;
int n,m,f[2][BIT],two[50],len[N],list[N],ans;
short ok[N][N],hf[BIT],v[2][BIT],T,num[BIT];
char str[N][LEN];
bool same(int a,int b){
if(len[a]!=len[b])return 0;
for(int i=1;i<=len[a];i++)
if(str[a][i] != str[b][i] && str[a][i]!='?' && str[b][i]!='?')return 0;
return 1;
}
typedef pair<int,int>Node;
queue<Node>dui;
void update(int next,int zt,int val){
if(hf[zt] ==-1)return;
if(hf[zt] == next&&next>0 && num[zt] == m){
ans += val;if(ans>=MOD)ans-=MOD;return;
}
int &fn = f[next&1][zt];
short &vn = v[next&1][zt];
if(vn!=next)vn=next,fn=0,dui.push(Node(next,zt));
fn += val;
if(fn >= MOD) fn-=MOD;
}
int main(){
int i,j,mbit,nn;
for(i=1,two[0]=1;i<=30;i++)two[i]=two[i-1]*2;
scanf("%d",&nn);
while(nn--){
scanf("%d%d",&n,&m);
mbit = two[n];
memset(v,-1,sizeof(v));
for(i=1;i<=n;i++){
scanf("%s",str[i]+1);
len[i] = strlen(str[i]+1);
for(j=1;j<i;j++)
ok[i][j] = ok[j][i] = same(i,j);
}
for(i=0;i<mbit;i++){
int cot=0,tmp=i;list[0]=0;
for(j=1;tmp;j++,tmp/=2)if(tmp&1)cot++,list[++list[0]]=j;
num[i] = cot;
if(cot < m)hf[i]=-1;
else{
int ii,jj;
hf[i]=len[list[1]];
for(ii=1;ii<=list[0];ii++)
for(jj=ii+1;jj<=list[0];jj++)
if(!ok[list[ii]][list[jj]])hf[i]=0;
}
}
ans = 0;
update(0,two[n]-1,1);
while(!dui.empty()){
Node NOW = dui.front();dui.pop();
int now = NOW.first,zt = NOW.second,&val = f[now&1][zt];
int tmp,next;
for(tmp=zt,j=1;tmp;j++,tmp/=2)
if((tmp&1) && now == len[j])continue;
for(i=0;i<26;i++){
next = zt;
for(tmp=zt,j=1;tmp;j++,tmp/=2)
if((tmp&1) && (str[j][now+1]!='?' && str[j][now+1]-'a'!=i))
next -= two[j-1];
update(now+1,next,val);
}
}
printf("%d\n",ans);
}
return 0;
}

题解:
状压DP
f[i][j]表示当前走到第i步,仍能匹配上的串状态是j
每次枚举放的字符就行了
注意预先处理下合法状态什么的,不然可能会T
  评论这张
 
阅读(65)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017