Intel Code Chanllenge Elimination Round

题目链接与代码链接

A题在自己知道坑的情况下还是挂了，D题在最后五分钟想出思路，又一次懵逼，没有时间敲完。。。

*A Broken Clock

题意是给出表的12计时方式与24计时方式，12计时方式时钟在112的范围内，分钟在059的范围内。24计时方式时钟在023的范围内，分钟在059的范围内。问改动最少的数字，使得给出的时间符合要求。

注意12计时方式下的20：00这种情况，不是变成01：00而是10：00。。。。

B Verse Pattern

算每一个字符串数组中的元音字符数量是否与给定的数相等。。。

C Destroying Array

给定一个数组，每次删掉一个数字，问每次删掉之后剩下的连续数字的最大和。

反过来考虑就是添加数字，每次添加用并查集来合并左右数字，维护最大值。

*D Generating Sets

题意是有不同的$n$个数，可以任意选一个数$x$，有两种操作，1.$x\ast 2$之后放回去。2.$x\ast 2+1$之后放回去。经过若干次这样的变换之后，变成了给出的数组，要求就是找回最开始的n个数，使得这n个数里面最大的数最小。

实际上是一颗二叉树，每一次选最大的数除以2，看可不可以占这个位子，不能的话再往上找，直到找不到向上的路径了。

别人都是set就过了，我非得搞个优先队列+map。。。mdzz。

*E Research Rover

有$n\ast m$的格子，一开始站在$(1,1)$的点上，有$S$的油量，现在有一些点会让油量减半，问最终到达(n,m)这个格子所剩油的期望。化简之后分数表示成$\frac{P}{Q}$，给出$P\ast Q^{-1}$的结果，其中$Q^{-1}$代表$Q$模${10}^9+7$的逆元。

首先结果的分数是不用考虑化简的，因为假设$P$和$Q$都有公约数$d$，那么
$$P_d\ast d\ast Q_d^{-1}\ast d^{-1}=P\ast Q^{-1}$$
所以$Q$就是从$(1,1)$到$(n,m)$的方案数，$P$即是所有情况下到达的油量总和。

这道题还要发现一点就是$S$最大值是${10}^6$，也就是说如果经过了超过20个消耗点，那么就会一直是1了。所以只需要考虑小于等于20个消耗点的情况。

这样的话和51nod上大大走格子(这个也是codeforces上的。。。)思路就类似了。dp[i][v]表示第$v$个点到终点经过$i$个消耗点的方案数量。从后往前考虑，等于
$$dp[i][v]=C(n+m-x_v-y_v,n-x_v)-\sum _{j=v+1}^{k}C(x_j+y_j-x_v-y_v,x_j-x_v)\ast dp[i][j]-\sum _{j=0}^{i-1}dp[j][v]$$
解释一下上面的式子，$C(n+m-x_v-y_v,n-x_v)$是该点到终点的方案总数，减去前面的点经过$i$个点了乘以它到这里的方案数，这块和大大走格子的思路是一致的。这一部分等于它到终点经过$0$到$i$次的，减掉之前的，就是该点经过$i$个点的方案数。最后是(1,1)这个点的方案数乘以油量。

最后考虑经过的数量大于20的情况，$C(n+m-2,n-1)$减去之前算出来的方案数就是剩下的情况，乘以1，添到结果内。

最后这个题卡常，算逆元的话最好用递推式:
$$inv[i]=(Mod-\frac{Mod}{i})\ast inv[Mod$$

F Cyclic Cipher

题意是给出了$n$个序列，每个序列$k_i(1\le k_i\le 40)$个数，每次序列向右不断循环一位，取每个序列的第一个数再从上到下组成一个序列，算每一个数的最长连续序列，一共进行${10}^{100}$次，问在这些中，每个数的最长连续序列是多少。

会发现如果$x$在连续序列中碰到一起了，假设是在第$S$秒，在第$i$个序列中的位置为$p_i$，第$i$序列的长度为$k_i$，那么会满足下面的条件
$$S\equiv p_i(mod{k}_i)$$

$$S\equiv p_j(mod{k}_j)$$

发现这样的话就是中国剩余定理的内容，参考这个的评论，可以推出：
$$p_i+k_i\ast x=p_j+k_j\ast y$$

$$\Rightarrow p_i-p_j=k_j\ast y-k_i\ast x$$

$$\Rightarrow p_i-p_j\equiv 0(modGCD(k_i,k_j))$$

因为在连续序列里面的任意两个都要满足这样的关系，所以枚举右端点，更新左端点即可。