[省选联考 2023] 填数游戏
题目描述
众所周知,Alice 和 Bob 是一对好朋友。今天,他们约好一起玩游戏。
一开始,他们各自有一张空白的纸条。接下来,他们会在纸条上依次写 \(n\) 个 \([1,m]\) 范围内的正整数。等 Alice 写完,Bob 在看到 Alice 写的纸条之后开始写他的纸条。
Alice 需要保证她写下的第 \(i\) 个数在集合 \(S_{i}\) 中,Bob 需要保证他写下的第 \(i\) 个数在集合 \(T_{i}\) 中。题目保证 \(1 \leq\left|S_{i}\right|,\left|T_{i}\right| \leq 2\) 。
Alice 喜欢相同,因此,她希望她写下的数与 Bob 写下的数对应位置相同的个数尽量多。Bob 喜欢不同,因此,他希望他写下的 \(n\) 个数 \(b_{1}, \cdots, b_{n}\) 互不相同。在此基础上,Bob 希望他写下的数与 Alice 写下的数对应位置相同的个数尽量少。
即设 Alice 写下的数为 \(a_{1}, \cdots, a_{n}\),Bob 写下的数为 \(b_{1}, \cdots, b_{n}\),记 \(X\) 为满足 \(1 \leq i \leq n, a_{i}=b_{i}\) 的下标 \(i\) 的个数,则
- Alice 希望最大化 \(X,\)
- Bob 在保证 \(b_{1}, \cdots, b_{n}\) 互不相同的前提下希望最小化 \(X\)。
你首先想知道 Bob 能否保证他写下的 \(n\) 个数互不相同。如果 Bob 能够做到,你想知道在双方均采取最优策略的前提下 \(X\) 的值会是多少。
输入格式
本题有多组测试数据。
输入的第一行包含一个正整数 \(T\),表示测试数据组数。
接下来包含 \(T\) 组数据,每组数据的格式如下:
第一行包含两个正整数 \(n,m\),表示纸条上需要写的数的个数和数的值域。
接下来 \(n\) 行,每行输入的第一个整数为 \(\left|S_{i}\right|\) 表示集合 \(S_{i}\) 的元素个数,接下来输入 \(\left|S_{i}\right|\) 个正整数描述 \(S_{i}\) 中的元素。
接下来 \(n\) 行,每行输入的第一个整数为 \(\left|T_{i}\right|\) 表示集合 \(T_{i}\) 的元素个数,接下来输入 \(\left|T_{i}\right|\) 个正整数描述 \(T_{i}\) 中的元素。
输出格式
对于每组测试数据输出一行:若 Bob 无法做到他写下的 \(n\) 个数互不相同,输出 -1
;否则输出在双方均予取最优策略的前提下 \(X\) 的值。
样例 #1
样例输入 #1
1
3 4
1 3
2 1 2
2 3 4
2 1 2
2 2 3
2 3 4
样例输出 #1
1
提示
【样例 1 解释】
在这组样例中,\(S_{1}=\{3\}, S_{2}=T_{1}=\{1,2\}, S_{3}=T_{3}=\{3,4\}, T_{2}=\{2,3\}\)。Alice 的填法有 \(4\) 种,列举如下:
第一种:\(a_{1}=3,a_{2}=1,a_{3}=3\)。
第二种:\(a_{1}=3,a_{2}=1,a_{3}=4\)。
第三种:\(a_{1}=3,a_{2}=2,a_{3}=3\)。
第四种:\(a_{1}=3,a_{2}=2,a_{3}=4\)。
由于 Bob 必须保证他所填的数互不相同,所以他有以下填法:
第一种:\(b_{1}=1,b_{2}=2,b_{3}=3\)。
第二种:\(b_{1}=2,b_{3}=3,b_{3}=4\)。
第三种:\(b_{1}=1,b_{2}=2,b_{3}=4\)。
第四种:\(b_{1}=1,b_{2}=3,b_{3}=4\)。
若 Alice 选择第一种填法,则 Bob 为最小化 \(X\),选择第二种填法,得到 \(X=0\)。
若 Alice 选择第二种填法,则 Bob 为最小化 \(X\),选择第一种填法,得到 \(X=0\)。
若 Alice 选择第三种填法,则 Bob 为最小化 \(X\),选择第一种填法,得到 \(X=0\)。
若 Alice 选择第四种填法,则 Bob 无论选择哪种填法,\(X\) 均不小于 \(1\)。
因此,Alice 为最大化 \(X\) 的值,她会选择第四种填法。
\(\sum n,\sum m\le 1.5\times 10^6,\sum n,\sum m\le 10^6\)
【提示】
本题部分测试点读入规模较大,我们建议你采取效率较高的读入方式。
二元的关系,考虑连边。
对 T 的两个数连边,然后如果存在某一个连通块,边数大于点数,那么一定无解。所以每个连通块要不是基环树,要不是树。
先看基环树。基环树的话只有两种方案,也就是环的部分有两种方向,树的部分只能全部选儿子那里。那么 Alice 怎么选才能使 Bob 选的重复更多呢?分讨一下,对于树上的点,Bob 选的方式固定,看 Alice 能不能和他选一样的就行了。对于环上的点,可以贪心一下。给他顶个顺序后,列一下数学式子就可以了。把 某个方向跑出来的链设为 \(p_1,p_2\cdots p_k\),设有 \(x\) 个 \(p_{i-1}\in S_i\),\(y\) 个 \(p_i\in S_i\),\(z\) 个 \(p_i,P_{i-1}\in S_i\)(当然,\(x\) 和 \(y\) 统计的不包括 \(z\),设 \(x<y\))。那么尽量用 \(z\) 去填 \(x\) 的空,剩下的尽量评分。也就是 \(y(x+z\le y\) 时),\(\lfloor \frac {z-x+y}2\rfloor\)( \(x+z>y\) 时)
然后看树,如果一棵树有 \(n\) 个点,那么他有 \(n\) 种填法,设第 \(i\) 种为以 \(i\) 为根,然后往儿子那里选。
考虑通过从 \(|S|\) 中取选择 Alice 选哪个,去贡献每个根的会重复的位置数量。现在转化成了这样一个问题:对于某些边,可以选择给这个边的两边子树所有点+1,求最后所有点最小值的最大值。
首先一个结论:选择方案中,所有的选择一定存在一个共同点。这是因为,如果某两个边选择的方案没有共同点,那么把他们两个方案取反一定不劣于之前的方案。
考虑枚举这个共同点,那么所有边的选择方案就固定了,暴力求答案即可。我们就有了一种 \(O(n^2)\) 的方法。
考虑换根这个共同点,然后维护最小值。换根过程中容易求出方案选择的变动,然后维护子树外的最小值,预处理出子树内的最小和次小值,如果往最小的方向走,那么子树外最小值与目前子树内次小值取min,否则直接与子树内最小值取 min就行了。
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5,INF=2e9;
int TME,n,m,a[N][2],s[N],fa[N],sz[N],bz[N],v[N],in[N],st[N],tp,q[N],c1,c2,c3,us[N],ans,hd[N],e_num,r,ret,l,mn[N],tg,p[N],T;
struct edge{
int v,nxt,w;
}e[N<<1];
int find(int x)
{
if(fa[x]==x)
return x;
return fa[x]=find(fa[x]);
}
void add_edge(int u,int v,int w)
{
e[++e_num]=(edge){v,hd[u],w};
hd[u]=e_num;
e[++e_num]=(edge){u,hd[v],w};
hd[v]=e_num;
if(find(u)^find(v))
sz[find(v)]+=sz[find(u)],bz[find(v)]+=bz[find(u)],fa[find(u)]=find(v);
bz[find(u)]++;
}
void sou(int x)
{
if(v[x])
return;
st[++tp]=x;
v[x]=1;
for(int i=hd[x];i;i=e[i].nxt)
{
in[e[i].v]++;
sou(e[i].v);
}
}
int ok(int x,int y)
{
return a[x][0]==y||s[x]==2&&a[x][1]==y;
}
void suo(int x)
{
for(int i=hd[x];i;i=e[i].nxt)
{
if(!us[e[i].w])
{
int w=e[i].w,v=e[i].v;
us[e[i].w]=1;
if(ok(w,v)&&ok(w,x))
{
c3++;
if(v==x)
++ret,--c3;
}
else if(ok(w,x))
c1++;
else if(ok(w,v))
c2++;
suo(v);
}
}
}
int solve1(int x)
{
tp=ret=c1=c2=c3=r=0,l=1;
sou(x);
for(int i=1;i<=tp;i++)
if(in[st[i]]==1)
q[++r]=st[i];
while(l<=r)
{
for(int i=hd[q[l]];i;i=e[i].nxt)
{
in[e[i].v]--;
if(!us[e[i].w])
{
us[e[i].w]=1;
if(ok(e[i].w,q[l]))
++ret;
}
if(in[e[i].v]==1)
q[++r]=e[i].v;
}
++l;
}
for(int i=1;i<=tp;i++)
if(in[st[i]]==2)
suo(st[i]),i=tp;
if(c1>c2)
swap(c1,c2) ;
if(c1+c3<c2)
return ret+c1+c3;
return c2+(c3-c2+c1)/2+ret;
}
void yu(int x,int y,int s)
{
st[++tp]=x;
p[x]=mn[x]=s;
for(int i=hd[x];i;i=e[i].nxt)
{
if(e[i].v==y)
continue;
if(ok(e[i].w,e[i].v))
yu(e[i].v,x,s-1),++tg;
else if(ok(e[i].w,x))
yu(e[i].v,x,s+1);
else
yu(e[i].v,x,s);
mn[x]=min(mn[x],mn[e[i].v]);
}
}
void dfs(int x,int y,int s,int c)
{
int mn=INF,cmn=INF;
for(int i=hd[x];i;i=e[i].nxt)
{
if(e[i].v^y)
{
if(::mn[e[i].v]<mn)
cmn=mn,mn=::mn[e[i].v];
else if(::mn[e[i].v]<cmn)
cmn=::mn[e[i].v];
}
}
mn=min(mn,p[x]+tg);
cmn=min(cmn,p[x]+tg);
ret=max(ret,min(c+::mn[x],s));
for(int i=hd[x];i;i=e[i].nxt)
{
if(e[i].v==y)
continue;
int ts,tc=c;
if(::mn[e[i].v]==mn)
ts=min(s,cmn+c);
else
ts=min(s,mn+c);
if(ok(e[i].w,e[i].v)&&ok(e[i].w,x))
--ts,++tc;
dfs(e[i].v,x,ts,tc);
}
}
int solve2(int x)
{
tg=ret=tp=0;
yu(x,0,0);
for(int i=1;i<=tp;i++)
mn[st[i]]+=tg;
dfs(x,0,INF,0);
return ret;
}
int main()
{
scanf("%d",&TME);
for(T=1;T<=TME;T++)
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
hd[i]=0,fa[i]=i,sz[i]=1,bz[i]=v[i]=in[i]=0,mn[i]=INF;
for(int i=1;i<=n;i++)
us[i]=0;
e_num=ans=0;
for(int i=1;i<=n;i++)
{
scanf("%d",s+i);
for(int j=0;j<s[i];j++)
scanf("%d",a[i]+j);
}
for(int i=1,x,y,s;i<=n;i++)
{
scanf("%d",&s);
if(s==1)
{
scanf("%d",&x);
add_edge(x,x,i);
}
else
{
scanf("%d%d",&x,&y);
add_edge(x,y,i);
}
}
int fl=0;
for(int i=1;i<=m;i++)
{
if(fa[i]^i)
continue;
if(bz[i]>sz[i])
fl=1,i=m;
else if(bz[i]==sz[i])
ans+=solve1(i);
else
ans+=solve2(i);
}
printf(fl? "-1\n":"%d\n",ans);
}
}
标签:写下,省选,个数,Alice,选择,填数,填法,Bob,联考
From: https://www.cnblogs.com/mekoszc/p/17580838.html