3月28日 周赛题解

发布于 2021-03-28  39 次阅读


A简单博弈

这题应该是最难的。首先看上去像是一道字符串,又像是找规律,也像思维,但是其实是一道数论题。(没想到吧?)

简单思考后,可以发现条件即为A的数量在每一个位置都要比B多。那么这道题可以看成A是左括号,B是右括号,题目转换成有多少对括号匹配。根据上周的经验,可以知道卡特兰数能够解决这一问题。

\frac {C_{2n}^n}{n+1}=\frac{(2n)!}{n!(n+1)!}

然后使用唯一分解定理将阶乘分解,得到每一个质因数的幂次,最后使用快速幂还原得到答案。

B一步两步

一开始想到bfs,但是显然bfs会爆内存(一开始当256MB考虑的)然后考虑剪枝,此时看到了那个显目的10MB。于是考虑dp,而且没法开二维数组,所以使用一维滚动数组。

状态转移非常好考虑,每一个顶点都由三个点转移而来,注意初始状态和结束状态即可。

C点击就送

真有你的啊,SQUARE ENIX(走错片场了)被良心出题人骗了两发。看下数据范围,可以发现O{(n^2)}会爆时间。利用后缀和压掉一层循环即可。

D区间异或

好像是入学前的暑假迪龙丢了这题,然后我找了一晚上的规律orz异或的性质:a^a=0。然后根据分奇偶根据区间长度讨论即可。当时他还提了二进制做法,其实就是把每个数全拆成二进制从位的角度考虑,具体规律就不贴了。

E直线重合

不难想,也不难写,算是经验题吧。首先,y=kx+b。然后分斜率是否存在进行讨论。重要的是由于浮点误差的存在,我们不能用double存k和b,而是要把分子和分母分别存一个变量。为了去重的方便,我们存的时候需要对分子和分母进行化简,也就是通分。至于如何通分,思考我们通分是怎么做的。如何去重?排个序,然后怎么做都行。


夢に僕らで帆を張って 来るべき日のために夜を越え。