专栏文章

题解：CF2056C Palindromic Subsequences

MMagallan_forever
CF2056C题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@miqh6f43
此快照首次捕获于
2025/12/04 04:44
3 个月前
此快照最后确认于
2025/12/04 04:44
3 个月前
查看原文

简要说明题意：

有一个含 nn 个元素的数组 aa，f(a)f(a) 是 aa 的最长回文子序列的长度，g(a)g(a) 是长度为 f(a)f(a) 的回文子序列的数量。
现在给出 nn，请给出一个序列 aa 满足如下条件：
  1. 1≤ai≤n, 1≤i≤n1 \leq a_i \leq n,\space 1 \leq i \leq n
  2. g(a)>ng(a)>n

题目分析：

提供一个邪道做法：样例给出了 6,9,156,9,15。
99 的样例是 g(a)=24g(a)=24，而 1515 的样例是 g(a)=190g(a)=190。
nn 的范围是 [6,100][6,100]，所以 n=6, 9≤n≤100n=6,\space 9 \leq n \leq 100 都可以用样例解决（长度不够就用序列中没出现过的数随便补全）
n=7,n=8n=7,n=8 的情况，随便构造一组，注意到 1,2,3,4,1,2,3(,8)1,2,3,4,1,2,3(,8) 可以满足条件。
然后...就做完了...但我在这个题上面的思考时间还是太多了，虽然最终用邪道做法速通了，但没怎么节省时间。
代码如下：
CPP
#include<cstdio>
#include<algorithm>
using namespace std;
int main(){
    int T,n;
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        if(n==6) printf("1 1 2 3 1 2\n");
        if(n==7||n==8){
            printf("1 2 3 4 1 2 3");
            if(n==8) putchar(' '),putchar('8');
            putchar('\n');
        } 
        if(9<=n&&n<15){
            printf("7 3 3 7 5 3 7 7 3 ");
            for(int i=10;i<=n;++i) printf("%d ",i);
            putchar('\n');
        }
        if(n>=15){
            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);
            putchar('\n');
        }
    }
    return 0;
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...