Codeforces Round 969 (Div. 2)

A

奇数偶数奇数时是最好的。

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
#include <bits/stdc++.h>
using namespace std;
#define int long long
using ll = long long;
vector<int> prefix_function(const string &s)
{
    int n = s.size();
    vector<int> pi(n);
    for (int i = 1, j; i < n; i++)
    {
        j = pi[i - 1];
        while (j > 0 and s[i] != s[j])
            j = pi[j - 1];
        if (s[i] == s[j])
            j++;
        pi[i] = j;
    }
    return pi;
}

void Totoro()
{
    int l, r;
    cin >> l >> r;
    if(l&1)
    {
        l--;
    }
    cout << (r - l + 1) / 4 << '\n';
}
signed main()
{
    int t = 1;
    cin >> t;
    while (t--)
    {
        Totoro();
    }
}

B

这个变化只和最大值有关。

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
#include <bits/stdc++.h>
using namespace std;
#define int long long
using ll = long long;
vector<int> prefix_function(const string &s)
{
    int n = s.size();
    vector<int> pi(n);
    for (int i = 1, j; i < n; i++)
    {
        j = pi[i - 1];
        while (j > 0 and s[i] != s[j])
            j = pi[j - 1];
        if (s[i] == s[j])
            j++;
        pi[i] = j;
    }
    return pi;
}

void Totoro()
{
    ll n, ma = 0, m;
    cin >> n >> m;
    for (int i = 1, x; i <= n; i++)
    {
        cin >> x;
        ma = max(ma, x);
    }
    for (int i = 1; i <= m; i++)
    {
        char op;
        ll l, r;
        cin >> op >> l >> r;
        if (ma >= l && ma <= r)
        {
            if (op == '+')
                ma++;
            else
                ma--;
        }
        cout << ma << ' ';
    }
    cout << '\n';
}
signed main()
{
    int t = 1;
    cin >> t;
    while (t--)
    {
        Totoro();
    }
}

C

结论：对于一个数字任意的加上a,减去a,加上b,减去b任意次就等于我们可以得到kgcd(a,b)。

因此只需要化简数组都取余gcd(a,b)最后贪心去算即可。

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
#include <bits/stdc++.h>
using namespace std;
#define int long long
using ll = long long;
const int N = 1e6 + 100;
ll A[N];

void Totoro()
{
    ll n, a, b;
    cin >> n >> a >> b;
    ll cc = __gcd(a, b);
    for (int i = 1; i <= n; i++)
    {
        cin >> A[i];
        A[i] %= cc;
    }
    sort(A + 1, A + 1 + n);
    n = unique(A + 1, A + 1 + n) - A - 1;
    ll ans = A[n] - A[1];
    for (int i = 2; i <= n; i++)
    {
        ans = min(A[i - 1] + cc - A[i], ans);
    }
    cout << ans << '\n';
}
signed main()
{
    int t = 1;
    cin >> t;
    while (t--)
    {
        Totoro();
    }
}