新年的巧克力棒

from Picks

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

算法一

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

算法二

对于 $n\le 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)\le 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 类型的数据。

算法二

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

算法三

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

算法四

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

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

取 $L=47$，就可以获得 ${10}^{-9}$ 级别的出错概率，几乎可以看作 $0$ 了。出错概率可以用： $$\sum _{k=0}^{(L-1)/2}(\genfrac{}{}{0ex}{}{L}{k})(\frac{7}{8}{)}^k(\frac{1}{8}{)}^{L-k}$$ 得出。

这个方法只适用于逻辑运算符，如果是算术运算符，我们可以通过计算两次然后比较值是否一样，如果一样就作为结果，如果不一样就再算一次。两次都算对的概率是 $(\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

第一个测试点

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

第二个测试点

假设这组数据有$2n$行，一开始的$\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}$为$2m-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\mathrm{\_}hp$，于是可以状压DP。

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

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

然后你会发现，这样做根本没法跑出第八个测试点$\mathtt{\text{= =}}$！

优化一

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

优化二

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

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

优化三

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

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

优化四

杀怪（或开门）有目的性。

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

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

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

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

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

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

最后祝大家春节快乐！