CF R1019

发表于 更新于 分类于 ， 阅读次数： 作者 Pomelorin ， Cool-breeze

Problem A

正整数范围内，长度为 \(n\) 的漂亮序列 \(x\) 的定义：存在与之长度相等、元素互不相同的序列 \(y\)，使得 \(\forall\text{ }i,j\in[1,n],x_iy_i=x_jy_j\)。给一个长度为 \(n\) 的正整数序列 \(a\)，求最长的子序列 \(a'\)，使 \(a'\) 为漂亮序列。\(t\) 组数据。

\(1≤t≤500,1≤n≤100,1≤a_i≤n\)。

点击查看题解

显然，\(x\) 是漂亮序列的必要条件为 \(x\) 内的元素互不相等。下面是充分性证明：令 \(M=\prod x_i\)，则 \(y_i=M/x_i\)，符合题意。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define PII pair<ll,ll>
const ll N = 150 + 50;

ll n, a[N], b[N], ans;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll T;
    cin >> T;
    while (T--) {
        cin >> n;
        memset(b, 0, sizeof(b));
        ans = 0;
        for (ll i = 1; i <= n; i++) {
            cin >> a[i];
            b[a[i]]++;
        }
        for (ll i = 1; i <= n; i++) {
            if (b[i])
                ans++;
        }
        cout << ans << endl;
    }
    return 0;
}

Problem B

需要用一根手指以及只有 0 和 1 两个按钮的打字机打出一个长度为 \(n\) 的 01 字符串 \(s\)。有两种操作：把手指放在另一个按钮上，或者按按钮。刚开始手指在按钮 0 上。可以选择翻转 \(s\) 内的任一个子区间，使得操作次数尽量少。求最少操作次数。

\(1≤n≤2\times10^5\)。

点击查看题解

减少操作次数的原理是翻转合并了一些数字相同区间，减少切换次数。由于翻转改变的是两头的数，内部和外部均不影响，所以最多减少 \(2\) 步操作次数。由于刚开始在按钮 0，可以将 \(s\) 开头插入一个 0，方便统计切换次数，以判断可以减少几步操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define PII pair<ll,ll>
const ll N = 150 + 50;

ll n, b[N], ans, cur, cha;
string s;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll T;
    cin >> T;
    while (T--) {
        cin >> n >> s;
        s = '0' + s;
        ans = cha = 0;
        cur = '0';
        for (ll i = 0; i <= n; i++) {
            ans += 1;
            if (s[i] != cur) {
                ans += 1;
                cha += 1;
                cur = s[i];
            }
        }
        if (cha >= 3)
            ans -= 2;
        else if (cha == 2) {
            ans -= 1;
        } else {
            ans -= 0;
        }
        cout << ans - 1 << endl;
    }
    return 0;
}

Problem C

定义长度为 \(m\) 的数列的中位数是数列中第 \(\lceil m/2 \rceil\) 小的数。现在给一个长度为 \(n\) 的正整数数列 \(a\) 和正整数 \(k\)，询问能否将数列分成三个连续的子数列 \(a_{1\sim l-1},a_{l\sim r},a_{r+1\sim n}\)，这三个子数列的中位数分别为 \(q_1,q_2,q_3\)，组成数列 \(q\)，使得 \(q\) 的中位数小于等于 \(k\)。

\(3≤n≤2\times10^5, 1≤k≤10^9,1≤a_i≤10^9\)。

点击查看题解

此题不必使用对顶堆等求出具体的中位数。对于一段区间，只需满足小于等于 \(k\) 的数字数量 \(\ge\) 大于 \(k\) 的数字数量，即可判断其中位数是否小于等于 \(k\)。令小于等于 \(k\) 的数字贡献为 \(-1\)，大于 \(k\) 的数字贡献为 \(1\)，利用前缀和或后缀和可以算出某个区间的中位数是否小于等于 \(k\)（区间贡献和小于等于 \(0\)）。

只需要满足三个 \(q\) 中有两个 \(\le k\)，即可满足题意。分类讨论：

  • 前缀、后缀均满足；
  • 前缀、后缀只有一个满足；
  • 前缀、后缀均不满足。

第一种情况：只需找出一个前缀和一个后缀，贡献和小于等于 \(0\) 即可。可以利用取 min 前缀 / 后缀和解决。

第二种情况：例如前缀满足，需要找出一个后缀，减去这个后缀之后中段小于等于 \(0\) 即可。可以利用后缀和减去取 max 后缀和解决。注意，企图使用“合法前缀 + 一个小于等于 \(k\) 的数字”的组合来判断是错误的。

第三种情况：不满足题意，输出 “NO”。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define PII pair<ll,ll>
const ll N = 200000 + 50, inf = 1145141919810;

ll n, k, a[N];
ll nump[N], numn[N], maxp[N], maxn[N], minp[N], minn[N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll T;
    cin >> T;
    while (T--) {
        ll ans = 0;
        cin >> n >> k;
        for (ll i = 1; i <= n; i++) {
            cin >> a[i];
        }
        nump[0] = numn[n + 1] = 0;
        maxp[0] = maxn[n + 1] = -inf;
        minp[0] = minn[n + 1] = inf;
        for (ll i = 1; i <= n; i++) {
            nump[i] = nump[i - 1];
            if (a[i] > k)
                nump[i]++;
            else
                nump[i]--;
            maxp[i] = max(maxp[i - 1], nump[i]);
            minp[i] = min(minp[i - 1], nump[i]);
        }
        for (ll i = n; i >= 1; i--) {
            numn[i] = numn[i + 1];
            if (a[i] > k)
                numn[i]++;
            else
                numn[i]--;
            maxn[i] = max(maxn[i + 1], numn[i]);
            minn[i] = min(minn[i + 1], numn[i]);
        }
        for (ll i = 1; i <= n - 2; i++) {
            if (minp[i] <= 0 && minn[i + 2] <= 0) {
                ans = 1;
                break;
            }
            if (nump[i] <= 0 && numn[i + 1] - maxn[i + 2] <= 0) {
                ans = 1;
                break;
            }
            if (nump[i + 1] - maxp[i] <= 0 && numn[i + 2] <= 0) {
                ans = 1;
                break;
            }
        }
        if (ans == 1)
            cout << "YES" << endl;
        else
            cout << "NO" << endl;
    }
    return 0;
}

Problem D

定义极大/小值：若 \(a_i\) 相邻的两个数（若 \(i=1\text{ or }n\)，则为相邻的一个数）都比 \(a_i\) 小/大，称 \(a_i\) 为极大/小值。

现给出长度为 \(n\) 的某排列 \(p\)，反复进行以下操作，直至剩余一个元素：

  • 删除所有非极小值元素；
  • 删除所有非极大值元素。

令数组 \(b\) 的定义为：若 \(p_i\) 在第 \(k\) 次操作被删除，则 \(b_i=k\)；若 \(p_i\) 为最后剩下的那一个元素，则 \(b_i=-1\)。

现在给出 \(b\)，求出任意一个满足的排列 \(p\)。

\(2≤n≤2\times 10^5\)，可以证明 \(b_i\) 最大不超过 \(\lceil\log_2 n\rceil\)。

点击查看题解

考虑贪心。

  • 由于 \(n\) 为最大值，一定在第一轮被删除；\(n\) 被删除后，由于 \(n-1\) 成为了新最大值，要么第一轮被删除要么第三轮被删除。
  • 显然任意时刻不会有两个相邻的极大/小值，不可能连续出现两个非 1（当前考虑的最小 \(b\) 值）。可以一层层递归考虑，每一层需要不是极大/小值，就直接一次填最小/大的数。

得到贪心策略：\(b_i=1,3,...\) 的位置从大往小填，\(b_i=2,4,...\) 的位置从小往大填；\(b_i\) 相同的连续段要单调上升/下降地填，双指针循环就行。例如（数字仅代表相对大小）：

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

如果考虑利用建图跑拓扑排序，由于不易利用好所有的大小关系进行建图，做法较复杂。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define PII pair<ll,ll>
const ll N = 200000 + 50, inf = 1145141919810;

ll n, a[N], ans[N];

ll nxt(ll x, ll cur) {
    for (ll i = x + 1; i <= n; i++) {
        if (a[i] < cur)
            continue;
        if (a[i] > cur)
            return -i;
        if (a[i] == cur)
            return i;
    }
    return 0;
}

ll pre(ll x, ll cur) {
    for (ll i = x - 1; i >= 1; i--) {
        if (a[i] < cur)
            continue;
        if (a[i] > cur)
            return -i;
        if (a[i] == cur)
            return i;
    }
    return 0;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    ll T;
    cin >> T;
    while (T--) {
        cin >> n;
        ll m = 0, l = 1, r = n;
        for (ll i = 1; i <= n; i++) {
            cin >> a[i];
            m = max(m, a[i]);
            ans[i] = 0;
        }
        for (ll i = 1; i <= n; i++) {
            if (a[i] == -1)
                a[i] = m + 1;
        }
        for (ll i = 1; i <= m + 1; i++) {
            ll j = 0, flag = 1;
            if (a[j] != i)
                j = nxt(j, i);
            for (; j > 0; j = nxt(j, i)) {
                if (ans[j])
                    break;
                if (i % 2)
                    ans[j] = r--;
                else
                    ans[j] = l++;
            }
            j = n;
            if (a[j] != i)
                j = pre(j, i);
            while (flag) {
                for (; j > 0; j = pre(j, i)) {
                    if (ans[j]) {
                        flag = 0;
                        break;
                    }
                    if (i % 2)
                        ans[j] = r--;
                    else
                        ans[j] = l++;
                }
                if (j == 0)
                    break;
                j = pre(-j, i);
            }
        }
        for (ll i = 1; i <= n; i++)
            cout << ans[i] << " ";
        cout << endl;
    }
    return 0;
}

Problem E

给定正整数 \(k\) 和长度为 \(n\) 的整数序列 \(a\)。可以进行以下操作：

选取两个索引 \(i,j\)，要求 \(a_i+a_j=k,i\not=j,1\le i,j\le n\)；接下来，可选取整数 \(x\in[0,a_i]\)，使 \(a_i\gets a_i-x,a_j\gets a_j+x\)。

可以证明，如果有解，最多进行 \(3n\) 次这样的操作，使得 \(a\) 变为一个单调非降序列。

请给出每一步操作方法，或者说明无解。

\(4≤n≤2\times10^5, 1≤k≤10^9,0≤a_i≤k\)。

点击查看题解

构造题。

如果不存在 \(a_i+a_j=k\)，操作则无从谈起。如果存在，则一定有解，采取以下策略。

可以将 \(a_i\) 变为 \(0\)，\(a_j\) 变为 \(k\)，之后设法使得 \(a_1=0,a_n=k\)。

对于一个数列，排为有序数列最少的交换次数为 \(n-l\)，其中 \(l\) 为循环节的数量。在一个循环节内，各元素只需要在循环节内交换即可排好序。

选取一个未排好的循环节中的任意一个元素，设为 \(a_q\)。之后，只需要两步操作即可实现一次交换：

  • 令 \(i=n,j=1,x=a_q\)。此时，\(a_1=a_q,a_n=k-a_q\)。
  • 令 \(i=q,j=n,x=a_q\)。此时，\(a_q=0,a_n=k\)。之后，坐标 \(q\) 成为 \(0\) 的位置，坐标 \(n\) 为 \(k\) 的位置，继续选取循环节中的下一个元素进行第一步操作，直至坐标 \(1\) 成为 \(0\) 的位置。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define PII pair<ll,ll>
const ll N = 200000 + 50;

ll n, k, a[N], oi[N * 3], oj[N * 3], ox[N * 3], cyc[N];
PII d[N];
map<ll, ll> b;
vector<ll> loop;

bool cmp(PII x,PII y) {
    return x.first < y.first;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    ll T;
    cin >> T;
    while (T--) {
        ll fin = 1, fail = 1, m = 0;
        ll ti, tj, tx, pos0, cur, flag = 1;
        ll curl = 0, lenl = 0;
        cin >> n >> k;
        for (ll i = 1; i <= n; i++) {
            cin >> a[i];
            d[i] = (PII){a[i], i};
            cyc[i] = 0;
        }
        b.clear();
        loop.clear();
        for (ll i = 1; i <= n; i++) {
            if (a[i - 1] > a[i]) {
                fin = 0;
            }
            if (b.count(k - a[i]) >= 1) {
                fail++;
                ti = i;
                tx = a[i];
            }
            b[a[i]] = 1;
        }
        if (fin == 1) {
            cout << 0 << endl;
            continue;
        }
        if (fail == 1) {
            cout << -1 << endl;
            continue;
        }
        for (ll i = 1; i <= n; i++) {
            if (a[i] == k - tx) {
                tj = i;
                break;
            }
        }
        pos0 = ti;
        if (a[1] == 0 && a[n] == k) {
        } else if (a[1] == k && a[n] == 0) {
            ti = 1, tj = n, tx = k;
            a[ti] -= tx, a[tj] += tx;
            if (ti != tj && tx != 0) { ++m, oi[m] = ti, oj[m] = tj, ox[m] = tx; }
        } else {
            a[ti] -= tx, a[tj] += tx;
            if (ti != tj && tx != 0) { ++m, oi[m] = ti, oj[m] = tj, ox[m] = tx; } //ti 0  tj k
            pos0 = ti;
            if (a[n] != k) {
                ti = tj, tj = pos0, tx = a[n];
                a[ti] -= tx, a[tj] += tx;
                if (ti != tj && tx != 0) { ++m, oi[m] = ti, oj[m] = tj, ox[m] = tx; } //ti 0
                ti = ti, tj = n, tx = a[ti];
                a[ti] -= tx, a[tj] += tx;
                if (ti != tj && tx != 0) { ++m, oi[m] = ti, oj[m] = tj, ox[m] = tx; } //pos0 0  n k
                pos0 = ti;
            }
            if (a[ti] == 0)
                pos0 = ti;
            ti = n, tj = pos0, tx = a[1];
            a[ti] -= tx, a[tj] += tx;
            if (ti != tj && tx != 0) { ++m, oi[m] = ti, oj[m] = tj, ox[m] = tx; } //n k
            ti = 1, tj = n, tx = a[1];
            a[ti] -= tx, a[tj] += tx;
            if (ti != tj && tx != 0) { ++m, oi[m] = ti, oj[m] = tj, ox[m] = tx; } //1 0 n k
        }
        for (ll i = 1; i <= n; i++)
            d[i] = (PII){a[i], i};
        stable_sort(d + 1, d + 1 + n, cmp);
        b.clear();
        for (ll i = 2, j = 2; i <= n - 1; i++, j++) {
            if (cyc[i])
                continue;
            if (i == d[i].second)
                continue;
            cur = i;
            do {
                cyc[j] = cur;
                j = d[j].second;
            } while (cur != j);
        }
        for (ll i = 2; i <= n - 1; i++) {
            if (cyc[i] == 0)
                continue;
            b[cyc[i]] = i;
        }
        for (auto [bel,id]: b) {
            loop.push_back(bel);
        }
        lenl = loop.size();
        pos0 = cur = 1;
        while (flag) {
            if (pos0 == 1) {
                curl++;
                if (curl > lenl)
                    flag = 0;
                else
                    cur = loop[curl - 1];
            }
            ti = n, tj = pos0, tx = d[cur].first;
            a[ti] -= tx, a[tj] += tx;
            if (ti != tj && tx != 0) { ++m, oi[m] = ti, oj[m] = tj, ox[m] = tx; }
            ti = d[cur].second, tj = n, tx = d[cur].first;
            a[ti] -= tx, a[tj] += tx;
            if (ti != tj && tx != 0) { ++m, oi[m] = ti, oj[m] = tj, ox[m] = tx; }
            if (pos0 == 1) {
                d[cur].second = 1;
            }
            pos0 = cur = ti;
            b[pos0] = 1;
        }
        cout << m << endl;
        for (ll i = 1; i <= m; i++) {
            cout << oi[i] << " " << oj[i] << " " << ox[i] << endl;
        }
    }
    return 0;
}