[NC记录]AT1982 [AGC001D] Arrays and Palindrome
command_block
2021-02-27 22:04:34
回流 ATC 。
**题意** : 对于两个数组 $A,B$ ，满足 $\sum\limits_{i=1}^{|A|}A_i=\sum\limits_{i=1}^{|B|}B_i=n$。
对于一个长度为 $n$ 的字符串，若其满足下列条件 :
- 前 $a_1$ 个，接下来 $a_2$ 个，接下来 $a_3$ 个……都是回文串。
- 前 $b_1$ 个，接下来 $b_2$ 个，接下来 $b_3$ 个……都是回文串。
那么这个字符串的各个字符一定都相等。
现在已知 $A$ 是 $P$ 的一个排列，求一组符合要求的 $A,B$，或指出无解。
$n\leq 10^5,|P|\leq 100$ ，时限$\texttt{2s}$。
------------
构造题。
首先考虑如何判定一组 $A,B$ 是否合法。
对于一组回文要求，将需要相等的两个位置连一条无向边。若连通整个串，则各个字符一定都相等，反之则不一定。
对于某个 $A_i$ ，连出的边数是 $\lfloor A_i/2\rfloor$ 的。同时注意到总边数至少是 $n-1$ ，所以 $A,B$ 中若有三个及以上的奇数，则必然无解。
显然 ，$A,B$ 内部的边是不会相连的，将整个图连通需要 $A,B$ 边相互作用。
考虑使用两个回文串交叠能产生怎样的构造 :
左图是 奇串+偶串 ，右图是 偶串+偶串。通过这种错开一位的构造，可以使内部完全连通。（从回文周期理论看，这是自然的）
那么，最终方案就不难想到了 : 将 $P$ 中的至多两个奇数放到一边，然后逐步错位来构造 $B$ ，如图 :
（红色部分是奇串）
需要特判 $m=1$ 的情况。
```cpp
#include<algorithm>
#include<cstdio>
#define ll long long
#define MaxN 100500
using namespace std;
int n,m,x[MaxN],tn,ans[MaxN];
int main()
{
scanf("%d%d",&n,&m);
for (int i=1;i<=m;i++)scanf("%d",&x[i]);
if (m==1){
if (x[1]==1)printf("%d\n1\n1",x[1],x[1]-1);
else printf("%d\n2\n1 %d",x[1],x[1]-1);
return 0;
}
for (int i=1,cnt=0;i<=m;i++){
if (x[i]&1){
++cnt;
if (cnt>2){puts("Impossible");return 0;}
}
}
for (int i=1,cnt=0;i<m;i++){
if (x[i]&1){
++cnt;
if (cnt==1)swap(x[i],x[1]);
if (cnt==2)swap(x[i],x[m]);
}
}
for (int i=1;i<=m;i++)
printf("%d ",x[i]);puts("");
if (x[1]>1)ans[++tn]=x[1]-1;
for (int i=2;i<m;i++)
ans[++tn]=x[i];
ans[++tn]=x[m]+1;
printf("%d\n",tn);
for (int i=1;i<=tn;i++)
printf("%d ",ans[i]);puts("");
return 0;
}
```