【CodeChef】Starters 112 做题记录

发布时间 2023-12-14 01:04:14作者: syrreblum

A. Max Nutrition

开个 std::map 存储每个最大值即可,判断一下 \(\geq 0\)

sol

B. 3 Logicians Walk into a Bar

一共两种情况,要么全 1,要么从第一个 0 开始输出 NO。

sol

C. Cursed Indices

贪心,从开始往后填,用 std::multiset 找到第一个满足条件的数,否则随意填。

sol

D. Permutation Construction

首先按照打表的程序可以得到,如果 \(n\) 为偶数,那么必定有解,如果 \(n\) 为奇数且 \(x\)\(\frac{n+1}2\) 那么无解。

奇数构造规律比较好找,偶数的话可以考虑将奇偶性分开来做,这样差分数组中间的那一个数就可以随意填。

sol

E. Yet Another Array Game

先对数组 \(a\) 进行排序,然后对 \(S=0\)\(S=1\) 分开来讨论:

如果 \(S=0\),那么就是不允许不选,那么如果一共奇数个数,那么可以从第二个数开始取,否则就需要从第一个数开始取,模拟一下这个过程就可以发现是正确的。

如果 \(S=1\),那么允许不选,那么可以考虑一共取 \(len\) 个数,因为 B 一定取当前最大的数,所以只能让 A 取其中的一段连续的且和最大的序列,并且后面必须要空出 \(len-1\) 个位置。

sol