Charlie01

Charlie's Solution for ZJOI2015 day1

其实这次ZJOI的题目赛后想想都很简单呢

有句俗话讲考试的时候智商是减半的……事实真是如此呢

考挂了……就留下点什么吧

---

A. 幻想乡战略游戏

题意就是对于一棵树每次单点修改&询问带权重心

其实是很基础的点分治题呢

考虑一个subtask……询问一个点作为带权重心时的答案

那么对于每一个点分结构记录三个值——当前点分结构中的总权值、当前点分结构中的点到当前重心的带权距离和、当前点分中的点到当前重心的点分父亲的带权距离和

那么询问一个点时，沿着点分树走上去不断统计就可以了呢

然后我们考虑询问整棵树的带权重心

考虑一个重心，计算他作为带权重心的答案和原树上与其相邻的点作为带权重心的答案

如果某个相邻的点作为带权重心的答案小于当前点，那么答案一定在这个相邻点所在的子树中，将重心跳到那棵子树的重心就可以了

这样不断走，直到某个重心相邻的点作为带权重心的答案都不小于当前重心，那么当前重心就是答案

对于询问两个点的距离呢……我们可以用RMQLCA做到O(1)询问……具体就是记录欧拉路径然后建ST表就可以啦

这样询问答案是走log层，每层重心询问再走log层，时间复杂度O(Nlog^2N)

标算就是这样……简直可以当作点分治的入门题呢

然而出题人真是太良心了……出题人并没有卡暴力

于是呢……我们将上一次的带权重心暴力地爬到现在的重心就可以了呢

窝是暴力爬重心的代码：http://ideone.com/81mQ5v

窝是动态点分治的代码：http://ideone.com/yhb7YX

---

B. 地震后的幻想乡

题意就是求最小瓶颈树的期望啦

这题出题人在WC上几乎一模一样讲过呢……只能怪自己不好好听课咯

出题人给出的做法是积分……但是好像精度爆炸了呢然后要用__float128

这里给一种计数问题的做法……比较易于理解吧

令f[S][i]表示当前生成树的点集为S，最后一条加入的边的排名为i的方案数

令g[S][i]表示f[S][i]的前缀和

令cnt[S]表示点集S代表的子图的边数

那么易得转移方程为

自己yy下就好啦

得到方案数以后根据数学期望的定义和出题人的关怀，那么答案就是sigma(i*f[2^n-1][i]/m!/(m+1))啦

窝是萌萌哒代码：http://ideone.com/xBXveK

---

C. 诸神眷顾的幻想乡

题意就是给一棵树，以树上两个结点为起点和终点，把路径上的字符连起来作为字符串，问有多少本质不同的字符串

其实也是一道模版题啦

题目里有一句话是太阳花田的结构比较特殊，只与一个空地相邻的空地的数量不超过20个

提问：这句话是什么意思呢？A. 叶子结点最多20个 B. 每个结点的度最多为20

仔细看几遍后我们发现答案是A（相差一个“只”字题意就不一样啦）……这告诉我们语文在OI中的重要性

那么一切都很明朗了

我们可以从每个叶子开始DFS，建出很多很多Trie，然后把这些Trie合并成一棵大Trie

然后呢就有两种做法啦

一种做法是对于Trie建出后缀数组

怎么对Trie建后缀数组呢？

考虑倍增算法……在建SA的时候“某个位置后面的第2^j位”改成“Trie上第2^j个父亲”就可以啦

那么考虑height数组的定义，答案就是字符串总数减去sigma(height[i])

第二种做法呢是对于Trie建一个广义后缀自动机，那么答案就是sigma(i->value - i->parent->value)啦

窝是后缀数组的代码：http://ideone.com/7C25Tx

窝是后缀自动机的代码：http://ideone.com/Aqyruc

---

嗯 ZJOI2015day1的题目就是酱

看起来很水呢可自己但是为什么不会呢

人弱就该多做题呢

I am waiting on the edge of the unknown.

By Charlie

Apr 9, 2015