本文主要是介绍COCI Parametriziran —— 状压+dfs求相似字符串个数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Description
Input
Output
Sample Input
3 3
??b
c??
c?c
4 6
ab??c?
??kll?
a?k??c
?bcd??
5 2
??
b?
c?
?g
cg
Sample Output
2
3
8
Hint
题意：
给你n个长度相同的字符串，这些字符串中含有小写字母和’?’，’?'可以替换成任意字符，如果两个替换之后的字符串可以相等，那么就称为这两个字符串相似，求相似字符串的对数。
题解：
一个字符串，我们可以只考虑它数字的情况，例如a?b?c我们可以只考虑abc这三个位置，用状压来存，因为只有1<<6种可能，所以开这么大的unordered_map，那么对于上面的情况我们要查询的就是10101这个map，abc有很多对应的可能:abc,?bc,a?c,ab?,??c,?b?,a??,???都是可以的，所以我们dfs找他的所有可能，之后在将原字符串的所有可能的情况加入map:10000的位置加入a,01000的位置加入?，11000的位置加入a?，以此类推，注意string是会mle的，需要用hash。
#pragma gcc optimize(2)
#include<bits/stdc++.h>
using namespace std;
#define ll unsigned int
unordered_map<ll,int>mp[(1<<6)];
int p[10];
char s[10];
int have,n,m;
long long ans;
void dfs(int pos,int val)
{if(pos>=m){int has=0;for(int i=0;i<m;i++){if(!(have&p[i]))continue;if((val&p[i]))has=has*31+s[i];elsehas=has*31+'?';}ans+=mp[have][has];return ;}if(!(have&p[pos]))dfs(pos+1,val);else{for(int i=0;i<=1;i++)dfs(pos+1,(val|(i==0?0:p[pos])));}
}
int main()
{p[0]=1;for(int i=1;i<=6;i++)p[i]=p[i-1]*2;scanf("%d%d",&n,&m);int maxn=(1<<m),has;for(int i=1;i<=n;i++){scanf("%s",s);have=0;for(int j=0;j<m;j++)if(s[j]!='?')have|=p[j];dfs(0,0);for(int i=0;i<maxn;i++){has=0;for(int j=0;j<m;j++){if((i&p[j]))has=has*31+s[j];}mp[i][has]++;}}printf("%lld\n",ans);return 0;
}
这篇关于COCI Parametriziran —— 状压+dfs求相似字符串个数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
