Codeforces Round 909 (Div. 3)

A

思路

因双方的行动可以相互抵消，故当 \(n\) 不为 \(3\) 的倍数时，先手必胜

Code

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 all(v) v.begin(), v.end()
#define INF 0x3f3f3f3f
#define endl '\n'
const int mod = 998244353;
const int N = 1e5 + 10;
const int M = 1e5 + 10;

void solve()
{
    int n;
    cin >> n;
    cout << (n % 3 ? "First" : "Second") << endl;
}

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

    int t;
    cin >> t;
    while (t--)
        solve();

    return 0;
}

B

思路

枚举所有的 \(k\) ，计算此时的最大差值，记录出现的最大值。 \(O(n \log n)\)

Code

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(v) v.begin(), v.end()
#define INF 0x3f3f3f3f
#define endl '\n'
const int mod = 998244353;
const int N = 1e5 + 10;
const int M = 1e5 + 10;

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

    vector<int> v(n + 10);
    for (int i = 1; i <= n; i++)
        cin >> v[i];

    vector<ll> sum(n + 10);
    for (int i = 1; i <= n; i++)
        sum[i] = sum[i - 1] + v[i];

    ll ans = 0;
    for (int i = 1; i < n; i++)
    {
        if (n % i == 0)
        {
            vector<ll> a;
            for (int j = i; j <= n; j += i)
                a.push_back(sum[j] - sum[j - i]);
            ans = max(ans, *max_element(all(a)) - *min_element(all(a)));
        }
    }
    cout << ans << endl;
}

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

    int t;
    cin >> t;
    while (t--)
        solve();

    return 0;
}

C

思路

将数组分为若干个区间，每个区间边界为相邻的奇偶性相同的两个数之间，维护每个区间的最小前缀，可以通过舍弃最小前缀保证当前值是最大值。\(O(n)\)

Code

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
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#include <map>
using namespace std;
typedef long long ll;
#define all(v) v.begin(), v.end()
#define INF 0x3f3f3f3f
#define endl '\n'
const int mod = 998244353;
const int N = 1e5 + 10;
const int M = 1e5 + 10;

void solve()
{
    int n;
    cin >> n;
    vector<int> v(n);
    for (int i = 0; i < n; i++)
        cin >> v[i];

    int ans = v[0], sum = v[0], pre = min(0, v[0]);
    for (int i = 1; i < n; i++)
    {
        if ((v[i] + v[i - 1]) % 2 == 0)
        {
            pre = 0;
            sum = 0;
        }
        sum += v[i];
        ans = max(ans, sum - pre);
        pre = min(pre, sum);
    }
    cout << ans << endl;
}

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

    int t;
    cin >> t;
    while (t--)
        solve();

    return 0;
}

D

思路

通过对式子的改写，可知满足条件的可能情况为 \(b_i = b_j\) 或 \(b_i = 1, b_j = 2\) 或 \(b_i = 2, b_j = 1\) 。

Code

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(v) v.begin(), v.end()
#define INF 0x3f3f3f3f
#define endl '\n'
const int mod = 998244353;
const int N = 1e5 + 10;
const int M = 1e5 + 10;

void solve()
{
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++)
        cin >> a[i];

    ll ans = 0;
    map<int, int> mp;
    for (int i = 0; i < n; i++)
    {
        ans += mp[a[i]];
        if (a[i] == 1)
            ans += mp[2];
        if (a[i] == 2)
            ans += mp[1];
        mp[a[i]]++;
    }

    cout << ans << endl;
}

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

    int t;
    cin >> t;
    while (t--)
        solve();

    return 0;
}

E

思路

对于这个序列，我们无法对整个序列的最小值以后的数进行操作，若最小值以后的数不满足不递减的顺序，则这次排序是不可能的，反之则输出最小值之前的元素数量。

Code

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(v) v.begin(), v.end()
#define INF 0x3f3f3f3f
#define endl '\n'
const int mod = 998244353;
const int N = 1e5 + 10;
const int M = 1e5 + 10;

void solve()
{
    int n;
    cin >> n;
    vector<int> v(n);
    for (int i = 0; i < n; i++)
        cin >> v[i];

    int pos = min_element(all(v)) - v.begin();

    for (int i = pos; i < n - 1; i++)
    {
        if (v[i] > v[i + 1])
        {
            cout << -1 << endl;
            return;
        }
    }

    cout << pos << endl;
}

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

    int t;
    cin >> t;
    while (t--)
        solve();

    return 0;
}

F

思路

初始化树为一条链，此时两个叶结点之间的距离为 \(n-1\) ，每次移动 \(n\) 结点，使其与链上编号为 \(d_i\) 的结点相连，此时 \(n\) 结点与 \(1\) 结点之间的距离为 \(d_i\) 。

Code

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(v) v.begin(), v.end()
#define INF 0x3f3f3f3f
#define endl '\n'
const int mod = 998244353;
const int N = 1e5 + 10;
const int M = 1e5 + 10;

void solve()
{
    int n, q;
    cin >> n >> q;
    vector<int> d(q);
    for (int i = 0; i < q; i++)
        cin >> d[i];

    for (int i = 1; i < n; ++i)
        cout << i << " " << i + 1 << endl;

    int now = n - 1;
    for (int dis : d)
    {
        if (dis != now)
        {
            cout << n << " " << now << " " << dis << endl;
            now = dis;
        }
        else
            cout << "-1 -1 -1" << endl;
    }
}

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

    int t;
    cin >> t;
    while (t--)
        solve();

    return 0;
}
ACM > 题解 > Codeforces
#算法 #Codeforces
Codeforces Round 909 (Div. 3)
http://xiaowhang.github.io/archives/2728152226/
作者
Xiaowhang
发布于
2023年11月18日
许可协议