AC. 梦想

frank_c1

Codeforces Round #367 (Div. 2)

发布于2016年08月12日 | 暂无评论 | 1,112阅读 | 比赛经历

凌晨的CF,一如既往的酸爽。

由于这是Div. 2,打Div. 1 Unofficial不划算,不如小号。

一看是蓝名出题,顿时觉得可做许多。当然也不能掉以轻心。

于是开场看题。A模拟 B排序 C DP D经典题,看起来前四题正常人都能在读完题后就明白怎么做了,看起来又是手速场。于是花了40min切了ABCD,都1A资瓷~ 到Standings一看居然rank 9不容易啊。

于是开黑小队里开始讨论E怎么做。开始我提出个链表做法结果有定位的debuff。后来发现十字链表就资瓷了耶。但我好累啊不想写,先吃堆饼干压压惊。结果就是E差了5min 调不完惨啊。

开测啦。基本上没偏差,Hillan爷的C怎么了QAQ。AwD AK啦好强。

早上起来发现Hillan和AwD都紫了,我的小号也紫了(两把上紫成就Get)。

嗯以后就是Div. 1开黑了吗…… 时代的速度真快啊。

A. Beru-taxi

给定平面上若干点(x_i,y_i),第i个点会以速度v_i运动。

已知所有点均朝向点(a,b)运动,求最先到达(a,b)的点花费的时间。

1 \le n \le 1000, 1 \le v_i \le 100, -100 \le a,b,x_i,y_i \le 100

按照题意模拟。

时间复杂度O(n)

B. Interesting drink

给定长度为n的数组xq个询问。

i个询问m_i要求数组x中有多少元素不大于m_i

1 \le n,q \le 10 ^ 5, 1 \le x_i \le 10 ^ 5, 1 \le m_i \le 10 ^ 9

x排序。

可以把询问离线排序按单调性做,也可以直接STL。

时间复杂度O(n \log n)

C. Hard problem

给定n个字符串s_i

将第i个字符串反转所需花费是c_i

求使得这s_i个字符串字典序单调不降的最小花费。如果不可能,输出-1

2 \le n \le 10 ^ 5, 0 \le c_i \le 10 ^ 9, \sum {|s_i|} \le 10 ^ 5

f(i,0)是第i个字符串不取反最小花费,f(i,1)是第i个字符串取反最小花费。

于是随便转移一下即可。时间复杂度O(n)

D. Vasiliy's Multiset

维护一个可重非负整数集S,支持以下操作:

1. + \; xx加入S

2. - \; xxS中删掉一个。

3. ? \; x 询问x \; xor \; y的最大值,其中y是可重集中的元素。

1 \le q \le 2 \cdot 10 ^ 5 ,1 \le x_i \le 10 ^ 9

这种经典题目怎么出到正式Round来的……

建一棵Trie做一做。

时间复杂度O(q \log \max(x_i))

E. Working routine

给定n \times m的矩阵vq次操作。

每次操作将两个大小相同的子矩阵互换位置。保证子矩阵之间没有重叠,没有共边。

你需要输出经过q次操作后的矩阵。

1 \le n,m \le 1000, 1 \le q \le 10000, 1 \le v_{i,j} \le 10 ^ 9

我们发现只需要输出所有操作后的矩阵,必然不是什么在线数据结构。

考虑交换位置,我们发现链表可以快速支持这个操作。

但是如果我们对某一行或某一列建链表,定位的复杂度就是O(nm)的,无法接受。

可以把链表建成十字的,定位就是O(n)的,就可以做了。

时间复杂度O(nq)