JOISC2020 题解

发表于 分类于

吐槽

日本人是真的喜欢通信题。。。下面通信题的 Anna 和 Bruno 由于习惯被我换成了 Alice 和 Bob。

Day1

曲芸飛行 (Aerobatics)

咕咕咕

简要题意

咕咕咕

Code

咕咕咕

T2

咕咕咕

简要题意

咕咕咕

Code

咕咕咕

T3

简要题意

有 n(1≤n≤2.5×105)n(1\le n\le 2.5\times 10^5) 个初始为空的序列，又有 mm 个团体。你要支持以下三种操作：

  1. 给出 li,ri,ki,cil_i,r_i,k_i,c_i，

Day3

古代の機械 (Ancient Machine)

简要题意

这是一道通信题

Alice 知道一个长度为 n(1≤n≤105)n(1\le n\le 10^5) 的字符串 ss，字符集为 X,Y,Z。Bob 要在这个 ss 上玩游戏，但是他并不知道 ss 的具体信息，只知道他的长度 nn。他每次能擦掉一个字符，他要把整个字符串都擦掉；特别的，如果某一次 Bob 擦掉的字符是 Y，并且它前面的字符是 X，后面的是 Z，则 Bob 的得分 +1+1。

Alice 要告诉 Bob 一个长度不超过 7000070000 的 01 串，Bob 要根据这个串确定他要怎么玩这个游戏，让自己得分最大化。

题解

当时做的时候贪心假了好几次，就离谱。。。幸好最后拿到了 7070，比赛结束前 33 分钟想出了 100100 做法。

首先，把整个串都传给 Bob 是很蠢的，因为你怎么压缩都没有办法压到 nn 以下。可以 Alice 先把答案做出来，把这个序列再传给 Bob。

我们首先考虑 Alice 怎么算出答案。我们考虑贪心，找到第一个 X，再找到它后面所有的 Z。我们从前往后处理每一个 Z，对于每个 Z，我们先把它之前的到第一个 X的从后往前删掉，再把这个 Z 删掉，最后把剩下多余的删掉。

这样必是正确的，因为对于每个 Y，因为后面的 Z 存在，所以只要考虑 X 的影响。如果这个 Y 会贡献，那因为是从前往后删的，所以它前面的 X 一定不会比它先删掉，所以它一定会贡献。所以一个贡献都不会漏掉。

于是我们把第一个 X 和后面的所有 Z 都用 11 表示，剩下的用 00 表示，Bob 就可以知道怎么删了。这样子就可以把操作序列的长度做到 nn，得到 7070 分。

我们继续考虑这个序列有什么性质：你发现这个序列如果有两个连续的 11，后面的 11 就没有用了，可以改成 00，所以这个序列就不可能有两个连续的 11。这样子的长度为 nn 的序列的个数我们记作 fnf_n，可以从 fn−1f_{n-1} 加一个 00 转移，也可以从 fn−2f_{n-2} 加 0101 转移，所以有fn=fn−1+fn−2f_n=f_{n-1}+f_{n-2}，又有 f0=f1=1f_0=f_1=1，所以就是斐波那契数列。

斐波那契数列的第 nn 项可以大概是 1.168n1.168^n，所以我们大概是要用长度为 log⁡21.168n=nlog⁡21.168≈69400\log_2{1.168^n}=n\log_2{1.168}\approx 69400 的二进制数可以表示出所有的长度为 nn 的这样的串，所以就过了。

Code

咕咕咕

ボディーガード (Bodyguard)

简要题意

有一条街，其中有 n(1≤n≤2800)n(1\le n\le 2800) 个人，第 ii 个会从 tit_i 的时间开始出发以一个单位长度每秒的速度从 aia_i 移动到 bib_i，一到 bib_i 这个人就会消失。

现在有 q(1≤q≤3×106)q(1\le q\le 3\times 10^6) 个保镖从 TiT_i 的时间开始从 AiA_i 开始接工作，速度也是每秒一个单位长度，来保护这 nn 个人，如果在某一时间点上如果保镖和一个人在同一位置上他就可以保护这个人。但是保镖不能同时保护两个人，即使两个人的坐标重合。保镖保护一个人 ii 保护了 d(d∈R)d(d\in \mathbb{R}) 个单位长度（保镖可以还没有走完完整的格子就溜号），这个保镖就可以得到 cidc_id 的报酬。

对于每个保镖，你要求出他可以获得的最大的报酬。

0≤ti,Tj≤1090\le t_i,T_j\le 10^9，−109≤ai,bi,Aj≤109-10^9\le a_i,b_i,A_j\le 10^9。

题解

咕咕咕

Code

咕咕咕

ビーバーの会合 2 (Meetings 2)

简要题意

给定一棵 n(1≤n≤105)n(1\le n\le 10^5) 个点的树，对于每一个 k=1∼nk=1\sim n，我们要计算要怎么在树上选择 kk 个点，使得到这些点的距离之和最小的点的数量最多。你只需要输出这个最大数量即可。

题解

一开始想了一个假做法，交上去 WA 00，之后加一个点分治就过了。赛后被指出正确性可能有问题，吓死我了。。。后来证明了一下发现是没有问题的。

时间复杂度为 O(nlog⁡n)O(n\log n)，空间复杂度为 O(n)O(n)。

Code

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
#include <bits/stdc++.h>
#define il inline
const int N=4e5+5;

int n,rt,Z,S,ans[N],s1[N],s2[N],f[N],g[N];
int to[N],nx[N],hd[N],sze; bool o[N];

il void add(int u,int v){to[++sze]=v,nx[sze]=hd[u],hd[u]=sze;}

il void dfs1(int u,int p,int d)
{
	s2[u]=1; int i,v;
	for (i=hd[u]; i; i=nx[i]) if ((v=to[i])!=p&&!o[v]) dfs1(v,u,d+1),s2[u]+=s2[v];
	f[s2[u]]=std::max(f[s2[u]],d);
}

il void dfs2(int u,int p,int d)
{
	g[s2[u]]=std::max(g[s2[u]],d); int i,v;
	for (i=hd[u]; i; i=nx[i]) if ((v=to[i])!=p&&!o[v]) dfs2(v,u,d+1);
}

il void cal(int u)
{
	memset(f,0,S+1<<2),dfs1(u,0,1); int i,j,v;
	for (i=S; i; i--) ans[i+i]=std::max(ans[i+i],f[i]),f[i-1]=std::max(f[i-1],f[i]);
	for (memset(f,0,S+1<<2),i=hd[u]; i; i=nx[i]) if (!o[v=to[i]])
	{
		memset(g,0,s2[v]+1<<2),dfs2(v,u,2);
		for (j=s2[v]; j; j--)
			ans[j+j]=std::max(ans[j+j],f[j]+g[j]-1),
			f[j]=std::max(f[j],g[j]),g[j-1]=std::max(g[j-1],g[j]);
	}
}

il void getrt(int u,int p)
{
	s1[u]=1; int i,v,z=0;
	for (i=hd[u]; i; i=nx[i]) if ((v=to[i])!=p&&!o[v])
		getrt(v,u),s1[u]+=s1[v],z=std::max(z,s1[v]);
	if ((z=std::max(z,S-s1[u]))<Z) Z=z,rt=u;
}

il void sol(int u)
{
	o[u]=1,cal(u); int i,j,v;
	for (i=hd[u]; i; i=nx[i]) if (!o[v=to[i]])
		S=Z=s1[v],getrt(v,0),sol(rt);
}

int main()
{
	scanf("%d",&n); int i,u,v;
	for (i=1; i<n; i++) scanf("%d%d",&u,&v),add(u,v),add(v,u);
	
	for (S=Z=n,getrt(1,0),sol(rt),i=1; i<=n; i++) if (i&1) puts("1"); else printf("%d\n",ans[i]);
	
	return 0;
}

Day4

T1

简要题意

有 n(1≤n≤2×105)n(1\le n\le 2\times 10^5) 个开区间，第 ii 个开区间为 (li,ri)(−109≤li,ri≤109,li≠ri)(l_i,r_i)(-10^9\le l_i,r_i\le 10^9,l_i\ne r_i)，编号为 ii。你要从中选出 k(1≤k≤n)k(1\le k\le n) 个区间，使得这些区间的编号形成的序列进行从小到大排序后字典序最小。

题解

咕咕咕

Code

咕咕咕

T2

简要题意

这是一道通信题

有一个 n×n(1≤n≤100)n\times n(1\le n\le 100) 的期盘，上面有 k(k=7)k(k=7) 个关键点。Alice 知道这些关键点和 nn，Bob 不知道这些信息。Alice 要给这个矩阵的每个数赋上一个不超过 1212 的正整数权值，Bob 不知道 Alice 是怎么赋值的。

Bob 现在在这个棋盘上的某个点 (x,y)(x,y)，这个点不会在棋盘的边界上。但是 Bob 不知道 xx 和 yy，他只知道他周围九个格子上的点权值的情况。Bob 要根据这些信息输出这 kk 个关键点在他的哪个方位。如果一个点在 Bob 的右上，可以输出“右”也可以输出“上”；但如果在正右方，那只能输出“右”；如果他正好在这个点，你也要输出“正好在这里”。

题解

咕咕咕

Code

咕咕咕

T3

简要题意

有 n(2≤n≤2×105)n(2\le n\le 2\times 10^5) 个选手，第 ii 个选手的分数是 hi(1≤hi≤109)h_i(1\le h_i\le 10^9)。还有 nn 条信息，形如：“ai(1≤ai≤n)a_i(1\le a_i\le n) 的分数不必 ii 的低”。

但是现在你发现选手的分数和给的信息矛盾，你可以花费 cic_i 元把第 ii 个选手的分数改成在区间 [1,109][1,10^9] 的整数。你要求最小花费，使得选手的分数和信息不冲突。

题解

咕咕咕

Code

咕咕咕