CSU-ACM Home Page

2019暑假集训选拔赛第二场题解

Update Time: 2019-06-02 22:58:16     Recent Editor: Scanf     Create Time: 2019-06-02 22:34:15     Creator: Scanf    


A -csuoj2334 正解是Bfs+剪枝。好像不剪枝直接Bfs爆搜也能过??? Bfs: 直接枚举每个方向的速度bfs搜索下去即可。 剪枝:在状态拓展过程中可以去掉一些重复无用的搜索。走一条线的时候,如果出现了前方有一个位子(x,y,z),使得从起点走到这个点的时间小于等于当前点时间的话,无需继续向那个方向继续走了。因为那个方向的取优方案可以通过点(x,y,z)来更新,所以多余步骤可以删除。同时如果搜索到终点的话也可直接退出。

Ac代码链接: https://paste.ubuntu.com/p/wg98JYpvnp/

B -csuoj2336 由于只考虑出现次数的奇偶,所以可以处理出一个26位的二进制数来表示每个字符串,表示每个字母出现次数的奇偶。然后问题就转为求有多少个子集的异或值为0。很容易想到枚举每个子集,但子集数会有2^n个,直接枚举在这题里是过不了的。 这里需要将字符串分为两部分,再分别枚举这两部分的子集的xor值,用个map记录每个xor值的出现次数,这样时间复杂度就降为了 log n * 2^(n/2) 了。

Ac 代码链接:https://paste.ubuntu.com/p/2RYh3Jk5QQ/

C

只有当n=1,单个数字为0或1或2时才为NO 首先当n=1的时候,若数字大于等于三,我们可以利用阶乘操作使得数字变大,然后通过开根号和上下取整操作得到一个首尾为4的数字,把这个大数不断除10得到4,最后4的阶乘就是24。 n>=3的时候很容易利用加法得到大于等于3的数字 n=2 两个数字分别为0 0的时候,先得到1 1,以(1/10/10/10)为底的1的对数就是3

D

签到题

E

记录一下当前出现过的最多的数字pre和出现的次数sum,然后读入下一个数x,首先判断sum是否为0,若sum==0,则sum=1,pre=x,跳过循环。

然后若x==pre,则++sum,否则--sum。

F

参考链接:

https://www.cnblogs.com/Dragon-Light/p/6744132.html?tdsourcetag=s_pcqq_aiomsg