0%

Codeforces-182

没想到坑的居然是 C 题 →_→

已填坑。

鼓起勇气用一次大号,结果……结果 unrated 真是喜闻乐见(不然我要跌回黄了)。

solution

A

这题特别坑。我就不说我 -6 了。

首先注意到,我们可以把任意两个元素一起取反,所以最后至多剩下一个负数。

\(n\) 是奇数的时候,如果还剩下一个负数,我们选择这个负数以及 \(n - 1\) 个正数,可以把负数的个数变为偶数,所以最后必定是每个元素都是正数,直接求绝对值的和就好了。

\(n\) 是偶数的时候,最后剩下的负数的绝对值是绝对值最小的数的绝对值,判掉就好。

B

由于 \(d\) 特别大,所以可以认为重复经过一个点是不可能的,直接跑最短路就好了。

明明 floyed 好写多了为啥还有人写 SPFA/dijkstra 呢。(模板党请自行无视这句话)

C

好牛叉的构造。

我们完成两个任务: 1. 在字符串末尾放上两个 ? 2. 利用这两个 ? 进行加法

第一个的构造:在最后放上一个命令 >>? 凭空在字符串开始出产生一个 ? 。然后在之前放入若干个 ?x>>x? x 从 0 枚举到 9,把这个 ? 不停从字符串开始传到字符串结束,最后再在一个合适的地方构造 ?>>?? 即可。

第二个的构造:我们以 ?? 为分界线,?? 前的部分表示未处理的, ?? 后的部分表示已处理的。构造若干个 x??<>y 其中 y = x + 1 ,表示一旦最后一个未处理的数不是 9 ,我们把这个数加上 1 后终止算法。接着特判 9 , 9??>>??0 9 + 1 = 10 进位需要继续处理。最后还需要一个特判:如果初始时的串全部都是 9 ,那么我们需要在前面补个 1 ,??<>1

D

想了好久的这个题,最后的结果是看错题了。

注意到 \(p\) 是一个排列,而满足 \(a \| b\)\((a, b)\) 的个数是 \(O(n \log n)\) 的,因此可以考虑对于询问统计有多少 \((a, b)\) 在这个询问里面。

\((a, b)\) 抽象成平面上的一点,则每个询问就是查询某个矩形内点的个数。很水了吧,离线乱搞就好。

E

很显然是 dp 。

首先我们要解决一个子问题: \(1, 2, \dots, n\) 内每个数的出现次数依次为 \(a_1,a_2,\dots,a_n\) ,求这些数构成的不同的 good sequence 的数目。由于前不久的中南校赛中出现过一道类似的题,我直接说结论了(我觉得解释起来很绕 →_→)

\[\prod_{i = 2}^{n} {a_i - 1 \choose \sum_{j=1}^i (-1)^{i - j} a_j}\]

于是 dp 中需要记录当前的最大值(强制令最小值为 1)、当前的总个数、当前的方案数、 \(\sum_{j = 1}^i (-1)^{i - j} a_j\) ,转移就是枚举当前这个数出现次数,复杂度算起来是 \(O(n^5)\) 的,但是由于常数特别小,递归式的 dp 可以过 →_→

一开始组合数的上界设小了囧了好久。

situation

CF 真心太脆弱了。

看了 A 觉得不是一眼题就有点虚。YY 了个结论发现是错的,继续 YY 发现还是错的,接着 YY 仍然还是错的我快受不了。最后 -6 强过 pretest 。

收到了 unrated 的信息就不想做了 →_→

others

目测一堆人和我一样看到 unrated 就不做了 →_→