2016 Multi-University Training Contest 4 总结

这场来说是打的不错的,不过也有一点小小瑕疵,比如 1001 没有看到取模 WA 了一发。不过第一次在比赛的时候做出数论题也是挺开心的。
总之还是需要继续努力啊。

 

1001 Another Meaning

题意子串 B 可能有两种意思,问 A 这句话可能有几种意思。首先对 A 进行一遍 KMP 预处理一下匹配的信息,然后做一遍 DP 就好了。按含义替换和含义不替换两种状态转移,还是挺好理解的,还有注意答案要取模 T^T。

 

1005 Lucky7

第一次写容斥,第一次在比赛时候做出来的数论题,还是挺开心的。
题目大意是,在 [x,\ y] 之间,有多少数能被 7 整除,且模 p_i 不等于 a_i. 主要是先容斥,容斥的过程中用中国剩余定理算出数量,在做 CRT 的时候会爆 long long, 需要用按位相乘处理一下。

 

1010 The All-purpose Zero

很巧妙的智商题。意思是数列里的 0 可以替换成任何数。做法很巧妙,如果 a_1\ ~\ a_i 中有 z 个 0 的话,就把 a_i 当作 a_i\ -\ z 处理。遇到 0 不处理,最后把答案数加上总的 0 的个数即可。

 

1011 Where Amazing Happens

水题,写段程序处理一下题面即可,不过也挺有趣的。

 

1012 Bubble Sort

问在冒泡排序中,每个数可能出现的最左位置和最右位置之差。最多往右移动次数其实就是这个数在当前位置时右边有多少个比它小的个数,这个倒过来做一遍即可,用树状数组维护。接着再排序一遍,在初始位置,最右位置,排序后的位置中分别找出最左和最右,然后算出答案。

发表评论

电子邮件地址不会被公开。 必填项已用*标注