EDU-CFR-53(Div.2)解题报告

cxm1024 · 2021-10-14 15:50:48 · 个人记录

更好的阅读体验

A. Diverse Substring

Problem

定义一个字符串为多变的，当且仅当字符串中没有一个字符的出现次数严格大于 n/2。给定一个只由小写字母构成的字符串，问是否能找出一个多变的字串，如果能，任意输出一个。

Solution

只有两个不同字符的字符串时多变的，所以只要给定的字符串中包含至少两个字符就一定可以，输出相邻两个不同字符即可。

B. Vasya and Books

Problem

有一摞书，从上到下依次编号为 a_1,a_2,a_3...，现在 Vasya 想把它们分 n 次挪到别的地方，每次他会告诉你他想挪的书的编号，如果这本书还没有被挪动，他将会把这本书以上的书（包括这本书）一块搬走。对于每次挪动，回答他搬了多少本书（没搬输出 0）。

Solution

开一个桶记录每一本书的位置，记录当前搬到那个位置了，每搬一次就更新一下，减一下即可。

C. Vasya and Robot

Problem

有一个机器人，初始在 (0,0) 点，给你一个长度为 n 的操作序列，每次让机器人向上、下、左、右中的一个方向走一步，你需要修改连续的一段操作序列（这一段中的操作不必全部都修改），使它最终走到 (x,y) 点，问修改的操作序列的最短长度。（不是很严谨，序列长度的详细定义见原题面）

Solution

如果修改一个长度为 len 的序列可以使它走到终点，那么一定存在一种长度为 len+1 的方案也能走到终点（大不了就加一个空修改），于是我们发现这是可以二分的。二分最终修改的长度 len，对于一个长度，我们需要 O(n) 判断是否可行，怎么判断呢？对于每一段长度为 len 的修改，判断不考虑这段修改后机器人会走到哪个位置，再从这个位置开始，判断随便走 len 步能否走到终点（反正允许修改这一段，那想怎么改就怎么改）。

实现上，我们维护一个走的位置的前缀和和后缀和，就可以 O(1) 判断去除这段修改后机器人会走到那个位置，然后再考虑一些细节问题即可。

D. Berland Fair

Problem

有一个人前来买东西。Polycarp 带了 T 元钱，去逛商铺。有 n 家商铺顺时针排成一圈，编号 1-n，第 i 个商铺卖一种价格为 a_i 的商品（数量有无限个）。Polycarp 从一号商铺开始，只要钱足够，就买一件商品，否则跳过这家店，直到他一个商品也买不了为止，问他一共会买多少件商品。

Solution

先算出来买一圈要花多少钱，让他买尽可能多的圈。为什么他买不了下一圈了呢？一定是到某一个商铺是他买不起了。现在买不起，以后也不可能买的起，于是直接把这个商铺删掉，不考虑。于是我们暴力跑一圈，看看是哪些商铺买不起，把它们都删掉，删完后再让他转圈，知道所有的商品全都被删完为止。由于每一次至少删掉一个商品，最多删 n 次，每次 O(n)，总时间复杂度为 O(n^2)。（别问我为什么能过 2\times 10^5，我也不知道）（经过同学推导，复杂度为 O(n\log(n))）