A. Dora's Set

要使三个数互质，那么一定是两个奇数\(+\)一个偶数，因此遍历\(l\)到\(r\)，每次删除相邻的奇偶奇序列即可

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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <bits/stdc++.h>

#define int long long

using namespace std;

int T;
int n, m;

signed main()
{
    cin >> T;
    while (T--)
    {
        cin >> n >> m;
        
        int res = 0;
        while (n <= m)
        {
            if (n % 2 == 0) n++;
            n += 3;
            if (n <= m + 1) res++;
        }
        
        cout << res << endl;
    }

    return 0;
}
```  

## B. Index and Maximum Value
不难发现，只有对$a$中最大值进行操作，答案才会发生变化，因此只关注最大值即可  

### code:
```cpp
#include <bits/stdc++.h>

#define int long long

using namespace std;

const int N = 100010;

int T;
int n, m;
int a[N];

signed main()
{
    cin >> T;
    while (T--)
    {
        cin >> n >> m;
        for (int i = 1; i <= n; i++) cin >> a[i];
        
        int res = 0;
        for (int i = 1; i <= n; i++) res = max(res, a[i]);
        
        while (m--)
        {
            char op;
            int l, r;
            cin >> op >> l >> r;
            if (res >= l && res <= r)
            {
                if (op == '+') res++;
                else res--;
            }
            cout << res << ' ';
        }
        cout << endl;
    }

    return 0;
}

C. Dora and C++

经过任意次操作，可以使一个数增加的最小值为\(r=gcd(a,b)\)，因此数组\(c\)在经过一定操作后可以达到的最小差值为 \(max(c[i]\%r)-min(c[i]\%r)\)

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
#include <bits/stdc++.h>

#define int unsigned long long

using namespace std;

const int N = 100010;

int T;
int n, a, b;
int c[N];

int gcd(int a, int b)
{
	return b? gcd(b, a % b) : a;
}

signed main()
{
    cin >> T;
    while (T--)
    {
        cin >> n >> a >> b;
        for (int i = 0; i < n; i++) cin >> c[i];

        int x = gcd(a, b);
        for (int i = 0; i < n; i++) c[i] %= x;

        sort(c, c + n);

        int res = 1e9, maxv = c[n - 1];
        for (int i = 0; i < n; i++)
        {
            res = min(res, maxv - c[i]);
            maxv = c[i] + x;
        }

        cout << res << endl;
    }

return 0;
}

D. Iris and Game on the Tree

手玩一下可以发现，若要使\(01\)字符串中\(01\)和\(10\)的数量不同，则只需要字符串的开头和结尾不同就行，也就是根节点和叶子节点的值不同

接下来就可以分情况讨论： 将叶子节点的值为\(0,1,?\)的个数分别记为\(c_0,c_1,c_2\)，除了叶子节点和根节点外节点值为\(?\)的个数记为\(cnt\)

  • 当根节点的值为\(1\)时，游戏过后叶子节点值为\(0\)的个数为\(c_0+(c_2+1)/2\)
  • 当根节点的值为\(0\)时，游戏过后叶子节点值为\(1\)的个数为\(c_1+(c_2+1)/2\)

当根节点的值为\(?\)时，需要考虑谁会对根节点进行操作

  • 当\(c_0=c_1\)，并且\(c_2\%2=1\)时，那么在\(c_2=1\)的时刻，轮到\(Iris\)走，此时\(c_0=c_1\)，如果\(Iris\)对最后一个叶子节点进行操作，\(Dora\)后手会对根节点操作，使得答案为\(c_0\)和\(c_1\)中较小的一个，因此\(Iris\)要避免对最后一个叶子节点操作，这时可以对\(cnt\)进行操作，\(Dora\)同理，所以两人会轮流对\(cnt\)操作，不难看出，当\(cnt\%2=0\)时，\(Dora\)最后会对根节点操作，答案为\(c_0+(c_2+1)/2\)，反之答案为\(c_0+c_2/2\)
  • 当\(c_0=c_1\)，并且\(c_2\%2=0\)时，可以发现最好的情况就是\(c_2\)平均分配给\(c_0\)和\(c_1\)，因此\(Iris\)先手对根节点操作即可，答案为\(c_0+c_2/2\)

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
53
54
#include <bits/stdc++.h>

using namespace std;

const int N = 100010;

int T;
int n;
string s;
vector<int> h[N];

int main()
{
    cin >> T;
    while (T--)
    {
        s.clear();
        
        cin >> n;
        for (int i = 0; i < n - 1; i++)
        {
            int a, b;
            cin >> a >> b;
            h[a].push_back(b), h[b].push_back(a);
        }
        cin >> s;
        s = ' ' + s;
        
        int c0 = 0, c1 = 0, c2 = 0, cnt = 0;
        for (int i = 2; i <= n; i++)
        {
            if (h[i].size() == 1)
            {
                if (s[i] == '0') c0++;
                else if (s[i] == '1') c1++;
                else c2++;
            }
            else if (s[i] == '?') cnt++;
        }
        
        if (s[1] == '0') cout << c1 + (c2 + 1) / 2 << endl;
        else if (s[1] == '1') cout << c0 + (c2 + 1) / 2 << endl;
        else if (c0 == c1)
        {
            if (cnt % 2) cout << c0 + (c2 + 1) / 2 << endl;
            else cout << c0 + c2 / 2 << endl;
        }
        else cout << max(c0, c1) + c2 / 2 << endl;
        
        for (int i = 1; i <= n; i++) h[i].clear();
    }

    return 0;
}