題目鏈接

題意

這題的題意是個坑。。。
意思是給一個字符串，在從某一位開始的m位字符中選一個每個字符都不相鄰的子序列，然后把這個子序列中的每個字符和他在原串中的下一個字符交換位置，如果能夠有一個子序列使交換完成后的字符串和給出的字符串一致，就表示該位可行，最后輸出每一位是否都可行。

思路

因為選出來的子序列是不相鄰的，而交換是只發生在相鄰兩個字符之間的，所以可以認為交換之間是不相互影響的，因而可以遍歷s的每一位，直接掃描兩個串，若交換以后匹配，則繼續掃描，如果原來就不匹配，交換以后還是不匹配，則當前位無解，直接跳出。

官方題解給的是O(nmw)的 DP做法，其中w是機器的字節長

實際上暴力雖然是O(nm)， 但是因為一旦有一位不合適立即跳出，這個剪枝實際是很強力的，所以暴力可以水過（而且比標程還快（逃

代碼

#include <bits/stdc++.h> const int maxn = 1e5+10; char s[maxn]; char p[5000+10]; int ans[maxn];using namespace std;int main(){int T;cin >>T;while(T --){int n,m;scanf("%d %d", &n,&m);scanf("%s",s);scanf("%s",p);for(int i = 0 ; i < n - m + 1; i ++){bool flag = true;for(int k = 0 ; k < m ; k ++){if(s[i+k] == p[k+1] && s[i+k+1] == p[k])k++;else if(s[i+k] == p[k])continue;else{flag = false;break;}}ans[i] = flag;}for(int i = n - m + 1 ; i < n ; i ++)ans[i] = 0;for(int i = 0 ; i< n ; i ++)printf("%d",ans[i]);puts("");} }

總結

以上是生活随笔為你收集整理的2016 Multi-University Training Contest 2 1012 La Vie en rose （暴力）的全部內容，希望文章能夠幫你解決所遇到的問題。

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