[国庆集训]Day2解题报告

发表于 | 阅读次数：

题目链接

戳我n(≧▽≦)n

T1

又是我在场上唯一A的一题。。。（话说的今天的题怎么比昨天难这么多啊！！！(#`O′)）

一看到这题首先想了一下线段树。emmm…好像没法做，看看了数据范围，$10^5$啊，肯定是$O(NlogN)$的算法。

于是我就很傻*的把所有$logN$的数据结构都想了一遍。

。

。

。

后来，我几乎想要放弃的时候，我盯住了一个$dalao$的脸，打量了许久后，看回屏幕，发现了重要关键字求最矮的花的最大高度，突然想到了$dalao$说过的经典语句像这种要求最小的最大值什么的，就用二分试试看。于是，我仔细考虑了一下，难点在于二分答案后怎么进行判断。

于是，我又再次盯住那个$dalao$的脸（事实证明$dalao$这题只有$50$），思考这种区间加的操作怎么快速实现。然后然后然后，就想到了差分约束。于是我大喊一声：“牛逼！”，然后开始光速敲代码。

快交卷的时候，教练说这是$CodeForces$上的原题，我顿时震惊(○´･д･)ﾉ。于是，光速打了个暴力，然后开始对拍（甚至还错了），事实证明我生成数据的时候居然生成了$L=0$的数据（我真是*了）。吓得我以为我错了。

。（讲点正经的↓↓↓）

由于高度单调，所以我们考虑二分答案，重要就在于怎么对答案进行判断。于是，我们对于二分出的高度$k$与花的高度$h[i]$进行逐一判断，如果一束花的高度小于$k$，那么，我们就必须让他长到$k$，但是我们是区间操作啊！所以考虑维护一个数组$s$进行差分，记录下当前的花已经长高了多少。这样我们可以逐一判断，就算有重合的区间操作也能够考虑完全。时间复杂度为$O(NlogN)$，就可以$A$掉这题了（不要像我这么傻*地去想数据结构）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <stdio.h>
#include <iostream>
#define Re register int

int N,M,L,h[100005],s[100005],l,r,ans;

template <typename T> inline void read(T &var)
{
	T x=0; int w=0; char ch=0;
	while (!isdigit(ch)) w|=ch=='-',ch=getchar();
	while (isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	var=w?-x:x;
}
bool Check(int k)
{
	int Day=M;
	for (Re i=1; i<=N+1; ++i) s[i]=0;
	for (Re i=1; i<=N; ++i)
	{
		s[i]+=s[i-1];
		if (s[i]+h[i]<k)
		{
			if (k-(s[i]+h[i])>Day) return false;
			Day-=(k-(s[i]+h[i]));
			if (i+L<=N) s[i+L]-=(k-(h[i]+s[i]));
			else s[N+1]-=(k-(h[i]+s[i]));
			s[i]+=(k-(h[i]+s[i]));
		}
	} return true;
}
int main(int argc, char const *argv[])
{
	read(N),read(M),read(L); l=1;
	for (Re i=1; i<=N; ++i) read(h[i]),r=std::max(r,h[i]); r+=M;
	while (l<=r)
	{
		int mid=(l+r)>>1;
		if (Check(mid)) ans=mid,l=mid+1;
		else r=mid-1;
	}
	printf("%d\n",ans);
	return 0;
}

T2

这算是Day2里面最难的一题了，我一看到这题就printf("6\n9\n6\n");了（结果还有10分O(∩_∩)O）

考完后看了看官方题解

把删边操作倒过来，变成每次加边，维护直径
有一个容易证明的结论
两棵树合并后的直径，它的端点一定从这两棵树原本的直径中取
那么预处理好最终树的形态，利用LCA和并查集就行了

说的实在是太好了（你TM还能再简单点吗？(╯▔皿▔)╯）

不过这里有个很重要的思路就是把删边操作倒过来（虽然我在考试的时候想过，但是还是不会。。。）

至于那个题解中的容易证明的结论

在下面我将给出证明

假设此树的最长路径是从s到t,我们选择的点为u。反证法：假设搜到的点是v。
1、v在这条最长路径上，那么dis[u,v]>dis[u,v]+dis[v,s]显然矛盾。
2、v不在这条最长路径上，我们在最长路径上选择一个点为p，则dis[u,v]>dis[u,p]+dis[p,t]，那么有dis[s,v]=dis[s,p]+dis[p,u]+dis[u,v]>dis[s,p]+dis[p,t]=dis[s,t]，即dis[s,v]>dis[s,t]矛盾。
也许你想说u本身就在最长路径，或者其它的一些情况，但其实都能用类似于上面的反证法来证明的。
综上所述，你两次dfs(bfs)就可以求出最长路径的两个端点和路径长度。

所以说两棵树合并后的直径，它的端点一定从这两棵树原本的直径中取

那么如何计算答案呢？

我们只需要对已经计算的$Ans$经行乘除操作就行，但是，可能会出现爆精度的情况。所以这个时候我们就需要用到逆元。至于什么是逆元，怎么求解逆元，则不再本题解的范围内。（如果想了解的请点我）

然后我们就可以大方的A掉这题了（再吐槽一下：你TM快100行的程序你题解就4行？？？）（我写的还算简短的了）（我们机房还有dalao写了180行！！）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#define MOD int(1e9+7)
#define Re register int
#define LL long long
using namespace std;

struct Edge{
	int to,next;
}e[200005];
struct Point{
	int u,v,w;
	inline bool operator < (const Point &a) const {return w>a.w;}
}d[6];
int cnt,head[100005],dx[100005],dy[100005],dz[100005],dis[100005],maxd;
int N,w[100005],f[100005][18],u[100005],v[100005],k[100005],Fa[100005],dep[100005];
LL Ans=1,ans[100005];

template <typename T> inline void read(T &var)
{
	T x=0; int w=0; char ch=0;
	while (!isdigit(ch)) w|=ch=='-',ch=getchar();
	while (isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	var=w?-x:x;
}
inline void AddEdge(int u,int v)
{
	e[++cnt]=(Edge){v,head[u]}; head[u]=cnt;
	e[++cnt]=(Edge){u,head[v]}; head[v]=cnt;
}
int GetF(int x) {return x==Fa[x]?x:Fa[x]=GetF(Fa[x]);}
inline int KSM(int x,int y)
{
	int ret=1;
	while (y)
	{
		if (y&1) ret=ret*1LL*x%MOD;
		x=x*1LL*x%MOD; y>>=1;
	} return ret;
}
void LCA_dfs(int now,int fa)
{
	dep[now]=dep[fa]+1; dis[now]=dis[fa]+w[now];
	f[now][0]=fa; maxd=max(maxd,dep[now]);
	for (Re i=head[now];i;i=e[i].next)
		if (e[i].to!=fa) LCA_dfs(e[i].to,now);
	return;
}
inline int LCA(int u,int v)
{
	if (dep[u]>dep[v]) swap(u,v);
	for (Re i=17; i>=0; --i)
		if (dep[f[v][i]]>=dep[u]) v=f[v][i];
	for (Re i=17; i>=0; --i)
		if (f[u][i]!=f[v][i]) u=f[u][i],v=f[v][i];
	return u==v?u:f[u][0];
}
inline int Dist(int u,int v) {return dis[u]+dis[v]-2*dis[LCA(u,v)]+w[LCA(u,v)];} 
int main(int argc, char const *argv[])
{
	read(N);
	for (Re i=1; i<=N; ++i)
	{
		read(w[i]); dx[i]=dy[i]=Fa[i]=i;
		dis[i]=dz[i]=w[i]; Ans=Ans*w[i]%MOD;
	}
	for (Re i=1; i<N; ++i) read(u[i]),read(v[i]),AddEdge(u[i],v[i]);
	for (Re i=1; i<N; ++i) read(k[i]);
	dep[1]=1; LCA_dfs(1,0); ans[N]=Ans;
	for (Re j=1; (1<<j)<=maxd; ++j)
		for (Re i=1; i<=N; ++i)
			f[i][j]=f[f[i][j-1]][j-1];
	for (Re i=N-1; i>=1; --i)
	{
		int fx=GetF(u[k[i]]),fy=GetF(v[k[i]]); Fa[fx]=fy;
		Ans=Ans*KSM(dz[fx],MOD-2)%MOD*KSM(dz[fy],MOD-2)%MOD;
		d[0]=(Point){dx[fx],dy[fx],dz[fx]};
		d[1]=(Point){dx[fy],dy[fy],dz[fy]};
		d[2]=(Point){dx[fx],dx[fy],Dist(dx[fx],dx[fy])};
		d[3]=(Point){dx[fx],dy[fy],Dist(dx[fx],dy[fy])};
		d[4]=(Point){dy[fx],dx[fy],Dist(dy[fx],dx[fy])};
		d[5]=(Point){dy[fx],dy[fy],Dist(dy[fx],dy[fy])};
		sort(d,d+6);
		dx[fy]=d[0].u; dy[fy]=d[0].v; dz[fy]=d[0].w; 
		Ans=Ans*dz[fy]%MOD; ans[i]=Ans;
	}
	for (Re i=1; i<=N; ++i) printf("%lld\n",ans[i]);
	return 0;
}

T3

这算是Day2中最简单的一题了（Guest：那你怎么没A？）（我：谁让他放最后一题？！高一蒟蒻不会数学期望啊，瑟瑟发抖）

不过教练前天晚上还给我们讲了期望，说明天会考（那就是我太菜了吧）

但是很多人都没有在现场A出来啊。。。看见题目中的与答案的差值<=10^-5即视为正确。以为妥妥过了。

可是官方（线上测试）并没有写SPJ（官方说不会用）。。。

导致很多人AC的程序都被卡掉了。（心中窃喜）

不过后来想想，woc他们怎么都会，于是我打算好好学数学了……（过几天开坑写个数学笔记）

不扯淡了，看题解吧↓↓↓

我们考虑设$f[i][j]$表示剩余$i$张红牌，剩余$j$张黑牌时的在最优策略下的期望收益。

很容易想到，$f[i][j]$肯定由$f[i−1][j],f[i][j−1]$转移而来。

同时，决策数量也很少，只有3种（别怪我，我不懂弄支持大括号）

  1. $f[i][j]=(f[i−1][j]+1)∗i/(i+j)$
  2. $f[i][j]=(f[i][j−1]−1)∗j/(i+j)$
  3. $f[i][j]=0$

分别对应的是

  1. 抽到红牌
  2. 抽到黑牌
  3. 停止游戏

这样我们很容易写出状态转移方程

然后这里还可以使用滚动数组优化

程序不长，思路也挺简单的（但是我就是没A，看来要好好学数学了）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <stdio.h>
#include <iostream>
#define Re register int

double f[2][1005];
int N,M,p;

template <typename T> inline void read(T &var)
{
	T x=0; int w=0; char ch=0;
	while (!isdigit(ch)) w|=ch=='-',ch=getchar();
	while (isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	var=w?-x:x;
}
int main(int argc, char const *argv[])
{
	read(N),read(M);
	for (Re i=1; i<=N; ++i)
	{
		p^=1; f[p][0]=i;
		for (Re j=1; j<=M; ++j)
			f[p][j]=std::max(0.0,(f[p^1][j]+1)*i/double(i+j)+(f[p][j-1]-1)*j/double(i+j));
	}
	printf("%.8lf\n",f[p][M]);
	return 0;
}