Test-TeX
纯粹试试 TeX 的。
不知道 github 支不支持 blahtex 诶。
传说中的行内公式 \(O(\sqrt{n} \log n \frac{n}{m})\) 。再来一个? \(O(n \sqrt{n})\) 。
传说中的行间公式: \[f(n) = \sum_{i = 1}^n i\]
纯粹试试 TeX 的。
不知道 github 支不支持 blahtex 诶。
传说中的行内公式 \(O(\sqrt{n} \log n \frac{n}{m})\) 。再来一个? \(O(n \sqrt{n})\) 。
传说中的行间公式: \[f(n) = \sum_{i = 1}^n i\]
XHR 问我关于动态 MST 的问题,于是找论文看到一个很神奇的 O(sqrt(m))
per update 的方法。把思路简单说一下吧。(你可以简单地把这篇文章看成是翻译 = =||)
原论文标题是 Data Structures for On-Line Updating of Minimum Spanning Trees, with Applications
,作者是 Greg N. Frederickson
。
保证每条边的权为正,这是显然的。
首先要构造一个图,使得和原图的 MST 相同,且保证每个点的度不超过 3 。
原图 G(V, E), \|V\| = n, \|E\| = m
,新图 G'(V', E'), \|V'\| = m, \|E'\| = m
,做法是将原图中的每个点拆成 D 个点(D 表示这个点的度),这 D 个点形成一个环,环上边的权为 0 ,原图的每一条边就可以对应新图一条边,而且任意两条原图的边不会占用同一个新图的点,可以保证每个点的度不超过 3 。
z:块的大小
块状树的构造:
def csearch(v) :
clust = set()
for u in child[v] :
clust = cluse \| csearch(u)
if len(clust) > z :
# find a new clust
return set()
return clust
E[i, j]
:表示所有连接第 i 个块和第 j 个块的边
minE[i, j]
:表示 E[i, j]
中权最小的边
delB(i)
:删除第 i 个块。复杂度 O(z)
。
addB(S)
:建立一个块,块内的元素集合为 S 。复杂度 O(z)
。
delE(x, y)
:删除树上连接 x 和 y 的边。如果这条边连接两个块,直接无视。否则先把两个点所在的块删除,然后和相邻的某个块合并,如果合并后的块大小超过某个值,再分裂。所有访问到的块为常数个,复杂度 O(z)
。
addE(x, y)
:添加一条连接 x 和 y 的边,然后试图合并两个块。复杂度 O(z)
。
由于度数限制,每个操作的复杂度均为 O(z)
。
我们用块状树维护 MST 。
有四种可能的操作:减小树边的权,增加非树边的权,减小非树边的权,增加树边的权。前两种总是可以忽略的。
对于第三种情况,直接查询最大的树边,有可能的话就把它替换掉。替换就是先删除一条边,再添加一条边。
对于第四种情况。我们先把这条树边删去,然后枚举所有的块对,如果可以覆盖这条边,那么用 minE[i, j]
来更新最优的非树边。最后再比较一次,如果可以更新 MST 就执行一次替换。
复杂度的事呢,第三种情况显然是 O(z)
的,第四种情况是 O(z + (m/z)^2)
的,于是 z = m^{2/3}
好了。
上述做法没有用到任何数据结构维护。一个显然的优化是用某种奇怪的数据结构来优化。
这里用到的数据结构是 Topology Tree 。Topology Tree 是一种动态树,他用一个奇怪的树形结构来维护原来的树,可以在 O(log m) 的时间内往原树加入、删除一条边。
考虑一棵任意点度数不超过 3 的树,我们可以 O(n)
构造它的 Topology Tree 。具体构造方式,自己参考论文吧,因为要用图来解释我就懒得搞了。
容易证明, Topology Tree 的高度是 O(log n)
的。Topology Tree 中任意一个节点的孩子数不超过 4 。
为啥这里需要 Topology Tree 呢?因为后面需要支持若干个操作: 1. 合并两棵树 2. 把一棵树分成两棵 3. 查询一棵树的最小权
构造一个新树叫做“块树”,也就是把原树一个块缩为一个点。可以得到块树的大小是 O(m / z)
的。
很囧的一点,块树的度数并没有保证。于是我们要找到一个合适的划分块的方式,使得满足: 1. 在 MST 中,任意一个块至多与三个块相邻。 2. 任意一个大小小于 z 的块必定与三个块相邻。
这种划分块的方式只要在 csearch
的基础上稍稍修改即可。每次函数再多返回一个值,表示与几个块相邻。一旦块的大小超过 z 或者度数等于 3 ,这就应该要被分成一个块。可以证明,这种方式可以满足要求。(证明懒得看了)
我们把这种划分的方式成为 度限制划分
(自己随口 YY 的名字)。
我们在度限制划分时会产生 O(m / z)
个小块,对于每个小块我们构造一棵 Topology Tree 。这棵 Topology Tree 的每个叶子表示一个划分出来的小块,顺便用一个堆按边权大小维护 E[i, j]
以及最小权的边;对于每个内节点,我们维护这棵子树内的最小权的边。很显然,所有的 O(m / z)
棵 Topology Tree 的形状是一模一样的,只是要维护的值不一样。空间复杂度易知为 O(m^2/z^2 + m)
。当 z > sqrt(m)
时,空间复杂度为 O(m)
。
再次考虑删除(添加)一个块需要做的操作。每次需要修改 O(m / z)
棵 Topology Tree 。每次修改需要修改最下层的叶子,然后依次更新内节点。由于 Topology Tree 的高度为 O(log (m / z))
,所以每次操作的复杂度为 O(m/z log (m/z))
。
考虑第三种情况。由于替换边的本质是重新维护块,而需要维护的块的个数是常数个,而且要构造常数个块的 Topology Tree ,所以复杂度是 O(m/z log (m/z) + z)
。
考虑第四种情况。这一步就可以通过维护的 Topology Tree 来加快速度。不妨设这条树边连接的是 x 和 y 。如果 x 和 y 在同一个块中,我们需要把这个块分裂成两个,这也可以通过改变常数个块来实现。在前一种算法中,我们要 O(m2/z2) 地枚举块对,现在我们只要枚举一个块,在这个块对应的 Topology Tree 中把 x-y 这条边删去,这样会产生两个 Topology Tree ,选择不包含这个块的 Topology Tree ,用维护的子树最小权的边即可更新答案。第一步的复杂度是 O(m/z log (m/z) + z)
,第二步的复杂度为 O(m/z log (m/z))
,总时间复杂度为 O(m/z log (m/z) + z)
。
均衡一下,令 z = sqrt(m log m)
可以得到整个算法 per update 的时间复杂度为 O(sqrt(m log n))
。真是太令人(理性)愉悦了~
在上一种做法中,我们建立了 O(m / z)
棵 Topology Tree ,而这若干棵树的形态完全一样。于是我们可以考虑建立一棵“二维 Topology Tree ”来继续优化。
然后啪啦啪啦优化就是 O(sqrt(m)) 了 = =|| (具体过程正在看……)
\(O(\sqrt{n})\)
总感觉很忙没时间,却刷了无数次水。
禁了人人 ,发现逛 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……
这个水题也不水的啊……
可以知道, p^2
只包含长度为 1 和 2 的循环,而且长度为 1 的循环至多只有一个,所以 p
只包含长度为 1 和 4 的循环,且长度为 1 的循环至多只有 1 个。于是无解的充要条件是 n = 2/3 (mod 4)
。
然后我们把若干个长度为 2 的循环合并起来就好了。
居然没做出来,囧。
如果提前把序列旋转一次(就是把第一个放在最后去啦),那么有改动的位置是 O(n / i)
的,数组就好了。开个两倍的数组好了。
手速慢啊。FST 啊。
主要思想就是尽量晚地退栈。每次遇到一个必须配对的,我们就看看栈顶,如果栈顶为我们等待的元素,那就 OK 了,否则弹出栈顶,递归配对栈顶。
然后某个地方忘记 break 导致死循环了,囧。
一开始看错题了囧。
其实这个题蛮好玩的。
我们建立一个平面直角坐标系,x 坐标表示时间,y 坐标表示人物的 y 坐标。那么所谓“墙壁”可以看为一个向右无限延伸的条形,人物的运动轨迹就是直线 y = x - T
,T 表示人物开始运动的时间,答案就是直线在所有条形内的线段在 y 轴上的投影长度和。我们把二维平面直角坐标系变换一下: (x, y) -> (x - y, y)
,则人物的运动轨迹 x = T
,条形变成了一个无限延伸的梯形。我们可以求出所有梯形的并的形状,再水平剖分后成若干个梯形。这若干个梯形对答案的贡献是独立的,每个梯形对答案的贡献可以很方便的求出来。
如何球梯形并?按 t 排序后暴力,用并查集保证复杂度就好了。
感觉就是暴力 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 不能用其他的数的和表示。
听说下午有 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 。
怎么看都比我好是不。
看 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 了吗?
我该怎样吐槽这两个人?
我会说 fotile96
是镇海神 dyh ?
我会说 roosaphu 是 XLk? 你这是闹哪样啊……我一开始居然还没反应过来 = =||
最后献上一张图,不忍直视。
结果还没出就开始写了……随便啦,免得成为坑。
A 有 1000 分诶,所以不是简单题了。这是个简单数据结构题,写个树状数组就好了。
我勒个去坑翻我了。
很容易可以知道,只要记忆化一下就好。于是我开了个 map 来搞。但是在递归的时候为了预防死递归,我还用了个 set 来保存当前的栈。于是若干次错误就在这个栈这里了……最后 +4 才过。
感觉是个水题啊。
首先如果没有变量的限制条件,那就是一个很暴力的 dp 了。无解的一种情况就是出现了环。假设不存在环,考虑消除这种限制条件。对于一组限制 x[c] > x[b]
,我们可以尝试令 y[c] = x[c] - x[b] - 1
,这样 y[c]
是没有限制条件的,同时,把 a[b]
加上 a[c]
。这样意味着每次取了一次 b 就要取一次 c ,而 y[c]
就是 c 比 b 多取的。
剩下的就是背包了。
这个题还蛮有意思的。
先考虑两个数可以相邻的条件。(x, y)
合法,当且仅当存在 t 使得 x = yt + y(y-1)/2
。所以当 y 为奇数时,只要 x = 0 mod y
即可。当 y 为偶数时,则条件为 x = y/2 mod y
。
接下来就是 dp 了。f[i]
表示前 i 个最多保留多少个,其中第 i 个必须保留。f[i] = max(f[j]) + 1
,j 的条件为 j 到 i 这一段能凑出一个序列。考虑 a[i - 1]
, 如果 a[i]
是奇数,自然一种很自然的想法就是前一个继续用 a[i]
,否则前一个用 a[i] / 2
。这样维护一个数就好了,是这次 CF 中最好写的题。
我居然没看这个题……看了后发现应该是可做的,但是我不一定写得出。
首先需要用到 WC 某费用流题《石头剪刀布》的一个结论:
ans = C(n, 3) - sum(C(w[i], 2))
其中 w[i]
表示 i 的入度(或者出度)。证明很巧妙的说。
然后考虑如何统计 w[i]
。原题是在一个 n * n 的格子上进行操作的,每次取反一个子矩形。差分一维,线段树维护即可。
首先做 A 。第一反应是维护一个和就好了,啥数据结构都不用。第二反应是要写个带标记的线段树,恶心啊。最后决定写树状数组吧。坑爹的 cout 输出精度,我一开始只输出了 6 位有效数字不幸 WA1 。换成 10 位就过了。
然后看 B 。我勒个去停电是什么状况啊!向总不是和门卫打了招呼了吗!坑爹啊亲!感觉这个题也蛮水的,写啊写提交发现 MLE 了……这明显是死递归的节奏啊,怒看代码发现了 WA 点。改了再交收获 WA 5 。又发现一个 WA 点再交,还是 WA 5 。还发现一个 WA 点终于过了 5 了——变成 WA 9 了……再找终于过了 pretest 了,泪流满面。只有 592 pts 了。
看 C 。一开始以为这是宇宙大水题,写了发现过不了样例,才发现看错题了 = = 重新看了遍题目发现仍然是水题,怒过。
看 D 觉得这题蛮适合我的口味的,偏数学,代码短。总之推了一下就发现可做了。
然后就没有然后了,连 E 的题目都没看。
最后发现 A 用时 11min C 用时 17min D 用时 13min B 用时 40 min ……最佳的做题顺序是 DCAB 啊亲,又被做题顺序坑了。
幸亏没有 FST 。#14 怒踩 Egor、CLJ 也不错了。下次如果 RP 还这么好就可以红了~
ST 之前 7k+ 夫妇怒占前二,然后 CLJ 怒 FST * 2 。
Seter 居然也在做?我很少看见他做啊。 #20 好牛叉。他首先做的 D ,犹豫了好久不敢交……他要是交了绝对虐我。
liouzhou_101 #22 和我一样被 B 坑了 50min
wuzhengkai #31 A 居然 FST 真是 xwlj 。
lyd 的 C 莫名其妙被 Skipped 了……于是 #35
然后我就很奇怪为啥 FredaShi 为啥每题都交的比 lyd 慢。
wyl8899、squarefk 都是前三题。wyl8899 的 D FST 了。
秋锅只过了两题。B 1A 分数比我还高= =
a142857a FST * 2 真是太令人桑感了。
最近 我/主席/xiaodao/Seter/7k+ 几个商量再出一场 CF ~
当然 idea 有限,时间也是个问题~
显然是贪心,每次取最大的一个元素,然后去能超过他的最小的两个就好了。
直接用 set 暴力搞。
我勒个去这都会想错……
首先一个很简单的结论就是:一定存在一组最优解,使得不会出现新的种类的高度。
有了这个结论就好做了。点的范围只有 50 ,于是直接 f[i][j]
表示第 i 个点的高度为 j ,且 0 号点能到达 i 号点时的最小修改代价。显然可以用最短路来做。构不构图随你,反正范围很小。
我居然很脑残的写了个 bellman-ford ……还是个错的 bellman-ford ……
为了填这个坑我容易么我。等 TC 的题解等了这么久,今天晚上终于出来了。
首先很明显,坐标轴需要转一下。然后目标点就被限制在一个矩形范围内了。现在我们要统计所有的初始点到达矩阵中某个点的方案数的和。 注意到每次移动对于 x 和 y 的改变是不相关的 ,也就是说 x 和 y 可以分开解决。知道了这一点一切都好做了。
由于可以分开解决,那么啥问题都没有了,不妨假设要求 x 吧。枚举最后的 x ,再枚举每个点,方案数可以由一个组合数表达出来,所以可以 O(1)
解决。总复杂度就是 O(nm)
。
居然没想到 x、y 分开解决,诶……
早上给小朋友发了题后开始刷水,在八点四十多发现今天的 TC 是早上九点而不是晚上,怒开小号注册。
似乎我在 room 排名蛮低的?桑心~
250 pts 似乎是水题,秒掉。
450 pts 不会做,乱猜了个结论,感觉是对的(的确是对的)。于是开始敲代码。不想构图了,于是 YY 了一个算法,用 dp 来做。结果一测发现连样例都没过 = =|| 然后想着这个算法没错啊,于是又加了一层循环怒过样例。后来一想这是哪门子的算法啊,错的妥妥的……
既然过了样例就没想了,看着第三题只有 850 pts 觉得可做于是就做了一下……发现这不是个数学题吗?蛮合我口味的。感觉是个组合数学题?也还可以。于是 YY 来 YY 去还是没想法……
看完 Analysis 后瞬间发现我脑残了,分开考虑就很简单了。
最后 450 pts 的当然 FST 。排名 #173 如果没有 FST 的话前 20 应该没问题……
由于是小号所以还是可以涨的。但是……这会不会对自已要求太松了点?
AC_Rush 时隔多年之后终于回来了!但是 #36 似乎有点不合人意啊……(不要给我)
我们 room 的 NaHS 前两题开的很慢,刚交完的时候是 room 的 #10+ 。但是不知怎么的慢慢慢慢就到了 #2 了,最后 #35 怒压教主。
cherudim9 #49 感觉 450 pts 的有 300+ 应该是不难的。
liouzhou_101 #95 主要是 450 pts 的交慢了吧。
UESTC_elfness 居然 FST 了 250 pts 的,出乎我想象。
ryz #165 ,250 的比我快……
huzecong 蛮好玩的,他的 250 是我们 room 交得最快的,后来他重交了一遍,就只有 75 pts 了。450 速度也还可以,然后又重交了一遍就只有 135 pts 了,最后 250 的 FST 了还 cha 错一个人囧……
另外求 @xiaodao 小号 ID ……
有人 -150 什么心态 = =||
第一次参加 CF 的出题,感觉蛮好的……
虽然我打了一圈酱油啊!啥都没做啊!
你还想要有多水?
普通青年:枚举分母。
文艺青年:连分数展开。
二逼青年: Fraction(x,y).limit_denominator(n)
普通青年:暴力半平面交
二逼青年:暴力推公式
文艺青年:跳掉不做
要我的话还是半平面交吧,虽然这样也要推一些公式 T_T
这个题是我从耀爷那里蒯来的,结果没想到成为最水的题了……
一个结论就是最大值/次大值对只有 O(n)
个,用单调队列处理出来就好了。
感谢大叔提供了几个好数据~
有谁看得出这题是我出的么……其实我还黑了人的,只不过黑得很不明显罢了,连某热衷于黑我的小朋友都没看出来。
答案就是每个点的深度的倒数和。(根的深度为 1)
证明嘛,我还不会一个显然的证明,但是我找规律找出来是对的。
有一种理解是这样的:我们考虑每个点,这个点只有在选择某次其祖先的时候才可能被删,选中自己的可能性是 1/dep(i)
,也就是这个点对答案的贡献期望是 1/dep(i)
,又由于每个点对答案的贡献是独立的(这点怎么看?),所以直接加起来就好了。
来自 fanhq 的加强版。
对于一个序列,求 k-MSS ,我们可以用网络流来做:一条链,限制流量为 k ,跑最大费用最大流。
这不是比暴力还慢么!注意到每次增广的特殊性,一定是选择一个区间,取了其中的值,然后区间取反。线段树维护即可。当然由于维护的信息比较多。要支持取反于是要还要记录最小值,还要顺便记录答案,比较麻烦。
于是就 O(n k log n)
了……
这个题居然被水过去了,坑爹啊……算了算了还是那句话:暴力能水过去也是他的能耐嘛。
主席的加强版的弱化版。(一种蛋疼的忧桑?)
做过原题的话应该知道用折线来刻画 dp 值这方法。对原题来说令 f[i][j]
表示第 i
个数为 j
时的最小代价和,可以知道 f
是一条折线,且只包含 O(i)
条线段,于是我们维护 f[i]
所表示的折线,递推出 f[i+1]
的折线。事实上这个方法是可以推广的,不过在这个题上是用曲线来刻画。曲线不好表示是吧,于是考虑维护曲线的导数。
维护了导数,找最小值也好找了,直接求与 x 的交点即可,方程也可以维护了。由于 n
只有 6000,暴力维护即可。当然你要有能耐的话可以用平衡树维护,保证复杂度 O(n log n)
,不过略难写。
一开始是在 G+ 上,主席说要给 CF 出题赚外快,于是我就回了句 bg ,然后就被主席拉过来出题了。
YY 能力完全不够啊。幸亏最难的几个题主席都已搞好了,于是我和 xiaodao 专注水题三十年。小岛出的 2A & 1A ,我出的 2B & 1B
一开始出 2B 的想法是要给一道水题是吧,然后瞬间想到 Python.fractions.limit_denominator 。当然连分数展开是果断不可行的,于是暴力枚举分母即可。
1B 的来源是耀爷讲课时的某题,我就直接蒯了下来~Gerald 好像搞了个很复杂的方法的说,其实就是个水题嘛。
一开始 1B 想出最大值除以次大值,后来想把数据出强一点,于是写了个 cheater 发现全部骗过去了,后来才发现如果是除以的话,答案一定是相邻两个数的商……宇宙大水题啊……
出题是放在 Polygon 上。真心是个专业网站,自带版本控制,用起来非常方便。里面有 invocation 用来测试数据,gen 建议用命令行做初始化,可以用脚本来生成数据,validator 检验特严格,一个字符都不能多,checker 感觉很松的,package 可以下载这个题目的所有相关信息,题目支持部分 TeX 语法真是太好了。幸亏前一段时间用过 git ,对版本控制还是有点理解的,用起来不难。唯一需要吐槽的一点,就是你必须等网页缓冲完毕后再点击超链接,否则会直接回到首页,蛋碎的感觉……每次 commit 都会发一份邮件,所以这几天被轰炸了不少。
主席某天突然之间就住院了,一开始我也不知道是啥情况,但是似乎很严重的样子。于是他的题就被分了,我、xiaodao、Seter 一起搞。我写了 E 的 cpp 以及 java ,慢出翔了,后来还是用的 Seter 的 java 。不过我写的 D 的 java 倒是跑得蛮快的样子。时限要求为 java 的两倍还真是蛋疼。为了照顾 Java 我不得不优化常数,结果最后和 xiaodao 一商量决定把时限开为 5s ,于是就有人水过了 T_T 其实我觉得 n 开小 k 开大蛮好的嘛,CLJ 说限制 k 的和也是可以的,这样更好卡了。
在比赛的前几天,突然得到消息说 C 冲了,于是怒 YY 题目。刚好做了一个 Project Euler 的题,于是 YY 出一个题,但是被 CLJ 抢得先机用了他的题。没关系下次再用嘛。
于是这场比赛的 problem setter 真是多,xiaodao、我、CLJ、fotile、kissbuaa ,另外 Seter、7k+、pashka、Gerald 来验题,规模也算得上庞大了,于是有人怒吐一槽:
话说现在 WJMZBMR 与 Petr 正大战三百回合,有兴趣的同学可以去围观。
然后晚上本来不打算围观了的,因为没人做,但是跑回寝发现大叔在做,于是怒围观。Seter、xiaodao、CLJ 开了语音,我和 7k+ 俩人就只好打字了……好苦逼。
于是讨论组里面的人全部开了上帝视角,成了权限狗。期间由于 XLk 突然之间回话了所以和 XLk 聊了一下天,他好久不回我了 T_T
发现 div2 的题超水,3min 左右 400+ 人过了 2A ,太可怕了。然后继续有人过 2B 。我很想不通那些过了 2C 没过 2B 的人是啥心态……我更想不通居然没人用 limit_denominator
来做,我还想不同有人用 Fraction 构造分数的时候用了小数从而精度有 bug ,我最想不通一堆人说这题精度太紧了太紧了。明明 Gerald 说这题太水要把数据组数减小的……
居然有人 5min 内过了 1A ,真是太令人惊悚了。我还看到若干个纯代数流,太可怕了。由于 1A 题过难,导致 1B 被迅速秒,成为这次 CF div1 AC 人数最多的题。
wuzhengkai 和 watashi 俩人同时在 33min 过了 A ,死磕着 A 不放干啥嘛,A 明显是用来坑人的。(wzk 的人人头像越看越觉得萌 = =||)
比赛的时候一堆人问 excluding OR 是什么意思。我明明记得我原题写的是 XOR 啊,那个英文翻译改成了这个东西真是蛋疼……偏偏样例精心手构答案是 7 和 15 无论 or 还是 xor 都可以解释。不过明明题目是 XOR 样例解释是 XOR 你还有什么问题吗?
哇卡居然有人交了 E ?WA pretest 2 连样例都过不了囧爆了。讨论组里面没人认为有人可以 AK 。
然后在 1h5min 有人过了 E 的 pretest ?为了和谐 pretest 是直接上了极限数据的,人民群众喜闻乐见欢兴鼓舞拍手称好。然后 Seter 拿过去一测发现可以 A 。经仔细研究后发现这个算法是错的……于是 Seter 出数据开始卡发现稍微一卡就可以卡掉了……结果一场腥风血雨在 CLJ 和 Petr 展开……再一看这个人还只交了 E ?果 E 大神!他的 AB 是后来才写的,太强大了……
大叔 YY 了一个 1B 算法,于是交了一次发现是错的,然后再交一次,于是我求数据加入 tests ,然后又写了个 gen 来生成类似的数据,似乎卡掉了一些人的样子。
D 题居然有人写正解!UESTC_Nocturne 太强大了……不过这个题被 liouzhou_101
骗过去了还真就不甘心呢。但是时限放的太宽卡不掉真是蛋疼呢。
之后一堆人在吐槽说 div2 的题太难了太难了太难了,你想要我做什么表情?
这次 CF 成功把 tourist 拖下 3k ……只要拼了前三题的手速就不会太差,后两题基本上没人过的。
好吧就是这样,感觉蛮好玩的呢。
骗钱向:以后有谁要出 CF 了我可以过来打酱油啊,专业酱油三十年。
刚刚对主题做了点小改动。原因蛮简单的,在 XFCE 下开启透明效果后,我发现原来的背景与桌面这张阿狸的图片混在一起蛮好看的,于是心血来潮加了个背景。各位觉得怎么样啊~不好看的话我还是改回来吧。
具体实现其实蛮简单的。首先找到你的壁纸,用 GIMP 打开,然后新建一个全黑的图层,然后 菜单 -> 颜色 -> 曲线
, 通道设为 alpha
,然后把那根线段的端点往下拉,就是 x
不变 y
变小,开启预览的话就按照自己喜好调。然后 Ctrl-Shift-E
导出即可。似乎这种图上 jpg
比 png
小一些?
如果图片大了的话缩放一下即可,我直接用 XnView MP
来重采样了。
然后要改 Jekyll-Bootstrap
了。我用的主题是 hooligan
,于是在 /assets/themes/hooligan/css/style.css
这个文件内有一行
background: url(../images/bgs/body.png) repeat; |
我要的效果是背景不随网页滚动而滚动,于是改成:
background: url(../images/bgs/bg.jpg) fixed; |
刷新几次,收工。
当然还有不满意的一点,就是壁纸大小不能根据屏幕大小自动换。这个要实现的话应该是可行的,因为这几天鼓捣 bootstrap
发现可以提供响应式设计,多 YY 一下应该是可以 YY 出来的吧~
终于没有 hole
这个 tag 了~
做这个 250 不要 250 了……
枚举最大值在这个序列的位置,可以根据位置及 d
算出这个数是多少,然后取遍 max
即可。
二分答案,没了。
感觉这个题好囧啊。
令 S
表示随便放一个马,除自己这个格子外,期望能够攻击到多少个格子;令 P
表示同时能被两个马攻击到的期望格子数。经过一定的推理后,我们可以发现如下公式:
ans = 2S + 2 - 2S/(n^2-1) - P
于是我们只要求出 S
和 P
即可。求 S
的话可以考虑统计每个方向上可以放的马的数目, P
的话我们就枚举同时被攻击到的马的位置。
首先考虑 a == b
的情况。 S
倒是很好求, P
的话可以推出一个公式来的。
再考虑 a /= b
的情况, S
照样很好求, P
就不一定了。我 YY 了一个很奇葩的方法。首先找到边界上的若干个分界点: {0, a, b, n - b, n - a, n}
。这若干个点把大矩形分成了 25 个小矩形。矩形内部的 P
是一定的,随便找一个点(例如找中点)即可判断出某矩形内的点的 P
。然后再用组合数乱搞一下即可。
怒刷小号~从此我也是有 TC 小号的人了~
一进 room 一看,cherudim9 是 room 内 rating 最高的,我是最低的,高下立判。
一打开 250 pts,插件自动帮我生成了……Java 模板?我勒个去果断自己手写 C++ 。
随便一想觉得这题蛮水的啊,写完后样例都没测(因为没插件不好测),直接在 Arena 里面测了。觉得没啥问题就交了。这题真心水啊怎么 room 里第二个交的才 230+ 呢?
果断重新配置插件。把默认语言改为 C++ 一切就好了。
然后开 500 pts,这不是一个绝世大水题吗……怒写然后过掉。
现在时间还多的很呢,于是开始 YY 1k pts 。一开始的时候根本就没想到还有 P
这种干扰,后来才想起来……
感觉样例很强的啊,于是感觉是可过的。
cha 人的时候看到 500 pts 有人没用 long long 来保存中间结果,就想着这是不是一个 cha 点。我看到有人程序和我的特别像,于是在 cha 之前用自己代码测了一遍,发现过了?继续 YY 发现就是过了。自己一想发现中间结果至多是 2k
怎么可能会爆 int ……
最后的 FST 是什么情况啊!发现是 a == b
时的特判写挂了 T_T
所以最后是 #60 。如果 1k pts 不 FST 的话前二十没压力的 T_T
这次做的人不多,很多人都做前两次去了。
cherudim9 本来还好的,可是被 500 pts 的那个不是 cha 点的 bug 搞错了于是 +0/-2 囧…… #174
秋锅 #72 。令人惊悚的是他现在 rating 还没我小号高 = =||
看到了 DL.uhT 分布式哈希堕落?其实是某盾啦 #93
lydrainbowcat 1k pts 的被 cha 于是 #107 。
至于大叔……哇过了两道诶,虽然速度比较慢但是没爆零了啊~#227 不过 rating 还没他的第一次高……
cjsyj 的 250 pts FST 了? 这不科学
! #425
This_poet 居然 FST 了 500 pts ?#685 momo
今晚 CF 欢迎各位参加~
似乎坑越来越多了……得填填啊。
XLk 去北京学英语了。(而且问他又会黑我的 T_T)
唔,似乎是水题的样子。
大概就是利用 K
找出每一条链,链上找出出现次数最多的字母,其余的字母全部变为这个字母即可。
又是渣手速。
暴搜是会 T 的~hahahaha 感觉只要答案大点就好了。(random 搜怎么破?)
我的方法是这样的:前面 4 位枚举原数,得到所有前四位的匹配情况。后 5 位就可以直接暴搜了。这相当于一个双向搜索,先从某一半开始搜,把所有可能的解全部塞到一个 set 里,从另一半检验的时候就直接在 set 里找了。
用 set 的话可能常数比较大,用个 trie 效果会更好些。不过这无关紧要了,不会 T 的。
话说感觉 TC 的 500 pts 很喜欢出这种暴力题啊。
坑。
这次 TC 居然是晚上八点。话说 TC 没小号真是让人感到可怕……(xiaodao:rating 是用来跌的!)
于是机房里都在做 TC 。
上次 TC 给我发了个啥邮件,说啥 warning of unused code ... 于是这次交之前把模板神马的全删了……
250 这不是水题吗……手速硬伤。只有 237 分了。 T_T
500 想着感觉暴搜很容易过的?但是复杂度不靠谱啊……没敢写,继续 YY ……
突然之间 YY 出来了?写啊写……代码能力越来越差了,写了好久才调出来。只有 270 分了。
看了一下 1000 pts 的题,感觉很厉害的样子,没怎么动心思去想……
然后啥都没做了, Challenge 对我来说一直是打酱油的。
大叔又一次没爆零!普大喜奔~
tourist 怒 cha 掉 Petr 的 1000 pts 成功 #1!
我会说 Petr 只靠前两题还有 #4 ?
WJMZBMR #10 。第二题 350+ 太快了啊……
我居然看到了 Gerald ? #16
某 id 为 ainu7 的神犇只过了第一题,第二题 FST 了。然后他居然连 cha 了 6 个人 #17 !跪。
然后我就是中规中矩的 #22 ……
还有 Mike Mirzayanov 。CF 的都来了?
edly 说跪了,然后 #35 = =|| 然后怒黑之。
一堆人 FST 了 500 pts 。zhouerjin/xiaodao/NaHS/ChnLich/cherudim9/ryz/wuzhengkai ……momo
有位小朋友在做 div2 ……只交了两道于是 FST * 2 momo
另外 orz huzecong div2 虐场。
CF-172 求围观啊~求各位大神虐啊~
前几天某人(特指)进入国家队了,然后 renren 上转了条状态(miffy 的),然后被一群人围观,然后四处被黑 T_T
有必要么!
嘛,wyl8899 问我是不是刷小号……
我才不刷小号呢,我刷的是小小号。
惯例水题。直接用并查集搞搞就可以了。
注意没有一个人会一门语言的情况。我因为这里 WA 了一次。
构造。
rng_58
的构造方法:对于 m=3
的情况手算,可以证明若 n>4
则无解。于是这里手算很简单的。
然后考虑两条抛物线: y = x^2 + U
与 -y = x^2 + U
,其中 U
是一个很大的数。如果我们在抛物线上选点,由于抛物线的特殊性质(凹还是凸分不清啊 T_T),可以得到如果两个抛物线上都有点被选,那么这样构出的凸包的大小最多是 4 ,所以如果要选择尽量多的点的话,应该是选择某一条抛物线上的所有点。我们令一条抛物线上点的个数为 m
即可。
感觉还蛮简单的。
容易知道每行每列都是独立的,我们可以把这看成是若干个不相关的组合游戏。对于每一行/列,我们只关心没有被覆盖的线段的条数。这个可以用排序+点事件维护,也可以直接用 set 暴力维护。
然后把所有的数 xor 起来就是 SG 了。注意一种特殊情况就是初始时没有出现过的行/列。很显然,我们只关心奇偶。
如何输出方案?一行一列枚举下去,如果通过改变这一行/列可以把 SG 变为 0 则找到一组解。
代码量比较大吧。
没看懂题目的说……
稍稍一想就发现这是水题。
每个点的出点向所有可能的父亲的入点连边,容量 1 费用为距离。源向每个点的出点连边,容量 1 费用 0 。每个点的入点向汇连边,容量 2 费用 0 。跑一遍费用流,如果最大流是 n - 1
那么有解否则无解。如果有解则最小边权和就是最小费用。
大家都蒯模板啊我还老老实实自己打啊。
本来以为秋锅不做的,结果居然做了。
看完 A 觉得这不是水题吗?于是怒敲代码,写着写着觉得有 bug 于是怒换一种写法。submit 后怒 WA#4 。瞬间想到某特例,加上特判后过 pretest 。
然后 B 。按照惯例,B 应该是水题吧。于是我被惊悚到了,完全不会做啊。YY 了好久想到了用抛物线但就是没想到用两条抛物线。一开始看错题了,以为是要构造一个大小为 n 的点集使得凸包大小恰好是 m 。交了后发现过不了样例才发现看错题了 T_T
瞟了一眼 Dashboard 发现有几个 E 已经出来了,看了一眼 E 觉得不会做。然后看 C 的题目去。看完 C 的题目后发现我会做 E 了 = =|| 于是回去写 E 。1A 。
然后发现 C 不也是水题么。只是处理起来比较麻烦罢了。于是再次怒看错题。然后就没有然后了,1:50 的时候交了个 FST 程序过去。后来调的时候才发现又看错题了 T_T
一看 D 的题目这么长我就直接撤了。目测等我理解完题目 CF 都结束了。
最后 #41 由于是小小号然后还是可以涨的。快追上小号的说~
XLk 你真的 AFK 了吗……考完后没人和我聊天了 T_T
scottai1 怒过 ACE 。E 手速还很快的说,于是有 #8 。于是 rating 又超过我了 T_T
wuzhengkai #25 、xiaodao #32 都是 ABE 。我觉得 B 的这个构造很巧妙的说。
watashi 和我一样的,默默 C FST 了。
秋锅 AE #90 。看起来又黄了。
另外我就不吐槽 FredaShi、CatCat、liouzhou_101 三个人的分数都差不多,都是 AB ,提交的时间也差不多,代码也差不多,连 E FST 了都是 T 12 。
ztxz16、sths、edly01、vfleaking 都只过了 A ,而且和我一样,默默 wa 了一次 ……
最后还要吐槽这次 CF 的分数变来变去的,一刷新就发现题目的分数变了。
感觉这次 CF 难度很大的说……
然后发现还有人 AK 。
于是感觉 CF#172 也会有好多人 AK 的说。