OI题解 - Burza [COCI 2016/2017 Round 2]

这场比赛真的不错~

这应该是第六题也就是最后一题。


· 题目

有一棵$n$个节点的树,树的 节点$1$ 上有一枚硬币。Daniel 和 Stjepan 用这棵树玩游戏。游戏的过程如下:

  1. Daniel 选择一个节点并把它标记;
  2. Stjepan 将硬币移动到与硬币所在节点$u$相连的未标记的节点$v$,并标记节点$u$;
  3. 一直循环1,2步骤,直到Stjepan将进行2步骤时无法移动硬币。

Daniel 想要尽快结束游戏(也就是让Stjepan移动硬币的次数尽可能小),而Stjepan想要尽可能多地移动硬币。为了增加游戏难度,Daniel 决定不看 Stjepan 将硬币移动到哪个位置(也就是说 Daniel 标记节点时并不知道此时硬币在哪),但是 Daniel 知道这棵树长什么样子。

Daniel 希望硬币移动的次数 小于 $m$ 次。请问是否存在 Daniel 标记节点的方案,使得 Stjepan 无论如何移动硬币,都不能移动硬币 $m$ 次。存在输出 “DA”,否则输出“NE”。

数据规模:

$1\leq m\leq n\leq 400$


· 解析

- 初步分析

我们将节点$1$作为树的根,并把节点$1$的深度设为$0$,不难发现 Stjepan 第 $i$ 次移动硬币后,硬币会在深度为 $i$ 的某一个节点上。那么问题就变成“是否存在Deniel标记节点的方案,使得Stjepan无论怎么移动硬币都不能使硬币到达深度为$m$的节点”。

只要硬币到达深度为 $m$ 的节点,这个标记方案就“失败”了。可见深度大于$m$的节点是没有意义的。
所以我们称深度恰好为 $m$ 的节点为“叶节点”。

请看下面两种情况,硬币在节点$U$,此时Daniel标记节点:

img1

贪心地想——为了使硬币走的步数尽可能少,显然图一的情况更容易。为什么呢?

我们定义 $cnt_i$ 表示以节点 $i$ 为根的子树中“叶节点”的个数。假设上图的图一、图二中第$3$层的点都是“叶节点”,那么图一中 节点$U$ 的子节点的 $cnt$ 为 $2$ ,而图二中 节点$U$ 的两个子节点的 $cnt$ 都为 $1$。

仍然是贪心的思想,我们标记 $cnt$ 大的点一定更“合算”,因为 $cnt$ 越大,能够“堵住”的叶节点就越多。

根据这一点,我们可以构造出一个最坏情况的图:

img2

这个图“坏”在除了根节点$U$,其他所有点的 $cnt$ 都是 $1$,这意味着我们标记一个点只能堵住一个叶节点。对于这种图,我们怎么完成方案呢?

可以发现当硬币的深度为 $i$ 时,我们一定会标记深度为 $i+1$ 的点。而且相同深度的点我们只会标记一个。

假设叶节点的个数是 $t$,我们就需要标记 $t$ 个点才能将所有叶节点堵完。则当 $m\ge t$ 时,我们就可以把所有叶节点堵完,就输出 $DA$。

这是最坏情况,需要满足 $t\leq m$ ,那么对于其他情况,如果 $t\leq m$ ,也一定可以找到解。而我们知道,对于最坏情况,$t\leq \frac nm$ —— 如果 $\frac nm\leq m$ ,即 $n\leq m^2$,那 $t$ 就一定小于等于 $m$,此时一定存在解,如果最坏情况情况都有解,那其他情况都有解。

于是分成两种情况:

  1. $n\leq m^2$ 此时直接输出 “DA”;(证明看上面)
  2. $n>m^2$

- 处理 $n>m^2$ 的情况

因为 $n\leq 400$ ,那此时 $m<20$ 即 $m\leq 19$ 。

也就是说叶节点的深度不超过 $19$ ……又因为根据之前的分析,同一个深度的节点我们最多会标记一个……en……状态压缩?(Right!)
对于二进制数 $S$ ,如果 $S$ 的第 $i$ 位为 $1$ ,就说明标记了一个深度为$i$的节点。

对于每个叶节点,我们将它们从左到右编号(这样能够保证一棵子树里包含的叶节点的编号是连续的),并且定义 lev[u][0] 表示以 $u$ 为根节点的子树中的叶节点的最小编号,lev[u][1] 表示以 $u$ 为根节点的子树中的叶节点的最大编号。因为以 $u$ 为根节点的子树中叶节点的编号是连续的 ,那么该子树中包含的叶节点为 lev[u][0]~lev[u][1]

定义数组 rig[i] 储存 lev[u][1]==i 的所有 u

定义 dp[i][S] 表示能否通过标记 $S$ 深度的点堵住前 $i$ 个叶节点。

显然:最初状态为 dp[0][0]=true ,状态转移方程式为:

1
2
3
4
u=rig[i][t]
dp[i][S]|=dp[lev[u][0]-1][S^(1<<dep[u])]
//dep[u]表示u的深度
//保证 (1<<dep[u])&S == 0

最后判断 (cntlev是叶节点个数) dp[cntlev] 中有没有 S 满足 dp[cntlev][S]==true 就好了~


· 源代码

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
/*Lucky_Glass*/
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
const int N=400,INF=(1<<29);
int n,m,cntlev;
vector<int> lnk[N+5],rig[N+5];
int dep[N+5],lev[N+5][2];
bool dp[N+5][(1<<19)+5];
void DFS(int u,int pre) {
dep[u]=dep[pre]+1;
if(dep[u]==m-1) {
lev[u][0]=lev[u][1]=++cntlev;
return;
}
for(int i=0; i<(int)lnk[u].size(); i++) {
int v=lnk[u][i];
if(v==pre) continue;
DFS(v,u);
lev[u][0]=min(lev[u][0],lev[v][0]);
lev[u][1]=max(lev[u][1],lev[v][1]);
}
}
int main() {
freopen("burza.in","r",stdin);
freopen("burza.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=1; i<n; i++) {
int u,v;
scanf("%d%d",&u,&v);
lnk[u].push_back(v);
lnk[v].push_back(u);
}
if(m*m>=n) {
printf("DA\n");
return 0;
}
for(int i=1; i<=n; i++) lev[i][0]=INF,lev[i][1]=-INF;
dep[0]=-2;
DFS(1,0);
for(int i=2; i<=n; i++)
if(lev[i][0]!=INF)
rig[lev[i][1]].push_back(i);
dp[0][0]=true;
for(int pos=1; pos<=cntlev; pos++)
for(int S=0; S<(1<<m); S++) {
for(int i=0; i<(int)rig[pos].size(); i++) {
int u=rig[pos][i];
if((1<<dep[u])&S)
dp[pos][S]|=dp[lev[u][0]-1][S^(1<<dep[u])];
}
}
for(int i=0; i<(1<<m); i++)
if(dp[cntlev][i]) {
printf("DA\n");
return 0;
}
printf("NE\n");
return 0;
}

The End

Thanks for reading!

Email: lucky_glass@foxmail.com ,欢迎提问~

0%