Codeforces Round 367 Div. 2
点击打开链接
A. Beru-taxi (1s, 256MB)
题目大意:在平面上 \(n\) 个点 \((x_i,y_i)\) 上有出租车,每辆出租车的行驶速度为 \(v_i\),求所有出租车到点 \((a,b)\) 的时间中的最短时间。
数据范围:\(-100 \leq a,b,x_i,y_i \leq 100\),\(v_i \leq 100\),\(n \leq 1000\)
简要题解:依次求出所有的时间,取最小值即可。
时空复杂度:\(O(n) + O(n)\)
关键字:模拟
B. Interesting drink (2s, 256MB)
题目大意:有 \(n\) 个不同的酒吧,第 \(i\) 个酒吧一瓶酒售 \(x_i\) 元。现在已知接下来的 \(q\) 天,每天会有 \(m_i\) 元用来买酒。求分别每天有多少酒吧可供选择买一瓶酒。
数据范围:\(n,x_i,q, \leq 10^5\),\(m_i \leq 10^9\)
简要题解:先将 \(x_i\) 排序,对于每天的钱 \(m_i\),二分出在数组 \(x_i\) 中有多少个数小于等于 \(m_i\) 即可。
时空复杂度:\(O(nlogn) + O(n)\)
关键字:二分查找
C. Hard problem (1s, 256MB)
题目大意:有 \(n\) 个字符串 \(s_i\),将第 \(i\) 个字符串翻转将会花费 \(c_i\) 的代价。求若仅进行翻转操作,不进行交换操作,而使这 \(n\) 个字符串非降序排列所需要花费的最小代价。若无法满足要求,输出 \(-1\)。
数据范围:\(n,\sum |s_i| \leq 10^5\),\(0 \leq c_i \leq 10^9\)
简要题解:令 \(f_{i,0}\) 表示考虑前 \(i\) 个字符串且第 \(i\) 个字符串不翻转的最小代价,\(f_{i,1}\) 则表示第 \(i\) 个字符串翻转的最小代价。那么,易知其可以由状态 \(f_{i-1,0}\) 和状态 \(f_{i-1,1}\) 转移过来。
时空复杂度:\(O(n) + O(n)\)
关键字:动态规划,dp
D. Vasiliy's Multiset (4s, 256MB)
题目大意:有一个初始仅含 \(0\) 的可重集合 \(A\) 和 \(q\) 个操作,操作有如下几类:
+ x
向集合 \(A\) 中加入元素 \(x\)- x
将集合 \(A\) 中元素 \(x\) 的数量减一,保证操作前至少有一个 \(x\)? x
询问 \(max_{y \in A} (x \oplus y)\),其中 \(\oplus\) 为异或运算
要求对每次询问给出答案。
数据范围:\(q \leq 2 \times 10^5\),\(1 \leq x \leq 10^9\)
简要题解:将集合 \(A\) 中的每个元素 \(x\) 以二进制的形式从高位向低位插入一棵二进制树(类似于字母树,仅含代表 \(0\) 和 \(1\) 的边)。询问时直接贪心地沿着树边走即可。
时空复杂度:\(O(32q) + O(32q)\)
关键字:字母树,贪心
E. Working routine (2.5s, 256MB)
题目大意:给定一个 \(n \times m\) 的矩阵 \(V_{n \times m}\),对该矩阵进行 \(q\) 次操作。每次操作会将矩阵中两个大小形状相同的子矩阵交换位置(即对应元素互换)。保证每次操作对应的两个子矩阵不重叠且不共边,但允许共角。要求输出经过 \(q\) 次操作后的矩阵。
数据范围:\(n,m \leq 1000\),\(q \leq 10000\),\(v_{i,j} \leq 10^9\)
简要题解:将矩阵 \(V_{n \times m}\) 用二维链表的形式存储起来,即每个元素有四个指针分别指向其上下左右的四个元素。那么,每次操作则仅要将子矩阵边界元素的指针修改即可。
时空复杂度:\(O(q(n+m)) + O(nm)\)
关键字:二维链表,模拟