CF2056C Palindromic Subsequences

题解

先扔结论：

当 $n = 6$ 时构造 $1, 1, 2, 3, 1, 2$ 。
其他情况构造 $1, 2, 3, 4, \dots, n - 3, n - 2, 1, 2$ 。

第一种情况是样例，不用解释。

第二种情况可以发现最大的回文子序列的长度永远是

3

，分别为：

$1, 2, 1$
$1, 3, 1$
$\dots$
$1, n - 3, 1$
$1, n - 2, 1$
$2, 3, 2$
$2, 4, 2$
$\dots$
$2, n - 2, 2$
$2, 1, 2$

总共有

2 \times (n - 3)

个，又

n > 6

，所以构造是合法的。

代码

CPP

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
#define dbg(x) cout << #x " = " << (x) << endl
#define quickio ios::sync_with_stdio(false);
#define quickin cin.tie(0);
#define quickout cout.tie(0);

using namespace std;

signed main() {
    quickio
    quickin
    quickout
    int t;
    cin >> t;

    while(t--) {
        int n;
        cin >> n;

        if(n == 6) {
            cout << "1 1 2 3 1 2\n";
            continue ;
        }
        cout << "1 2 ";
        for(int i = 3; i <= n - 2; i++) {
            cout << i << ' ';
        }
        cout << "1 2\n";
    }
    return 0;
}

CF2056C Palindromic Subsequences

文章操作

题解

代码

相关推荐

评论

CF2056C Palindromic Subsequences