Educational Codeforces Round 10(#652)

雪舞喵建站以后的第一发代码=。=

英文题面戳[这里]喵~

A题:Gabriel and Caterpillar

大概意思就是9年级学生某某一天放学看到了一只h1位置的毛虫要向上爬够到h2位置的苹果(1<=h1<h2<=100000)。在第0天的14点毛虫在h1位置,之后的每个小时如果是白天(10:00-22:00)他将向上爬a长度,如果是夜晚(22:00-10:00)他将下降b长度1(1<=a, b<=100000),问第几天毛虫能够到苹果,高度可以为负。

输入第一行为h1和h2, 第二行是a和b,输出第几天,如果无解输出-1。


好的那么我们只需要让他的初始状态在第0天的22点然后直接模拟就好了,我写的是如果超过500000天或者掉到-1e9高度以下就无解,事实上只要在0天22点判断a<=b则输出无解就可以了。

时间复杂度O(n), 空间复杂度O(1)。事实上也可以直接计算把时间复杂度压到O(1)。

代码部分:

B题:z-sort

给定一个序列A,要求把序列A排成非严格的'z'型,就是对于i为偶数 A[i]>=A[i-1],对于i为大于1的奇数A[i]<=A[i-1]

输入序列中的元素数n(1<=n<=1000)和序列A(1<=A[i]<=1e9)。要求输出排序结果,如果无解输出“Impossible”不含引号。


事实上是不可能无解的=。=只要把它排序然后分两半 前半段顺序(或者随机序如果你愿意的话)放在奇数位置,后半段放在偶数位置就可以啦。

时间复杂度O(排序),空间复杂度O(n)

代码部分:

C题:Foe Pairs

(CDE三道题蒟蒻没做出来,参考了一下官方题解[英文版传送门]因此有的并没有代码。)

题意是给定一个n长度的排列P(保证为1-n的一个排列)和m个数对(a[i],b[i])(保证a[i]!=b[i]但不保证不会重复给出),这些数对是“互斥的”。要求输出满足条件的闭区间[i,j]的个数。

条件是序列中第i个到第j个位置的数里不能有互斥的两个数。

输入第一行是n和m(1<=n, m<=3e5)

接下来的一行是排列P(1<=P[i]<=n)

接下来的m行是互斥的数对a[i], b[i](1<=a[i], b[i]<=n, a[i]!=b[i])

输出一个数表示满足条件的区间个数。


首先O(n)预处理出每个数在排列中的位置pos[i],接下来读入这些数对的同时维护Z[i]表示和i位置的数互斥并且在i右边的最左边的数的位置(=。=)

接下来只需要在O(n)倒着扫一遍数组维护临时变量t表示以i为区间左端点合法的最右端点的位置,很容易得出t=min(t, Z[i]-1)

然后对于每个元素 ans += t-i+1就可以啦

时间复杂度O(n+m)空间复杂度O(n)

[更新1.0.1]附上参考题解后的代码:

[更新1.0.2]D题:Nested Segments

(此题时间2秒)现在坐标轴上有n条线段,保证所有的线段端点都不相同,输出每条线段包含的线段条数。

输入第一行线段个数n(1<=n<=2e5)

接下来的n行分别是每条线段的起点和终点l[i]和r[i](-1e9<=l[i]<r[i]<=1e9)

按输入顺序输出n行每行一个数代表每条线段包含的线段个数。


 

我们只需要从右向左扫描坐标轴,同时维护一棵线段树(或是其他的什么能区间查询的东西),包含的元素是一直到当前处理的线段为止的所有右端点。每扫描到一个左端点,就区间查询一下他覆盖的右端点(因为按从右向左的顺序保证之前处理的线段左端点一定在他右边),保存答案并把它的右端点插入线段树就可以啦~

时间复杂度O(nlogn) 空间复杂度O(n)

E题:Pursuit For Artifacts

(此题时间3秒)题目大意:有个人现在在一个n个点m条边无自环无重边的无向连通图上。有些边上有宝藏。这个人现在在点a他不能重复的经过任何一条边,想要拿到宝藏并到达点B,请你告诉他可不可以。

输入第一行为n和m(1<=n<=3e5, 0<=m<=3e5)

接下来的m行分别是各边的起点,终点和是否有宝藏(1是有0是没有)。

输出一行,如果可以为"YES"不可以为"NO"不含引号。


首先我们双连通缩点(这个双连通分量比较特殊,他属于边-双连通,所以只需深搜两遍即可)。他变成了一棵树。然后我们可以暴力的找到a到b的路径,如果经过有宝藏的边或者有宝藏的双连通分量则输出YES否则输出NO。

时间复杂度O(n+m),空间复杂度O(n+m)
F题:Ants on a Circle

(此题时间2秒)现在有n只蚂蚁在一个m长度的环上(环上的点按逆时针编号为1到m),每只蚂蚁一开始在s[i]位置(保证位置不重叠)并面向L(顺时针)或R(逆时针)。接下来 所有蚂蚁以1的速度匀速运动,如果某蚂蚁和任何蚂蚁碰撞他们将同时立刻掉头。求t时刻后所有蚂蚁的位置。

输入第一行为n(2<=n<=3e5), m(2<=m<=1e9), t(0<=t<=1e18)。

接下来的n行分别为s[i]和方向L或R。

输出一行,按输入顺序输出每只蚂蚁的位置。


由于是老人家蓝书的第一题所以很快的想到了算法。然而由于细节问题到比赛最后也没过去,看数据之后才调过的。

和蓝书第一题一样,我们站在远处看这些蚂蚁,当他们碰撞时,相当于“对穿而过”,因此我们可以通过物理学公式O(n)的计算出所有蚂蚁的结束位置。接下来,我们注意到蚂蚁的相对位置是并不会改变的,因此我们只需要顺序的把蚂蚁安排到位置即可。

但是有个小问题,这把是个环了不是直线了,因此第一只蚂蚁就不知道是哪一个了。我的做法就是在点1和点n之间放一个隐形的门,每当有蚂蚁顺时针(从n到1)穿过这个门就把计数器-1,反之则+1。最后按计数器结果安排第一个蚂蚁,然后按顺序安排其他的就可以啦~

这样的话只要在计算最终位置的时候把位置结果除以m就能得到计数器的变化值了。然而此处有个小细节,计算计数器偏移值是如果是逆时针(即位置是增加的)就要先-1在/m,要是逆时针并且最终位置(未取模结果)小于等于0则需要除完n在-1。(看看题解部分第一句“细节问题”就是他……)

由于穿过n次和一次都没穿过是等价的,所以计算计数器的时候可以%n。

时间复杂度O(排序),空间复杂度O(n)

代码部分:

 

 

发表评论