Google Kickstart 2017 Round F题解

Google Kickstart 2017 Round F,当时做了两条就睡觉了,早上把剩下两条也过了。感觉不算是很难,可能也和这场限时24h有关吧。不过提交的时候倒是手忙脚乱,第一条交了三发,第一发是从VS迁移到DevC上是DevC由于之前配了个C++14所以崩了,第二发输出里面是Unicode BOM,WA了,蛋疼。

A. Kicksort

找规律发现每次找的pivot的位置是从原数组的中心点(奇)或中心线靠左(偶)开始,如果小于原数组的中位数,则下一个位置是其轴对称,否则是其左边一个位置。这样从数组的中部交替往外移动,结束条件是pivot到达原数组的最后一个元素。由于这个过程中所有选为的pivot都是最大/小值才返回YES,否则直接返回NO,所以只要迭代继续,我们去掉的就一直是最大/小值。因此使用l和r记录此时所有还没被作为pivot去掉的数中的最大/小值,判断新的pivot是否等于l或r。
AC代码

B. Dance Battle

由于Delay和Truce规则,我们实际上并不需要考虑舞者的顺序问题。我们将舞者的S值从小到大排序,从小端开始Dance,从大端开始Recruit。当在l位置处e不够的时候去Recruit是不亏的,因为虽然在大端位置r处损失了一点honor,但是大端增加的S[r]肯定至少能够干掉S[l]获得一点honor了,除非l = r,这时候应该直接Truce。
AC代码

C. Catch Them All

有个无向图,N点M边,第i条边要走$D_i$分钟,宠物小精灵以$1/(N-1)$的均匀几率出现在你不在的地方,直到你抓到后另一个小精灵才出现。求抓到P个小精灵的时间期望。
首先自然是floyd求一下最短路。然后是一个没有环的概率DP,可以正着迭代掉。

D. Eat Cake

Leetcode原题Perfect Squares
AC代码