Wuyanru's blog
0%

[CF1943E2] MEX Game 2

发表于 分类于 ，

炒鸡神仙的博弈题。

场上想到了 E1 正解，同时挂 5 个地方同时过了样例，悲。

题目链接。

题意

现在有两个数组 ，初始时 是空的， 中所有数字的值域为 ，且 中恰有 个数字 。

Alice 和 Bob 两个人现在做游戏，两人轮流操作，Alice 先手。

当 Alice 操作时，她会从 中拿出一个元素，将其加入数组 ，并从 中删掉。

当 Bob 操作时，他会直接从 中拿走 个元素，并直接删掉。

最终 Alice 的得分是 中所有元素的 ，Alice 想要让得分最大，Bob 想要让得分最小。

假设两人都绝对聪明，求 Alice 最后的分数。

。

。

题解

首先考虑 E1 怎么做。

这种题一般来说都需要先确定两个人的策略，所以我们先考虑两个人的策略分别是什么。

经过思考可以发现，直接确定两人的策略应该是行不通的，不妨先二分一个答案 ，考虑如何判断，最终的答案与 的大小关系（即判断是 还是 ）。

如果有 ，那么 Alice 一定将 中的所有数字都至少取走了一个。

考虑寻找此时 Alice 与 Bob 的最优策略。

显然，此时 Alice 与 Bob 都只会操作 内的元素，因为操作 的元素不会改变答案。

其次，这个时候 内所有元素的大小关系也不重要了，因为 Alice 想要成功，总要把所有元素都拿一遍。

所以我们可以假设 ，不成立的时候排个序就好了。

考虑 Alice 的第一次操作，可以发现 Alice 一定去会拿 。

证明如下，如果 Alice 拿了 ，那么剩余未拿的数字个数是 。

如果 Alice 去拿了另一种数字 ，那么剩余的数字个数是 。

可以发现，只有 和 这两个数字的差别。

显然，当只有其中一个位置不同时，一定是这个位置越大对 Alice 越有利。

所以 Alice 在一开始一定会拿次数最小的数字 。

不难发现，这个结论对之后 Alice 所有的操作都成立，Alice 每一次一定是拿当前没有拿过的数字中，出现次数最小的一个，证明与上面一样。

下面考虑 Bob 的操作。

容易发现，Bob 的操作还是不好确定，那我们不妨在枚举一个数字 ，表示 Bob 赶在 Alice 拿走之前，最小的删空的数字。

那么我们想要判断是否有 ，就只需要判断，对于每一个 ，Bob 是否都不能达成目标就可以了。

现在考虑如何对一组 进行求解。

首先，对于 的数字 ，我们也不需要去管它了，因为 Alice 和 Bob 的操作一定不会涉及它们。

此时再考虑 Bob 的操作是怎么样的。

因为 Bob 需要恰好拿空数字 ，所以 Bob 一上来一定是猛消数字 。

那是不是只要把数字 消完就结束了呢？

显然不是，因为如果消到某个时刻，有 ，这就不满足我们之前 不降的假设了，此时 Alice 会先拿 再拿 。

考虑将 Bob 的操作看为每次拿走 个元素，一共操作 次。

那么这个时候，Bob 每一次操作就可以看为拿走当前最大的数字，然后将所有 排序。

这就满足了我们 不降的假设。

宏观来看，Bob 就是每一次将若干个极大值一起消到（几乎）同一个位置。

考虑时间复杂度，枚举 需要一个 ，而 check 一个 需要模拟 轮，每次是 的。

总时间复杂度为 ，可以通过 E1。

考虑对其进行优化。

对于一组 ，我们进行 check 的复杂度是 的模拟，这显然有优化空间。

对于第 个回合，Alice 一定拿走了第 个数字，而 Bob 对一段后缀 进行操作。

考虑最小的，使得 （即 Bob 的操作范围是剩余所有数字）的时刻 。

找到时刻 是简单的，可以直接二分判一判，这一步复杂度是 。

而对于后面的部分，不难发现，所有的数字极差不会超过 （因为 Bob 此时的操作范围是整段区间）。

那么这一部分能不能快速处理呢？

可以！考虑使用 表示剩余 种数字，每种数字个数的极差不超过 ，最多剩多少个数字的时候，Bob 可以拿完。

对于边界情况有 ，因为如果剩余 个数字的话 Alice 一步就那完了。

对于 的情况，一定是 Alice 先拿走最小的数字，然后 Bob 对整段区间进行操作。

也容易得到递推式 。

这样，我们就可以在 的时间完成对一组 的判断。

总时间复杂度降为 。

但是复杂度还能降！

对于每一组 ，我们都要重新寻找 ，这真是太不牛了！

容易发现，若 增加，那么 一定会随之增加，我们直接双指针维护。

这样总时间复杂度就降为了 。

瓶颈在于初始的排序与后面的二分。

代码

这里的双指针实现与上面的不同。

当时脑抽了，采用了一种很笨的写法来保证时间复杂度，但是其实直接用上面的 来算就完全可以了，复杂度也是正确的。

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
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3fll
#define debug(x) cerr<<#x<<"="<<x<<endl
using namespace std;
using ll=long long;
using ld=long double;
using pli=pair<ll,int>;
using pi=pair<int,int>;
template<typename A>
using vc=vector<A>;
inline int read()
{
    int s=0,w=1;char ch;
    while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return s*w;
}
ll sum[200005];
ll dp[200005];
int id[200005];
int b[200005];
int a[200005];
int n,k;
inline bool get(int lim)
{
    int c=0;
    for(int i=0;i<=n;i++) if(id[i]<=lim)
    {
        b[++c]=a[id[i]];
        sum[c]=sum[c-1]+b[c];
    }

    if(!b[1]) return false;
    int l=1,r=2;
    for(int i=2;i<=c;i++)
    {
        while(true)
        {
            ll need=sum[i]-sum[r]-(ll)(i-r)*b[r];
            if(need>(ll)l*k)
            {
                l++;
                if(l==r) r++;
            }
            else if(r==l+1) break;
            else r++;
        }
        ll rest=sum[i]-sum[l]-(ll)l*k;
        if(rest<=dp[i-l]) return false;
    }
    return true;
}
inline void solve()
{
    n=read(),k=read();dp[1]=0;
    for(int i=0;i<=n;i++) a[i]=read(),id[i]=i;
    sort(id,id+n+1,[](int x,int y){ return a[x]<a[y];});
    for(int i=2;i<=n+1;i++)
    {
        ll now=dp[i-1]+k;
        dp[i]=now+now/(i-1);
    }
    int ans=-1;
    for(int i=1<<17;i;i>>=1) if(ans+i<=n&&get(ans+i)) ans+=i;
    printf("%d\n",ans+1);
}
int main()
{
    int T=read();
    while(T--) solve();
    return 0;
}

感谢观看！