Educational Codeforces Round 112 (Rated for Div. 2) 题解(A-E)

A. PizzaForces

注意到\(6 : 15 = 8 : 20 = 10 : 25 = \frac{1}{2.5}\),然后题目翻译一下就是在\(6x + 8y + 10z \ge n\)的情况下最小化\(15x + 20y + 25z\),然后其实就有\(15x + 20y + 25z \ge 2.5n\)\(n\)为偶数时答案就是\(2.5n\),否则就为\(2.5(n + 1)\)

(n为奇数时的结论是猜的,关键我还不会证

B. Two Tables

分类讨论一下,先看是否能不移动,再看是否能只向上下左右4个方向移动,若还不行就只能是移动到4个角落了。

可以不移动当且仅当第一个矩形的边界距离上边或下边不低于\(w\),或者距离左边或右边不低于\(h\)

可以只向上下左右移动当且仅当可以通过向上下左右移动满足前一种情况。

然后模拟一下就可以了。

C. Coin Rows

将先手经过的格子打上标记1,仅有后手经过的格子打上标记2。那么可以得到

1111222
2221111

可以看出,后手可能拿到的分数只有第1行的某个后缀或者第2行的某个前缀。假设先手在第\(i\)行向下走,则后手有两种得分方案,后手肯定选二者中的较大值。

然后先手可以选择在那一列向下走,肯定是选择后手的分最小的。

\(O(n)\)预处理出前缀和再枚举一下完事。

D. Say No to Palindromes

首先,没有长度大于等于2的回文串等价于\(s_i \ne s_{i-1}\)\(s_i \ne s_{i - 2}\),又因为字符集大小只有3,所以满足条件的串只能是abc的某个排列的不断重复。

然后排列的数量只有6个,对于某一个串,将其变为好串的代价,就是将其变为某个排列的不断重复的代价,枚举一下那个排列再取最小值就是最小代价了,然后就可以\(O(n)\)判断。

然后题目要回答多个询问,可以对每个排列再搞个代价前缀和,然后这个是满足可减性的,所以在经过\(O(n)\)预处理之后就可以\(O(1)\)回答询问。

E. Boring Segments

先将线段按权值排序,依次记为\(s_1, s_2, \dots, s_n\),然后双指针求最小代价。

现在问题来了,怎么判断\(s[l; r]\)可以满足条件呢?

错误做法

搞个线段树,\(cnt_i\)表示第\(i\)个点被多少个线段覆盖,如果\([1, m]\)的最小值大于零就说明满足条件。这样需要区间加操作和区间最小值查询,经典操作了。

这样搞会有一个问题,有一种情况没有考虑到:\([x, y]\)\([y + 1, z]\)两个线段,\(x\)并不能跳到\(z\)但是这个做法检测不出来。

正确做法

搞个线段树,\(cnt_i\)表示区间\([i, i + 1)\)被多少个线段覆盖,这样就可以避免上述问题了,其他操作不变。

F. Good Graph

就过了70个人,算了算了

闲话

快乐周六

虽然没出去吃但是和室友叫了丰盛的外卖,舒服

然后好像又发生了震撼我三观的事?

Educational Codeforces Round 112 (Rated for Div. 2) 题解(A-E)

上一篇:【在更】做一个损失函数专题


下一篇:安装使用vur-router