題意

對于一對數(shù)組\(a_i\)和\(b_i\)，滿足\(\sum\limits_{i=1}^{k_a}a_i=\sum\limits_{i=1}^{k_b}b_i=N\)，而且對于所有長度為\(N\)的字符串，如果在滿足下列兩個條件的前提下：

• 對于前\(a_1\)個，接下來\(a_2\)個，再接下去\(a_3\)個……都是回文串

• 對于前\(b_1\)個，接下來\(b_2\)個，再接下去\(b_3\)個……都是回文串

同時還必然滿足這個字符串一定全部字符都一樣。如果只有原來\(a_i\)的一個排列，求一種這個\(a_i\)數(shù)組和相應(yīng)的\(b_i\)數(shù)組。注意可能不存在。

• \(N\leq 10^5\)
• \(k_a \leq 100\)
• \(A_i\leq 10^5\)

分析

先考慮\(k_a\)比較小的情況，例如\(k_a=1\)，這個時候可以發(fā)現(xiàn)我們只需要讓回文串錯一位就可以了。

對于\(k_a=2\)，考慮我們從那個中間分隔的點開始往外直接擴(kuò)展，實際上只要覆蓋到兩邊回文串中間的那個點，然后剩下來的直接隨便覆蓋就可以了（因為就這一些已經(jīng)將兩個回文串“連接”在了一起），這是一個思路，但是比較難以實現(xiàn)。

更加直接的思路（按照題解），還是按照錯位，我們考慮實際上只需要將中間那個分割點向左邊移動一下，那也是能夠相應(yīng)建立關(guān)系的。

按照這個思路，我們應(yīng)該可以進(jìn)一步地考慮推廣！我們應(yīng)該可以按照這個思路，只需要取\(b=\{a_1-1,a_2,\cdots,a_{k_a-1},a_{k_a}+1\}\)，這種答案的構(gòu)造方法，除非是中間的數(shù)是偶數(shù)，否則都是可以的。

那么當(dāng)存在大量偶數(shù)的時候有沒有可能構(gòu)造出一個相應(yīng)的解呢？我們考慮設(shè)\(a\)里面偶數(shù)有\(O_a\)個，\(b\)里面偶數(shù)有\(O_b\)個，那么邊數(shù)是\(\frac{N-O_a}{2}+\frac{N-O_b}{2}\)，考慮如果我們要讓這\(N\)個點連通，我們肯定至少需要\(N-1\)條邊，那么也就是\(\frac{N-O_a}{2}+\frac{N-O_b}{2}\geq N-1\)，這個不等式算出來是\(O_a+O_b\leq 2\)……于是我們發(fā)現(xiàn)不可能偶數(shù)多于\(2\)個。如果滿足的話那一定可以將這兩個偶數(shù)調(diào)到最前和最后。

那么我們只要掃一遍就可以得到了。回顧一下思路，我們從\(k_a=1\)的情況推出了錯位的思路，然后進(jìn)一步推廣到了一般情況，同時對于一種看上去比較特殊的情況得出了解。最后，我們證明了剩下的情況沒有解，實際上也就是說因為有偶數(shù)，所以相當(dāng)于要浪費一部分邊去專門將偶數(shù)導(dǎo)走，然后整個圖就無法導(dǎo)通。

注意在寫的時候有可能會出現(xiàn)減出\(0\)的情況，所以需要再判一下邊界情況。

# include <bits/stdc++.h> # define il inline # define fi first # define se second # define pb push_back # define mem(x,v) memset(x,v,sizeof x) # define rep(i,x,y) for(int i=x;i<=y;++i) # define re(i,x,y) for (int i=x;i<y;++i) using namespace std; typedef long long ll; il ll read(){ll x=0; char c=getchar();for(;c<'0'||c>'9';c=getchar());for(;c>='0'&&c<='9';c=getchar())x=x*10+c-'0';return x; } const int maxm = 100+10; int n,m; int a[maxm]; vector<int> b; int main(){n=read(); m=read();rep(i,1,m) a[i]=read();if (m == 1){b.pb(1); b.pb(n-1);}else{int cnt = 0;rep(i,1,m) cnt += a[i] % 2;if (cnt > 2){puts("Impossible"); return 0;}rep(i,2,m-1)if (a[i]%2==1){if (a[1]%2==0)swap(a[1],a[i]);else swap(a[m],a[i]);}b.pb(a[m]+1);for (int i=m-1;i>1;--i) b.pb(a[i]);b.pb(a[1]-1);}rep(i,1,m) printf("%d ",a[i]); printf("\n");int bs=b.size();if (b[bs-1] == 0)--bs;printf("%d\n",bs);for (int i=bs-1;i>=0;--i) printf("%d ",b[i]); printf("\n");return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/wendavid/p/8982266.html

總結(jié)

以上是生活随笔為你收集整理的[AGC001 D]Arrays and Palindrome的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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