Wuyanru's blog
0%

[省选联考2023] 填数游戏

发表于 分类于 ，

场上 秒掉所有特殊性质，然后在不知道正解是什么的情况下去冲了正解（？

我也不知道自己冲了个啥。

最后差点暴力打挂，不过幸好拿了 分。

题意

Alice 和 Bob 在玩填数游戏，每一个人需要填 个范围在 的整数。

Alice 先填数，Alice 的第 个数 只能是集合 中的一个。

Bob 在看到 Alice 写完之后开始填数，Bob 的第 个数 只能是集合 的一个。

设 。

Alice 希望最大化 。

Bob 希望在 两两不同情况下最小化 。

若两个人都以最优操作填数，Bob 是否有合法方案，有的话，最终的 是多少。

题解

首先我们看到集合大小最多是 ，很容易能想到 2-SAT。

但是可惜，这个算法显然是错的，2-SAT 算法不能求最值（起码我没有遇到过。

但是我们会发现一个关键的地方，Bob 填的数字互相不同，这是一个比较强的限制。

这个时候其实要用到一个（可能经典的）套路。

我们把一个值看作“点”，一个位置的（Bob 的）填数方式看作一条“边”的两个端点，建一个无向图出来。

特别地，对于 的位置，我们给这一个元素建自环。

例如样例 的图就是一个 的链。

现在我们就可以发现，这个无向图被分成了若干个连通块，不同连通块之间显然没有影响。

Bob的一种方案实际上就是为每一条边定向，使得每一个点的入度不超过 。

所以我们对这些连通块进行分类讨论。

第一种情况是连通块的边数严格大于点数。

若这个连通块内有 条边，那么给边定向后，所有的点的入度之和必然为 。

但是点的数量不足 ，所以最终一定有点的度数大于 。

所以一旦出现这种情况，Bob不存在合法方案。

基环树

若一个连通块中，点数与边数相等，那么这个连通块是一棵基环树。

显然可以发现，每一个点的入度一定是 。

首先我们可以将所有边分成两类，环上的和树上的。

我们会发现，所有树上的边一定是从上往下连的（否则叶子入度为 ）。

所以 Alice 知道 Bob 这些位置填了哪些数字，可以直接贪心。

所以只剩下环上的部分。

不难发现，环上的所有边，要么一起被定向为顺时针，要么一起被定向为逆时针，Bob 只有这两种填数方式。

所以 Bob 会根据 Alice 的方案，选择两种中较小的哪个。

而 Alice 的目标是最大化 ，所以她需要使这两种方案的最小值最大。

Alice 的填数方案也可以看作是一种给边定向的方式。

所以我们枚举环上的所有边，统计出：Alice 只能选择顺时针的边，只能选择逆时针的边，和顺时针逆时针都可以定向的边。

（显然，都不能定向的边 p 用没有）

那么 Alice 的方案其实是用第三种“万能边”优先填补前两种中较少的，再进行“平均分配”。

特别要注意一种情况，就是基环树的环是一个点的自环。

在这种情况下，Bob 的方案只有一种，可能需要特判。

树

若一个连通块中，点数恰好比边数多 ，那么这个连通块是一棵树。

这就是本题中最复杂的情况。

还是一样，我们会发现最终的方案中恰好只有一个点入度为 ，其余所有点入读都是 。

那么 Bob 的方案肯定只有“连通块大小”这么多种，我们不妨称这个度数为 的点为“中心”。

再来考虑 Alice 的方案。

假设 Alice 有两条“万能边” 与 ，这两条边被定向为 与 ，并且 在 的最短路上。

简单来说，就是有如下两条的"对冲"的边：

我们会发现，若 Bob 的“中心”在 A 或 C 区域，则这两条边对答案有 的贡献，若“中心”在 B 区域，则有 的贡献。

但是如果我们将这两条边的方向都调换一下呢？

我们会发现，若 Bob 的“中心”在 A 或 C 区域，则这两条边对答案有 的贡献，若“中心”在 B 区域，却有 的贡献。

显然，第二种方案是更优的。

也就是说，对于所有 Alice 的“万能边”，一定不会出现“对冲”的情况。

也就是说，Alice 的方案也存在一个“中心”，使得所有“万能边“方向向外。

下来我们来考虑一个 的做法。

首先我们枚举 Alice 的”中心“，以它为整棵树的根，来看 Bob 的”中心“选在哪个位置。

不难发现，当 Bob 的”中心“移动 的距离时，一定恰好使一条边变向，我们可以直接统计答案。

这个做法可以直接拿到 分。

设 Alice 的中心为 ，Bob 的”中心“在 时的答案为 。

那我们可以直接维护 。

当 变化时，显然可以使用一个线段树维护 ，这样的时间复杂度是 的。

但是我们还有一种时间复杂度更小的做法。

我们使用 表示 在 子树内时，子树内的合法边数量比 时最大多多少，使用 表示次大值。

然后进行换根 dp，以 dfs 的方式枚举 的位置，并统计答案。

最后时间复杂度是 的。

代码

换根的地方细节很多。

此外，我使用了并查集，时间复杂度并不是严格线性的。

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
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
#include<cstring>
#include<cassert>
#include<cstdio>
#include<vector>
using namespace std;
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;
}
int head[1500001];
int nx[2000001];
int to[2000001];
int w[2000001];
int memu[1500001];
int memv[1500001];
int memw[1500001];
bool h[1500001];
int fad[1500001];
int fa[1500001];
int f[1500001];
int S[1500001][2];
int T[1500001][2];
int mx[1500001];
int se[1500001];
int cntm;
int n,m;
inline void clear()
{
    cntm=0;
    memset(h,0,sizeof(bool)*(m+1));
    memset(fa,0,sizeof(int)*(m+1));
    memset(head,0,sizeof(int)*(m+1));
    memset(memu,0,sizeof(int)*(m+1));
    memset(memv,0,sizeof(int)*(m+1));
    memset(memw,0,sizeof(int)*(m+1));
}
inline void ad(int u,int v,int w)
{
    cntm++;
    to[cntm]=v;
    nx[cntm]=head[u];
    ::w[cntm]=w;
    head[u]=cntm;
}
inline void add(int u,int v,int w)
{
    ad(u,v,w);
    ad(v,u,w);
}
inline int find(int num)
{
    if(f[num]==num) return num;
    return f[num]=find(f[num]);
}
void dfs1(int num)
{
    for(int i=head[num];i;i=nx[i])
    {
        int p=to[i];
        if(p==fa[num]) continue;
        fa[p]=num,fad[p]=w[i];
        dfs1(p);
    }
}
inline int check(int u,int v,int w)
{
    int ans=0;
    if(S[w][0]==u||S[w][1]==u) ans|=1;
    if(S[w][0]==v||S[w][1]==v) ans|=2;
    return ans;
}
int dfs2(int num)
{
    int ans=0;
    for(int i=head[num];i;i=nx[i])
    {
        int p=to[i];
        if(p==fa[num]||h[p]) continue;
        ans+=(check(p,num,fad[p])&1)+dfs2(p);
    }
    return ans;
}
inline int run1(int s)
{
    // printf("huan %d\n",s);
    dfs1(memu[s]);vc<int>nod,wn;int ed=-1;
    for(int i=memv[s];i;i=fa[i])
    {
        nod.push_back(i);
        wn.push_back(fad[i]);
        h[i]=1;
        ed++;
    }
    wn[ed]=memw[s];
    int num1=0,num2=0,num3=0,ans=0;
    for(int i:nod) ans+=dfs2(i);
    if(ed==0) return ans+(check(nod[0],nod[0],wn[0])&1);
    for(int i=0;i<ed;i++)
    {
        int num=check(nod[i],nod[i+1],wn[i]);
        if(num==1) num1++;
        if(num==2) num2++;
        if(num==3) num3++;
    }
    int num=check(nod[ed],nod[0],wn[ed]);
    if(num==1) num1++;
    if(num==2) num2++;
    if(num==3) num3++;
    if(num1>num2) swap(num1,num2);
    if(num3+num1<num2) return ans+num1+num3;
    return ans+num2+(num3-num2+num1)/2;
}
inline int get(int num,int p,int w)
{
    int ans=0,val=check(num,p,w);
    if(val>>1) ans++;
    if(val==1) ans--;
    return ans;
}
void dfs3(int num,int &cnt)
{
    mx[num]=se[num]=0;
    for(int i=head[num];i;i=nx[i])
    {
        int p=to[i];
        if(p==fa[num]) continue;
        fa[p]=num,fad[p]=w[i];
        dfs3(p,cnt);
        cnt+=check(p,num,fad[p])&1;
        int val=get(num,p,fad[p])+mx[p];
        if(val>mx[num]) swap(mx[num],val);
        if(val>se[num]) swap(se[num],val);
    }
}
int dfs4(int num)
{
    int ans=mx[num];
    for(int i=head[num];i;i=nx[i])
    {
        int p=to[i];
        if(p==fa[num]) continue;
        int mem1=mx[num],mem2=se[num],mem3=mx[p],mem4=se[p];

        int val=get(num,p,fad[p])+mx[p];
        if(val==mx[num]) swap(mx[num],se[num]);

        val=get(p,num,fad[p])+mx[num];
        if(val>mx[p]) swap(mx[p],val);
        if(val>se[p]) swap(se[p],val);

        ans=min(ans,dfs4(p)+(check(p,num,fad[p])&1)-(check(num,p,fad[p])&1));

        mx[num]=mem1,se[num]=mem2,mx[p]=mem3,se[p]=mem4;
    }
    return ans;
}
inline int run2(int s)
{
    int all=0;
    dfs3(s,all);
    return all-dfs4(s);
}
int main()
{
    int TT=read();
    while(TT--)
    {
        n=read(),m=read();
        for(int i=1;i<=m;i++) f[i]=i;
        for(int i=1;i<=n;i++)
        {
            int k=read();
            S[i][0]=read();
            S[i][1]=k==2?read():S[i][0];
        }
        bool flag=1;
        for(int i=1;i<=n;i++)
        {
            int k=read();
            T[i][0]=read();
            T[i][1]=k==2?read():T[i][0];

            int u=find(T[i][0]),v=find(T[i][1]);
            if(u!=v)
            {
                f[v]=u;
                if(memu[u]&&memu[v]) flag=0;
                memu[u]|=memu[v];
                memv[u]|=memv[v];
                memw[u]|=memw[v];
                add(T[i][0],T[i][1],i);
            }
            else
            {
                if(memu[u]) flag=0;
                memu[u]=T[i][0];
                memv[u]=T[i][1];
                memw[u]=i;
            }
        }
        if(!flag)
        {
            printf("-1\n");
            clear();
            continue;
        }
        int ans=0;
        for(int i=1;i<=m;i++) if(find(i)==i)
        {
            if(memu[i]) ans+=run1(i);
            else ans+=run2(i);
        }
        printf("%d\n",ans);
        clear();
    }
    return 0;
}

感谢观看！