Educational Codeforces Round 163 (Rated for Div. 2)

by JiuQiin Codeforces, 题解on Posted on
首页 » 题解 » Codeforces » Educational Codeforces Round 163 (Rated for Div. 2)

一些废话（建议跳过）

之前连着打十天，每天不知道为啥，跟疯了一样，每打完一场，一定要写题解，可能是之前有人告诉过我，写题解是为了督促自己补题吧，是，是有一定的效果，但是不长久，连着写了十天后，彻底写伤了（意思就是写腻了），于是摆了三四天，后来发现，生活好像除了做题，那就只剩下单片机和追剧了，剧，是永远的都追不完的，而单片机并非长远之计，只有写题貌似最有可能出现在我以后的日子中。于是,又死皮赖脸地继续把之前欠的账给还了

Contents hide
1 A. Special Characters
1.1 题意
1.2 思路
1.3 代码
2 B. Array Fix
2.1 题意
2.2 思路
2.3 代码
3 C. Arrow Path
3.1 题意
3.2 思路
3.3 代码（DFS By BlackLily）
3.4 代码（BFS）
3.5 思路
3.6 代码
3.7 题外话
4 D. Tandem Repeats?
4.1 题意
4.2 思路
4.3 代码
5 E. Clique Partition
5.1 题意
5.2 思路
5.3 代码

A. Special Characters

题意

给出一个 nn ，请你创建一个字符串，满足其中有 nn 个特殊字符

特殊字符的定义：其相邻的字符有且仅有一个与他相同

思路

先写一些例子看看：

A : 0

AA : 2

AAA : 2

AAAA : 2

AB : 0

AAB : 2

AAAB : 2

AABB : 4

AAABB : 4

AAABBB : 4

发现，每一种只有在到达两个及以上的时候才会有贡献，但是只有两个是贡献的转折点，再多，都不会增加特殊点的个数，因为中间都是左右两边相邻的都相同，所以，构造出来的形式一定是 AABBCCDD…并且，答案都是以两个两个往上加，不会有奇数个的存在

代码

#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) (x & (-x))
#define endl '\n'
typedef long long LL;
#define PLL pair<LL, LL>
const LL MOD = 998244353;
const LL MAX = 1e6 + 100;
const LL INF = 0x3f3f3f3f3f3f3f;

void solve() {
    int n;
    cin >> n;

    if (n & 1) {
        cout << "NO" << endl;
        return;
    }

    cout << "YES" << endl;
    for (int i = 0; i < n / 2; ++i) {
        cout << char(i % 26 + 'A') << char(i % 26 + 'A');
    }
    
    cout << endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    LL T;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

B. Array Fix

题意

给你一个数组 a，你可以进行以下操作任意次：

选取 aia_i，删除它，然后在相同位置插入 aia_i 包含的数字，按照他们在 aia_i中出现的顺序

问，是否可以将数组 a 变成非递减序列

思路

贪心{\color{yellow}贪心}

如果你正着去思考的话，若当前碰到的 ai<ai−1a_i < a_{i-1}，则你需要拆 ai−1，ai−1 a_{i-1}，a_{i-1} \ 减小，可能会小于 ai−2 \ a_{i-2} \ ,那么你还要去判断是否要拆 ai−2a_{i-2}，然后继续往前判断，可以做，但是不好写

正难则反，我们倒着来思考，若 ai>ai+1a_i > a_{i+1}，则必拆 aia_i ，若没法儿拆，则输出 NO，若拆了以后，组成 aia_i 的元素中第一个大于第二个，则输出 NO，若组成 aia_i 的元素第二个仍大于 ai+1a_{i+1}，则输出 NO。若以上情况都不满足，则将组成 aia_i 的元素中的第一个赋值给 aia_i。继续往下判断

代码

#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) (x & (-x))
#define endl '\n'
typedef long long LL;
#define PLL pair<LL, LL>
const LL MOD = 998244353;
const LL MAX = 1e6 + 100;
const LL INF = 0x3f3f3f3f3f3f3f;

void solve() {
    int n;
    cin >> n;

    vector<int> a(n+ 1);

    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }

    for (int i = n - 1; i >= 1; --i) {
        if (a[i] > a[i + 1]) {
            if (a[i] < 10) {
                cout << "NO" << endl;
                return;
            }
            int d1 = a[i] / 10;
            int d0 = a[i] % 10;
            if (d1 > d0) {
                cout << "NO" << endl;
                return;
            }
            if (d0 > a[i + 1]) {
                cout << "NO" << endl;
                return;
            }
            a[i] = d1;
        }
    }
    cout << "YES" << endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    LL T;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

C. Arrow Path

题意

给你一个 2×n2 \times n 的网格，每个格子中都有 ‘<‘ 或者 ‘>’ ，你从 (1,1)(1, 1) 出发，按照以下规则行驶：

  • 首先，你可以随意选取一个方向走，向上，向下，向左，或者向右，只要在网格中都行
  • 然后，你必须按照网格中的指示的方向走

问，能否到达 (2,n)(2, n)

思路

DFS/BFS{\color{yellow}DFS/BFS}

这个道题用 DFSDFS 还是 BFSBFS 都是差不多的时间复杂度

代码（DFS By BlackLily）

// 为何妄自菲薄你我本是同类 莫非你也认为存在即是原罪
#include <bits/stdc++.h>
using namespace std;
const int maxn = 500005;
int n, m, T, ans, flg;
int a[maxn], vis[3][maxn], dx[5] = {0, 1, 0, 0, -1}, dy[5] = {0, 0, 1, -1, 0};
string s[3];
int dfs(int x, int y)
{
    if (vis[x][y])
        return 0;
    if (x == 2 && y == n)
        return 1;
    vis[x][y] = 1;
    for (int d = 1; d <= 4; d++)
    {
        int u = x + dx[d], v = y + dy[d];
        if (u >= 1 && u <= 2 && v >= 1 && v <= n)
        {
            if (u == 2 && v == n)
                return 1;
            int c = s[u][v] == '<';
            if (c)
                v--;
            else
                v++;
            if (dfs(u, v))
                return 1;
        }
    }
    return 0;
}
int main()
{
    scanf("%d", &T);
    while (T--)
    {
        scanf("%d", &n), cin >> s[1] >> s[2], s[1] = " " + s[1], s[2] = " " + s[2];
        puts(dfs(1, 1) ? "YES" : "NO");
        for (int i = 1; i <= n; i++)
            vis[1][i] = vis[2][i] = 0;
    }
    return 0;
}

代码（BFS）

// 万物皆在消亡，唯有意识仍在反抗。若终焉是所有生命的归宿，那我便要在毁灭之前，向虚无宣告我的名字
#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) (x & (-x))
#define endl '\n'
typedef long long LL;
#define PLL pair<LL, LL>
const LL MOD = 998244353;
const LL MAX = 1e6 + 100;
const LL INF = 0x3f3f3f3f3f3f3f;

int dx[] = {0, 0, -1, 1};
int dy[] = {-1, 1, 0, 0};

void solve() {
    int n;
    cin >> n;
    vector<vector<char>> g(3, vector<char>(n + 5));

    for (int i = 1; i <= 2; ++i) {
        for (int j = 1; j <= n; ++j) {
            cin >> g[i][j];
        }
    }

    vector<vector<int>> vis(3, vector<int> (n + 5, 0));

    auto in = [&](int x, int y)
    {
        return x >= 1 && x <= 2 && y >= 1 && y <= n;
    };

    queue<PLL> q;

    q.push({1, 1});

    while (!q.empty()) {
        auto [x, y] = q.front();
        q.pop();

        if (x == 2 && y == n) {
            cout << "YES" << endl;
            return;
        }

        if (vis[x][y]) continue;
        vis[x][y] = 1;

        for (int i = 0; i < 4; ++i) {
            int a = x + dx[i];
            int b = y + dy[i];

            if (!in(a, b)) continue;
            if (vis[a][b]) continue;

            if (a == 2 && b == n) {
                cout << "YES" << endl;
                return;
            }

            vis[a][b] = 1;

            if (g[a][b] == '>') {
                ++b;
            }
            else {
                --b;
            }
            if (in(a, b)) {
                q.push({a, b});
            }
        }
    }

    cout << "NO" << endl;
}


signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    LL T;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

思路

观察法{\color{yellow}观察法}

发现，轮到第一行偶数时，应该按照指示走，若当前指示为 ‘<‘，那就得退回去，往下走，若下面的指示也为 ‘<‘，则被堵住了。同理，若轮到第二行奇数时，应该按照指示走，若当前指示为 ‘<‘，那就得退回去，往上走，若上面也是 ‘<‘，则无解。综上，去判断所有对角线是否都是 ‘<‘，除开 (2, n)

代码

#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) (x & (-x))
#define endl '\n'
typedef long long LL;
#define PLL pair<LL, LL>
const LL MOD = 998244353;
const LL MAX = 1e6 + 100;
const LL INF = 0x3f3f3f3f3f3f3f;

void solve() {
    int n;
    cin >> n;

    string s0, s1;
    cin >> s0 >> s1;
    s0 = ' ' + s0;
    s1 = ' ' + s1;

    for (int i = 2; i <= n; i += 2) {
        if (s0[i] == '<' && s1[i - 1] == '<') {
            cout << "NO" << endl;
            return;
        }
        if (s0[i] == '<' && i + 1 < n && s1[i + 1] == '<') {
            cout << "NO" << endl;
            return;
        }
    }
    cout << "YES" << endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    LL T;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

题外话

第一个 DFS 的代码由 BlackLily 写的，在最开头有一段很中二的话，不知道为啥，我莫名很喜欢，所以专门去搜了一下， 以下是 ChatGPT 的解释：

这句话带有比较浓厚的哲学和文学色彩，可以拆开来看。

为何妄自菲薄，你我本是同类。莫非你也认为，存在即是原罪？

逐句解释：

第一句：为何妄自菲薄，你我本是同类

  • 妄自菲薄：过分轻视自己，看不起自己，觉得自己不如别人。
  • 你我本是同类：我们本质上没有什么区别，都是一样的人（或者一样的生命）。

这句话的意思就是：

为什么要看不起自己？我们本来就是一样的人，没有高低贵贱之分。

它是在劝对方不要自卑，不要否定自己的价值。

第二句：莫非你也认为，存在即是原罪？

这里借用了西方哲学和宗教中的表达。

原罪（Original Sin）

  • 在基督教中，人类因为亚当和夏娃犯罪，出生就带有”原罪”，需要救赎。
  • 后来很多文学作品会把”原罪”引申成一种宿命性的罪恶。

存在即是原罪并不是严格的哲学命题，而是一种文学化表达。

它大概表示：

是不是你觉得，只要活着、只要存在，本身就是一种错误、一种罪过？

也就是说，一个人已经否定自己到了极点，觉得：

  • 我什么都做不好。
  • 我不应该活着。
  • 我的存在就是拖累别人。
  • 我生下来就是错的。

这种极端的自我否定，就可以用”认为存在即是原罪”来形容。

合起来理解

整句话其实是在反问对方：

为什么这样贬低自己？我们本来没有什么不同。难道你已经觉得，连自己的存在都是一种错误吗？

它的潜台词是：

你的价值并不比别人低，不要把自己否定到连存在都觉得有罪的程度。

D. Tandem Repeats?

题意

给你一个字符串 s，问你最长的串联重复的长度是多少，串联重复的定义是：

将该字符串分成左右两部分，左半部分完全等于右半部分（不是回文串的那种轴对称等于，是平移的那种等于）

思路

暴力{\color{yellow}暴力}

f[i][j]f[i][j] : 第 ii 个字符是否有可能等于前面第 (i−j)(i – j) 个字符

所以，假设我们要找固定长度为 k 的答案是否存在，就去看是否存在长度为 kk 的 f[i][k]=1,f[i+1][k]=1,f[i+2][k]=1…f[i+k−1][k]=1f[i][k] = 1, f[i + 1][k] = 1, f[i + 2][k] = 1 . . . f[i + k – 1][k] = 1，就是去看某个长度为 kk 的区间，和是否为 kk，用前缀和维护。枚举一次 kk ，时间复杂度是 O(n)O(n)，k 次时间复杂度为 O(n2)O(n^2) ，而 nn 是 50005000，所以，暴力能过

代码

#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) (x & (-x))
#define endl '\n'
typedef long long LL;
#define PLL pair<LL, LL>
const LL MOD = 998244353;
const LL MAX = 1e6 + 100;
const LL INF = 0x3f3f3f3f3f3f3f;

void solve() {
    string s;
    cin >> s;
    LL n = s.size();

    vector<vector<LL>> f(n + 1, vector<LL>(n + 1));

    for (LL i = 1; i <= n; ++i) {
        for (LL j = 1; j <= i; ++j) {
            if (s[i] == s[i - j] || s[i] == '?' || s[i - j] == '?') {
                f[i][j] = 1;
            }
        }
    }

    LL ans = 0;
    for (LL k = 1; k <= n / 2; ++k) {
        vector<LL> pre(n + 1, 0);
        for (LL i = 1; i <= n; ++i) {
            pre[i] = pre[i - 1] + f[i][k];
        }
        for (LL l = 0, r = l + k; r <= n; ++l, ++r) {
            if (pre[r] - pre[l] == k) {
                ans = max(ans, k);
            }
        }
    }

    cout << ans * 2 << endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    LL T;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

E. Clique Partition

题意

给你两个整数 n,kn, k，请你构造出一个排列 aa 。若i,j i, j 满足 |i−j|+|ai−aj|≤k|i – j| + |a_i – a_j| \leq k ，则 aia_i 与 aja_j 之间有一条连线，在一个群当中的每两个点之间都有连线。问如何构造才能使群的数目最少

思路

首先，最显而易见的一点就是一个群中不可能有 (k+1)(k + 1) 个数，根据鸽巢原理，呃，其实并未，你就简单的想一下，假设有 (k+1)(k +1) 个数，则其中必有两个数之间的下标之差的绝对值为 kk，而由排列的定义， ai≠aja_i \neq a_j，所以 |ai−aj|≥1\ |a_i – a_j| \geq 1，则两者相加必定大于 kk ，不可能

那现在就来猜了，假设一个群中最多有 kk 个数字，可以感觉出来，数与数之间差值尽量要小对吧，所以，分类大概就是 1  ˜ k,k+1  ˜ 2k,2k+1  ˜ 3k,...1 \ \~\ \ k, k+1 \ \~\ \ 2k, 2k+1 \ \~\ \ 3k, …

现在就来找当 n=kn = k 时，如何排列使得该群中的数字都满足两两之间都有连线，打表，将 n≤10\ n \leq 10 的答案都打印出来，打表的代码如下：

#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) (x & (-x))
#define endl '\n'
typedef long long LL;
#define PLL pair<LL, LL>
const LL MOD = 998244353;
const LL MAX = 1e6 + 100;
const LL INF = 0x3f3f3f3f3f3f3f;

void solve() {
    
    int n = 10;

    auto check = [](vector<int> &a, int k) {
        int m = a.size();
        for (int i = 0; i < m; ++i) {
            for (int j = i + 1; j < m; ++j) {
                if (abs(i - j) + abs(a[i] - a[j]) > k)
                    return false;
            }
        }
        return true;
    };

    for (int i = 2; i <= n; ++i) {
        cout << i << endl;
        vector<int> a(i);
        iota(a.begin(), a.end(), 1);
        do {
            if (check(a, i)) {
                for (auto v : a) {
                    cout << v << " ";
                }
                cout << endl;
            }
        } while (next_permutation(a.begin(), a.end()));
        cout << endl;
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    LL T = 1;
    //cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

结果如下：

2
1 2 
2 1 

3
1 3 2 
2 1 3 
2 3 1 
3 1 2 

4
1 4 3 2 
2 1 4 3 
2 3 4 1 
2 4 1 3 
3 1 4 2 
3 2 1 4 
3 4 1 2 
4 1 2 3 

5
2 1 5 4 3 
2 4 5 1 3 
2 5 1 4 3 
3 1 5 4 2 
3 2 1 5 4 
3 2 5 1 4 
3 4 1 5 2 
3 4 5 1 2 
3 5 1 2 4 
4 1 5 2 3 
4 2 1 5 3 
4 5 1 2 3 

6
2 1 6 5 4 3 
2 5 6 1 4 3 
3 2 1 6 5 4 
3 2 5 6 1 4 
3 2 6 1 5 4 
3 4 1 6 5 2 
3 4 5 6 1 2 
3 5 1 6 2 4 
3 5 6 1 2 4 
3 6 1 2 5 4 
4 1 6 5 2 3 
4 2 1 6 5 3 
4 2 6 1 5 3 
4 3 2 1 6 5 
4 3 6 1 2 5 
4 5 1 6 2 3 
4 5 2 1 6 3 
4 5 6 1 2 3 
5 2 1 6 3 4 
5 6 1 2 3 4 

7
3 2 1 7 6 5 4 
3 2 6 7 1 5 4 
3 2 7 1 6 5 4 
3 5 1 7 6 2 4 
3 5 6 7 1 2 4 
3 6 1 7 2 5 4 
3 6 7 1 2 5 4 
4 2 1 7 6 5 3 
4 2 6 7 1 5 3 
4 3 2 1 7 6 5 
4 3 2 7 1 6 5 
4 3 6 1 7 2 5 
4 3 6 7 1 2 5 
4 3 7 1 2 6 5 
4 5 1 7 6 2 3 
4 5 2 1 7 6 3 
4 5 2 7 1 6 3 
4 5 6 1 7 2 3 
4 5 6 7 1 2 3 
4 6 2 1 7 3 5 
4 6 7 1 2 3 5 
5 2 1 7 6 3 4 
5 2 7 1 6 3 4 
5 3 2 1 7 6 4 
5 3 7 1 2 6 4 
5 6 1 7 2 3 4 
5 6 2 1 7 3 4 
5 6 7 1 2 3 4 

8
3 2 1 8 7 6 5 4 
3 2 7 8 1 6 5 4 
3 6 1 8 7 2 5 4 
3 6 7 8 1 2 5 4 
4 3 2 1 8 7 6 5 
4 3 2 7 8 1 6 5 
4 3 2 8 1 7 6 5 
4 3 6 1 8 7 2 5 
4 3 6 7 8 1 2 5 
4 3 7 1 8 2 6 5 
4 3 7 8 1 2 6 5 
4 3 8 1 2 7 6 5 
4 5 2 1 8 7 6 3 
4 5 2 7 8 1 6 3 
4 5 6 1 8 7 2 3 
4 5 6 7 8 1 2 3 
4 6 2 1 8 7 3 5 
4 6 2 8 1 7 3 5 
4 6 7 1 8 2 3 5 
4 6 7 8 1 2 3 5 
4 7 2 1 8 3 6 5 
4 7 8 1 2 3 6 5 
5 2 1 8 7 6 3 4 
5 2 7 8 1 6 3 4 
5 3 2 1 8 7 6 4 
5 3 2 8 1 7 6 4 
5 3 7 1 8 2 6 4 
5 3 7 8 1 2 6 4 
5 4 3 2 1 8 7 6 
5 4 3 8 1 2 7 6 
5 4 7 2 1 8 3 6 
5 4 7 8 1 2 3 6 
5 6 1 8 7 2 3 4 
5 6 2 1 8 7 3 4 
5 6 2 8 1 7 3 4 
5 6 3 2 1 8 7 4 
5 6 3 8 1 2 7 4 
5 6 7 1 8 2 3 4 
5 6 7 2 1 8 3 4 
5 6 7 8 1 2 3 4 
6 3 2 1 8 7 4 5 
6 3 8 1 2 7 4 5 
6 7 2 1 8 3 4 5 
6 7 8 1 2 3 4 5 

9
4 3 2 1 9 8 7 6 5 
4 3 2 8 9 1 7 6 5 
4 3 2 9 1 8 7 6 5 
4 3 7 1 9 8 2 6 5 
4 3 7 8 9 1 2 6 5 
4 3 8 1 9 2 7 6 5 
4 3 8 9 1 2 7 6 5 
4 6 2 1 9 8 7 3 5 
4 6 2 8 9 1 7 3 5 
4 6 7 1 9 8 2 3 5 
4 6 7 8 9 1 2 3 5 
4 7 2 1 9 8 3 6 5 
4 7 2 9 1 8 3 6 5 
4 7 8 1 9 2 3 6 5 
4 7 8 9 1 2 3 6 5 
5 3 2 1 9 8 7 6 4 
5 3 2 8 9 1 7 6 4 
5 3 7 1 9 8 2 6 4 
5 3 7 8 9 1 2 6 4 
5 4 3 2 1 9 8 7 6 
5 4 3 2 9 1 8 7 6 
5 4 3 8 1 9 2 7 6 
5 4 3 8 9 1 2 7 6 
5 4 3 9 1 2 8 7 6 
5 4 7 2 1 9 8 3 6 
5 4 7 2 9 1 8 3 6 
5 4 7 8 1 9 2 3 6 
5 4 7 8 9 1 2 3 6 
5 4 8 2 1 9 3 7 6 
5 4 8 9 1 2 3 7 6 
5 6 2 1 9 8 7 3 4 
5 6 2 8 9 1 7 3 4 
5 6 3 2 1 9 8 7 4 
5 6 3 2 9 1 8 7 4 
5 6 3 8 1 9 2 7 4 
5 6 3 8 9 1 2 7 4 
5 6 7 1 9 8 2 3 4 
5 6 7 2 1 9 8 3 4 
5 6 7 2 9 1 8 3 4 
5 6 7 8 1 9 2 3 4 
5 6 7 8 9 1 2 3 4 
5 7 3 2 1 9 8 4 6 
5 7 3 9 1 2 8 4 6 
5 7 8 2 1 9 3 4 6 
5 7 8 9 1 2 3 4 6 
6 3 2 1 9 8 7 4 5 
6 3 2 9 1 8 7 4 5 
6 3 8 1 9 2 7 4 5 
6 3 8 9 1 2 7 4 5 
6 4 3 2 1 9 8 7 5 
6 4 3 9 1 2 8 7 5 
6 4 8 2 1 9 3 7 5 
6 4 8 9 1 2 3 7 5 
6 7 2 1 9 8 3 4 5 
6 7 2 9 1 8 3 4 5 
6 7 3 2 1 9 8 4 5 
6 7 3 9 1 2 8 4 5 
6 7 8 1 9 2 3 4 5 
6 7 8 2 1 9 3 4 5 
6 7 8 9 1 2 3 4 5 

10
4 3 2 1 10 9 8 7 6 5 
4 3 2 9 10 1 8 7 6 5 
4 3 8 1 10 9 2 7 6 5 
4 3 8 9 10 1 2 7 6 5 
4 7 2 1 10 9 8 3 6 5 
4 7 2 9 10 1 8 3 6 5 
4 7 8 1 10 9 2 3 6 5 
4 7 8 9 10 1 2 3 6 5 
5 4 3 2 1 10 9 8 7 6 
5 4 3 2 9 10 1 8 7 6 
5 4 3 2 10 1 9 8 7 6 
5 4 3 8 1 10 9 2 7 6 
5 4 3 8 9 10 1 2 7 6 
5 4 3 9 1 10 2 8 7 6 
5 4 3 9 10 1 2 8 7 6 
5 4 3 10 1 2 9 8 7 6 
5 4 7 2 1 10 9 8 3 6 
5 4 7 2 9 10 1 8 3 6 
5 4 7 8 1 10 9 2 3 6 
5 4 7 8 9 10 1 2 3 6 
5 4 8 2 1 10 9 3 7 6 
5 4 8 2 10 1 9 3 7 6 
5 4 8 9 1 10 2 3 7 6 
5 4 8 9 10 1 2 3 7 6 
5 4 9 2 1 10 3 8 7 6 
5 4 9 10 1 2 3 8 7 6 
5 6 3 2 1 10 9 8 7 4 
5 6 3 2 9 10 1 8 7 4 
5 6 3 8 1 10 9 2 7 4 
5 6 3 8 9 10 1 2 7 4 
5 6 7 2 1 10 9 8 3 4 
5 6 7 2 9 10 1 8 3 4 
5 6 7 8 1 10 9 2 3 4 
5 6 7 8 9 10 1 2 3 4 
5 7 3 2 1 10 9 8 4 6 
5 7 3 2 10 1 9 8 4 6 
5 7 3 9 1 10 2 8 4 6 
5 7 3 9 10 1 2 8 4 6 
5 7 8 2 1 10 9 3 4 6 
5 7 8 2 10 1 9 3 4 6 
5 7 8 9 1 10 2 3 4 6 
5 7 8 9 10 1 2 3 4 6 
5 8 3 2 1 10 9 4 7 6 
5 8 3 10 1 2 9 4 7 6 
5 8 9 2 1 10 3 4 7 6 
5 8 9 10 1 2 3 4 7 6 
6 3 2 1 10 9 8 7 4 5 
6 3 2 9 10 1 8 7 4 5 
6 3 8 1 10 9 2 7 4 5 
6 3 8 9 10 1 2 7 4 5 
6 4 3 2 1 10 9 8 7 5 
6 4 3 2 10 1 9 8 7 5 
6 4 3 9 1 10 2 8 7 5 
6 4 3 9 10 1 2 8 7 5 
6 4 8 2 1 10 9 3 7 5 
6 4 8 2 10 1 9 3 7 5 
6 4 8 9 1 10 2 3 7 5 
6 4 8 9 10 1 2 3 7 5 
6 5 4 3 2 1 10 9 8 7 
6 5 4 3 10 1 2 9 8 7 
6 5 4 9 2 1 10 3 8 7 
6 5 4 9 10 1 2 3 8 7 
6 5 8 3 2 1 10 9 4 7 
6 5 8 3 10 1 2 9 4 7 
6 5 8 9 2 1 10 3 4 7 
6 5 8 9 10 1 2 3 4 7 
6 7 2 1 10 9 8 3 4 5 
6 7 2 9 10 1 8 3 4 5 
6 7 3 2 1 10 9 8 4 5 
6 7 3 2 10 1 9 8 4 5 
6 7 3 9 1 10 2 8 4 5 
6 7 3 9 10 1 2 8 4 5 
6 7 4 3 2 1 10 9 8 5 
6 7 4 3 10 1 2 9 8 5 
6 7 4 9 2 1 10 3 8 5 
6 7 4 9 10 1 2 3 8 5 
6 7 8 1 10 9 2 3 4 5 
6 7 8 2 1 10 9 3 4 5 
6 7 8 2 10 1 9 3 4 5 
6 7 8 3 2 1 10 9 4 5 
6 7 8 3 10 1 2 9 4 5 
6 7 8 9 1 10 2 3 4 5 
6 7 8 9 2 1 10 3 4 5 
6 7 8 9 10 1 2 3 4 5 
7 4 3 2 1 10 9 8 5 6 
7 4 3 10 1 2 9 8 5 6 
7 4 9 2 1 10 3 8 5 6 
7 4 9 10 1 2 3 8 5 6 
7 8 3 2 1 10 9 4 5 6 
7 8 3 10 1 2 9 4 5 6 
7 8 9 2 1 10 3 4 5 6 
7 8 9 10 1 2 3 4 5 6

说真的，真的能看出来的人也是很牛逼了，我不知道有什么更好的办法，真就 定眼法{\color{yellow}定眼法}

观察发现，对于 kk 为偶数，直接将其平均分成两半，左右部分分别翻转

对于 kk 为奇数，将前 ⌊k2⌋\left \lfloor \frac{k}{2} \right \rfloor 翻转，将剩下的一半翻转

对于 nn 除以 k 有余数的情况，最后余下的那部分也进行翻转

代码

#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) (x & (-x))
#define endl '\n'
typedef long long LL;
#define PLL pair<LL, LL>
const LL MOD = 998244353;
const LL MAX = 1e6 + 100;
const LL INF = 0x3f3f3f3f3f3f3f;

void solve() {
    int n, k;
    cin >> n >> k;

    vector<int> a(n + 1), c(n + 1);
    iota(a.begin() + 1, a.end(), 1);

    k = min(n, k);

    int cnt = 0;
    for (int i = 1; i <= n; ) {
        int l1 = i;
        int r1 = min(i + k / 2 - 1, n);
        int l2 = min(r1 + 1, n);
        int r2 = min(i + k - 1, n);
        while (l1 < r1) {
            swap(a[l1], a[r1]);
            ++l1, --r1;
        }
        while (l2 < r2) {
            swap(a[l2], a[r2]);
            ++l2, --r2;
        }

        ++cnt;
        for (int j = i; j <= min(n, i + k - 1); ++j) {
            c[j] = cnt;
        }
        i += k;
    }

    for (int i = 1; i <= n; ++i) {
        cout << a[i] << " ";
    }
    cout << endl;
    cout << cnt << endl;
    for (int i = 1; i <= n; ++i) {
        cout << c[i] << " ";
    }
    cout << endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    LL T;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}
“惟将终夜常开眼，报答平生未展眉。”
— 元稹 · 遣悲怀三首·其三

Leave a Comment

您的邮箱地址不会被公开。 必填项已用 * 标注