CF2056C Palindromic Subsequences 题解
jianhe
·
·
题解
前言：
第一次无伤通过 A,B,C，写篇题解纪念一下。
思路：
可能与题解区的不太一样。
结论： 构造序列 1123123123\cdots 即可。
思路： 观察样例一的输出是 112312，于是想把后面变成 123123\cdots，交一发就过了。
证明： 考虑序列 1123123123\cdots1（这里先讨论末尾是 1 的情况），设序列长度为 3k+2（k\in \mathbb{N}^+），则有 k+2 个 1。
k+2 为奇数时：
首先，f(a)=k+2。（原因是：如果只取 1，结果显然。如果取了其他数，那么如果 1 全部取上就不是回文的了。）
那么来计算回文子序列的个数（下面没有包含所有情况）。
$111\cdots2\cdots111$：$2k$ 个。（取序列中第 $\lfloor\frac{k+2}{2}\rfloor$ 个 $2$ 时，这个 $2$ 右边的 $k$ 个 $1$ 可以去掉任意一个，方案数为 $k$。取第 $\lceil\frac{k+2}{2}\rceil$ 个 $2$ 同理。所以总方案数为 $2k$。）
$111\cdots3\cdots111$：$2k$ 个。（同上）
所以 $g(a)\ge 4k+1$。
可以发现，当 $k>3$ 时，方案数比 $(3k+2)+2$ 都要大（即末尾是 $3$ 的时候）。当 $k\le3$ 时，可以手玩一下，也是对的。
#### $k+2$ 为偶数时：
$f(a)=k+3$。（$1$ 全部选上，中间再选一个数，一定是最优的。）
那么来计算回文子序列的个数（下面没有包含所有情况）。
$111\cdots2/3\cdots111$：$2$ 个。
固定中间一个 $2/3$，将几对 $1$ 替换为 $2/3$ 的方案数：至少 $2\times2^{\frac{k}{2}}$ 个。（只计算不同于固定的数的，对数为 $\frac{k}{2}$，每对可替换可不替换。）
显然 $g(a)>n$。
### 代码：
#### 赛时代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=4e5+10;
ll T,n,ans,ct,a[N];
int main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin>>T;
// T=1;
while(T--){
cin>>n;
for(int i=1;i<=n;i++){
if(i==1) cout<<"1 ";
else cout<<(i-2)%3+1<<" ";
}
cout<<"\n";
}
return 0;
}
```
#### 稍微压个行：
```cpp
#include<bits/stdc++.h>
using namespace std;
int T,n;
int main(){
cin>>T;
while(T--){
cin>>n,cout<<"1 ";
for(int i=2;i<=n;i++) cout<<(i-2)%3+1<<" ";
cout<<"\n";
}
return 0;
}
```