A. Submission Bait

博弈

  • 当最大数的数量是奇数时，第一个选择最大数是必胜的，因此 \(Alice\) 先手选择最大数即为必胜策略

  • 当最大数的数量是偶数时，第一个选择最大数是必败的，因此两人都要避免第一个选择最大数，这时可以考虑选择次大数，可以发现，当次大数的数量为奇数时，先手拿次大数的人会后手拿最大数，反之会先手拿最大数

从后往前递推，可以发现，当存在一个数的数量是奇数时，先手必胜，否则先手必败

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

#define x first
#define y second
#define int long long

using namespace std;

const int N = 200010;

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

signed main()
{
    cin >> T;
    while (T--)
    {
        cin >> n;
        for (int i = 0; i < n; i++) cin >> a[i];
        
        map<int, int> p;
        for (int i = 0; i < n; i++) p[a[i]]++;
        
        bool flag = false;
        for (auto it: p)
            if (it.y % 2)
                flag = true;
        
        if (flag) cout << "YES" << endl;
        else cout << "NO" << endl;
    }

    return 0;
}

B. Array Craft

构造题，需要分一下几点情况

  • \(a[x]\) 和 \(a[y]\) 都是 \(1\)，并且 \(a[x+1]\) 和 \(a[y-1]\) 都是 \(-1\)，这样可以保证 \(pre[x-1]<pre[x]<pre[x+1]\)，\(suf[y+1]<suf[y]<suf[y-1]\)
  • 当 \(x<y\) 时，\((x,y)\) 可以全部设为 \(-1\)，\([1,x-2]\) 和 \([n,y+2]\) 用 \(-1\) 和 \(1\) 轮流赋值，当 \(x-1=1\) 时，\(a[x-1]=-1\) 否则 \(a[x-1]=1\)，当 \(y+1=n\) 时，\(a[x-1]=-1\)，这样是为了保证 \(y\) 之后的后缀和没有更大的，a[y+1]同理
  • 当 \(x>y\) 时，\((y,x)\) 全部设为 \(1\)，\([1,x-2]\) 和 \([n,y+2]\) 用 \(-1\) 和 \(1\) 轮流赋值即可
  • 当 \(x=y\) 时，\(n\)只有两种情况，就是$ n=1 \(和\) n=3 \(，当\) n=1 \(时，\)a[1]$ 可以为任意值，当 \(n==3\) 时，序列为 \(-1,1,-1\)，可以发现 \(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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <bits/stdc++.h>

#define x first
#define y second
#define int long long

using namespace std;

const int N = 200010;

int T;
int n, x, y;
int a[N];

signed main()
{
    cin >> T;
    while (T--)
    {
        cin >> n >> x >> y;
        
        a[x] = a[y] = 1;
        if (x < y)
        {
            for (int i = x + 1; i < y; i++) a[i] = -1;
            for (int i = 1; i < x - 1; i++)
            {
                if (i % 2 == 0) a[i] = -1;
                else a[i] = 1;
            }
            if (x - 1 == 1) a[x - 1] = -1;
            else a[x - 1] = 1;
            for (int i = n; i >= y; i--)
            {
                if (i % 2 == n % 2) a[i] -1;
                else a[i] = 1;
            }000000000

            if (y + 1 == n) a[y + 1] = -1;
            else a[y + 1] = 1;
        }
        else if (x > y)
        {
            for (int i = y + 1; i < x; i++) a[i] = 1;
            for (int i = y - 1; i >= 0; i--)
            {
                if (i % 2 == (y - 1) % 2) a[i] = -1;
                else a[i] = 1;
            }
            for (int i = x + 1; i <= n; i++)
            {
                if (i % 2 == (x + 1) % 2) a[i] = -1;
                else a[i] = 1;
            }
        }
        else
        {
            if (n == 1) a[1] = 1;
            else a[1] = -1, a[2] = 1, a[3] = -1;
        }
        
        for (int i = 1; i <= n; i++) cout << a[i] << ' ';
        cout << endl;
    }

    return 0;
}

C. Mad MAD Sum

手玩一下可以发现，第一次操作后，\(b\) 数组变为有序数组，并且之后每进行一次操作，就会清除数量为 \(1\) 的数，以及最后一位数，可以发现，第二次操作后，除了最后一位，所有数量为 \(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
46
47
48
49
50
51
52
53
54
55
56
57
#include <bits/stdc++.h>

#define x first
#define y second
#define int long long

using namespace std;

const int N = 200010;

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

signed main()
{
    cin >> T;
    while (T--)
    {
        cin >> n;
        for (int i = 0; i < n; i++) cin >> a[i];
        
        int res = 0;
        for (int i = 0; i < n; i++) res += a[i];
        
        int cnt = 0;
        map<int, int> p;
        for (int i = 0; i < n; i++)
        {
            p[a[i]]++;
            if (p[a[i]] >= 2) cnt = max(cnt, a[i]);
            a[i] = cnt;
        }
        for (int i = 0; i < n; i++) res += a[i];
        
        cnt = 0;
        p.clear();
        for (int i = 0; i < n; i++)
        {
            p[a[i]]++;
            if (p[a[i]] >= 2) cnt = max(cnt, a[i]);
            a[i] = cnt;
        }

        int sum = 0;
        for (int i = 0; i < n; i++) sum += a[i];
        for (int i = n - 1; i >= 0; i--)
        {
            res += sum;
            sum -= a[i];	
        }
        
        cout << res << endl;
    }

    return 0;
}

D. Grid Puzzle

手玩一下可以发现

  • 当前行剩余黑色方格可以被一次操作 \(1\) 全部变为白色时，进行操作 \(1\)，并将修改传到下一行
  • 当前行剩余黑色方格不能被一次操作 \(1\) 全部变为白色时，进行操作 \(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
55
56
57
58
59
60
61
62
#include <bits/stdc++.h>

#define x first
#define y second
#define int long long

using namespace std;

const int N = 200010;

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

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

    int res = 0, st = -1;
    for (int i = 1; i <= n; i++)
    {
        if (!a[i]) st = -1;
        else if (~st && st <= a[i])
        {
            if (st == 1 || st == a[i] - 1)
            {
                if (a[i] <= 2) st = -1;
                else
                { 
                    res++;
                    if (a[i] <= 4) st = st == 1? 3 : 1;
                    else st = -1;
                }
            }
            else if (st == a[i])
            {
                if (a[i] <= 1) st = -1;
                else
                {
                    res++;
                    if (a[i] <= 3) st = 1;
                    else st = -1;
                }
            }
            else res++, st = -1;
        }
        else
        {
            res++;
            if (a[i] <= 2) st = 1;
        }
    }

    cout << res << endl;
    }

    return 0;
}