HDU5745-La Vie en rose-字符串dp+bitset优化

这题现场的数据出水了，暴力就能搞过。

标解是拿bitset做，转移的时候用bitset优化过的操作（与或非移位）来搞，复杂度O(N*M/w) w是字长

第一份标程的思路很清晰，然而后来会T。

 /*--------------------------------------------------------------------------------------*/

 #include <algorithm>

 #include <iostream>

 #include <cstring>

 #include <ctype.h>

 #include <cstdlib>

 #include <cstdio>

 #include <vector>

 #include <string>

 #include <bitset>

 #include <queue>

 #include <stack>

 #include <cmath>

 #include <set>

 #include <map>

 //debug function for a N*M array

 #define debug_map(N,M,G) printf("\n");for(int i=0;i<(N);i++)\

 {for(int j=;j<(M);j++){\

 printf("%d",G[i][j]);}printf("\n");}

 //debug function for int,float,double,etc.

 #define debug_var(X) cout<<#X"="<<X<<endl;

 #define LL long long

 /*--------------------------------------------------------------------------------------*/

 using namespace std;

 int N,M,T;

 const int maxn = 1e5+;

 const int maxm = +;

 bitset <maxn> dp[],D[];

 char s[maxn],p[maxm];

 void solve()

 {

     for(int i=;i<;i++) D[i].reset();

     for(int i=;i<N;i++)  D[s[i]-'a'][i] = ;

     dp[].reset();

     dp[].reset();

     dp[].reset();

     for(int i=;i<N;i++) dp[][i] = ;

     for(int i=;i<M;i++)

     {

         int cur = p[i]-'a';

         dp[(i+)%] = dp[i%] & D[cur]>>i;

         if(i > )

         {

             int lst = p[i-]-'a';

             dp[(i+)%] |= dp[(i+)%] & D[cur]>>i- & D[lst]>>i;

         }

     }

     for(int i=;i<N;i++)

     {

         if(dp[M % ][i] == ) putchar('');

         else putchar('');

     }

     puts("");

 }

 int main()

 {

     //freopen("1012.in","r",stdin);

     //freopen("1012.bitset.out","w",stdout);

     scanf("%d",&T);

     while(T--)

     {

         scanf("%d%d ",&N,&M);

         scanf("%s%s",s,p);

         solve();

     }

 }