【Codeforces652】Educational Codeforces Round 10

打的第一场CF比赛。。虽说这次不算rank。。

前几个题都是水题来的。。不过因为十点半就要回寝只做出了A、B两个大水题。。

A. Gabriel and Caterpillar

模拟就行了。。

就是题意容易理解错= =

B. z-sort

这道题比T1还傻逼(T1理解错了写一个小时也是WA的)

排个序把大的放偶数位小的放奇数位就完了

C. Foe Pairs

并不难,然而比赛时没想出来

一对Foe Pair会让某个区间不能被穿越

那么枚举起点,终点单调后移即可

D. Nested Segments

一开始也没想出来。。回寝室后恍然大悟

问cab说是主席树。。然而树状数组就可以做了(当然主席树也可以写(那天上午我还写了233))

一条线段i包含另一条线段j的条件是:\(l_i<=l_j, r_j<=r_i\)

当然这道题保证了没有右端点重复

那么可以将l和r视为两个关键字,题目即为第一关键字大于它而第二关键字小于它的有多少个

按第二关键字排序,按第二关键字顺序将第一关键字加入树状数组,即可查询。

当然第一关键字要先离散化

E. Pursuit For Artifacts

首先Tarjan求一遍桥。。如果起点和终点都在桥的一侧那么把这条边丢掉,肯定不能走。

然后DFS/BFS过去看看有没有artifacts(神器?)就可以了

不写代码了

F. Ants on a Circle

不会做

刚才正好向总走进来教育我们要用非完美算法

那么这题模拟的话。。

可能会骗个10分哦?

说点什么

您将是第一位评论人!

提醒
wpDiscuz