题解 CF727E 【Games on a CD】

sdxjzsq

2020-03-18 19:41:06

Solution

### 题目链接 https://www.luogu.com.cn/problem/CF727E https://codeforces.com/problemset/problem/727/E ### 题意 已知$g$个长度为$k$互不相同的字符串$r[1..g]$和一个长度为$n\times k$的环形字符串$s$,问是否能从$r[1..g]$中选出$n$个组成字符串$s$。如果能,则输出`YES`,并在第二行按在$s$中的顺序输出对应的$r$的编号,否则输出`NO`。 ### 思路 算法:字符串哈希(双哈希) 首先,因为本题的字符串$s$是一个环,所以读入以后需要复制一遍(其实只复制前$k$个字符就可以。) 之后,把$r[1..g]$的双哈希值放入map中,值为字符串的编号。 接着,因为环形字符串$s$划分为长度为$k$的划分方法只可能有$k$种,也就是只能把$s[1],s[2],\cdots,s[k]$作为划分后第一个字符串的第一个字符,$s[k+1]$就与第一种划分方式重复了(这就是为什么我前面说只需要复制前$k$个字符就可以)。所以枚举$s[1],s[2],\cdots,s[k]$作为划分后第一个字符串第一个字符的情况,对于每个$s$的长度为$k$的子串在map中匹配并记录编号,如果曾经匹配过或者不在map中直接进入下一次枚举即可。 复杂度$O(n\times k)$ ### Tips 1. 本题一定要用双哈希,大概尝试了好多模数,最多也就撑到测试点22,换了双哈希以后直接就A掉了。 2. 双哈希判断相同字符串的条件的时候,必须是两个哈希值之前同时出现过才是相同字符串,因为这个被卡了好几次提交... 3. 双哈希用map记录编号的时候可以将map定义为`map<pair<long long,long long>,int> M`,这样就可以用`M[make_pair(foo_1,foo_2)]=bar`来记录数据了。 ### code ``` cpp #include<cstdio> #include<map> #include<queue> using namespace std; const int maxn = 2e6+7; long long mod = 998244353,mod2 = 1e9+7,base = 131; map<pair<long long,long long>,int> M;//Tips3 map<long long,int>N,N2; //其实N也可以定义成和M一样的形式,甚至可以把get_hash都写成pair的返回值,但是懒得改了咕咕咕 int n,m,k,t,ans[maxn]; char s[maxn]; long long h[maxn],h2[maxn],p[maxn],p2[maxn],g[maxn],g2[maxn]; inline long long get_hash(int l,int r) { return (h[r]-h[l-1]*p[r-l+1]%mod+mod)%mod; } inline long long get_hash2(int l,int r) { return (h2[r]-h2[l-1]*p2[r-l+1]%mod2+mod2)%mod2; } int main() { scanf("%d%d%s%d",&n,&k,s+1,&t);m=n*k;p[0]=1;p2[0]=1; for(register int i=1;i<=m;i++)s[i+m]=s[i];m<<=1; for(register int i=1;i<=m;i++) h[i]=(h[i-1]*base+s[i])%mod,h2[i]=(h2[i-1]*base+s[i])%mod2,//计算哈希 p[i]=p[i-1]*base%mod,p2[i]=p2[i-1]*base%mod2; for(register int j=1;j<=t;j++) { scanf("%s",s+1); for(register int i=1;i<=k;i++)g[j]=(g[j]*base+s[i])%mod,g2[j]=(g2[j]*base+s[i])%mod2,M[make_pair(g[j],g2[j])]=j; } for(register int j=1;j<=k;j++) { N.clear();N2.clear();bool flag=true; for(register int i=0;i<n;i++) { long long now = get_hash(i*k+j,i*k+j+k-1),now2 = get_hash2(i*k+j,i*k+j+k-1); if((N.count(now)&&N2.count(now2))||(M.count(make_pair(now,now2))==0)){flag=false;break;}//Tips2这里一定要now和now2同时出现过才需要退出! N[now]=N2[now2]=1;ans[i+1]=M[make_pair(now,now2)];//记录出现情况并记录答案 } if(flag) { printf("YES\n"); for(register int i=1;i<=n;i++)printf("%d ",ans[i]); return 0; } } printf("NO"); return 0; } ```