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 树处理询问即可……

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

代码在这里