题目链接：https://codeforces.com/contest/2244

A - Iskander and Drawings#

算是模拟题，我们直接暴力找出最大连续的 $'\#'$ 子串再判断最长时间就可以了。我这里的实现思路是先判断有没有 $'\#'$ ，没有直接输出 $0$ 返回，有就初始化最大长度 $max\_len$ 为 $1$ ，然后遍历字符串找出最大连续的 $'\#'$ 子串长度。最后根据最大长度计算出最大时间。（奇数除 $2$ 加 $1$ 偶数除 $2$ ）

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

3
using namespace std;
4
using ll = long long;
5
using ull = unsigned long long;
6
#define endl '\n'
7
#define mod 998244353
8
typedef pair<ll, ll> pll;
9
typedef pair<int, int> pii;
10

11
void solved() {
12
    int n; cin >> n;
13
    string s; cin >> s;
14
    int max_len = 1;
15
    int len = 1; bool f = false;
16
    for(int i = 0; i < n;i++)
17
        if(s[i] == '#') f = true;
18
    if(!f) {cout << 0 << endl; return;}
19
    for(int i = 1; i < n;i++){
20
        if(s[i - 1] == '#' && s[i] == '#')
21
            len++;
22
        else len = 1;
23
        max_len = max(max_len, len);
24
    }
25
    cout << ((max_len % 2) ? max_len / 2 + 1 : max_len / 2) << endl;
26
}
27

28
int main() {
29
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
30
    int _ = 1;
31
    cin >> _;
32
    while (_--) {
33
        solved();
34
    }
35
    return 0;
36
}

B - Nikita and Books#

这题我们根据题意可以知道，对应一个数 $n$ ，使其满足严格单调递增的 $a_n$ 数组，至少需要 $1,2,3,4,5....n-1,n$ 这样的排列。也就是数组元素之和要至少大于等于 $\frac{n(n + 1)}{2}$ 。（第一个条件）我们可以发现大于等于这个值的数无论如何都能构造出一个满足条件的数组。
然后我们再注意到题目的另外一个关键条件：书本的传递是只能从左向右的。这其实说明一个情况，如果前 $k$ 项的和无法满足大于 $\frac{k(k + 1)}{2}$ ，（第二个条件）那么整个数组也就无法严格单调递增了，所以最终能满足条件的数组必须要满足这两个条件。（实际上第二个条件也就是第一条件的严苛版）
我们在实现时就在遍历时就判断当前的前缀和是否大于等于 $\frac{i(i + 1)}{2}$ 即可。（这里我在实现时还复杂了些，第一处特判 $NO$ 的部分可以删去。）

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

3
using namespace std;
4
using ll = long long;
5
using ull = unsigned long long;
6
#define endl '\n'
7
#define mod 998244353
8
typedef pair<ll, ll> pll;
9
typedef pair<int, int> pii;
10

11
int a[200010];
12

13
void solved() {
14
    int n; cin >> n;
15

16
    ll sum = 0, pre = 0;
17
    ll cmp = n * (1 + n) / 2;
18
    for(int i = 1; i <= n;i++){
19
        cin >> a[i]; sum += a[i];
20
    }
21
    if(sum < cmp){cout << "NO" << endl; return;}
22

23
    sum = 0;
24
    for(int i = 1; i <= n;i++){
25
        pre += a[i];
26
        sum += i;
27
        if(pre < sum){
28
            cout << "NO" << endl;
29
            return;
30
        }
31
    }
32
    cout << "YES" << endl;
33
}
34

35
int main() {
36
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
37
    int _ = 1;
38
    cin >> _;
39
    while (_--) {
40
        solved();
41
    }
42
    return 0;
43
}

C - Stepan and Permutation#

这题我们可以转化一下题意，实际上能交换的两个元素就是需要满足两者之间的距离为 $x$ 或者 $y$ 就可以交换了。这里我们还需要理解的就是这个条件还可以转化得更加细一些：只要满足距离 $g = gcd(x, y)$ （最大公因数）的两个元素都可以交换元素，这个是很显而易见的，因为我们完全可以通过两个或者更多次操作实现这个更短距离 $g$ 的交换。
因此，根据这个最短交换距离 $g$ ，我们可以判断一个元素最终是否能回到它作为排列的位置。也就是需要他当前的位置 $i$ 和 $p[i]$ 之差要是 $g$ 的倍数（或者就已经在原位了），那么它就是可达的，否则就不可达。所以我们就只需要判断这个条件即可，如果存在 $p[i]$ 和 $i$ 不满足这个条件就直接输出 $NO$ ，都满足就输出 $YES$ 。

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

3
using namespace std;
4
using ll = long long;
5
using ull = unsigned long long;
6
#define endl '\n'
7
#define mod 998244353
8
typedef pair<ll, ll> pll;
9
typedef pair<int, int> pii;
10

11
int p[200010];
12

13
void solved() {
14
    int n, x, y;
15
    cin >> n >> x >> y;
16
    for(int i = 1; i <= n;i++) cin >> p[i];
17

18
    int g = gcd(x, y);
19
    for (int i = 1; i <= n; i++) {
20
        if ((p[i] - i) % g != 0) {
21
            cout << "NO" << endl;
22
            return;
23
        }
24
    }
25
    cout << "YES" << endl;
26
}
27

28
int main() {
29
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
30
    int _ = 1;
31
    cin >> _;
32
    while (_--) {
33
        solved();
34
    }
35
    return 0;
36
}

D - Yaroslav and Productivity#

这题我们不妨以 $b_i$ 作为边界划分每个区间： $[1, b_1], [b_1 + 1, b_2], ... [b_{n - 1} + 1, b_n], [b_n + 1, n]$ 。那么我们就会发现，每个区间的和只有两种状态，要么是正要么是负。除了最后一个区间 $[b_n + 1, n]$ 我们无法翻转操作之外，其他区间我们都希望尽可能取到正。（因为我们需要找出一种操作所有元素之和的最大值最大）
而事实上，我们完全可以做到让所有的区间为正。我们不妨从最右边的区间 $[b_{n - 1} + 1, b_n]$ 开始，它的正反只由 $b_n$ 决定，所以我们一定可以让它取得正。我们假设翻转了前 $n$ 项的所有区间定义 $op_n = 1$ ，反则设置为 $0$ 。然后看到 $[b_{n - 2} + 1, b_{n - 1}]$ ，它的正反会受到 $b_n$ 和 $b_{n - 1}$ 的共同影响，但我们完全可以根据已经设定好的 $op_n$ 适当调整 $op_{n - 1}$ 使得这个区间也取到正：
假设 $[b_n + 1, n]$ 需要翻转才能取到正那么 $op_n = 1$ ，并且 $[b_{n - 2} + 1, b_{n - 1}]$ 不需要翻转才能取到正那么 $op_{n - 1} = 1$ ，这样才能抵消 $[b_n + 1, n]$ 的翻转。因此后面这两个区间的状态对前面区间的操作的影响其实是 $op_n \bigoplus op_{n - 1} = 0$ 也就是没翻转前面的 $n - 2$ 个区间的。所以传递给前面的状态就是 $op_{n - 1}$ 重赋值为 $0$ （未翻转前面的区间），那么 $op_{n - 2}$ 就可以再根据这个 $op_{n - 1}$ 来判断是否需要翻转。
以此类推前面的区间的 $op_i$ ，同样可以根据后面传递上来的 $op_{i + 1}$ 的状态来取 $1$ 或 $0$ ，使得最终每个区间都取到正。
所以我们最终的实现只需要将这些划分的区间的正值相加，再加上最后一段无法操作的区间 $[b_n + 1, n]$ 的原值即是最终答案了。

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

3
using namespace std;
4
using ll = long long;
5
using ull = unsigned long long;
6
#define endl '\n'
7
#define mod 998244353
8
typedef pair<ll, ll> pll;
9
typedef pair<int, int> pii;
10

11
void solved() {
12
    int n, m; cin >> n >> m;
13

14
    vector<ll> prefix(n + 1, 0);
15
    for(int i = 1; i <= n;i++){
16
        ll x; cin >> x;
17
        prefix[i] = prefix[i - 1] + x;
18
    }
19

20
    vector<int> b(m, 0);
21
    for(int i = 0; i < m;i++) cin >> b[i];
22
    sort(b.begin(), b.end());
23

24
    ll ans = 0; int last_end = 0;
25
    for(int it : b){
26
        ll sum = prefix[it] - prefix[last_end];
27
        last_end = it;
28
        ans += abs(sum);
29
    }
30
    ans += prefix[n] - prefix[last_end];
31
    cout << ans << endl;
32
}
33

34
int main() {
35
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
36
    int _ = 1;
37
    cin >> _;
38
    while (_--) {
39
        solved();
40
    }
41
    return 0;
42
}

Mkrari的个人博客

A - Iskander and Drawings#

B - Nikita and Books#

C - Stepan and Permutation#

D - Yaroslav and Productivity#