首页 > 其他分享 >CFR-744-Div-3解题报告

CFR-744-Div-3解题报告

时间:2023-03-01 16:00:10浏览次数:65  
标签:10 le 744 传送门 sum Solution Div CFR Problem

赛时 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) 操作为:

  1. 指定一个数 \(x(x\le len)\) 为操作的周期。
  2. 每次将区间左移一位,移出去的那一位放到最右边,重复 \(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_boundupper_bound 以及 swap 来实现,时间复杂度 \(O((\sum a_i)\log(n))\)。

实现 2

使用 lower_boundupper_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

相关文章

  • CFR-840-Div-2解题报告
    比赛传送门C.AnotherArrayProblem题意:给你一个数组\(a\),每次可以选两个位置\(i,j(i<j)\),将\([i,j]\)内的所有数替换为\(|a_i-a_j|\)。问最终数组的和最大为多少......
  • CFR-843-Div-2解题报告
    比赛传送门C.InterestingSequence题意:给你\(n,x\),求最小的\(m\gen\),使\(n\&(n+1)\&(n+2)\&\cdots\&m=x\),或判断无解。首先每一位独立,分别考虑。与运算每一位都......
  • CFR-850-Div-1解题报告
    比赛传送门A.Monsters(easyversion)题意:有\(n\)个怪物,每个有\(a_i\)滴血,每次可以选择一个怪物减一滴血,也可以“让所有怪物减一滴血,且如果杀死怪物则重复操作”。......
  • EDU-CFR-115-Div-2解题报告
    赛时AC3道,补题做出来一道A.ComputerGame\(Problem\)有一个\(2\timesn\)的01矩阵,1为障碍,你要从\((1,1)\)走到\((2,n)\),每一步只能向右、上、下、右上、右下走,问......
  • EDU-CFR-116-Div-2解题报告
    比赛传送门做出来五道题。A.ABBalance{%noteinfono-iconproblem%}给你一个只含有a和b的字符串,问怎样通过修改尽可能少的字符,使得ab的数量和ba的数量相......
  • EDU-CFR-138解题报告
    比赛传送门A.CowardlyRooks题意:有一个\(n\timesn\)的棋盘,有\(m\)个位置上有车,保证互不攻击。问是否能将一个车移动一次使得仍然互不攻击。稍加思考可得,如果\(......
  • EDU-CFR-143解题报告
    A.TwoTowers题意:有两个积木塔,由红色/蓝色积木组成,你每次可以将一个塔的塔顶放到另一个塔上,问任意次操作后能否使得两座塔都是红蓝相间。可以将一个塔全部转移到另一......
  • 【比赛记录】 Codeforces Round #706 Div.2
    Problems:#NameSubmitASplitit!BMaxandMexCDiamondMinerDLet'sGoHikingEGardenoftheSunFBFSTrees题解:A:Splitit!判......
  • Educational Codeforces Round 143 (Rated for Div
    EducationalCodeforcesRound143(RatedforDiv.2)Problem-BIdealPoint给定n个线段区间\([l,r]\),我们定义\(f(x)\)为覆盖点\(x\)的线段数,我们每次操作可以删......
  • Codeforces Round #254 (Div. 1) C - DZY Loves Colors 线段树|lazytag维护区间加
    开一个变量维护同一个区间内颜色是否相同,而且显然要用lazytag了递归到颜色相同的区间时就可以直接打标记然后对于标记,维护的就是常规区间加的部分(最开始没写lazy,wa6,没明......