2015年计算机学院程序设计大赛结果及题解

我出的有4道题,其他4道题的题解:hate13

院赛结果


 

镜像翻转

可以在纸上推出n=1,2,3的答案,分别为3,8,15,就可以看出规律, \(ans=(n+1)^2-1\) ,或者其他的变形

其实题目中第二种跳跃操作的无论颜色是迷惑人的,最短路线就是异色才能跳,因为越过同色之后会出现需要退后的情况,反而浪费了步数。

如果限制只能越过异色的,那么就只有一种走法。那就是先形成红蓝相间的情况,之后就很好走了。

本来之前是准备出小数据让你们能BFS过的,但是自己写了一发,发现n=7的时候都要跑1S(也有可能是我的姿势不对),所以直接改成找规律了。然后强行模了一发QQ号~

 

标程:

 

 


 

 

字符矩阵

这道题就是考察字符串相关的知识,在我印象中字典树应该是个很基础的东西了。本来预计算法题最有可能被AC的就是这道题,但是结果出乎意料- -

方法很容易想到,就是直接枚举每一个起点,然后开始DFS,只是DFS的时候不能暴力比对每一个字符串,那样对于每一层循环时间都是字符串个数*字符串长度,这样肯定会超时。

之后就会想到一个可以用字典树来优化,DFS向下传递字典树的结点地址,这样就不会重复比对。

而且要注意每次找到一个字符串之后要从字典树里删去,不然也会超时。

 

标程:

 


 

 

数组变换

这道题其实不是我想出来的,是队友说的。

解法就是线段树。

其中的难点在于区间异或,我们可以把每一个数转换为二进制,根据数据范围拆成31颗线段树,那么求和就转换成了求区间内1的个数,再对应转换为10进制。而异或就变成了1与0的个数交换或者不变。

加法操作是随便加的,没有难度。

注意写代码的姿势,姿势不好也是会超时的,比如用结构体,比如不用位运算,都是会超时的。

 

标程:

 


 

 

模板题

这道题没什么难度,就是拼模板。。。

通过运用简单的排列组合知识可以推出公式 \(ans=(K^L\times C_{L}^{M}\times (K-1)^M / 2) \ mod \ N\)

因为K或者K-1必有一个为偶数,所以不用求逆元

难点就在于 \(C_{L}^{M} \ mod \ N\)

因为N不一定为素数,就可以把它分解为 \(N=\prod _{i=1}^{k} p_{i}^{t_i},(k=1,2,3...)\) 的形式, \(p_i\) 为素数

可以求出所有的 \(C_{L}^{M} \ mod \ p_{i}^{t_i}\) ,再用中国剩余定理合并

至于求 \(C_{L}^{M} \ mod \ p_{i}^{t_i}\) ,可以直接用lucas的模板解出

 

标程:

 

Categories: ACM