首页 > 其他分享 >GYM103102/SEERC2020 J One Piece

GYM103102/SEERC2020 J One Piece

时间:2023-11-08 20:11:06浏览次数:40  
标签:GYM103102 int 距离 SEERC2020 宝藏 Piece 中点 operatorname dis

GYM103102/SEERC2020 J One Piece

这题讲杂题的时候人没讲清楚,下来问做出来的大佬也没说清楚,网上翻半天题解一两句没了,心态炸了都。

题意略过,各位自己去看一遍原题目。

提前约定一些符号:\(\operatorname{dis}(a,b)\) 表示点 \(a,b\) 之间的距离。

首先我们设题目中给出的点 \(i\) 的最远距离为 \(a_i\)。

注意到只有一个宝藏的时候一定存在一个 \(a_i=0\),特判很好做,下面我们将这种情况剔除。

假设我们已经知道了宝藏点的情况,我们可以得到什么结论?

\(a_i\) 中最小值一定是这些宝藏中 最远的两个作为端点得到的链的中点(当然可能中点是在边上,这时两边的点同时取到最小值)。

为什么?其实还是比较显然,画一张图就基本看懂了:

Pic1

红点有宝藏,黑点没有,中间那个实心红点就是中点,自己手模一下也就大概懂了。

严谨证明大概可以这么写:

假设存在一个 \(u\) 不为中点取到最小值,我们设距离它最远的这个宝藏点为 \(v\)。

此时一定存在另一个宝藏点 \(t\) 满足 \(u\) 到 \(t\) 的距离小于到 \(v\) 的距离,由于 \(u\) 不为中点,可知距离差至少为 \(2\),那就可以通过移动 \(u\) 使得 \(a_u\) 变小,因此 \(u\) 一定为中点。

这个时候我们就可以把这个中点拉出来单独看,设其为 \(p\)。

此时我们很容易知道与 \(p\) 的距离大于 \(a_p\) 的点的概率全为 \(0\),与 \(p\) 的距离小于 \(a_p\) 的点不受任何影响,自然全是 \(\frac{1}{2}\)。

哎,稍等,为什么不会有某些点限制住距离小于 \(a_p\) 的点概率为 \(0\),就像是下图这样呢?

Pic2

实际上注意看,这种情况很显然不成立。

为什么?可以尝试一下标上所有点,会发现此时中点根本就不是上面那个点(按照前面图一的标法很容易看出来)。

严谨证明:

首先易得若存在一个点 \(x\) 使得 \(a_x\lt\operatorname{dis}(x,p)+a_p\),则点 \(x\) 会出现上图的情况(为什么我就不写了)。

然后我们从图一里面就能看出来,\(\forall y,a_y=\operatorname{dis}(y,p)+a_p\),这是因为距离点 \(y\) 最远的宝藏想要到一定要经过 \(p\),也就是一定在 \(p\) 的另一端,也就得到 \(\operatorname{dis}(y,p)+a_p\)。

为什么一定在 \(p\) 的另一端?这就很显然了,因为在这一端内得到的最远的宝藏一定可以映射到 \(p\) 的另一端一个和 \(p\) 等距离的宝藏,绕过 \(p\) 到那个宝藏一定是更远的。

得到这个结论,显然 \(a_x\lt\operatorname{dis}(x,p)+a_p\) 不成立。

现在我们回到正轨,预防你忘了,我再写一遍我们刚得到的结论:

与 \(p\) 的距离大于 \(a_p\) 的点的概率全为 \(0\)。与 \(p\) 的距离小于 \(a_p\) 的点不受任何影响,概率都是 \(\frac{1}{2}\)。

这之后我们需要特别关注 \(\operatorname{dis}(z,p)=a_p\) 的这些点 \(z\),它们比较特殊。

下面我们认为 \(z\) 是一类点的统称,这类点满足 \(\operatorname{dis}(z,p)=a_p\)。

注意到要保证 \(p\) 是中点这个条件成立,\(p\) 的各个子树中至少要有两个里面存在 \(z\)。

既然可能存在不合法的情况,直接就可以说其概率一定大于 \(\frac{1}{2}\),因为在所有的 \(z\) 都没被选的时候一定不合法,这个情况不存在,也就直接让所有 \(z\) 被选的概率大于 \(\frac{1}{2}\) 了。

那么这些 \(z\) 各自之间的概率如何比较?注意到每个情况出现的概率都是相等的,可以通过方案数来比较概率。

下面我们认为 \(p\) 为根,下述“子树”指 \(p\) 的儿子节点为根的子树。

假设对于某个点 \(z\),它被选择了,那么它这个子树里面选/不选都无所谓了,剩下在外面的点一定需要选至少一个,也就得到不合法方案数和所属子树大小有关,子树越大,不合法方案数越多。

给一张图就好理解了:

Pic3

尝试计算实心红点的不合法方案数量,然后改变实心红点再算一下就明白了。

所以最后统计一下就做完了,给一份没有注释也毫无参考价值的代码吧:

#include<bits/stdc++.h>
using namespace std;
const int N=250010;
struct edge
{
	int v,nex;
}e[N*2];
int fir[N],ent;
inline void add(int u,int v)
{
	e[++ent]={v,fir[u]};
	fir[u]=ent;
	return;
}
int a[N],dep[N],siz[N];
struct Temp
{
	int u,c;
	bool operator < (const Temp &oth){if(siz[c]==siz[oth.c])return u<oth.u;return siz[c]<siz[oth.c];}
};
vector<Temp>point;
void DFS(int u,int f,int c)
{
	if(dep[u]==a[c])
	{
		siz[c]++;
		point.push_back({u,c});
		dep[u]=-1;
		return;
	}
	for(int i=fir[u];i;i=e[i].nex)
	{
		int v=e[i].v;
		if(v==f)continue;
		dep[v]=dep[u]+1;
		DFS(v,u,c);
	}
	return;
}
int main()
{
	int n;
	scanf("%d",&n);
	for(int i=1;i<n;i++)
	{
		int a,b;
		scanf("%d%d",&a,&b);
		add(a,b),add(b,a);
	}
	int mn=N;
	for(int i=1;i<=n;i++)scanf("%d",a+i),mn=min(mn,a[i]);
	if(mn==0)
	{
		for(int i=1;i<=n;i++)if(a[i]==0)printf("%d ",i);
		for(int i=1;i<=n;i++)if(a[i])printf("%d ",i);
		return 0;
	}
	int u=0,v=0;
	for(int i=1;i<=n;i++)
	{
		for(int j=fir[i];j;j=e[j].nex)if(a[i]==mn&&a[e[j].v]==mn){u=i,v=e[j].v;break;}
		if(u&&v)break;
	}
	if(u&&v)
	{
		dep[u]=dep[v]=1;
		DFS(u,v,u),DFS(v,u,v);
	}
	else 
	{
		for(int i=1;i<=n;i++)if(a[i]==mn)u=i;
		dep[u]=1;
		for(int i=fir[u];i;i=e[i].nex)dep[e[i].v]=2,DFS(e[i].v,u,e[i].v);
	}
	sort(point.begin(),point.end());
	for(auto it:point)printf("%d ",it.u);
	for(int i=1;i<=n;i++)if(dep[i]>0)printf("%d ",i);
	for(int i=1;i<=n;i++)if(dep[i]==0)printf("%d ",i);
	return 0;
}

标签:GYM103102,int,距离,SEERC2020,宝藏,Piece,中点,operatorname,dis
From: https://www.cnblogs.com/XiaoShanYunPan/p/17815265.html

相关文章

  • 量化交易之One Piece篇 - spdlog - 示例demo
    #include<memory>#include<onepiece/datacore/DataCore.h>#include<spdlog/spdlog.h>#include<spdlog/sinks/basic_file_sink.h>#include<memory>usingnamespacestd;intmain(intargc,constchar*argv[]){//testsp......
  • A piece of cake
    1.Apieceofcake(易事情)2.Breakaleg(祝好运)3.Don'tcountyourchickensbeforetheyhatch(不要过早乐观)4.Don'tputallyoureggsinonebasket(不要孤注一掷)5.Everycloudhasasilverlining(黑暗中总有一线希望)6.Facethemusic(勇敢面对现实)7.Fitasafiddle(身体非......
  • A piece of code for loading and caching Skeleton Animation in IO task [Cocos2dx.
    /****************************************************************************Copyright(c)2017-2018XiamenYajiSoftwareCo.,Ltd.http://www.cocos2d-x.orgPermissionisherebygranted,freeofcharge,toanypersonobtainingacopyofthissoft......
  • numpy(二)piecewise
    1、关于值域和定义域的坑【坑了我一下午,怎么都不对,直到和朋友探讨,才一点点排除问题,真挺坑的。实际上还是自己对于函数的值域定义域的注意不够。】(1)定义域是int时,值域是int,输出中带的小数会被舍弃(不是四舍五入、而是直接抹掉)错误使用:#注意!piecewise的输出(值域)类型按照定......
  • A piece of cake
    1.Apieceofcake(易事情)2.Breakaleg(祝好运)3.Don'tcountyourchickensbeforetheyhatch(不要过早乐观)4.Don'tputallyoureggsinonebasket(不要孤注一掷)5.Everycloudhasasilverlining(黑暗中总有一线希望)6.Facethemusic(勇敢面对现实)7.Fitasafiddle(身体非......
  • CF36D New Game with a Chess Piece 题解
    前言:都大半年没在洛谷上提交过题解了。SPOJ上有双倍经验,题号为SP7602。我看题解区的大佬们有的正经用博弈论做,有的打表,但是感觉没有讲得很形象,这篇题解将生动讲述打表做法,同时为了让大家在感性理解后,还可以理性理解,会附上证明(这部分参考了别的题解)。正文:Step1:打表找规律......
  • E. Two Chess Pieces -- (codeforces) 树形DP
    原题链接:https://codeforces.com/contest/1774/problem/E题意:两颗棋子,给出两颗棋子必须要去的顶点,且给出两颗棋子的相隔距离不能大于d,算出两颗棋子完成目标后走的距离。最后两颗棋子都要回到顶点1上。思路:刚开始没想出来,顺着官方题解写的,大意就是我用数组s1和s2代表两颗棋子......
  • 1465. Maximum Area of a Piece of Cake After Horizontal and Vertical Cuts
    将数组排序之后,进行差分,然后选择各自最大的能够元素相乘,就能得到最大的蛋糕块了。注意按照题目要求,最终结果要取余数classSolution:defmaxArea(self,h:int,w:int,horizontalCuts:List[int],verticalCuts:List[int])->int:horizontalCuts.sort()......
  • UVA1514 Piece it together 题解
    图论题还是在于建图题意给定一个长度为\(n\timesm\)的网格图,有的地方是白方块,有的是黑方块,有的啥也没用。给你如下四种\(L\)形方块,询问是否存在方法,让这些方块正好就是给出的图的形状。$L$形方块如下思路二分图首先我们要想,为什么需要二分图:若能拼成,那么就说......
  • [ARC114D] Moving Pieces on Line 解题报告
    AT题面简要题意有一个红色的数轴,相邻两个整点之间连有一条边,所有边初始为红色。数轴上有\(n\)个棋子,将一个棋子从\(a\)位置移到\(b\)位置,可以将\((a,b)\)之间红边变为蓝边,蓝边变为红边。给定\(k-1\)条线段,问能否进行若干次操作,使得当\(i\)是奇数,第\(i\)条线段是蓝......