首页 > 代码库 > BZOJ 4032 trie树+各种乱搞
BZOJ 4032 trie树+各种乱搞
思路 :
先对b 的所有后缀建立trie树
第一问
暴力枚举a串的起点
在trie树上跑 找到最短的
第二问
也是暴力枚举a串的起点
a和b顺着暴力匹配就好
第三问
求出来a在第i个位置 加一个字母j 能够到的最近的位置 f[i][j] 到最后就是inf
从f[0][j]DFS 在trie上跟着跑找到最小的deep更新答案
第四问
先按照求f一样同理求出b串 的 g
dp[i][j]表示a的前i个位置 b不得不匹配到b的第j个位置
dp[i+1][j]=min(dp[i+1][j],dp[i][j]),
dp[i+1][g[j][a[i]]]=min(dp[i+1][g[j][a[i]]],dp[i][j]+1);
1—>strlen(a)+1 min dp[i][inf]就是答案
这题看起来简单 其实感觉在考场根本写不出来...
//By SiriusRen#include <cstdio>#include <cstring>#include <algorithm>using namespace std;const int N=2050,inf=2010;int ch[N*N/2][27],f[N][27],g[N][27],dp[N][N],cnt,ans1,ans2,ans3,ans4,vis[27];void insert(char *a){ int now=0; for(int i=0;a[i];i++){ if(!ch[now][a[i]])ch[now][a[i]]=++cnt; now=ch[now][a[i]]; }}int solve1(char *a){ int now=0,i; for(i=0;a[i];i++){ if(!ch[now][a[i]])return i+1; else now=ch[now][a[i]]; }return inf;}void solve3(int x,int now,int deep){ if(x==inf)return; if(!now&&deep){ans3=min(ans3,deep);return;} for(int i=1;i<=26;i++)solve3(f[x][i],ch[now][i],deep+1);}char a[N],b[N];int main(){ scanf("%s%s",a+1,b+1); int n1=strlen(a+1),n2=strlen(b+1); for(int i=1;i<=n1;i++)a[i]=a[i]-‘a‘+1; for(int i=1;i<=n2;i++)b[i]=b[i]-‘a‘+1; for(int i=1;i<=n2;i++)insert(b+i); ans1=ans2=ans3=ans4=inf; for(int i=1;i<=n1;i++)ans1=min(ans1,solve1(a+i)); for(int i=1;i<=n1;i++){ int now=1; for(int j=0;i+j<=n1;now++,j++){ while(a[i+j]!=b[now]&&now<=n2)now++; if(now>n2){ans2=min(ans2,j+1);break;} } } for(int i=0;i<=n1;i++){ memset(vis,0,sizeof(vis)); for(int j=i+1;j<=n1;j++)if(!vis[a[j]])vis[a[j]]=j; for(int j=1;j<=26;j++)f[i][j]=vis[j]?vis[j]:inf; }solve3(0,0,0); for(int i=0;i<=n2;i++){ memset(vis,0,sizeof(vis)); for(int j=i+1;j<=n2;j++)if(!vis[b[j]])vis[b[j]]=j; for(int j=1;j<=26;j++)g[i][j]=vis[j]?vis[j]:inf; } memset(dp,0x3f,sizeof(dp)),dp[0][0]=0; for(int i=0;i<=n1;i++) for(int j=0;j<=n2;j++) dp[i+1][j]=min(dp[i+1][j],dp[i][j]), dp[i+1][g[j][a[i]]]=min(dp[i+1][g[j][a[i]]],dp[i][j]+1); for(int i=1;i<=n1+1;i++)ans4=min(ans4,dp[i][inf]); printf("%d\n%d\n%d\n%d\n",ans1==inf?-1:ans1,ans2==inf?-1:ans2,ans3==inf?-1:ans3,ans4==inf?-1:ans4);}
BZOJ 4032 trie树+各种乱搞
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。