首页 > 其他分享 >[省选联考2023] 填数游戏

[省选联考2023] 填数游戏

时间:2023-07-25 19:55:32浏览次数:43  
标签:写下 省选 个数 Alice 选择 填数 填法 Bob 联考

[省选联考 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

相关文章

  • P3750 [六省联考 2017] 分手是祝愿
    本篇为该题解的补充与说明处理出来一共有个多少的要摁的开关(最优的方法是摁多少次)我们可以先从\(k\)入手,从后往前扫,只要遇到\(1\)的位置就操作,并更新编号为\(i\)的约数的点一个点不会被操作\(2\)次以上,因为\(2\)次操作相当于没操作操作\(i\)不会影响到比ii......
  • P3750 [六省联考 2017] 分手是祝愿 做题记录
    P3750[六省联考2017]分手是祝愿做题记录题目传送门题目描述ZeitundRaumtrennendichundmich.时空将你我分开。B君在玩一个游戏,这个游戏由\(n\)个灯和\(n\)个开关组成,给定这\(n\)个灯的初始状态,下标为从\(1\)到\(n\)的正整数。每个灯有两个状态亮和灭,......
  • 省选计划(第一周)
    知识回顾:巩固:生成树,DP,分层图,简单数论,线段树。深入研究:网络流。简单了解/没学明白:FFT。练题:P6144[USACO20FEB]HelpYourselfP定义\(f_r\)为以\(r\)结尾的线段集合的总贡献。对于一个线段\([l,r]\)可以考虑分成\([1,l)\),\([l,r]\)和\([r+1,n]\)三种情......
  • 省选计划(第三周)
    知识回顾:巩固:概率DP,错排,组合数深入研究:组合数,后缀数组,tarjan,2-SAT简单了解/没学明白:练题:[ABC280F]PayorReceive概率DP。定义\(f_i\)为把怪物打成i滴血的期望攻击次数。令\(p=\frac{p}{100}\)。则\(f_i=f_{i+2}\cdotp+f_{i+1}\cdot(1-p)+1\)。最终......
  • 省选计划(第二周)
    知识回顾:巩固:二分,倍增,优化DP,莫队,分数规划,网络流,二分图,贪心,set/map,KMP深入研究:分治(线段树分治),后缀数组,费用流简单了解/没学明白:线性基,边分治,数位DP,博弈论练题:[SCOI2015]国旗计划直接模拟复杂度\(O(n^2)\),显然会超时,于是考虑倍增。定义\(st_{i,j}\)表示从i这条......
  • 省选计划(第五周)
    知识回顾巩固:线段树,贪心深入研究:数论,容斥,除法分块,根号分治简单了解:lucas,prufer序列,莫比乌斯反演练题P2606[ZJOI2010]排列计数可以发现这符合小根堆的性质,把它建出来。定义\(f_u\)为以u为根的子树的方案数,转移方程为:\[f_u=\dbinom{siz_u-1}{siz_{2\cdotu}}\c......
  • 省选计划(第四周)
    第四周知识回顾巩固:2-SAT深入研究:概率与期望简单了解/没学明白:练题P3825[NOI2017]游戏很麻烦的2-SAT。如果没有x,就是个传统的问题。然后我们发现d的取值很小,考虑对于每个x枚举其类型为a还是c。为什么不枚举b呢?因为a、c已经包含b了。连边的时......
  • 省选计划 (第七周)
    练了好久CF&AT的题,现在要回归省选计划了!知识回顾巩固:二维树状数组深入了解:可持久化数据结构简单了解/没学明白:练题P3567[POI2014]KUR-Couriers主席树模板题。如果左子树的个数大于右子树的个数,则递归左子树,否则右子树。最后到达单点的时候就判断一下个数是否......
  • 省选计划(第六周)
    知识回顾巩固:Lucas,网络流,二分图深入研究:背包DP,树形DP,区间DP,状压DP。简单了解/没学明白:博弈论,插头DP练题Workingroutine读完题后以为矩阵可以相邻,费了一个小时去写...(可恶直接暴力交换复杂度是\(O(nmq)\),无法接受,考虑链表。对于每个点i,定义\(right_i\)为i的......
  • 洛谷 P6620 [省选联考 2020 A 卷] 组合数问题
    洛谷传送门记一下是怎么推的。\[\sum\limits_{k=0}^nf(k)\timesx^k\times\binom{n}{k}\]\[=\sum\limits_{p=0}^m\sum\limits_{k=0}^na_pk^p\timesx^k\times\binom{n}{k}\]\[=\sum\limits_{p=0}^m\sum\limits_{k=0}^nx^k\times\binom......