CF2056C Palindromic Subsequences

hjm777 · 2025-01-20 09:04:48 · 题解

题解

先扔结论：

• 当 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，所以构造是合法的。

代码

#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;
}