籟·来·也

这次SRM时间挺不错的，连半年没在TC露面的Fire也跑来做了，并且很神奇的和我分在了同一个room，结果room里悲剧的有八个红人，直接导致本来很有机会的challenge阶段无所事事……

这次又是rng_58出的一套非常有意思的题，总的来说这次的250非常的简单，几乎没有挂的；500比较难想，我也是纯yy，直到AC的时候也没法证明使用的贪心是对的；1000只有某有追求的人过了，主要是难想，知道了做法后并不难写。

TC Utilities的结果还没出来，于是就截个rating图，达到2637的新高，顺便不小心变成school第一了，貌似有希望向2700的高度冲击了，加油。

1. 250P RabbitNumbering

有50个兔子，要给每个兔子编号，每个兔子i允许的编号是小于等于num[i]的自然数，且要求每只兔子的编号不能相同，问一共有多少不同的编号方式。

这个题似乎想不到10秒就能想到做法了，显然，给兔子编号的顺序是无关的，于是把所有兔子按照num[i]排序，从num[i]值比较小的兔子开始编号。这样的话，不管当前兔子编什么号，都会让只好的每个兔子少一个选择。于是，每个兔子可以选的编号数num[i]-i种，把所有的乘起来就是答案了。

2. 500P Nisoku

有50个大小范围为[1.5, 10.0]的浮点数，每次可以取出两个数相加或者相乘，然后把结果放回去，直到剩下一个数。问如何操作才能使最后剩下的数最大，求这个最大的数。

首先我们可以发现，1.5这个数字出现在范围里显然是有点突兀的，一般情况下使用这样一个奇怪的数字一定是有原因的，让我们一步步来分析。首先我们来看看，对于两个数什么时候相加比相乘要好。a+b>a*b可以推出1/a+1/b>1，转化一下，对于固定的a，当b<a/(a-1)的时候，a+b是大于a*b的。其中当a等于1.5的时候，要求b<3，于是我们可以发现，1.5保证了我们不会需要3个数加在一起的情况，因为两个数加在一起至少是3.0了，不可能再去加任何的数。于是，最优解一定是某些数对相加，然后所有的数相乘。

于是让我们继续来考察应该如何的乘，假设有一对进行相加的数对为(a_i, a_j)，而有另外一个不参加相加的数为ak，我们可以证明一定有a_k>a_i和a_k>a_j，这个证明应该不是麻烦。于是我们知道，所有参加相加的数一定小于等于所有不参加相加的数。接着我们来考察这些相加的数如何相加能使答案更大，考虑两对相加的数(a_i, a_j)和(a_k, a_l)，我们可以证明一定有一对数完全在另一对之间，也即一定是a_i<=a_k<=a_l<=a_j或者a_k<=a_i<=a_j<=a_l，因为否则可以通过交换使的答案更大，这个证明也不难。

最后我们只要先把所有数排序，然后枚举前多少的小的数进行加的操作，同时保证加的时候是一头一尾的加，这样就可以计算出最优解了。比赛的时候很幸运的根据sample yy除了这个正确的算法，虽然没有证明出来，但是因为1000完全没想法，于是干脆写了个暴力程序来对拍，没有发现有错误的，于是觉得应该没问题了，还是yy王道啊。顺便，Nisoku到底是个啥东西，召唤日语帝。

3. 1000P RabbitPuzzle

一条直线上有三只兔子，还有三个窝，每轮可以有一只兔子进行跳跃：一只兔子可以从以另外一只兔子为中心点，跳到当前位置的对称位置，但是跳跃的过程中不能越过第三只兔子，最后也不能和第三只兔子重合。现在问一共进行了恰好K<=100次的跳跃，一共有多少种不同的跳跃方式可以让三只兔子最后跳到三个窝里，顺序可以不对应。所有坐标都是long long范围。

刚看到这个题，感觉豪无头绪，不知道如何去刻画兔子的跳跃，感觉不同的状态应该有很多，于是就无从下手了。事实证明还是要多多的思考和观察，对于某个特定的三只兔子的位置，其中间的那只兔子肯定可以向左向右跳，这样的跳跃会使得离的最远的两只兔子之间的距离增加；然后两头的两只兔子，只有离中间那只较近的兔子可以向中间跳（如果两个一样近的话就无法跳了），这样的跳跃使得离的最远的两只兔子之间的距离减少了。下面就要发挥yy的功力了，我们把无法向中间跳的格局看成是一个root，向左右跳分别看成是走向这个节点的左右childs，向中间跳看成是走向这个节点的parent，于是就形成了一个森林（很多棵树，其实是无数棵）的模型，其中每棵树有一个root，然后所有的节点都有两个childs，因此是棵无限延伸的树。

现在回到正题，题目给的初始位置格局和目标位置格局各对应了森林中的一个节点，如果这两个节点不在同一棵数上，那显然就无解了。否则我们就只要在一棵树上考虑问题即可，题目就是问在一个树上从一个点跳K次跳到另外一个节点的方案数。通过思考，我们发现可以用一个K^3的dp方法来搞定，dp[i][j][k]表示当前共跳了i次，深度为j，与目标位置的lca的深度为k的方案数，这里引入了lca，然后只考虑深度，有效的限制了状态数，并且因为最多跳100次，使的虽然节点的深度可以到long long的范围，但是实际变化的幅度不超过K，从而把状态限制在O(K)的级别里。

具体的各个细节的实现还是需要稍微推敲一下的，但并不是很难，在此也不赘述，还是想法最要紧。