Intel Code Chanllenge Elimination Round
A题在自己知道坑的情况下还是挂了，D题在最后五分钟想出思路，又一次懵逼，没有时间敲完。。。
*A Broken Clock
题意是给出表的12计时方式与24计时方式，12计时方式时钟在1
12的范围内，分钟在059的范围内。24计时方式时钟在023的范围内，分钟在059的范围内。问改动最少的数字，使得给出的时间符合要求。
注意12计时方式下的20：00这种情况，不是变成01：00而是10：00。。。。
B Verse Pattern
算每一个字符串数组中的元音字符数量是否与给定的数相等。。。
C Destroying Array
给定一个数组，每次删掉一个数字，问每次删掉之后剩下的连续数字的最大和。
反过来考虑就是添加数字，每次添加用并查集来合并左右数字，维护最大值。
*D Generating Sets
题意是有不同的$n$个数，可以任意选一个数$x$，有两种操作，1.$x*2$之后放回去。2.$x*2+1$之后放回去。经过若干次这样的变换之后，变成了给出的数组，要求就是找回最开始的n个数，使得这n个数里面最大的数最小。
实际上是一颗二叉树，每一次选最大的数除以2，看可不可以占这个位子，不能的话再往上找，直到找不到向上的路径了。
别人都是set就过了，我非得搞个优先队列+map。。。mdzz。
*E Research Rover
有$n*m$的格子，一开始站在$(1,1)$的点上，有$S$的油量，现在有一些点会让油量减半，问最终到达(n,m)这个格子所剩油的期望。化简之后分数表示成$\frac {P}{Q}$，给出$P*Q^{-1}$的结果，其中$Q^{-1}$代表$Q$模$10^9+7$的逆元。
首先结果的分数是不用考虑化简的，因为假设$P$和$Q$都有公约数$d$，那么
$$
P_{d}*d*Q_{d}^{-1}*d^{-1}=P*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)*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})*inv[Mod %i]%Mod
$$
F Cyclic Cipher
题意是给出了$n$个序列，每个序列$k_i(1 \leq k_i \leq 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*x=p_j+k_j*y
$$
$$
\Rightarrow p_i-p_j\ = k_j*y-k_i*x
$$
$$
\Rightarrow p_i-p_j\equiv 0 (mod\ GCD(k_i,k_j))
$$
因为在连续序列里面的任意两个都要满足这样的关系，所以枚举右端点，更新左端点即可。