Codeforces 754E：Dasha and cyclic table

Codeforces 754E：Dasha and cyclic table

题目链接：http://codeforces.com/problemset/problem/754/E

题目大意：$A$矩阵（$size(A)=n \times m$，仅含'a'-'z'）在整个平面做周期延拓，问$B$矩阵（$size(B)=r \times c$，包含'a'-'z'及'?'，'?'为通配符）在哪些位置能与$A$矩阵匹配。输出$n \times m$的01矩阵，1表示在该位置匹配.

枚举+bitset常数优化

直接暴力的话复杂度为$O(n^4)(n=400)$，而bitset做位运算复杂度为$O(\frac{n}{32})$，若能用bitset优化，则可将$O(n^4)$优化为$O(\frac{n^4}{32})$.

假定$B$矩阵可以匹配$A$矩阵的每一位，令输出矩阵$ans$每个元素都为$1$.

 

睡觉(～﹃～)~zZ...

转载于:https://www.cnblogs.com/barrier/p/6680737.html

总结

以上是生活随笔为你收集整理的Codeforces 754E：Dasha and cyclic table的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。