7
20
2016
0

2016多校联合训练

因为最近各种事情加比赛加神志不清…… 专题训练被弃坑了……

现在多校开始了……搞篇文章记录一下做的多校里的神题吧……(别人看来都是水题)

 

第一场(7.19):


A:给定一个图,求最小生成树和最小生成树上任意两点距离的最小期望。

题目中有说边权各不同,所以MST是唯一的。于是期望也是唯一的。只需先求出最小生成树,再求期望即可。期望的话只需计算总和/边数(n*(n-1)/2)可以考虑每一条边对总和的贡献是这条边两侧的点的数量的乘积*边权。因为两边点的数量加起来一定是n,那么我们只需求小的那边,另一侧是n-小的那边的点数。而小的那边的点的数量一定是某个子树的点之和。那我们只需随意选一个点进行dfs,递归计算每一个子树的点个数即可。注意最后除以的时候要/N/(N-1),因为N是10e5,乘了再除会爆LL。递归部分代码如下:

void dfs(int x,int pre)
{
	rest[x]=1;
	for(int i=head[x];i;i=e[i].next)
	{
		int to=e[i].to;
		if(to!=pre)
		{
			dfs(to,x);
			rest[x]+=rest[to];
		}
	}
}

B:一个n*20的棋盘上有一些棋子,两个人玩游戏,每个人可以把任意一个棋子右移(如果下一个格子是空格),如果说一个棋子前面也是一个或多个棋子,则跳过这些棋子到下一个空格,如果棋子到最右边则不能操作该棋子。两个人轮流操作,如果轮到某个人时他不能操作,则他输掉比赛。

经典的博弈论 SG函数的题目。和取石子差不多的类型。这里n行互相独立互不影响,只需要算出每一行的SG函数值xor起来就好了。那么每一行的话,因为只有20列,状态数一共是(1<<20)个。那么我们只需要从终态往前暴力计算每个状态的SG值即可。而具体的计算方法是这样。。我对于一个状态i,依次考察它的从右往左数的第j位,如果该位是0则last=j(当前最左边的空格),如果该位是1,则将该位变为0,并将last变为1。(相当于将当前的棋子右移或者跳过若干个棋子到达了最近的空格)因为这个状态是当前状态的后继状态,由SG(x)=mex{S} (s为x的所有后继状态) 我们可以依次计算出所有状态的SG值。 计算SG值部分的代码:

for(int i=1;i<(1<<20);i++)
	{
		int last=-1;
		memset(h,0,sizeof(h));
		for(int j=0;j<20;j++)
		{
			if(!((i>>j)&1)) last=j;
			else if(((i>>j)&1)&&(last!=-1)) 
			h[sg[i^(1<<last)^(1<<j)]]=1;
		}
		int j=0;
		while(h[j]) j++;
		sg[i]=j;
	} 

 

第三场 7.26 :

1、最多开方5次,大于13位的肯定不行,然后暴力判断即可。

2、算单点贡献。

3、博弈 终态推每一个点的状态,预处理出来。(画图画出来)

 

10、神一般的物理题,不会。公式:a*v1/(v1^2-v2^2) a==0时是0,else  v1<=v2是Inciqity。

11.由抽屉原理,暴力判断,距离数不会超过2*10^5

 

Category: 未分类 | Tags: | Read Count: 804

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com