CF-Round-Div2-1089 - FZSGBall's Blog

528 字

3 分钟

CF-Round-Div2-1089

2026-03-30

算法

CF题解

/

算法

/

CFRound

A题 A Simple Sequence#

原题

思路#

题目中提到了要构造一个排列，满足：

a_1 \bmod a_2 \ge a_2 \bmod a_3 \geq \ldots \ge a_{n-1} \bmod a_{n},

很容易想到，对于一个排列来说，它的倒序排列必定符合这个要求

代码#

1
#include <bits/stdc++.h>
2

3
using namespace std;
4

5
int main() {
6
    int t;
7
    cin >> t;
8
    while (t --) {
9
        int n;
10
        cin >> n;
11
        vector<int> r(n);
12
        int j = 0;
13
        for (int i = n; i > 0; i --) {
14
            r[j] = i;
15
            j ++;
16
        }
17

18
        for (int i = 0; i < n; i ++) {
19
            cout << r[i];
20
            if (i != n - 1) cout << " ";
21
        }
22
        if (t != 0) {
23
            cout << endl;
24
        }
25
    }
26
}

B题 Simply Sitting on Chairs#

原题

思路#

先理清题目涉及到的操作：

给出一个长度为 $n$ 的排列 $p$
从第1把椅子出发，到第i把椅子

移动到第 $i$ 把椅子时：

如果第 $i$ 把椅子被标记了：游戏立即结束
如果第 $i$ 把椅子未被标记：玩家可以坐在第 $i$ 把椅子上，并标记第 $p[i]$ 把椅子并移动到下一把椅子上；或者：跳过当前的椅子，直接移动到下一把椅子上

WARNING
需要注意的是，标记的是第 $p[i]$ 把椅子，不是当前坐上去的椅子
e.g. 当 $p$ 为： $[4, 3, 2, 1]$ 时，如果坐在了第 $2$ 把椅子上，标记的是第 $p[2] = 3$ 把椅子（按照题意，这里的索引以 $1$ 为起始）

理清了上述点之后，按照题目的要求：“最大化坐下次数”，我们不难发现，对于满足条件：

p[i] \le i

的椅子来说，是可以计入答案中的，因为坐上第 $i$ 把椅子后，标记的 $p[i]$ 是已经坐过的，在后续不会出现，不会影响到我们后续结果的增加

所以我们只需要统计，有多少个椅子满足上述的条件即可

代码#

1
#include <bits/stdc++.h>
2

3
using namespace std;
4

5
int main() {
6
    int t;
7
    cin >> t;
8
    while (t--) {
9
        int n;
10
        cin >> n;
11

12
        int ans = 0;
13
        for (int i = 1; i <= n; i++) {
14
            int x;
15
            cin >> x;
16
            if (x <= i) ans++;
17
        }
18

19
        cout << ans << '\n';
20
    }
21
    return 0;
22
}