Educational Codeforces Round 71 (Rated for Div. 2) 题解

Posted on In

(5-1)/7 Penalty: 224 Rank: 1243/1082

小号被 hack 人生大落大起大落还能上蓝我是真的佛了。

A. There Are Two Types Of Burgers

题目描述

做一个汉堡需要两片面包和一片牛肉，做一个鸡肉汉堡需要两片面包和一块鸡肉。现在有 片面包， 片牛肉和 片鸡肉。做一个汉堡挣 元，做一个鸡肉汉堡挣 元。求最大总利润。

数据范围：。

题解

数据范围很小，直接暴力都行……

时间复杂度 ，空间复杂度

如果 范围大的话，根据每个汉堡的价格贪心即可。

但是一分钟手速掉这道题发现网太慢了交不上去……

代码在这里

B. Square Filling

（反正这里是熊猫头，下面是脏话）

题目描述

一个 的矩阵，初始全是 ，每次可以选择一个 的范围将它们全部填充为 ，求是否能填充成给定的 矩阵，若能则输出填充最少步数的方案，否则输出 。

题解

直接枚举每个 区域填充即可，最后判断一下是不是和给定矩阵一样。

注意只能填充 范围内全部是 的范围。

然后手贱把 打成 了之后被 hack 了。

（反正这里是熊猫头，下面是脏话）

时间复杂度 ，空间复杂度 。

代码在这里

C. Gas Pipeline

题目描述

给了一条街道和一个 串，如果串的某一位为 则表示这一段是路口，管道高度必须为 ，否则高度为 或 均可。一个单位长度管道价格为 ，一单位支管道的柱子价格为 ，求建管道的最小花费。

数据范围：。

题解

队友贪心过去了，实际上和 DP 打的是一样的……

记 表示第 段路高度为 的花费。

对于高度没有要求的路段，转移如下：

对于高度有要求的路段，转移如下：

初值为：

答案就是 了。

时间复杂度 ，空间复杂度 。

代码在这里

D. Number Of Permutations

题目描述

有 个二元组 ，一个坏排列定义为这 单调不减或 单调不减，求好排列数量对 取模。

数据范围：。

题解

好排列数量等于 减去坏排列数量。统计一下坏排列数量个数就行了。

坏排列数量直接容斥一下，就是 单调不减的排列数量加 单调不减的排列数量减去 均单调不减的排列数量。

单调不减的排列数量只需要统计 中元素相同的个数，然后乘一下全排列就行了， 和 同理，但是注意 统计后需要再检查一下这个序列是不是真的单调不减（排完序之后会出现第二维减的情况），如果不是则这部分贡献为 。

然后输出答案就行了……

时间复杂度 ，空间复杂度 。

代码在这里

E. XOR Guessing

题目大意

可以询问 或 个数，要求猜一个给定的数。Grader 会返回询问的数中的某一个与要求猜的数的异或值。

数据范围：

题解

分二进制前 位为 和后 位为 ，分别查询 个数即可。

数据范围很良心，最大查询是 正好在 范围内……

代码在这里

F. Remainder Problem

题目描述

给定一个长度为 的序列，有 个操作，分为两类：

  • 给位置 的元素加 ；
  • 查询位置编号对 取模为 的所有元素值之和。

数据范围：。

题解

下面记 。

CF 又双叒叕出原题辣，在这里。

2014 年集训队论文里也写辣，详见《根号算法——不只是分块》。

我们想对直接统计不是那么优秀的合并统计，直接统计很快的暴力过去，于是我们统计所有 的答案，这样就合并了这些统计出来很慢的东西，然后对于大于 的部分，直接暴力，复杂度是 的。

对于修改，暴力过去就完事了……

时间复杂度 ，空间复杂度 。

和 Codeforces Beta Round #80 (Div. 1 Only) D. Time to Raid Cowavans 感觉上是一道题……

代码在这里

G. Indie Album

题目描述

给一棵 Trie 树，询问一个字符串在某条链上的出现次数。

数据范围：。

题解

又被熊大爷教育了……

「 在 中的出现次数转化为有多少个 的前缀以 作为后缀， 的前缀以 作为后缀当且仅当代表前者的点在代表 的点的子树中。」

这里子树指 Fail 树。

然后就是基本操作了……对询问离线，插到 AC 自动机里，跑一遍 dfs 序，再 dfs 一下 Fail 树处理询问即可……

时间复杂度 ，空间复杂度 。

代码在这里