赛时 AC 2道题,掉大分(哭)
A. Casimir's String Solitaire
\(Problem\)
给你一个仅含 A,B,C 的字符串,每次可以删掉一个 A 和一个 B,或一个 B 和一个 C,位置、顺序不限,问能不能删完。
\(t\le 1000,len\le 50\)
\(Solution\)
大水题,只需要判断 A 的数量加 C 的数量是否等于 B 的数量。一开始脑抽还判断 A 的数量是否等于 C 的数量
B. Shifting Sort
\(Problem\)
定义对一段区间的 Cyclically Shift
(以下简称Shift
) 操作为:
- 指定一个数 \(x(x\le len)\) 为操作的周期。
- 每次将区间左移一位,移出去的那一位放到最右边,重复 \(x\) 次。
给你一个数列 \(a\),问如何用不超过 \(n\) 次 Shift
操作将 \(a\) 排好序(不要求使用次数最少,只要不超过 \(n\) 就行)。
\(1\le t \le 1000,2\le n\le 50\)
\(Solution\)
注意只要求不超过 \(n\) 次,也就意味着我们只需要每一次把一个数排好序就行了。我们可以每次挑选最大的数,通过一次 Shift
操作(\(x=1\))将它移到最右边的位置,如果已经在该在的位置就不操作,每次都能将一个数归位,重复 \(n\) 次即可。
eg.
原序列
2 5 1 4 3
将5归位
2 1 4 3 5
将4归位
2 1 3 4 5
将2归位
1 2 3 4 5
由于 \(n\) 很小,暴力找最大值就可以。
C. Ticks
\(Problem\)
给你一个 \(n\times m\) 的网格图,每个格子有 *
和 .
两种状态,*
表示填,.
表示不填,问能不能通过若干个大小超过 \(k\) 的“V字形”表示出这个图形(V 的两条边必须一样长,机房的两位大佬就是没判断这个而 FST 了)。
“V字形”大小的定义:
*...*
.*.*.
..*..
的大小为 \(2\)。
\(1\le k\le n\le 10,1\le m\le 19\)
\(Solution\)
注意到 \(n\) 和 \(m\) 的范围很小,完全可以通过暴力求解。对于每一个格子,尽可能多的往上延伸,如果超过 \(k\) 就把覆盖格子的标记一下,最后判断是否都被覆盖完。
D. Productive Meeting
\(Problem\)
在一场见面会中有 \(n\) 个人,会议开始后他们会两两交谈,每个人有一定的耐心值 \(a_i\),第 \(i\) 个人在交谈 \(a_i\) 次后会离开会议,两个人可以交谈多次,请找出一种方案使得总交谈次数尽可能多。
\(1\le t\le 1000,\sum n\le 2\times 10^5,\sum a_i\le 2\times 10^5\)
\(Solution\)
由于 \(\sum a_i\) 不大,我们可以依次考虑每一次交谈,容易想到每次让耐心值最大的两个人交谈是最优方案。
实现 1
先排好序,每次让剩余耐心值最大的两个人交谈,耐心值--,在考虑维护序列单调性,可以通过一通 lower_bound
和 upper_bound
以及 swap
来实现,时间复杂度 \(O((\sum a_i)\log(n))\)。
实现 2
使用 lower_bound
和 upper_bound
来维护需要考虑一大堆细节(我调错调了一下午加一晚上),不如用堆来维护。每次从堆里拿出两个耐心值最大的人,耐心值--,如果还有剩余耐心值,就把他们再扔回堆里,用 STL 的优先队列实现非常简洁,时间复杂度也是 \(O((\sum a_i)\log(n))\)。
E1. Permutation Minimization by Deque
在 Codeforces 中首次被 hack 祭。
\(Problem\)
给你一个 \(1-n\) 的排列,你需要把它们按顺序扔进双端队列里,你可以决定从哪一端扔。需要使得最终双端队列里的数的字典序最小。
\(1\le t\le 1000,\sum n\le 2\times 10^5\)
\(Solution\ 1\)
由于要让字典序最小,肯定最小的值放在最前面,最小值之前的数的放法先不管,放完最小值之前的数之后在把最小值放在最前面,最小值后面的数就只能从后面挨个放了。而最小值之前的数我们可以递归处理。
具体实现中我们需要用 ST 表维护区间最小值,再用分治递归的方法实现。
\(Solution\ 2\)
从通过人数上看,这道题的简单程度可是仅次于 A 题,怎么会这么复杂呢?
考虑用贪心的思想,先扔进去第一个数,以后对于每一个数,如果它比队首小,就扔到队首(这样可以让结果的字典序尽可能小),否则就扔到队尾(如果还扔到队首字典序就大了)。就是这么简单。
E2. Array Optimization by Deque
\(Problem\)
给你一个长度为 \(n\) 的数列(注意不是排列),你需要把它们按顺序扔进双端队列里,你可以决定从哪一端扔。需要使得最终双端队列里的逆序对尽可能少。
\(1\le t\le 1000,\sum n\le 2\times 10^5,-10^9\le a_i\le 10^9\)
\(Solution\)
同样是贪心,对于每个数,如果放在队首,则贡献的逆序对数为前面比它小的数的个数,反之则为比它大的数的个数,这个数放在队首还是队尾对以后的方法不会产生干扰,所以只需要判断它前面是比它大的多还是比它小的多,这可以用树状数组或权值线段树维护。由于 \(a_i\) 的值跨度过大,需要先进行离散化处理。
标签:10,le,744,传送门,sum,Solution,Div,CFR,Problem From: https://www.cnblogs.com/cxm1024/p/17168420.html