题意: 有串s,p.串p可以经过一些变换,变换规则是,每个字符可以跟它前一个字符或者后一个字符交换位置。交换次数不限,但是每个字符只能交换或者被交换一次。
结果输出一个n位的二进制,对于匹配串的字符位置i,如果s的子串(si,si+1,si+2,...,si+m-1)可以由p串变换得出的话,则这个位置输出“1”,否则输出“0”。
分析:
这个题目很坑,卡了常数,姿势不好就会超时。
首先很容易可以看出来这是一个dp题。dp[ i ][ k ][ j ] 表示 s[ i ] 经过 k 操作 能够跟 p[ j ] 匹配上并且 p[ j ] 之前的字符也已经匹配上了。
k = 0 ,当前字符跟之前的字符交换。
k = 1 ,当前字符不交换
k = 2 ,当前字符跟之后的字符交换。
那么状态转移为:
dp[ j ][ 0 ][ i ] = dp[ j-1 ][ 2 ][ i-1 ] && s[ i ] == p[ j-1 ] dp[ j ][ 1 ][ i ] = ( dp[ j-1 ][ 1 ][ i-1 ] || dp[ j-1 ][ 0 ][ i-1 ]) && s[ i ] == p[ j ] dp[ j ][ 2 ][ i ] = ( dp[ j-1 ][ 1 ][ i-1 ] || dp[ j-1 ][ 0 ][ i-1 ]) && s[ i ] == p[ j+1 ]
好我们根据这个状态转移方程式可以写出第一份代码:
代码1:
#include <cstdio> #include <cstring> #include <iostream> using namespace std; const int N=1e5+10; const int M=5010; char s[N],p[M]; bool dp[M][3][N]; int main() { std::cout.sync_with_stdio(false); int t,n,m; cin >> t; while(t--) { cin >> n >> m; cin >> s >> p; memset(dp,0,sizeof(dp)); for(int i = 0 ; i < n ; i ++) { if(s[i] == p[0])dp[0][1][i] = 1; if(m > 1 && s[i] == p[1]) dp[0][2][i] = 1; } for(int j = 1 ; j < m ; j ++) { for(int i = 0; i < n ; i ++) { dp[j][0][i] = dp[j-1][2][i-1]&&(s[i] == p[j-1]); dp[j][1][i] = (dp[j-1][0][i-1] || dp[j-1][1][i-1]) && (s[i] == p[j]); if(j+1<m) dp[j][2][i] = (dp[j-1][1][i-1] || dp[j-1][0][i-1]) && (s[i] == p[j+1]); } } for(int i = 0 ; i < n ; i ++) { if(dp[m-1][0][i+m-1] || dp[m-1][1][i+m-1]) cout << "1"; else cout << "0"; } cout << endl; } return 0; }
然而显然以上代码的时间复杂度是O(m*n) 空间复杂度是O(m*n)。先不说时间,根据m,n的范围可以知道dp[M][3][N]肯定会爆。我们仔细观察可以发现dp的递推只跟之前一个状态有关。所以我们可以使用滚动数组优化空间,使得空间复杂度变成O(n).
代码2:
#include <cstdio> #include <cstring> #include <iostream> using namespace std; const int N=1e5+10; const int M=5010; char s[N],p[M]; bool dp[2][3][N]; int main() { std::cout.sync_with_stdio(false); int t,n,m; cin >> t; while(t--) { cin >> n >> m; cin >> s >> p; memset(dp,0,sizeof(dp)); int cur = 0; for(int i = 0 ; i < n ; i ++) { if(s[i] == p[0])dp[cur][1][i] = 1; if(m > 1 && s[i] == p[1]) dp[cur][2][i] = 1; } for(int j = 1 ; j < m ; j ++) { cur ^= 1; for(int i = 0; i < n ; i ++) { dp[cur][0][i] = dp[cur^1][2][i-1]&&(s[i] == p[j-1]); dp[cur][1][i] = (dp[cur^1][0][i-1] || dp[cur^1][1][i-1]) && (s[i] == p[j]); if(j+1<m) dp[cur][2][i] = (dp[cur^1][1][i-1] || dp[cur^1][0][i-1]) && (s[i] == p[j+1]); } } for(int i = 0 ; i < n ; i ++) { if(dp[cur][0][i+m-1] || dp[cur][1][i+m-1]) cout << "1"; else cout << "0"; } cout << endl; } return 0; } 好,现在只剩时间了,其实这里我们需要使用一个奇计淫巧 ----------- bitset优化,实际上根据算法大体上已经不能再优化了O(m*n).但是显然这个代码是会超时的(比赛的时候时间开的8秒。暴力可过,挂出来的题只有4秒)。
我们可以观察算法主体代码:
for(int j = 1 ; j < m ; j ++) { for(int i = 0; i < n ; i ++) { dp[j][0][i] = dp[j-1][2][i-1]&&(s[i] == p[j-1]); dp[j][1][i] = (dp[j-1][0][i-1] || dp[j-1][1][i-1]) && (s[i] == p[j]); if(j+1<m) dp[j][2][i] = (dp[j-1][1][i-1] || dp[j-1][0][i-1]) && (s[i] == p[j+1]); }内循环可以看作是每位(i)的两个数通过与、或等方式得到另一个数。注意这里强调是每一位都执行的相同操作。并且每位只有0或者1两个值。我们可以联想到位运算。
这个时候我们把dp[ j ][ k ] 看作一个bool型的数组。嗯也可以看做一个长度为N的一个二进制数。那么内层循环可以直接用位运算实现而不用循环。这样做的好处是什么呢?
它可以把时间复杂度从O(n*m) 压缩到 O(n*m/w) w是电脑的机器字长。
这里我们使用的bool数组就是bitset容器。具体优化实现看这里------------bitset优化,
代码3(AC代码):
#include <cstdio> #include <cstring> #include <iostream> #include<bitset> using namespace std; const int N=1e5+10; const int M=5010; char s[N],p[M]; bitset<N>dp[2][3]; bitset<N>w[30]; int main() { std::cout.sync_with_stdio(false); int t,n,m,cur; cin >> t; while(t--) { cin >> n >> m; cin >> s >> p; for(int i=0;i<30;i++) w[i].reset(); for(int i=0;i<n;i++) w[s[i]-'a'][i]=1; for(int i=0;i<2;i++) for(int j=0;j<3;j++) dp[i][j].reset(); cur=1; dp[cur][1]=w[p[0]-'a']; if(m>1) dp[cur][2]=w[p[1]-'a']; for(int j=1;j<m;j++) { cur^=1; // 注意这里之所以要左移1位是因为w[p[j-1]-'a']每个i是跟dp[cur^1][2]的i-1相与。所以要将右边的左移,才能使得i-1与上i. dp[cur][0]=w[p[j-1]-'a']&(dp[cur^1][2]<<1); dp[cur][1]=w[p[j]-'a']&((dp[cur^1][0]|dp[cur^1][1])<<1); if(j+1<m) dp[cur][2]=w[p[j+1]-'a']&((dp[cur^1][0]|dp[cur^1][1])<<1); } for(int i=0;i<n;i++) if(dp[cur][0][i+m-1]||dp[cur][1][i+m-1]) printf("1"); else printf("0"); printf("\n"); } return 0; }