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的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。