/ SMOJ

2016.10.7 NOIP模拟赛

SMOJ/1433 立方体

直接模拟就好,开一个分数类型的结构体,记得要用long long,不需要高精度。一开始调试的时候发现数据一超过2147483648就会出问题,开了unsigned long long还是这样。仔细检查之后发现有一个地方的int没有改成long long,浪费了半个小时,实在不应该。

SMOJ/1343 字符串的划分

这题错的比较惨烈,没有拿到分。我分享一下我的做法吧。

首先从头开始贪心,碰到出现过的字母就截断,重置exist数组。这样估计是能得到最小段数的。为了得到最小字典序,我又从后往前扫一遍,如果在前一截中出现了一个比当前截开头更小的字母,那就把当前截的开头移过去。可以证明这样做能够使程序算出来的答案更靠近正确答案,但是没有办法证明这样做就能得到正确答案!

SMOJ/1344 糖果

这道题贪心。我想分几种情况考虑:

非连通图

如果有多个联通块,把多少糖果放在与T不联通的联通块上都无所谓,所以答案可以为无限大,在题目中直接输出-1.

联通图

题目中强调了该图为无向无环图,无环,又联通,只能是树了。

T为一个端点的链状树

这是最简单的情况了。考虑总共四个节点的情况:

T-0-0-0

可以在第二、三、四号位置放一个,一定不能取,所以不可能危及到T:

T-1-1-1

考虑再增多一点,如果还在这个图的基础上增多,怎样都一定会危及到T。

如果想在第二号位置上放一个,实际上可以认为是从3号位置推过来的:

T-0-3-1

因为在转移糖果的过程中有糖果会被消耗,我们应该尽量使它们恢复到“熵最小”的情况,也就是说最原始、消耗的最少的情况,应该就可以达到糖果总数的最大值:

T-0-0-7

所以最好的策略就是放在离T最远的地方,每离T远一格,允许放的糖果数目就可以*2+1。

普通的树

因为没有明确根,我们可以直接认为T就是根。

每棵子树之间因为T不能放糖,所以不能经过T来转移糖果,所以子树之间没有联系,只要考虑一棵子树,其他也是一样的策略。

子树可以看作一条链上面有支链。如果我们要使糖果数目最多,当然还是要把它放的最远,从根倒着转移回去的时候要把最多的数目给主链(类似有机物的概念)。怎么处理支链?

我们不能让支链对主链有影响。如果有的话,就要使得主链能够放的数目减少,支链放的数目增多,然而支链深度没有主链大,必定会造成答案不是最优。

推到支链的第一个节点的时候,允许的最大容量为1,再往回推一个节点,最大容量为3……这就相当于在这个分支点出来了一个T点,除了主链,其他的支链都不可以有糖果转移到这个分支点。

代码实现也就很清晰地出来了。两次DFS,一次先找每个节点深度最深的儿子,同时判断是否是联通图;第二次算出最多有多少个糖果,将允许的容量放在叶节点上,途中的点全部不放东西。记得一定要特判答案是否大于10910^9

总结

感觉这天做题已经进入状态了,AC两道题,思路清晰简洁。但是对于第二题,我有点贪,用贪心来蒙一个,希望能够得满分;但是事实上搜索就能拿到80分了。如果用搜索做了的话,总分可以达到280!