武汉大学新生寒假集训测试---Day1题解

题目为codeforces原题,戳下面的蓝色文字就能跳转到

A – Vova and Train

把l到r区间内的灯笼数目减去,就是最终能看到的数量。
在统计灯笼数目的时候,有点像前缀和的思想。先看1~l-1有多少个灯笼,再看1~r有多少个,相减即为l~r的灯笼数目。

B – Heaters

分情况讨论第一个加热器放在哪,[1,r]的任意位置都可以。
确定好了第一个的位置,当前情况的最优策略是:每次尽可能找最远的满足情况的下一个加热器,在两个半径长度之内即可。
每次把所有的加热器放完之后,先检验能不能把所有的位置都覆盖,如果可以则更新答案。

C – Many Equal Substrings

构造最小串的方法:
1.找出原串的一个最大前缀,满足该前缀为原串的后缀。
如:acbac,可以得到ac是原串的一个前缀,也是原串的后缀,同时满足长度最大。
对于串acacac,acac是原串的一个前缀,也是原串的后缀,同时满足长度最大。
然后将原串减去该前缀,例如acbac,把bac重复k-1遍即可。
注意特殊情况:1.原串无符合上述内容 2.原串为单个字母

D – Creating the Contest

原序列递增,因此一定满足我们选择的最长串是连续的。
证明:假如a < b < c,且a * 2 >= c,则一定有a * 2 >= b,b * 2 >= c。
所以只要检查a[i]是否<=2*a[i-1],如果是,则它一定和前一个字符在一个串里。

E – Maximal Intersection

思路1:尝试删去每一个区间,然后看剩下的区间相交出的最大长度,更新
问题是会TLE:一共有n个区间,每次取交集需要n-1次操作,复杂度是O(n^2)。
思路2:我们只需要看删去这个区间,是否会对原来的最小区间造成影响。
所以每次更新区间的时候,我们维护四个值:区间左端点的最大值和次大值,区间右端点的最小值和次小值。
然后枚举尝试删去每一个区间。
如果当前区间占去了左端点最大值/右端点最小值,那么我们把它删掉之后,原区间的端点就变成了左端点次小值/右端点次小值。这个时候再得出长度,更新答案。

F – Books Queries

(为啥看到有人在用树状数组和线段树)(挠头)
因为n不大,所以干脆开了一个很大的数组来模拟双向链表,从中间开始存
因为元素不重复所以搞个数组(代码里的nowp)记录一下元素的位置,和当前队列的头尾比较一下距离,更新答案就可以了

点赞

发表评论

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