题目描述

输入输出格式

输入格式：

 

本题包含多组数据。 第一行：一个整数T，表示数据的个数。 对于每组数据： 第一行：两个整数，N和K（含义如题目表述）。 接下来N行：每行一个字符串。

 

输出格式：

 

1 2 1 a? ?b

 

输入输出样例

输入样例#1：

50

输出样例#1：

对于30%的数据，T ≤ 5，M ≤ 5，字符串长度≤ 20；对于70%的数据，T ≤ 5，M ≤ 13，字符串长度≤ 30；对于100%的数据，T ≤ 5，M ≤ 15，字符串长度≤ 50。 真是玄学题 经历了从50分到70分再到AC 一开始看到觉得是带通配符的AC自动机状压DP，一看要求长度都一样，好像直接DP就行呀？ 然后写了最朴素的DP，dp[i][j]表示转移到第i个字符，目前能匹配上的状态为j的方案数，然后枚举下一位是什么，与所有字符串进行比较转移即可 这样的复杂度是  $ O(26TLn*2^n) $  ，能有50分 然后可以发现与所有字符串比较是很愚蠢的，进行了很多重复计算，我们可以预处理出每一位所有字符串匹配某个字符的结果，压在一个int里，转移时直接按位与即可 这样复杂度是  $ O(26TL*2^n) $  ，能有70分 然后你把它数字带进去发现，它乘出来是26*5*50*2^15约等于2e8，这是什么意思？这意思就是稍微卡一卡就能过了。 DP怎么稍微卡一卡呢？你想DP倒过来就是记忆化搜索，搜索可以剪枝啊，于是我们尝试剪一剪枝。 怎么剪枝呢？加上如果在遍历到某个状态dp[i][j]时，如果dp[i][j]==0就不转移 事实上这个效果好得出奇，速度快了10倍都不止，至此获得100分

1 #include 
       
         2 #include 
        
          3 #include 
         
           4 #include 
          
            5 #include 
           
             6 #include 
            
              7 #include 
             
               8 #include