北航第十届程序设计竞赛现场决赛题解

A.jsy与他的物理实验

f[i][j]表示做了i次实验得到j分的概率。 初始f[0][8] = 1.0

成功做了第i个实验:

f[i][j] += f[i - 1][j - k[i]] * p[i] / 100.0 ($8 \leq j - k[i] < 35$)

未做成第i个实验 :

f[i][j] = f[i - 1][j] * (100 - p[i]) / 100.0 ($8 \leq j < 35$)

最后算出期望后除以所有大于等于35分的概率和即为在能修够35分的情况下还需做实验次数的期望。 如果所有实验得分和加起来再加8仍小于35分则输出-1

B.flappy bird

我们只需算出到达每个管道所需耗费的最小体力。 我们可以知道bird的飞行路线一定是这样的一条折线(见下图)：

（1）：起点是(0,0);

（2）：转折点是管道活动空间的端点,即(Xi, Li) 或 (Xi, Hi);

（3）：最后沿着水平方向飞行;

关于(1)：显然；

关于(3)：”最后”就是说方向不会再变，这时候水平飞行最省体力，飞的最远；

关于(2)：我们假设若固定图中的A点和C点，这时候寻找一条从A到C的最短路径，想象用橡皮筋代替bird的飞行路线(这样的路线一定最短)，橡皮筋的拐点一定是管道的边界。

以上三点确定之后，算法就显而易见了。

为了方便处理，我们将所有管道的端点自左向右，自下向上编号，并求出到达编号为i的点的最小花费。

我们令dp[i]表示到达编号为i的点所需耗费的最小体力, 则 dp[i] = min{ dp[j] + dist(i, j) | 0 <= j < i && (i, j)可以无阻碍连线}

剩下就是判断( i, j )是否可以无阻碍相连。 对于给定的点i，我们从i点向右扫描，扫描过程中我们用L[i]和R[i]记录一个斜率区间，斜率在这个区间内的直线都可以无阻碍与i相连。对于当前扫描到的点j，我们求出i和j 的斜率k，若k在Li，Ri之间，则（i，j）可以直接相连。并用k更新Li，Ri。一直扫描到尽头为止。这样与i直连的点就扫出来了。

C.Kinfu的奥秘

我们知道三维空间中任何一个立方体都可以由一个顶点及往三个方向的向量所唯一决定。如题目中给的初始的立方体就是由(0,0,0)点作为原点以及v1:(L,0,0), v2:(0,L,0)和v3:(0,0,L)这三个方向的向量决定的。

那么对于旋转后的立方体，我们可以知道他的原点是p0，三个方向向量分别是v1’:p1-p0, v2’:p2-p0和v3’:p4-p0。

我们将旋转后的立方体原点平移回(0,0,0)，就可以发现对于原来立方体内的任何一个点(a,b,c)=(0,0,0)+a*v1+b*v2+c*v3，旋转后变化的只有原点坐标和三个向量，其相对位置并没有改变。所以旋转后的坐标为(a’,b’,c’)=p0+a*v1’+b*v2’+c*v3’，也就是要求的答案。

如果换一种方法思考也可以得到同样的结论：我们可以用一个3x3的矩阵来表述旋转操作，再加一列可以表示平移操作。所以我们可以构造一个4x4的矩阵M，其中最后一行为[0,0,0,1]，来表述平移+旋转的操作，其中有12个未知参数。如果获得了这个矩阵问题就解决了。

而对于每一个点我们有M*[pi|1]=[pi’|1]([x|1]表示对x向量增广一个参数1)这样8个等式，共可以列出24个方程，通过高斯消元就可以得到所要求的矩阵。而之前的解法就与用4个点列出12个方程节解出的结论一致。

其实题目输入只要给4个点的坐标就足以解决了。

D.这样还真是令人高兴啊

询问的排列一共就只有n种样子，所以可以一次预处理出这n种排列的逆序对数。

先任意用一种方法求出最初的排列的逆序对，每循环右移一位都是将最后一个数字移动至最前面。

由逆序对的定义，可以很容易计算它对答案的贡献。

E.已经没有什么好怕的了

把Pyotr的坐标按照模d的值分类。

这样就能转化成一个直观的贪心问题。

F.奇迹和魔法都是存在的

一旦确定了棱柱的起始位置，代价就能计算出来。

假设起始位置是x，代价就是|a_0-x|+|a_i-x-1|+...+|a_n-x-n|

可以看出只需考虑x等于某个a_i-i的情况，枚举后找最小的代价即可。

当然更好的方法是看出x等于{a_i-i}的中位数时最优。

G.这种事情我绝对不允许

此题的算法主要是二次函数的积分，有以下点需要注意：

• 曲线是抛物线还是直线
• 曲线在x轴上方还是下方，还是相交
• 曲线在分段处是否连续
• 抛物线的开口方向
• 二次函数的判别式和求根公式
• 抛物线的对称轴、零点坐标与区间的位置关系

此题数据规模不大，只要处理好各个细节就能过。

还有一种做法，直接暴力模拟积分，需要在精度和时间之间做出权衡。

H.再也不会依赖任何人了

由费马小定理$a^{60} ≡ 1\ mod\ 61 $ 得 $a^{64} ≡ a^4\ mod\ 61。$

意义即为一个数平方六次和平方两次的值的相等的。一个数字不断平方后的循环节长度仅为4。

用线段树维护这个序列，每个节点里面记录这段区间内部数的和、平方和、4次方和……32次方和，再维护一个下传的标记。

理解清楚标记下传对6个区间和的影响就很简单了。

时间复杂度为$O(n\log{n})$，隐含常数6，常数为61的话是过不了的……

这道题被吐槽如果数字是71啊91啊反而更容易往正解方向去想。

I.Microsoft 每周日麻训练

首先说明一下，这个题目的数据生成的方法是——随机一个麻将的排列，我二分找出能Ron的最小用牌数M，然后数据的牌数是M+rand()%6，所以放的还是非常宽。

这个题目就是非常裸的一个模拟+搜索题目。首先把手上的牌和牌堆里面的牌放在一起，找出一组Ron的解，然后模拟打牌就好。唯一要注意的是Ron时摸的那张牌必须要在最后的牌型中。

找解：

首先特殊判断国士无双和七对子（需要特判有4个一样的情况，这个是一个Trick）.剩下的就是贪心，对于字牌1c~7c 只可能有两种情况 当将或者当一个刻字（三张一样的）。那么我们首先贪心，把刻子和能找出来的将都找出来。剩下来的就是搜索，策略为——按照1m~7m 1s~7s 1p~7p 的顺序，判断是否用此牌形成刻子、将或顺子。因为一共就27种牌，并且只需要找出来4个刻子、顺子+1个将，那么搜索树就会非常小。

输出：

找到一组解之后，每摸一张牌就看手上的牌和胡牌的距离，打出来多余的牌即可。