UOJ Logo vfleaking的博客

博客

Goodbye Jiawu 题解

2015-02-17 17:30:24 By vfleaking

新年的巧克力棒

from Picks

数据是 vfleaking 造的,题解也是 vfleaking 写的。

算法一

有20分的数据巧克力棒长度非常小,直接搜索下或者手算就行了。

算法二

对于 $n \leq 1000$,我们可以用 DP 解决。 $f[i] = \max(f[k] + f[i - k] + [k == i - k])$。$[k = i - k]$ 表示 $k = i - k$ 时为 $1$ 否则为 $0$。时间复杂度 $O(n^2)$,可以通过前 $5$ 个点获得 50 分。

不靠谱的正解

你需要打个表,然后找规律,就能发现答案是 $n - c(n)$,其中 $c(n)$ 是 $n$ 的二进制表示中 $1$ 的个数。然后就 AC 了!

靠谱的正解

我们用数学归纳法证明上述结论。我们按二进制中 $1$ 的个数归纳。

对于只有一个 $1$,那么 $n = 2^k$,$k$ 是某个正整数,那么显然应该每次折半,递推式是 $f[n] = f[n / 2] \times 2 + 1$,解得 $f[2^k] = 2^k - 1$,只损失了$1$。

现在假设对于 $1$ 的个数比 $c(n)$ 少的都满足这个性质。

我们要证明,对于 $1$ 的个数多于 $1$ 个的时候,我们找到最低位的 $1$,假设在第 $j$ 位,然后把 $n$ 拆成 $2^j$ 和 $n - 2^j$,这是最优的。

根据归纳假设,我们只用看怎样能获得更少的 $1$。我们考虑两个数的加法,可以看作是先分别拆成 $2$ 的整数次幂之和,然后每次找到两个相同的 $2^k$ 合并成一个 $2^{k + 1}$。在这个过程中 $1$ 的个数显然是在减少的,所以对于任意 $i$ 均有 $c(n) \leq c(i) + c(n - i)$。而当 $i = 2^j$ 时可以取到等号,所以这就证明了这个算法的正确性。

新年的毒瘤

from Picks

数据是 ydc 造的,题解是 vfleaking 写的。

算法一

闷声大暴力,删点后判断是否是一棵树。时间复杂度 $O(n^2)$,可以获得 $40$ 分。

算法二

首先题目保证有解,所以肯定存在一个点使得删掉后是连通图,所以原图肯定也是连通的!很好,你要这么想就掉进我挖的大坑里去了。如果那个点是一个独立的连通块而剩下部分是棵树呢?这种情况 $m = n - 2$,我们特判掉。然后剩下的就都是连通图了。

对于 5 号测试点,保证 $m = n - 1$,说明是棵树,所以所有度数为 $1$ 的结点都是毒瘤结点。

对于 6, 7 号测试点,保证 $m = n$,说明是个环上长了很多树的样子,我们肯定要删环上的点。仔细想想可以发现就是删环上度数为 $2$ 的点就行了(即没有长出额外的树来)。

结合算法一能获得 $70$ 分。

算法三

正解需要你理解什么叫做树。如果你对树的理解仅仅是“长得像树的家伙”就完蛋了。

我们需要用一个定义来规定什么叫做树。我们可以理解成,有 $n - 1$ 条边的无向连通图。“有 $n - 1$ 条边” 提示我们最终图里有 $n - 2$ 条边,所以你需要删一个度数为 $m - (n - 2)$ 的结点。

考虑第二个条件,也就是说删掉这个点后剩下的图仍然连通,所以这个点不是割点就行了。

所以用 Tarjan 算法求割点,然后输出所有不是割点且度数满足条件的结点就行了。可以获得 100 分。(貌似这样能神奇地过掉 $m = n - 2$ 的情况……555……)

新年的桌游

from saffah

算法一

暴力出奇迹,20分可以各种方法枚举每一步的策略随便搜,不管是$O((8n)!)$,$O(2^{8n})$还是$O(n^8)$,都是可以轻松加愉快地通过的。

期望得分:20;这20分同时也是给正解写挂的人准备的,因为数据范围太小什么都卡不了。

算法二

有两个测试点没有【红太狼】和【美羊羊】,也就是只剩下了【灰太狼】和【喜羊羊】。显然【灰太狼】留在手里没有用能出就出,那么计算双方获胜所需的回合数取一个较小的获胜就可以了。

如果有【红太狼】怎么办呢?显然【红太狼】也是能出就出,那么先手一定是一下子扔出去所有的【红太狼】。唯一的问题先手是否要出【灰太狼】,这个问题我们枚举一下就可以了。

期望得分:20+40=60;这40分同时也是给正解写挂的人准备的,因为没有【美羊羊】什么都卡不了。

算法三

为了实现方便我们首先写一个纯暴力算法,然后考虑优化之。

首先如果存在一张牌你用掉就会赢,那么显然直接用就可以了;如果自己手里有【红太狼】也全用掉。

其实剩下的选项只剩下了每回合是否要出【灰太狼】。

如果当前是先手的第一回合,那么这一步暴力枚举,不会影响复杂度。

否则场上一定没有【红太狼】,现在分以下情况讨论:

如果双方都没有【美羊羊】,那么用算法二直接算出答案;

如果双方都有【美羊羊】,那么这一步暴力枚举即可;(因为双方总有一个【灰太狼】较多的,所以会很快出答案)

如果先手没有而后手有【美羊羊】,那么还是暴力一步,转化为下面的问题;

如果后手没有而先手有【美羊羊】,这个时候问题来了:

既然先手无法直接取胜,说明后手的【灰太狼】多于先手。先手的策略并不显然,但是后手是显然的:只要保证自己的【灰太狼】仍然多于先手,就一直使用【灰太狼】,否则不使用。

所以先手永远无法通过【美羊羊】取胜,只能通过【灰太狼】取胜。这个时候直接套用算法二就可以了。

但是【美羊羊】仍然有存在的意义,它可以将自己的【灰太狼】转化为一种无形威胁,使得对方不敢出过多的【灰太狼】。也就是说,在先手无法通过上述方法取胜时,可以考虑永远不出【灰太狼】,以维持平局局面。

以上两种情况取较优解就可以了。总之各种细节都注意到了还是能够愉快地AC的。

时间复杂度 $O(1)$,期望得分100。

vfk有话说

我见到比赛时不少人是人肉讨论欲仙欲死。其实我觉得这题亮点在于,你要机器去讨论嘛,你只用解决一些非常简单的问题,问题太复杂就暴暴暴暴力枚举下转化成简单问题,反正这题又不卡你时间。

如果不幸考虑了情况?样例当然是不可信的!所以我觉得你得写个暴搜来对拍一下。只要对战双方都势均力敌,就已经是比较强的数据了,所以在小范围对拍一下就好了。

夕阳西下,大家一大片一大片地 FST……

新年的QAQ

from vfleaking

我要吐槽!你们都不认真读题!比赛时好多人直接交QAQ代码。我们的要求是交一份能输出QAQ代码的代码啊……

算法一

考虑测试数据类型 A,直接输出 1,可以骗一些分。期望得分 $10$ 分。不过貌似会莫名过一些 C 类型的数据。

算法二

考虑测试数据类型 AB,用一条 if 区分这两种情况,这样期望得分 $20 \times \frac{7}{8} = 17.5$ 分。

算法三

考虑测试数据类型 C,发现只要打表就行了。可是怎么快速匹配 $n$ 呢?可以考虑用二分查找。$n \leq 16$ 需要 $4$ 次比较,正确率大概为 $(\frac{7}{8})^4 \approx 0.59$。这样直接做 C 类型就能有期望得分 $29.3$ 分。注意会顺便解决下 AB 类型的数据。通过调整二分的顺序应该能获得更高的分。

算法四

我们考虑正常向的做法,其实我们需要实现一个极高概率正确的运算。以比较两个数相等为例,返回值只可能是 $0$ 或 $1$,一个很朴素的想法就是多次比较取众数,但是问题来了,怎么不通过运算取众数?

要注意到,跳转是有 100% 的正确率的,这引导我们用行号来储存信息。我们利用所在的行号表示一个状态 $(i, j)$,即进行了 $i + j$ 次比较,有 $i$ 次是 $0$,有 $j$ 次是 $1$,这个你可以用 $i * 100 + j$ 之类的方法来编码。然后每到一个状态就再比较一次然后跳转到相应的下一个状态。我们设一个值 $L$,如果 $i + j = L$ 时就可以根据 $i, j$ 得出众数。

取 $L = 47$,就可以获得 $10^{-9}$ 级别的出错概率,几乎可以看作 $0$ 了。出错概率可以用: \begin{equation} \sum_{k = 0}^{(L - 1)/2} \binom{L}{k} (\frac{7}{8})^k (\frac{1}{8})^{L - k} \end{equation} 得出。

这个方法只适用于逻辑运算符,如果是算术运算符,我们可以通过计算两次然后比较值是否一样,如果一样就作为结果,如果不一样就再算一次。两次都算对的概率是 $(\frac{7}{8})^2$,所以期望 $(\frac{8}{7})^2$ 次就能遇上一个这种情况。而如果至少算错了一次,两个数相等的概率就是 $2^{-32}$,几乎可以看作不可能。

这样我们就实现了准确的逻辑运算符和算术运算符,然后写个程序组织一下就行了。

这就是为什么要大家交另一种语言输出 QAQ 代码了……因为如果人手写的话实在太冗长,反正你都是用生成器生成的代码,不如直接交生成器的代码好让更多人知道你的做法是怎样的。提交答案题的通病在于,你只提交了结果没有留下做题过程,无法和别人分享,这是我所不太喜欢的。

不过比赛中貌似出现了些直接一排 printf 的选手。我脑补了下大概是因为你不必做到 $10^{-9}$ 这么低的错误率,完全可以 $L$ 取小一点然后手写?总之给你们跪啦!

哦,当然还有一种方法是考虑 $(\frac{1}{8})^x$ 和 $(\frac{7}{8})^x$ 的增长速率的差异,然后取两个参数 $s, t$,如果 $s$ 次逻辑运算都是返回 $0$ 那么就返回 $0$,否则就再来一轮算 $s$ 次。如果进行了 $t$ 轮都没遇上全 $0$,那么就返回 $1$。适当选取参数可以获得很高的正确率。

以及……比赛时我才发现还有这种鬼畜做法:http://uoj.ac/submission/7555 囧傻了被屠了……我应该出成算术运算符也随机翻转奇偶性的……55555……都是我的错……

新年的魔塔

from wangyisong1996

第一个测试点

这组数据规模很小,写一个模拟器手玩就可以了。

第二个测试点

假设这组数据有$2 n$行,一开始的$\mathrm{HP}$为$m+1$。

容易发现, 这组数据由$n+1$个房间组成, 其中目标状态的位置所在的房间里 有一个能加$m-1$的$\mathrm{HP}$值的血瓶和一只$\mathrm{ATK}$为$m$,属性为2连击的怪物(我们称它为Boss)。

对于其他房间,都有若干怪物和若干蓝宝石,打死这些怪物所花费的血量跟该房间里蓝宝石加的防御值相等。

除了Boss房间以外,清空每个房间后都会得到一把黄钥匙。

假设我们进入并清空了若干房间,损失了$k (1 \le k \le m)$的$\mathrm{HP}$值, 于是打Boss前的$\mathrm{HP}$为$2 m - k$,打Boss损血$2 (m - k)$, 打完Boss后$\mathrm{HP}$为$k$。

这就说明了,这组数据是个$n$个物品,容量为$m$的01背包问题。

第二个测试点中$n = 100$, $m = 10^7$,直接dp就可以过。

第三个测试点

同上,但是$n = 55$, $m = 8 \times 10^{15}$,使用meet in the middle优化搜索即可。

第四个测试点

有$n\ (n = 24)$只怪,每只怪后面有若干个宝石和一把黄钥匙。

目标状态要求至少有$n$把黄钥匙,说明这$n$只怪都要打,而且要最小化损血。

考虑状压DP,$dp[S]$表示只打死$S$这个集合中的怪,最少的损血量,然后复杂度就是$O(n 2 ^ n)$了。

第五个测试点

$n \times n$的地图,只有$k\ (k = 10)$个点上面没有怪,且每只怪的损血是固定的,要求收集所有蓝宝石。

直接用斯坦纳树做就行了,复杂度$O(n ^ 2 3 ^ k)$。

第六个测试点

同上,但是蓝宝石被换成了血瓶。

(什么?只得了5分? ......因为有些血瓶不吃,答案可能会更优。 [捂脸熊]

第七个测试点

$100 \times 100$的地图,到处都是怪,一副不能玩的样子。

仔细观察后发现,一开始身边的怪是无伤的,先打死他们,可以得到一个蓝宝石, 接下来又有一些怪无伤,打完后又可以得到一个蓝宝石。

......

这样就可以清光所有怪了!

(什么?眼力不够?这个测试点不会做?没关系!写std!不小心就把这个点秒了!)

最后三个测试点

这是经典的魔塔模型。

(手玩大法好!如果花点时间认真手玩的话,至少能把第八个测试点玩到最优解。)

考虑一个通用的算法:

记$f[S]$为状态为$S$时的$max\_hp$,于是可以状压DP。

其中$S$为一个bitset,保存每个格子是否已经到达过, 转移时只要枚举下一个可以达到的格子即可。

所有状态和转移构成一张拓扑图,只要每次取出bitset中"1"的个数最少的状态,就能只用一个bfs来实现这个DP了。

然后你会发现,这样做根本没法跑出第八个测试点$\texttt{= =}$!

优化一

很多格子是空地,很多格子是墙壁,我们只要记录有事件(怪物,宝物,门)的格子的状态即可。

优化二

怪物的属性满足一个性质: 对任意怪物,不管玩家处于什么状态, 玩家的$\mathrm{ATK}$, $\mathrm{DEF}$, $\mathrm{INT}$中任意一项的增加都不会使打这种怪的损血变多。

于是可以在每次转移后,强制将所有能吃的宝物都吃掉(0损血的怪也可以直接杀掉),这样就能愉快的跑出第八个测试点了。

优化三

考虑一只怪,如果它边上的所有格子都已经能到达,就说明这只怪打了也是白打,可以直接在bitset中将它标记为已经访问过。

对于门也可以这样做,但是要把钥匙数量也记录在状态里,否则会因算错钥匙的数量而WA掉。

优化四

杀怪(或开门)有目的性。

考虑这样的情况,杀了一只怪(或开了一扇门)后,如果下一步能访问到的事件只多了一个, 那么从当前状态开始,一定存在一种最优的玩法,下一步访问的是那个事件。

 

在加了以上所有优化后,直接跑第十个测试数据,不一定能跑出来。

因为那组数据里有很多红门,导致优化三和优化四几乎没有效果。

但是数据里只有两把红钥匙, 我们只要枚举打开的红门是哪两个, 然后将其他红门看成墙壁,跑之前的算法,就行了。

第 8, 9, 10 号测试点的模拟程序:http://pan.baidu.com/s/1jGvcUFW 密码:2e2n

(请无视玩家死亡时模拟程序给出的分数)

 

最后祝大家春节快乐!

评论

matthew99
qianpai
phile
前排
wangyisong1996
前排好评
TKD
前排
Reisen
E题简直鬼畜= =
r_64
D题鬼畜算法好评。。。
1150076053
前排,D题鬼畜算法简直机智
Tunix
前排好评~~~
Gromah
orz
Recursion
E题用人类智慧果断滚粗了T_T
Damius
E题RMXP好评
Ezio
E题是什么。。鬼畜。。

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。