0%

Codeforces-176

总感觉很忙没时间,却刷了无数次水。

禁了人人 ,发现逛 NOIP 吧的时间快赶得上人人了。

echo 0.0.0.0 tieba.baidu.com \| sudo tee -a /etc/hosts && sudo systemctl restart network

最近看了看 Lisp ,感觉 Haskell 和 Lisp 是两个极端, Haskell 专业高科技三十年, Lisp 则是让码农自己配置一门语言。Haskell 专注于算法,Lisp 则专注于代码的编写。

好了不说了,说说这次 CF 吧。

结果嘛,自然很不理想。只做了 A、C 两个题,结果 C 还 FST 了囧,最后中号(以后就按照 rating 标记为大中小号好了)居然都跌了,sigh……

solution

A

这个水题也不水的啊……

可以知道, p^2 只包含长度为 1 和 2 的循环,而且长度为 1 的循环至多只有一个,所以 p 只包含长度为 1 和 4 的循环,且长度为 1 的循环至多只有 1 个。于是无解的充要条件是 n = 2/3 (mod 4)

然后我们把若干个长度为 2 的循环合并起来就好了。

B

居然没做出来,囧。

如果提前把序列旋转一次(就是把第一个放在最后去啦),那么有改动的位置是 O(n / i) 的,数组就好了。开个两倍的数组好了。

C

手速慢啊。FST 啊。

主要思想就是尽量晚地退栈。每次遇到一个必须配对的,我们就看看栈顶,如果栈顶为我们等待的元素,那就 OK 了,否则弹出栈顶,递归配对栈顶。

然后某个地方忘记 break 导致死循环了,囧。

D

一开始看错题了囧。

其实这个题蛮好玩的。

我们建立一个平面直角坐标系,x 坐标表示时间,y 坐标表示人物的 y 坐标。那么所谓“墙壁”可以看为一个向右无限延伸的条形,人物的运动轨迹就是直线 y = x - T ,T 表示人物开始运动的时间,答案就是直线在所有条形内的线段在 y 轴上的投影长度和。我们把二维平面直角坐标系变换一下: (x, y) -> (x - y, y) ,则人物的运动轨迹 x = T ,条形变成了一个无限延伸的梯形。我们可以求出所有梯形的并的形状,再水平剖分后成若干个梯形。这若干个梯形对答案的贡献是独立的,每个梯形对答案的贡献可以很方便的求出来。

如何球梯形并?按 t 排序后暴力,用并查集保证复杂度就好了。

E

感觉就是暴力 FFT 的题……

f(x) = \sum c_i x^i ,其中 c_i 表示 i 是否出现过。考虑 f^2(x) = \sum d_i x^i 。若 i <= m && c_i == 0 && d_i != 0 则显然无解,因为 i 能被若干个包表示出来,所以 i 必定是一个包;若 i <= m && c_i != 0 && d_i == 0 ,则 i 会出现在答案中,因为此时的 i 不能用其他的数的和表示。

situtaion

听说下午有 CF ,真是喜闻乐见。CF 的正常时间是晚上十一点半的啊。

大叔、秋锅被拉到招生办去了,于是就只有我一个人在做。

看了 A 发现第一眼居然没想法?这不科学!不过乱 YY 一下还是可以 YY 出来。10min 才过居然还是 room 中第一个……

然后看 B 。看完题目的第一想法是调和级数的前缀和是 O(n log n) 的,然后用 splay 暴力维护序列。

……用 splay 维护序列的题可以放在 B ?

……用 splay 维护序列的题有人可以 8min A ?

……用 splay 维护序列的题有 50+ 人 A ?

……只想到用 splay 维护序列的人就滚粗了。

总是感觉各种不科学不可做啊。感觉再在这个题上耗就要挂了,于是决定看 C 吧。

看了 C 后感觉只要 lazy 弹栈就好了。于是怒写。由于写的 dfs ,导致各种判无解退出 = =||

最后在 D 和 B 纠结。稍微看了看 D 的题目,一开始看错了,以为是一道裸数据结构题,写完了才发现囧。

那就只好做 B 了。一直拖拖到考试结束还是没做出来……

E 连题目都没看,要是看了题目的话或许能想到 FFT 的。

最后结果 C 还是少判了个无解退出,结果就死循环了,光荣 FST 。于是就只过了 A 。#190 怒 -64 。

others

怎么看都比我好是不。

看 standing 发现各种 FST 啊,我觉得这么坑爹的题本来数据就要加强点嘛,怎么忍心还让别人 FST 呢,出题人的良心啊。

7k+ 没跳 B 这个坑,于是过了 CE , D FST 了。 #9

peter50216 FST 了 DE 题。不过前三题过得快也不错的。#10

liouzhou_101 #36 略略跌了点。

lyd 和 shy 开黑我就不吐槽了。总之对于他俩开黑我已经习惯了。 lyd #32 shy#40

过了前三题的人都不错,ryz #48 。

楼教主也来了!FST 了 CDE 真是太残忍了。RAD 也 FST 了 CDE 囧。

发现一堆人 FST C 啊,RAD、a142857a、chnlich、cherudim、wuzhengkai、ACRush 。

WJMZBMR 退出了 IGM ,ACRush 最近的 TC、CF 表现都不佳。难道要让位给—— wjmsbmr 了吗?

nonsense

我该怎样吐槽这两个人?

我会说 fotile96 是镇海神 dyh ?

我会说 roosaphu 是 XLk? 你这是闹哪样啊……我一开始居然还没反应过来 = =||

最后献上一张图,不忍直视。