AtCoder AGC001D Arrays and Palindrome (构造)

补一下原来做过的AtCoder思维题的题解

题目链接: https://atcoder.jp/contests/agc001/tasks/agc001_d

先特判一些小的情况。

原题就相当于每个回文串对称的位置连边，要求图联通。一个长度为\(k\)的回文串，会连\([\frac{k}{2}]\)(中括号下取整)条边。假设所有回文串(包括\(a\)和\(b\))的长度为\(l_i\), 则\(\sum l_i=2n, \sum[\frac{l_i}{2}]\ge 2n-1\), 可得\(\sum (l_i\mod 2)\le 2\), 奇数长度的回文串不超过\(2\)个。

考虑一种连边方式: 比如\([1,9]\)是回文串，\([1,8]\)是回文串，那么\(a_9=a_1=a_8=a_2=a_7=a_3=a_6=a_4=a_5\), 很容易得到\(a_1\)至\(a_9\)全相等。假设我们再令\([10,17]\)是回文串，\([9,16]\)是回文串，那么\(a_9=a_{16}=a_{11}=a_{14}=a_{13}=a_{12}=a_{15}=a_{10}=a_{17}\), 则\(a_1\)至\(a_{17}\)全相等。但是如果我们令\([10,18]\)和\([9,17]\)，而不是\([10,17]\)和\([9,16]\), 那么将得到\(a_9=a_{17}=a_{11}=a_{15}=a_{13}\), 再无法连通。意思就是如果奇数的放到开头或者结尾没有问题，但是如果放到中间会有问题。那么既然奇数长度的回文串不超过\(2\)个那么把它们换到开头结尾即可。

代码

#include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> using namespace std;const int N = 2e5; int a[N+3]; int n,m;int main() {scanf("%d%d",&n,&m); int cnt = 0;for(int i=1; i<=m; i++) {scanf("%d",&a[i]); cnt += (a[i]&1);}if(m==1){if(a[1]==1) printf("1\n1\n1\n");else printf("%d\n2\n%d %d\n",a[1],1,a[1]-1);return 0;}else if(m==2){if(a[1]==1 && a[2]==1) {printf("1 1\n1\n2\n");}else if(a[1]==1) {printf("1 %d\n1\n%d\n",a[2],n);}else {printf("%d %d\n2\n%d %d\n",a[1],a[2],a[1]-1,a[2]+1);}return 0;}if(cnt>2) {printf("Impossible"); return 0;}if(cnt==1){for(int i=1; i<=m; i++) if(a[i]&1) {swap(a[i],a[1]); break;}}else{int flag = 0;for(int i=1; i<=m; i++) if(a[i]&1) {flag++; if(flag==1) swap(a[i],a[1]); else {swap(a[i],a[m]); break;}}}for(int i=1; i<=m; i++) printf("%d ",a[i]); puts("");printf("%d\n",a[1]==1 ? m-1 : m);if(a[1]>1) printf("%d ",a[1]-1);for(int i=2; i<=m; i++) printf("%d ",a[i]+(i==m?1:0)); puts("");return 0; }

总结

以上是生活随笔为你收集整理的AtCoder AGC001D Arrays and Palindrome (构造)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。