题解：CF2056C Palindromic Subsequences

· · 题解

人类智慧。

思路

发现第三组样例中 g(a)=190，我们只需要在这一组的答案之后输出一些没出现过的数就可以通过 n\ge15 的点。这是非常显然的，如果一个数字只出现过一次那么它不会构成更长的回文序列。\ 同理第二组样例中 g(a)=24，用它通过 9\le n<15 的点。\ 发现在第一组样例之后接上一个 3 后 g(a)=9。用它通过 n\in\{8,9\} 的点。n=6 输出样例。

代码

好想但是没正解好写。

#include<bits/stdc++.h>
using namespace std;
int T,n;
int main(){
    scanf("%d",&T);
    while(T --){
        scanf("%d",&n);
        if(n == 6) printf("1 1 2 3 1 2");
        else if(n == 7) printf("1 1 2 3 1 2 3");
        else if(n == 8) printf("1 1 2 3 1 2 3 4");
        else if(n >= 9 && n <= 14){
            printf("7 3 3 7 5 3 7 7 3 ");
            for(int i = 10;i <= n;i ++) printf("%d ",i); //注意不要和前面的数字重复，需要保证刚好 n 个数字
        }
        else{
            printf("15 8 8 8 15 5 8 1 15 5 8 15 15 15 8 ");
            for(int i = 16;i <= n;i ++) printf("%d ",i);
        }
        printf("\n");
    }
}

正解思路

参考完善 @jzjr 的题解。

考虑 f(a) 的值。\

$f(a)=2$ 不行，这样的序列势必由两个相同的数字构成，每个数字出现 $2$ 次，只有 $\frac{n}{2}$ 个。\ $f(a)=3$：要求的子序列由两端相同的数字和中间一个数字构成。构造：可以在左端放两个 $1$，右端放一个 $1$，中间的每一个数字任意放，互不相同即可。\ 左端靠右的 $1$ 作为中间数做出了 $1$ 的贡献，中间每一个数作为中间做出 $2$ 的贡献，易知 $g(a)=2n-5$。在 $n\ge6$ 时恒成立。 ## 正解代码 ```cpp #include<bits/stdc++.h> using namespace std; int T,n; int main(){ scanf("%d",&T); while(T --){ scanf("%d",&n); printf("1 1 "); for(int i = 4;i <= n;i ++) printf("%d ",i); printf("1\n"); } return 0; } ```