題目鏈接：點擊查看

題目大意：給出一個長度為 n 的模式串 s ，再給出一個長度為 m 的匹配串，匹配串的每一位的可行數字都會給出，現在問最多可以匹配多少個字符串

題目分析：模式串和匹配串的匹配，AC自動機的經典問題，但是在這個題目中匹配串的個數過于多，所以并不能這樣做，因為匹配串的長度比較短，所以可以預處理出一個可行數組用來記錄哪個位置可以放置哪個數字，這樣就能將時間復雜度優化為 n * m 暴力貪心匹配了，但是看數據范圍可知，n 為 2e6 ， m 為 800 ，顯然出題人是有意卡掉這樣的暴力匹配

考慮優化，其實我們可以使用 bitset 優化暴力，可以使得時空復雜度降低 64 個常數，優化方法非常巧妙：

首先就是利用 bitset 數組來充當可行數組，設其為 b 數組，即 bitset<800>b[ 10 ]，則 b [ i ][ j ] = 1 代表第 j 個位置上允許放置數字 i，然后利用一個 bitset 變量記錄每一次的匹配狀態，記這個變量為 cur，cur 的含義是：模式串遍歷到位置 i 時，cur 的第 j 位的狀態代表著 [ i - j + 1 , i ] 這段區間是否和匹配串的前 j 個字符匹配，注意 cur 的每一位都是相互獨立的

每一次對于 cur 的操作是，令其左移一位，再將第一個位置置為 1 ，設當前遍歷到的數字為 num ，則接下來就令 cur &= b[ num ] ，因為 b[ num ] 中存放的二進制為 1 的位置代表著可以放置字符 num 的位置，所以在進行 “ 或 ” 運算后，cur 中仍然為 1 的位置 j 表示在第 [ i - j + 1 , j - 1 ] 這段區間與匹配串的前 j - 1 個字符匹配的基礎上，第 j 個字符仍然匹配，所以根據動態規劃的思想可以巧妙地將狀態轉移為 cur 的第 j ?個位置也為 1

綜上所述，每次只要 cur 的第 m 個位置為 1 時，就說明當前連續的 m 個字符匹配成功，答案加一且將 cur 清空

代碼：
?

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=2e6+100;int a[N];bitset<810>b[10],cur,pre;int main() { #ifndef ONLINE_JUDGE // freopen("input.txt","r",stdin); // freopen("output.txt","w",stdout); #endif // ios::sync_with_stdio(false);int n,m;scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)scanf("%1d",a+i);for(int i=1;i<=m;i++) {int k;scanf("%d",&k);while(k--){int num;scanf("%d",&num);b[num][i]=1;}}int ans=0;for(int i=1;i<=n;i++){pre<<=1;pre[1]=1;cur=pre&b[a[i]];if(cur[m]){ans++;cur.reset();}pre=cur;}if(ans==0)puts("Failed to win the prize");elseprintf("%d\n",ans);return 0; }

?

總結

以上是生活随笔為你收集整理的牛客 - Prize(bitset优化暴力)的全部內容，希望文章能夠幫你解決所遇到的問題。

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