NOTE
比赛链接：Codeforces Round 1099.(Div. 2)

A - Construct an Array#

关键词：签到，构造

思路#

要求所有的相邻项和、所有的数组元素都互不相同，直接顺序输出所有奇数即可。

Code#

1
// Problem: CF 2231 A
2
// Contest: Codeforces - Codeforces Round 1099 (Div. 2)
3
// URL: https://codeforces.com/contest/2231/problem/A
4
// Time: 2026-05-21 23:47:25
5
#include <bits/stdc++.h>
6
using namespace std;
7

8
// clang-format off
9
#define endl '\n'
10
#define all(x) (x).begin(), (x).end()
11
#define fastio() ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
12
// clang-format on
13

14
using ll = long long;
15
using ull = unsigned long long;
16
using pii = pair<int, int>;
17
using pdd = pair<double, double>;
18
using pll = pair<long long, long long>;
19
using i128 = __int128;
20

21
const int dx[] = {-1, 0, 1, 0, -1, 1, 1, -1};
22
const int dy[] = {0, 1, 0, -1, 1, 1, -1, -1};
23
const int inf = 0x3f3f3f3f;
24
const int N = 0;
25

26
void solve()
27
{
28
    int n;
29
    cin >> n;
30

31
    for (int i = 1; i <= 2 * n; i += 2)
32
        cout << i << " ";
33

34
    cout << endl;
35
}
36

37
int main()
38
{
39
    fastio();
40

41
    int T = 1;
42
    cin >> T;
43

44
    while (T--)
45
        solve();
46

47
    return 0;
48
}

B - Another Sorting Problem#

关键词：贪心，思维

思路#

当我们遇到一个逆序对时，有 $a_i > a_{i+1}$ ，我们想让他变成顺序，只能通过给 $a_{i+1}$ 加上 $k$ 。

且 $k$ 有一个下界，为 $L = \max_{a_i > a_{i+1}} (a_i - a_{i+1})$ ，我们希望加上的 $k$ 尽可能小，因为假如 $k$ 非常大，后面的数也被迫要加 $k$ ，但根据前面的推导，逆序对前面的数 $a_i$ 是不能改动的，这样就矛盾了。

我们让 $k=L$ ，从左到右模拟，记录上一个确定好的数字为 $prev$ （初始为 $a_0$ ）。

对于接下来的每一个 $a_i$ ：

如果它原本就 $\ge prev$ ，我们不给它加 $k$ ，直接让 $prev = a_i$ 。
如果它 $< prev$ $< p r e v$ ，那它只能被迫加 $k$ $k$ 。我们检查 $a_i + k$ $a_{i} + k$ 是否 $\ge prev$ $\geq p r e v$ ：
- 如果是，更新 $prev = a_i + k$ 。
- 如果连加了 $k$ 还是小于 $prev$ ，说明不能变成顺序的，直接输出 NO。

如果顺利走到数组末尾，说明存在合法方案，输出 YES。

Code#

1
// Problem: CF 2231 B
2
// Contest: Codeforces - Codeforces Round 1099 (Div. 2)
3
// URL: https://codeforces.com/contest/2231/problem/B
4
// Time: 2026-05-21 23:48:58
5
#include <bits/stdc++.h>
6
using namespace std;
7

8
// clang-format off
9
#define endl '\n'
10
#define all(x) (x).begin(), (x).end()
11
#define fastio() ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
12
// clang-format on
13

14
using ll = long long;
15
using ull = unsigned long long;
16
using pii = pair<int, int>;
17
using pdd = pair<double, double>;
18
using pll = pair<long long, long long>;
19
using i128 = __int128;
20

21
const int dx[] = {-1, 0, 1, 0, -1, 1, 1, -1};
22
const int dy[] = {0, 1, 0, -1, 1, 1, -1, -1};
23
const ll inf = 0x3f3f3f3f;
24
const int N = 0;
25

26
void solve()
27
{
28
    int n;
29
    cin >> n;
30

31
    vector<ll> a(n);
32
    for (int i = 0; i < n; i++)
33
        cin >> a[i];
34

35
    ll k = 0;
36
    for (int i = 0; i < n - 1; i++)
37
        k = max(k, a[i] - a[i + 1]);
38

39
    if (k == 0)
40
    {
41
        cout << "YES" << endl;
42
        return;
43
    }
44

45
    ll prev = a[0];
46
    for (int i = 1; i < n; i++)
47
    {
48
        if (a[i] >= prev)
49
            prev = a[i];
50
        else
51
        {
52
            if (a[i] + k >= prev)
53
                prev = a[i] + k;
54
            else
55
            {
56
                cout << "NO" << endl;
57
                return;
58
            }
59
        }
60
    }
61

62
    cout << "YES" << endl;
63
}
64

65
int main()
66
{
67
    fastio();
68

69
    int T = 1;
70
    cin >> T;
71

72
    while (T--)
73
        solve();
74

75
    return 0;
76
}

C - Chipmunk Theo and Equality#

关键词：模拟

思路#

注意到对于任何一个给定的数字，它的下一步是唯一确定的，都不用搜索，直接模拟下去就可以。

对某个数字不断操作，它最后一定会落入 $1 \leftrightarrow 2$ 的无限循环，因此让所有数字相等的目标一定可以在有限步实现。

由于最多两次操作就能右移一位某个数字，任何一个高达 $10^9$ 的数字，最多只需要约 60 步，就会掉进 1 和 2 的循环中。

因此考虑枚举所有状态，并记录需要操作的步数，也就是 pair<int, int> （状态, 步数），并预留 $60 \times n$ 的空间。

最后排序所有状态，使用双指针统计答案，假设某个状态出现了 $n$ 次，说明可以集体到达这个数，记录并更新答案。

NOTE
本题卡 map。

Code#

1
// Problem: CF 2231 C
2
// Contest: Codeforces - Codeforces Round 1099 (Div. 2)
3
// URL: https://codeforces.com/contest/2231/problem/C
4
// Time: 2026-05-22 13:19:18
5
#include <bits/stdc++.h>
6
using namespace std;
7

8
// clang-format off
9
#define endl '\n'
10
#define all(x) (x).begin(), (x).end()
11
#define fastio() ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
12
// clang-format on
13

14
using ll = long long;
15
using ull = unsigned long long;
16
using pii = pair<int, int>;
17
using pdd = pair<double, double>;
18
using pll = pair<long long, long long>;
19
using i128 = __int128;
20

21
const int dx[] = {-1, 0, 1, 0, -1, 1, 1, -1};
22
const int dy[] = {0, 1, 0, -1, 1, 1, -1, -1};
23
const int inf = 0x3f3f3f3f;
24
const int N = 0;
25

26
void solve()
27
{
28
    int n;
29
    cin >> n;
30

31
    vector<int> a(n);
32
    for (int i = 0; i < n; i++)
33
        cin >> a[i];
34

35
    vector<pii> st; // pair<数值，步数>
36
    st.reserve(n * 60);
37

38
    for (int i = 0; i < n; i++)
39
    {
40
        int x = a[i], steps = 0;
41
        while (true)
42
        {
43
            st.push_back({x, steps});
44
            if (x == 1)
45
            {
46
                st.push_back({2, steps + 1});
47
                break;
48
            }
49
            if (x == 2)
50
            {
51
                st.push_back({1, steps + 1});
52
                break;
53
            }
54

55
            if (x % 2 == 0)
56
                x /= 2;
57
            else
58
                x++;
59

60
            steps++;
61
        }
62
    }
63

64
    sort(all(st));
65

66
    ll res = 1e18;
67

68
    for (int i = 0; i < (int) st.size();)
69
    {
70
        int val = st[i].first;
71
        int cnt = 0;
72
        ll cost = 0;
73

74
        while (i < (int) st.size() && st[i].first == val)
75
        {
76
            cnt++;
77
            cost += st[i].second;
78
            i++;
79
        }
80

81
        if (cnt == n)
82
            res = min(res, cost);
83
    }
84

85
    cout << res << endl;
86
}
87

88
int main()
89
{
90
    fastio();
91

92
    int T = 1;
93
    cin >> T;
94

95
    while (T--)
96
        solve();
97

98
    return 0;
99
}