籟·来·也

比赛前差点忘了今天有比赛，比赛开始又迟到了几分钟- -状态不好不坏，最后+8分。上一场Member比较难，而这次的还算正常，不过这次的题目的分数都比较低250 450 900，然后450的dp并不是十分好想，900的数学也难想清楚，而且还有超时的危险，还是太弱了。

PS，rng_58出题出上瘾了。。。

1. 250P BouncingBalls

x轴上有N <= 12个点，每个点等概率向正反方向以单位速度移动，所有碰撞都是完全弹性碰撞，即球相撞后各自沿反方向移动，速度大小不变。现在给定时间T，问T秒内发生了几次碰撞。

考虑到N比较小，我们可以用2^N枚举所有球的方向。确定每个球的方向以后，首先，最naive的做法，直接模拟，当然会写死的，不过也不是不能写。然后，我们可以发现，两个球发生完全弹性碰撞各自弹开，其实可以看成是两个球穿过彼此继续前进。这样一来就省却了碰撞的模拟，把每个点都看成是一直匀速直线运动，只要算T秒内有多少次相互穿越即可。这个转化很巧妙，我因为当初被ZOJ 2376虐过，因此印象深刻，这次一看完题就直接搞了，最后244分多，想起来自己好就没上240了。

最后，这题还有更加方便的做法，不用枚举方向。考虑任意两个球，他们有1/4的概率相向运动（否则肯定不会互相穿过）。所以，当两个点之间的距离小于等于2T的话，就有1/4的概率相撞。因此，答案就是距离小于等于2T的点对数除以4，这样写就很快了。

2. 450P NewCoins

需要定义一套新的货币，其面额从小到大分别为x₁, x₂, x₃ … x_i …。面额必须符合两个特性：

1. x₁ = 1
2. 对于所有的i < j，x_j是x_i的倍数

现在有N<=50件商品要买，每个商品的价值为小于等于10W的正整数。要求设计一套符合上面性质的货币，来买这N件商品，其中每种面额的货币都无限多，而购买的钱一定要刚好等于物品的价格。问最优的情况下，最少用多少张货币可以搞定。

首先，这是一个挺不错的dp题。首先价值最多只有10W，所以设计的面额最大也只要10W就可以了。然后考虑，如果给定这样的一套货币，去买一个东西，怎么求最少使用的货币张数。很自然就想到背包，因为货币的种类不会很多，所以单纯做一次背包的话复杂度也可以接受，但是如果要做很多次的话，复杂度就不行了。其实可以有O(钱币种类)的做法：贪心的用，能用大面额的就用大面额的。这个就要考虑这套钱币币值的特殊性了，因为如果能用大面额的不用，后面用的小面额里面，一定有某些小面额的值的和等于这个大面额，那么还不如直接用一张大面额。

OK，下一步，怎么来确定用什么面额。虽然我看完题就觉得可能是个dp题，但是10W这个不大不小尴尬的数让我有想暴力搜索的冲动。偏偏那时候nc了，dp想不清楚，总觉得要两维的才行，于是就试了一下dfs暴搜各种面额方法，不出意料TLE，加了最优化剪枝，继续TLE，于是放弃（最后发现，再加些剪枝还是可以过的，比如有个重要的素数剪枝我就没想到），回去仔细考虑dp的解法。

上面提到了，我们是用贪心的方法来买东西的，而且大面额的货币一定是小面额的货币的整数倍。那么我们可以用dp[i]表示上一次用了面额为i的货币的时候，剩下的价格最少要用几张货币搞定。因为上一次用了i，所以假设N个东西原价为a₁, a₂, … a_N，那么现在都变成了a₁%i, a₂%i, … a_N%i。然后就枚举这次用的货币j，j一定是i的约数。因为贪心，所以每个商品尽量用j来买。于是dp[i] = min(dp[j] + j使用的张数) for j | i。这个复杂度还是稍微有点大的，大概是10W以内数的约数个数总和*50（当然这里的约数个数其实可以优化成素数约数个数，可以快些）。有了dp后，最后枚举下最大的面额就可以得到最优解了。

3. 900P ModuloFourDivisor

数学题，题意还是比较好懂：如果存在某个正整数N，考虑其所有约数%4的结果，其中=0的有a个，=1的有b个，=2的有c个，=3的有d个，那么我们称四元组(a, b, c, d)是一个XXX。现在给四个非负整数向量A, B, C, D，其元素都不重复，大小小于等于50，问一共有多少个四元组(a, b, c, d)是XXX，且a in A, b in B, c in C, and d in D

因为50^4 = 6.25M不算很大，因此可以直接枚举，问题转化为判断一个四元组(a, b, c, d)是否为XXX。当然最后我发现这个转化并不保险，我的第一次提交居然超时了。于是要么优化判断的方法，要么试着yy下把这里的50^4优化成50^3，这个还没yy过，我把判断的方法加速了下就OK了。再说句话我觉得这里卡时间好像挺无聊的……

于是进入正题，首先，任何数都有1为约数，于是b等于0的肯定不行。然后，我们来考虑奇数的N，对于这样的N，很显然a=0且c=0。把N分解质因数：N = a₁^p₁ * a₂^p₂ * … * a_k ^ p_k，其中a₁, … a_k都是奇数。这些奇数可以分两类，一种是%4=1的，另外一种是%4=3的。我们发现：

1 * 1 = 1 (mod 4)
1 * 3 = 3 (mod 4)
3 * 3 = 1 (mod 4)

是不是有点象异或操作呢？1就是0，3就是1，*就是异或操作。当然这个没啥用。N的每个一个约束M，可以写成M = a₁^q₁ * a₂^q₂ * … * a_k ^ q_k，其中0 <= q_i <= p_i。M一定是%4=1或者%4=3，这个是怎么决定的呢？根据上面的表，我们发现%4=1的那些素数因子是打酱油的，完全是用%4=3的素数因子的个数决定的，个数为偶数则M%4=1，个数为基数则M%4=3。好的，于是我们又可以暂时把%4=1的那些素数抛开。不妨设a₁.. a_t为%4=3的数，而a_t+1…a_k为%4=1的数。取不同的q₁…q_t一共有(p₁+1)*(p₂+1)*…*(p_t+1)种。可以证明，如果所有的p_i+1都是奇数，那么这些取法中，一共取了偶数个数的次数比一共取了奇数个数的次数多1；否则如果有某个p_j+1为奇数，则一共取了偶数个数的次数=一共取了奇数个数的次数。换句话说，如果某个N的所有素因子都为%4=3的，那么一定有b = d或者b = d + 1。然后在考虑存在%4=1的素数因子的时候，我前面说过了，这些数是打酱油的，于是每加入一个a_j，只是单纯的把b和d各自乘以了(p_j+1)，于是，最后我们有，b = d或者存在k | b，使得b/k = d/k + 1（即b = d + k）。

上面解决了N为奇数的情况，然后考虑N为偶数，但是N/2为奇数的情况。这个时候多了一个素因子2，而2的次数只能取0或者1。显然，去0的时候，就是上面的结果，而取1的时候，我们发现(任意奇数乘以2)%4=2，因此，b和d的条件同上，而另外有a = 0，c = b + d。

最后考虑N中2的次数大于等于2的时候，这是2可以取0, 1, 2 … n，取0和1的时候就是上面的情况，而取2以及2以上的时候，结果一定是%4=0，于是：b、c和d的条件同上，而a为c的整数倍。这个其实可以和上面的可以合并起来，a % c = 0。至此问题解决。

4. challenge

450用大case盲cha了两个dfs的，失败一个成功一个，+=25，本来要是不cha的话估计要跌rating的……

最后，庄立变蓝BG~