Codeforces Round 960 (Div. 2)A-E

A题意：公平博弈。给定一个数组n个数，每个数只能用一次。给一个mxmx。每次轮到自己操作的时候就选一个数组里的数，满足a[i]>=mxa[i]>=mx,然后令mx=a[i]mx=a[i].双方轮流做直到一方无法操作，则另一方取胜。

Sol:赛时1min猜了个错解，只看最大值，只看最大值的出现次数，回来发现wa了。如果最大值出现偶数次，但次大值出现奇数次，先手也能win。递归考虑这个过程我们发现只需要统计所有数出现次数的奇偶性。只要出现一个奇数先手就能win，策略是从最大的出现奇数次开的数开始拿。

1
2
3
4
5
6
7
8
9
10
void solve(){
       cin>>n;
       map<int,int>mp;
       for(int i=1;i<=n;i++)cin>>a[i];
       for(int i=1;i<=n;i++)mp[a[i]]++;
       bool flag=0;
       for(auto [x,y]:mp)if(y%2==1)flag=1;
       if(flag)cout<<"YES"<<endl;
       else cout<<"NO"<<endl;
}

B题意：给定数组长度和两个位置x,y(y<x)x,y(y<x)，要求你构造只含-1和1的数组满足:x是最小的位置满足前缀和达到前缀和最大值，y是最大的位置满足后缀和数组达到后缀和最大值。

Sol：关键的突破点在于考虑到如果x这个位置作为最大值，起码x这个位置需要是1，反证显然。则y也同理。再考虑两边应该都是不能突破最大值的也就是需要-1，1，-1，1这样的。那么不难想到为了让x,y分别做到前缀最大和后缀最大，中间全放1即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void solve(){
	int x,y;
    cin>>n>>x>>y;
    for(int i=y;i<=x;i++)a[i]=1;
    for(int i=y-1;i>=1;i--){
    	if((y-i)%2==1)a[i]=-1;
    	else a[i]=1;
    }
   for(int i=x+1;i<=n;i++){
   	if((i-x)%2==1)a[i]=-1;
   	else a[i]=1;
   }
   for(int i=1;i<=n;i++)cout<<a[i]<<" ";
   cout<<endl;
    
}

C题意：每次对数组进行MAD操作，数组全为0终止。求每次操作后数组和的总和。MAD:新数组第i个数是上一轮数组的1-i的前缀中出现次数至少两次以上的数的最大值。

Sol:需要手动模拟几个样例，发现一轮操作后数组变成单调递增，但注意到这时候数组中只出现一次的数在下一轮会消失，而出现两次以上的数会存在较长时间。于是考虑再做一轮，我们发现当前数组中都是递增且长度大于2连续段.后面的操作会发现是右移。贡献可以O(1)O(1)计算。

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
void solve()
{
    cin >> n;
    vector<int> b(n + 1, 0);
    map<int, int> mp;
    int sum = 0;
    for (int i = 1; i <= n; i++)
        cin >> a[i], sum += a[i];
    int mx = 0;
    for (int i = 1; i <= n; i++)
    {
        mp[a[i]]++;
        if (mp[a[i]] >= 2)
        {
            mx = max(a[i], mx);
            b[i] = mx;
        }
        else
            b[i] = mx;
        sum += b[i];
    }
    //  for(int i=1;i<=n;i++)cerr<<b[i]<<" ";
    //  cerr<<endl;
    for (int i = 1; i <= n; i++)
        mp[a[i]]--;
    mx = 0;
    for (int i = 1; i <= n; i++)
    {
        mp[b[i]]++;
        if (mp[b[i]] >= 2)
        {
            mx = max(b[i], mx);
            b[i] = mx;
        }
        else
            b[i] = mx;
    }
    //  for(int i=1;i<=n;i++)cerr<<b[i]<<" ";
    // cerr<<endl;
    for (int i = 1; i <= n; i++)
        sum += b[i] * (n - i + 1);
    cout << sum << endl;
}

D题意：给出n∗nn*n方格，对于第ii行前a[i]a[i]列是黑，剩余是白色。闲杂其需要你全部染白，问最少操作次数？有两种操作：

  • 将一个 $2×2 $子网格染成白色；
  • 选择将某一行染白。

Sol:样例非常贴心给了提示，想到了状态机dp，但是没有关键贪心的dp很大概率是不对的。本题我注意到的是当一行出现至少五个黑的时候一定是操作二更优。

  • 性质：但还需要注意到的是对于当前行有四个黑格且上一行没影响的时候一定不会选择两次操作1，因为即使能直接把下一行染完也不优于直接两次操作2染色两行。影响思考的样例明明有两行4个的用的操作1，但值得注意的那个是三行互相交接的。

有了这个性质我们得出如下贪心策略：

  • 对于1-2的我们策略1，有利于下一行。

  • 对于<=4的我们看当前前后哪段被染色了，如果有一段被染，那另一段用OP1。会发现一定不会出现前后两段都被提前染色了，因为由于上面的性质这是一定不优的。

  • 对于>=5当然是选择OP2

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
void solve()
{
    cin >> n;
    int ans = 0;
    bool b1 = 0, b2 = 0;
    //b1表示前面是不是已经为当前第1，2块染过白色了
    //b2表示前面是不是已经为当前第3，4块染过白色了
    // 对于当前还剩两块的时候才用方块策略
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= n; i++)
    {
        if ((b1 == 0) && (b2 == 0))
        {
            if (a[i] == 0)
                continue;
            else if (a[i] <= 2)
            {
                ans++;
                b1 = 1;
            }
            else
                ans++;
        }
        else if (b1 == 1)
        {
            b1 = 0;
            if (a[i] <= 2)
                continue;
            if (a[i] <= 4)
            {
                b2 = 1;
                ans++;
            }
            else
                ans++;
        }
        else if (b2 == 1)
        {
            b2 = 0;
            if (a[i] == 0)
                continue;
            if (a[i] <= 4)
            {
                b1 = 1;
                ans++;
            }
            else
                ans++;
        }
    }
    cout << ans << endl;
}

E:给定一棵树，根为1.现在要求你在160次查询内获得当前老鼠的位置。每查询失败一次，老鼠会跳到它当前位置的父节点。跳到1后不再变动。

Sol：考虑对于树高根号分治，目标是把老鼠逼到一条链上，最后二分找到位置。

  • 首先处理树高<=71的，找一个叶子不停无效询问使得老鼠不停的向上跳，把老鼠逼到根节点，然后后面二分统一处理。
  • 对于深度大于71的，从根节点开始递归询问。对于一个节点的儿子，只有深度大于71才被询问，小于70的一定已经在链上了，直接跳过即可。
    询问为真或者只有一个儿子的时候就直接递归进去，为假就下一个儿子（这样就就排除了71个点），因此这样的询问最多71次。
  • 最后二分18次足够完成，注意每次查询失败的时候。左右边界都要向根偏移一个位置，防止边界问题把老鼠放走了。
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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
vector<int> e[N];
const int B = 71;
int query(int x)
{
    cout << "? " << x << endl;
    // cout.flush();
    int res;
    cin >> res;
    return res;
}
void solve()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
        e[i].clear();
    for (int i = 1; i <= n - 1; i++)
    {
        int u, v;
        cin >> u >> v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    vector<int> p(n + 1, -1), h(n + 1);
    auto dfs1 = [&](auto self, int u, int fa) -> void
    {
        for (auto v : e[u])
        {

            if (v == fa)
                continue;
            p[v] = u;
            self(self, v, u);
            h[u] = max(h[u], h[v] + 1);
        }
    };

    dfs1(dfs1, 1, 0);
    int tmp = find(h.begin() + 1, h.end(), 0) - h.begin();
    // cerr<<tmp<<endl;
    for (int i = 1; i <= B; i++)
    {
        if (query(tmp) == 1)
        {
            cout << "! " << tmp << endl;
            return;
        }
    }
    auto dfs2 = [&](auto self, int u) -> int
    {
        vector<int> a;
        for (auto v : e[u])
        {
            if (v == p[u] || h[v] < B)
                continue;
            a.push_back(v);
        }
        if (a.empty())
            return u; // 走到老鼠所在链的叶子了
        for (auto x : a)
        {
            // 下面这个判断很重要，考虑到如果是一条链每次的分叉的数量大于70，如果只有一个点显然不需要判断这是一个重要的优化
            //如果有分叉，保证下面有70个点，则最多会查询71次
            if (x == a.back() || query(x) == 1)
            {
                int res = self(self, x);
                return res;
            }
        }
        assert(false);
    };
    int ed = dfs2(dfs2, 1);
    vector<int> a;
    for (int i = ed; i != -1; i = p[i])
        a.push_back(i);
    reverse(alls(a));
    int l = 0, r = a.size() - 1;
    while (l < r)
    {
        int mid = (l + r + 1) >> 1;
        if (query(a[mid]))
            l = mid;
        else
        {
            // 查询失败，答案区间需要整体偏移1
            r = mid - 1;
            l = max(0, l - 1);
            r = max(0, r - 1);
        }
    }
    cout << "! " << a[l] << endl;
}