題目鏈接：點(diǎn)擊查看

題目大意：k-bag 序列的定義是由多個(gè) 1 ~ k 的排列順序連接起來的序列，現(xiàn)在問給定的序列是不是 k-bag 的連續(xù)子串

題目分析：讀完題目后，如果給定的序列是 k-bag 的連續(xù)子串的話，那么可以將所有情況都分為以下三種類型：

一個(gè)部分k-bag的前綴 + 數(shù)個(gè)（至少一個(gè)）完整的k-bag + 一個(gè)部分k-bag的后綴

一個(gè)部分k-bag的前綴 + 一個(gè)部分k-bag的后綴

一個(gè)部分k-bag

判斷部分k-bag和完整的k-bag需要用到兩種不同的方法，判斷部分k-bag的話，只需要判斷區(qū)間內(nèi)的每個(gè)數(shù)都是否不同即可，即區(qū)間的長度等于區(qū)間內(nèi)不同的數(shù)的個(gè)數(shù)，這個(gè)利用 dp 和 unordered_map 搭配就能 O( n ) 的時(shí)間內(nèi)預(yù)處理出來了，這里用 cnt1[ i ] 表示 1 ~ i 內(nèi)有多少個(gè)不同的數(shù)（前綴），cnt2[ i ] 表示 i ~ n 內(nèi)有多少個(gè)不同的數(shù)（后綴）

接下來需要判斷完整的k-bag，如果也是用 “ 區(qū)間內(nèi)有多少個(gè)不同的數(shù) ” 去判斷的話，需要用到主席樹，但可能會(huì)超時(shí)（群友是這樣說的），而且代碼復(fù)雜度也大大上升，很容易寫崩，這里用到一種哈希的方法，不會(huì)證明只會(huì)用，大概就是一個(gè)連續(xù)的序列?[ l , r ] ，維護(hù) sum 和 xor ，sum = l + ( l + 1 ) + ... + ( r - 1 ) + r ，xor = l ^ ( l + 1 ) ^ ... ^ ( r - 1 ) ^ r ，形成一個(gè)二元對(duì) < sum , xor > ，這個(gè)二元對(duì)和 [ l , r ] 是一一對(duì)應(yīng)的，可以稱之為 RSB哈希 （ rsb學(xué)長自己起的名字?）

上面開個(gè)小玩笑，回到這個(gè)題目中來，我們可以再次 O( n ) 維護(hù)一下整個(gè)數(shù)列的 sum前綴和 和 xor前綴異或和，然后再小分一下類，當(dāng) k < n 時(shí)，只會(huì)有上面的情況 1 和情況 2 ，這樣我們可以枚舉 [ 1 , k ] 作為滑動(dòng)窗口的起點(diǎn)，然后檢查每個(gè)長度為 k 的滑動(dòng)窗口，對(duì)于每個(gè)長度為 k 的滑動(dòng)窗口，我們現(xiàn)在可以 O( 1 ) 求出當(dāng)前窗口的xor之和以及sum之和，判斷一下是否等于 1 ~ k 的 xor 和 sum 就好了，當(dāng) k >= n 時(shí)，就只有情況 2 和情況 3 了，此時(shí)我們可以當(dāng)做情況 2 處理，O( n?) 枚舉一下斷點(diǎn)，將整個(gè)數(shù)列分割成前半部分和后半部分，如果某次分割下，前半部分和后半部分滿足了情況 2 的話，那么顯然答案就是 YES 了，相反，如果上面三種情況都不滿足的話，答案就是 NO 了

時(shí)間復(fù)雜度為 O( n ) ，如果不計(jì) unordered_map 的常數(shù)的話

代碼：

#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> #include<unordered_map> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=5e5+100;int a[N],n,k;LL sum[N],Xor[N],SUM,XOR;unordered_map<int,int>mp;int cnt1[N],cnt2[N];//cnt1[i]:1~i內(nèi)有多少個(gè)不同的數(shù),cnt2[i]:i~n內(nèi)有多少個(gè)不同的數(shù)bool check(int st)//檢查以st為起點(diǎn)的滑動(dòng)窗口是否滿足條件 {for(int i=st;i<=n;i+=k){int l=i,r=i+k-1;if(r<=n){if(sum[r]-sum[l-1]!=SUM||(Xor[r]^Xor[l-1])!=XOR)return false;}else return cnt2[l]==n-l+1;}return true; }bool solve() {if(k<n)//情況1和情況2{ SUM=0,XOR=0;for(int i=1;i<=k;i++)//O(k)處理一下1~k的xor和sum作為標(biāo)準(zhǔn){SUM+=i;XOR^=i;}for(int i=1;i<=k;i++)//枚舉起點(diǎn)位置{if(cnt1[i-1]!=i-1)break;if(check(i))return true;}}else//情況2和情況3{for(int i=2;i<=n;i++)//枚舉斷點(diǎn)if(cnt1[i-1]==i-1&&cnt2[i]==n-i+1)return true;}return false; }void init()//預(yù)處理cnt1和cnt2 {mp.clear();cnt1[0]=0;for(int i=1;i<=n;i++){cnt1[i]=cnt1[i-1];if(!mp[a[i]])cnt1[i]++;mp[a[i]]++;}mp.clear();cnt2[n+1]=0;for(int i=n;i>=1;i--){cnt2[i]=cnt2[i+1];if(!mp[a[i]])cnt2[i]++;mp[a[i]]++;} }int main() { #ifndef ONLINE_JUDGE // freopen("data.in.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false);int w;cin>>w;while(w--){scanf("%d%d",&n,&k);bool flag=true;//判斷數(shù)列的每個(gè)元素是否位于1~k之間for(int i=1;i<=n;i++){scanf("%d",a+i);if(a[i]<1||a[i]>k)flag=false;sum[i]=sum[i-1]+a[i];Xor[i]=Xor[i-1]^a[i];}if(!flag){puts("NO");continue;}init();if(solve())puts("YES");elseputs("NO");}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的牛客多校6 - K-Bag(哈希+滑动窗口)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。