因为最近各种事情加比赛加神志不清…… 专题训练被弃坑了……
现在多校开始了……搞篇文章记录一下做的多校里的神题吧……(别人看来都是水题)
第一场(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