玩脱了，目测要是用大号或者小号的话都会跌吧，幸亏用小小号 lol

Solution

A

水题，记个 max 就可以了。

我会说我看题看了 6min ？

B

对于相同横坐标的可以用很多种排法，这个用阶乘计算。然后除去 2 的满足 A[i] = B[i] 的 i 的数量次方就可以了。

如何除呢？约分就可以了。

C

构造。可以证明，任意一个满足要求的图都可以找到一种方法。考虑一个点，只要这个点周围和它在同一个集合的点的数目不超过和它在不同集合的点的数目，那么这个点就是满足要求的，即邻域中与它在同一个集合的点的个数一定不超过 1 ，因为这个点度数不超过 3 。

所以调整一下，每次选择一个超过的点，换到对面集合里去即可。由于每换一次，矛盾数会减少，所以这个调整总是可以结束的。

我就不吐槽这个题是 原题 或者 原题 了。

D

dp 。显然这个连通块一定是凸的，我们令 f[L, i, j, s] 表示前 L 列，第 L 列的范围为 [i, j] ，且边界状态为 s 的方案数。什么是边界状态呢？考虑上边界，一定是先上再下的，下边界一定是先下再上的，我们就把这个定义为边界状态。

转移的话，如果暴力枚举上一列的范围，复杂度会很高，于是记个前缀和就可以了。

一堆人蒯源代码 T_T……我还是不吐槽这是 原题 或者 原题 了。

E

不坑不科学。

situation

刚被 TC 打击到，现在又要被 CF 打击了。

看了好久 A 的题目才看到有张图。然后随手写个程序就是过不了样例，最后 YY 了好久才过样例 sad

然后看完 B 后想了一个错误算法……因为我想错题了，于是怒 WA #3 。最后是 44min 才过了 B 。

看了 CDE 觉得 C 题似乎考过的样子，但是当时靠着数据水骗了过去，现在不行了。于是就没写 C 了。

D 题看一眼觉得是 dp ，但是很难写的样子。E 没啥想法。我决定还是写 D 吧。

写啊写写啊写一个函数忘记返回值为 64 位贡献一次 WA #11 然后改了后就过了。

后面也没心思写题了，觉得也写不出啥了。但是后来发现如果有想法了，那么 C 还是可写的，代码量真的很少啊亲～

最后就挂了嘛，毫无疑问地挂了嘛。#64 哭了。

others

有人猜得到我第一句话应该是——

强烈谴责 XLk 的虐场行为！

D xiaodao 直接把 Petr 的 java 代码交了上去， XLk 还算良心，还改成了 C++ 代码 = =||

然后 XLk 在 1:58 的时候交了 C 过了。然后就 #12 了。

文学巨匠靠着 D 的手速混到了 #33 也还不错了。

hza 靠着每个题速度都不差混到了 #49 。

我就是太慢加上贡献了两次 WA 导致被虐残了 T_T

scottai 似乎是倒着做题的 = =|| 然后就挂了。

edly 居然 C 没过。

nonsense

XLk 的大号被小号超了！看来如果我再不做大号就要被 XLk 虐飞了（现在已经被虐出翔了） T_T 。

又被虐残了。强烈谴责 XLk 虐场。

#solution ## 250 一看就知道是水题嘛。模拟出一次之后的变化然后根据模 4 讨论一下就可以了。

我就不说我只有 150+ 了。

550

首先要把代价表示出来吧。我们发现， cost = 2 * components - 2 - vertices 。于是我们统计加了 2 之后的好了。

具体怎么搞呢？dp 。 f_{v, ca, cb} 表示 v 这棵子树，和 v 颜色相同的一部分的已有代价为 ca ，其余部分的代价和为 cb 的方案数。转移就是枚举孩子的状态。

复杂度感觉很高的样子，于是用 map 来写= =|| 想优化常数然后过了。但是直接数组就可以了嘛。

900

当然是坑。

situation

看完 250pts 发现这不是水题吗？于是开始码代码。

好的，用 x y 这两个变量来描述一个位置，然后似乎不好写啊？

好吧我就用 complex 。

好吧发现我不会用 complex ？还是老老实实地两个变量吧。

于是时间哗啦啦的流，然后就只有 150+ 分了。

再看 550pts 发现不会做啊。没有草稿本啊于是赶紧上画图。

好像是可做的？复杂度好像高了点？不管了用 map 看看能不能骗过去= =||

然后还真就过了= =|| 。其实数组就可以了啦。

交完没几分钟就结束了。

others

XLk 你不仅虐场，你还虐心啊。#3 啊亲~求抱大腿啊。

xiaodao 第一题有 230+ 于是 #20+ 也不错的说。

好多人第一题都有 200+ 于是我被虐飞了 T_T

最后 #40 ，也不算一个特别坏的结局吧。

nonsense

我说 TC rating 的 delta 能不能大一点啊。我看我的 delta 大部分都不超过 50 啊亲~

看人家 XLk 人生大起多痛快，一次 #1 一次 #3 。有这两次我也就满足了。

晚上居然还有次 CF 。

刷小小号呢。

一次大好的 rank1 的机会就被浪费了，好桑心……

不过 rank5 也还不错的说？

Solution

A

水题，枚举即可。

由于这几天写 Haskell 于是顺手用 Haskell 来写 = = 发现手速更慢了。

B

水题。预处理出每个数至少要加多少次，统计每一行每一列的和即可。

C

构造。有很多种构造的说。

无解显然是 n < 3k 。

我的： 1 1 2 1 2 2 循环很多次，如果 k 是奇数那么就是 k k 1 1 2 1 2 2 k 。

另一种： 1 1 2 2 ... k k 1 2 ... k

D

据说 hash 挂的很惨。

其实 trie 很好的啦……不过我写的不是 trie ……我把所有字符串全部排了序，然后减去 LCP 的长度和即可。

E

这个题就不太简单了。

首先可以证明： (x, y) 可以变化到任意一个 (x + a, y + a) ，不管 a 的正负。做法如下：

(x, y) -> (y, 2y - x) -> (x, 2y - x) -> (ceil(x/2), y - floor(x/2))

可以发现， 这两个数的差仍然是 y - x ，而当 x > 1 时， ceil(x/2) < x ，所以我们最后一定可以得到 (1, y - x + 1)

接着另一个结论：若 x 是奇数，那么 (1, x) 可以得到 (1, ceil(x/2)) 。显然嘛。

然后引出终极结论： (x, y) 最后可以变成 (1, 1 + t) ，其中 t 是 y - x 最大的奇因子。而能产生 (1, a_i) 则要求 t 是所有 a_i - 1 的因子。

于是暴力枚举 t 即可。

situation

在家做笔记本没手感啊。

看完 A 这不水题一个么……速上 Haskell 发现好慢 T_T

看完 B 这不水题一个么……怒上 C++0x ……数组开小了 FST 了啊……哭瞎了啊……

看完 C 同上。随手 YY 一下即可。

看完 D 同上。第一想法居然是后缀数组？发现长度只有 1500 ？暴力建后缀数组吧 = =||

看完 E 发现不会做啊。YY 了若干久没啥好想法，发现没草稿本啊亲……于是只好用画图 YY 了。

结果乱 YY 一个结论居然过了全部样例？好吧就这样吧。

然后开始 cha 人。看了半天没想法，看着 E 题某人只判 t = 2 的情况，于是想 cha 掉，然后挂了 T_T 。截图如下，我多么希望网速能够慢一点啊。

others

XLk 和 xiaodao 开黑……然后两人的 DE 全挂了……

xiaodao 只做了 DE 。是懒得刷 ABC 吧。

liouzhou_101 似乎没搞出 E ？还是 D 用的时间太久了？

zrx 小朋友一开始说要做的，结果不知道做没做，我还不知道他 ID 呢。

然后没谁参加了……

nonsense

现在大号红了小号黄了小小号紫了 div1 的各个颜色都有了。

昨天小朋友要我帮忙给他凑 ID ，原因是他看了 lkf 的 ID ： VFleaKing ，就是把名字 shuffle 后凑出一个还过得去的单词吧。他凑了好久凑出个 penguin ，但是还有 4 个字母 gaxy 死活凑不出了，要我帮忙想想。

嘛，这东西果断给机器做好啊。于是到网上搜英语词典，找到了一个 包 ，用 Python 处理把里面的所有单词全部提取出来，做了一个单词库。另外所有的单个字母都出现过了吧，还得特判掉呢。

我下的这个包比较囧，有些地方有空行，有些地方一行会断成两行。空行的我直接特判了，第二种还真就没办法，只好不处理这个文件了……不过这里面的全是 v 开头的单词全部忽略掉算了吧。

接下来就是暴搜了，没啥技术含量，我就直接拿我自己的名字做测试了。每次枚举下一个单词选啥。由于有些单词过于奇葩，所以又造了个 spam word list ，比如说你听说过 pl 这个单词吗？果断屏蔽掉。

发现了几个比较搞笑的东西：

u no lip guy
你这个没有嘴唇的家伙……233

gun lip you
枪 嘴唇 你……我勒个去这是有多 zkw 啊

i upon ugly
我 在...之上 丑 …… 物极必反么亲？

only pig u u
不想吐槽了。找喷啊你。

不过还是发现一个比较正常的：

guy up lion
狮子上的家伙……狮子王？

好吧就是这样很无聊的一个东西= =|| …… WJMKXMR ……

update:

自从写了这玩意后小朋友们纷纷要玩，于是找出几个比较还不错的：

i judge rein
我审判缰绳

hog in maze
迷宫里养猪。《论让猪不溜走的好方法》

angel conch gin
天使海螺杜松子酒。好酒！

gaze in ohm
专注于欧姆。物理帝。

quad shine
四倍闪耀。啥牌子的洗发露？

glance chignon
瞄一眼发髻

然后再把我以前的 ID 输进去发现：

ours hope
我们的希望

pure shoo
纯十拿九稳

pro house
专业房

hero soup
英雄汤，一口让你变英雄。

其实，到目前为止见过的最好凑的还是 XLk 的名字：

bike

天然中有木有！

被虐得飞起。果然退役了就暴露了一堆问题的说。

和 XLk 开黑。XLk 居然用新小号在 div2 进行了惨无人道的虐场，在此提出强烈批评。

Solution

A

水题。只需对于每一种大小的盒子算出要多大的盒子即可。

注意这组数据：

1
1 1

然后没了。

B

很显然这个题 m 和横坐标都是没用的，答案就是 n - LIS 。

似乎我把 LIS 看成了 LCS 然后怒坑 XLk ？

C

居然不会捉……还是 XLk 教我的。高下立判。

事实上只要注意到一点：整个图是没有环的。那么无论决定了哪些边的方向，都存在一个没有入度的点。我们从这个点开始把所有未决定方向的边的方向全部决定即可。

如何找到这个点？用个队列就可以了嘛。

注意到 n 这个点的特殊性。如果你 WA 22 了，请注意这个点：

4 4
1 2
1 3
2 4
3 4

D

看完题后觉得大水啊，比 C 还水些。

这题不就是去年 WC 的《记忆中的水杉树》吗？由于线段都是平行与 x 轴的，更好处理了。

从左往右依次扫描，用 set 来维护当前扫描线上的线段。

注意到连边的特殊性。我们要求 i 能向 j 连边的话要求中间不能插个 k ，于是你可以各种乱搞处理之类的。我的做法是动态删边，用 unordered_set 来维护当前点的出边。每次加入一条线段，我们就删除一条边。

后面在 DAG 上乱 dp 一通就行了。

但这个题有个小 trick ：

oo 要设为 2e9

哭瞎了，我后来一调，发现我一个地方 b 写成 a 了，另外就是 oo 设小了……

E

坑啊坑

situation

先怒水 A 。发现 WA 了。仔细一检查发现特判的时候加错一个变量了。T_T

然后 XLk 向我求解这个题的特殊情况。

然后发现 B 不也是水题嘛， 1A 好开心。

然后 C 看了半天没看出来。先写个 SAP 试试？怒 TLE 。T_T

感觉再不做题就要跪出翔了，于是怒写 D 。用 set 一下子就写出来了，但是 WA 了。

等 XLk 虐完 C 回来告诉我做法。怒写怒过。

然后就没有然后了。跪的挺惨的。果然实力还是不行呢。

由于小号 rating 低导致还可以涨？ 这不科学 ！似乎 +123 好数字……

others

XLk 果断虐场的节奏啊，怒涨 244 。顺便还带了 gjq 一起练呢。

我就不吐槽 XLk 的小号是 woxihuanni 了。（这是准备对谁说的？）

目测 XLk 的第二个小号都要红了我这个号都红不了呢。

liouzhou_101 和 lydrainbowcat 同时写挂 C 啥情况……于是 liouzhou_101 rating 大跌……momo

zcwwzdjn 目测做了半个小时就睡觉去了？ pty 似乎也一样……怒跪大神

我就不吐槽秋锅奇怪的 sort 了。

最近被虐得好惨啊……谁来拯救我啊……（转身默默学数英去 T_T）

Farewell

OI 生涯已完结。谢谢各位的关心与支持。

没什么好说的。能认识这么多人我也很开心了。

遗憾是肯定的。可是没办法，考试的残酷在这里表现的淋漓尽致。

一帆风顺的生活到此结束。不一定要活在别人的视线中的呢。

考挂自己弱，LYP 最弱。（XLk：版权！版权！）

Life

流水帐啥的就不写了，吐槽几点吧。

首先要吐槽宾馆= =||。还真就是个公寓式宾馆啊，居然提供厨房 -_- 。灯奇暗无比，网速呈脉冲型分布，故美其名曰：一大波流量正在接近。被子真心感觉薄。

UESTC 发了个啥 U 盘，样子到蛮好玩的，不过……一体机被卡了差不进去啊亲！

伙食嘛……第一天在旁边的一个川菜馆吃的，味道的确正宗，够麻。但是……分量倒是不多，某道鱼里面只有 5 片鱼肉（yxj 怒抢两片）。后来一直吃食堂。 贴吧上一堆人吐槽：少放点辣椒会死啊。 为啥我完全没吃出辣味啊。

还有这饭的质量确实让人捉鸡。连长郡食堂都比不上。不过早餐还是蛮不错的，油条泡豆浆真心舒服。

和 XLk、gjq 一起吃饭实在是太虐心了。gjq 衡水中学的有木有啊！！吃饭速度实在是太快了有木有！！

由于每天都在空调房里，导致脚出汗特别多……于是又化脓了哭。

XLk 真心高（一米九啊亲）富（连键盘都自带）帅（目测一堆妹子追？）啊。坐在他旁边亚历山大啊。

LRJ 在讲课的时候准备叫 jzp 回答问题，结果发现 jzp 睡着了，不忍心打扰他。钱桥：遇到这么好的老师你就嫁了吧！

机场的网速比宾馆快有木有！！ 机场遇到来旅游的学姐了有木有！！ 机场遇到了 hwd 和 ayq 有木有！！ 机场有机器可以免费上网/看视频有木有！！

吐槽：“双流机场” -> “二流机场”

闭幕式表演节目，hym 和谁（抱歉我不认识= =||）两人对唱《因为爱情》太高能了有木有！！只可惜当时相机不在我这里没法录像。学军 + 丽洁的《法海你不懂爱》无法直听有木有！！

营员交流，dyh 太可怕了……要不是我提前开挂看了 pdf ，不然根本就听不懂啊。话说这掌声真是人民群众喜闻乐见，讲到二项式反演时集体鼓掌，hwd 报时还剩 10 min 的时候集体鼓掌，还剩 1 min 的时候集体鼓掌，还剩 10s 的时候掌声雷动！不过最郁闷的是最后下来的时候还不忘黑我= =||

为啥营员交流 day1 的是 4 个 ppt ，day2 的是 3 个 beamer ？

最后讲课那天 hjf 将的东西蛮好玩的，可以去试试嘛。

文学巨匠 wzy ：我看过《约翰·克里斯托夫》。

• 大家好，我是来自石家庄二中的 LYD 。——by liouzhou_101
• 大家好，我是来自广西柳州高级中学的 WQS 。——by lydrainbowcat
• 大家好，我是 MIT 的 GYZ。 ——by WJMZBMR
• 大家好，我是来自青岛二中的王强松。——by lydrainbowcat
• 大家好，我是来自唐山一中的 SHY 。——by kAc
• 我是唐山一中的 SHY ，你快来黑我呀。——kAc to lydrainbowcat

小朋友看见我说 XLk 就说溴分快什么心态 = =||

Examination

第一题一看就一裸题啊，平面图转对偶图，然后点定位再写个倍增啥的就好了。可是可是可是，写得出来吗？

第二题一看想到了《小 Z 的袜子》，然后再一看想到了 COT2 ，然后就把它当成了 COT2 来写。

第三题看一眼没啥好思路，于是就放一边吧= =||

后来证明没做第三题是绝对错误的。那么多个点那么好玩，我完全没做啊。每个点全 0 骗了几分，用 checker 做第 9 个点骗了 10 分， 5 分钟怒写高斯消元过第三个点，第四个点骗了 4 分，然后没了，只有可怜的 31 分。这个题完全是最可做的啊。怒黑 XLk 第三题全场第一。

第二题其实还好的，写 70 分的莫队算法差不多了。想起了各种 sqrt 爆搞，但是觉得不太靠谱怕被卡常数，于是辛辛苦苦写了 Manhatton-MST 。（我去退役了在乎啥常数啊。）比较囧的是最后才拍出一个错误，就是某种情况下有些询问没有和最小生成树连通= =||，于是怒 for 一遍，没有连上去就直接连到 1 号点，然后普通情况下不错？算了就这样吧……

第一题实在是难写啊……先写平面图转对偶图了。想写 100 的算法发现写不完，于是怒写 70 的；再发现写不完，怒写 50 的；仍然写不完，转写 30 ；再发现怒写挂。

结果很凄凉。第一题玩脱了，完挂。第二题 70 + 第三题 31 = 101 。翻盘无望。退役了。

cherudim 以 0.02 分被 hym 强踩。momo。

liouzhou_101 打错第一题文件名了。

xpd、yzc、ldf 的优势被 WC 完卡。

Epilogue

两年半的 OI 生涯结束了。

pty sillycross 文学巨匠wzy 继续努力吧。默默祝福。

fotile 明年还有一次机会呢。祝你好运。

cherudim momo……不必太悲伤了呢，想开点吧。

XLk liouzhou_101 kAc xpd lydrainbowcat qdc dyh lyx 一起加油吧。

能认识你们真是我的荣幸。

谢老师、向总：很抱歉我没能完成任务。感谢您长期以来对我的关心、帮助。

遗憾也好，后悔也罢，就让这段 OI 历史成为我高中生活中最美好的回忆吧。

远处的地平线 闪耀着光辉
那是因为 有你在身后
点滴岁月令人如此怀念
是因为 有你相伴

世界不停转动 有你藏在其中
发亮的双眸 闪烁的灯火
世界不停转动 伴随着你
伴随着我们 直到重逢之日

Future

又回到最初的起点。

得考虑生存问题了。大学还是得继续的呢。

具体规划啥的还没出，不过大概说一下吧。

想进 IIIS 还真就不容易呢。

物理高数线代具数都看看吧。

然后怒学英语。

还要为学校做几件事的呢。

那个 MIT Challenge 貌似很好玩的样子。不过全部学完是不可能的，就当做是学英语了 T_T

ACM 啥的还是准备搞搞，CF/TC 啥的都玩玩吧。（怒求队友。请做好被坑的准备。）

小朋友也要辅导一下的说。

某人（特指）你加油呢。尽力就好，再惨不会比我惨是啵。

Winter Camp 的讲稿。

update: RTM 已出。

想要的人去下吧。src 神马的在 github 上自己去找吧。

链接在此

如果你会用 git ，你可以直接：

1

git clone https://github.com/roosephu/slides.git

内附 org/tex 。

谢谢大家的支持。随便乱讲一些东西，不要当真。感谢 XLk 指出错误。

快退役了吧。

最后再疯狂几次吧。

——谨以此纪念我的 WC 前最后一次 TC 。

summary

250pts 的速度一般般，但 500pts 的手速比较快，所以能混到 50+ 名。

总体来说 rating 还是涨了， +44 也还不错了。

Solution

250 points

我觉得最好写的方法就是容斥了。

把那个啥 sqrt 拆开，可以得到只要 AB 为完全平方数，那么 (sqrt(A) + sqrt(B))^2 就是整数。所以我们要统计的就是有多少个 AB 为完全平方数。而 AB 为完全平方数的充要条件是 A/x 和 B/x 均为完全平方数，其中 x 为 gcd(A, B) 。

令 f[i] 表示当 x = i 时的 (A, B) 数目。全集为 floor(sqrt(n / i)) * floor(sqrt(m / i)) ，我们要减去的是那些 gcd 不是 i 但是仍然

500 points

1000 points

others

XLk 看错题了。但是总 rating 还是比我高，瘦死的骆驼比马大。

cherudim 和我聊天去 = =|| ，于是没咋 cha 人。

哭瞎了。

OI 生涯最后一次 CF 做小号然后怒跌。

幸亏没用大号做……否则要会黄啊……

Solution

A

双端队列就可以了。读到一个 l 就在右边插入 i ，否则就在左边插入 i 。

B

直接 dp 就可以了。转移的时候优化一下，记录 g[i] 表示 i 的倍数的最大的 f 值，每次 O(sqrt(n)) 利用 g 来求 f， 再用 f 来更新 g

C

观察数据范围发现 O(nq) 可过，但是 O(nq log n) 也许会超，考虑每次询问重新处理。令 f[i] 表示选取第 i 个球的最大收益，通过枚举最后一个球的颜色来转移。由于只有两种可能性：与上次颜色相同，与上次颜色不同。对于每种颜色维护最大值，线段树查询。

这样会 T 。其实只要维护最大的两个元素就可以了，不用线段树，复杂度降至 O(nq) 。

D

考虑枚举 S 中的每个位置，实时维护 T 中的所有可行位置。

维护两个量， L, R 表示 S 在当前位置时， T 最近、最远在哪里。那么所有可行的位置一定在 [L, R] 内。但并不是所有的位置都是可行的，考虑在当前位置前一位时 [L, R] 内的所有相邻元素，如果相邻两个是 [S[i], S[i - 1]] ，那么 i 这个位置是不能到达的，减去即可。可以证明，其余的位置都可以到达。

E

rng_58 的程序居然这么暴力。哭瞎。

令 f[i] 表示从 i 开始的 LIS 的长度。暴力维护 f 。

插入：由于高度小，只有高度比他小的元素， f 才会受到影响，暴力更新。

删除：由于序号小，只有序号比他小的元素， f 才会受到影响，暴力更新。

situation

首先做了 A ，还是很快的。

然后看了 B 后觉得记录约数是可行的，于是写了。（然后不小心写挂了 T_T）

然后脑残想去 cha 人？于是 Lock 了 B ，然后一个人都没 cha 到。

感觉不行啊，要跪的节奏啊，于是看 CDE 去。

C 瞬间 YY 出 O(nq log n) 的怕 T 不敢写。

一看 E 那不是原题么肿么没人做啊。于是写啊写写啊写好开心～过样例了好开心～交上去 WA 2 了好开心～再仔细一看看错题了好开心～T_T

完了彻底玩脱了。于是赶紧补 C ，YY 出一个 O(nq) 的。结果维护最大的两个值的时候维护错了，交了 4 次才过。

E 题无望，D 题或许还有点可能性。于是继续 YY ，YY 出一个算法了好开心～手跑过不了样例好开心～

继续 YY ，经过各种常数微调似乎可以过样例好开心～3 个样例交上去就 WA 4 好开心～

于是乎小号都会跌……T_T

这大概是除了那次 Bayan 外跌得最惨的一次了……

others

liouzhou_101 稳定发挥 rank 16 怒虐场。

wwwwodddd rank 53 也不错。

cherudim 终于可以不用熬夜了。

大叔只过了 B 。不过遇上了一件奇葩的事：有人用大叔的 ID 交程序 = =|| 。这是肿么做到的……

nonsense

今晚 8 点有 TC 。没小号给我撑着大号要怒跌了。

刷小号。差一点就可以虐场了 T_T。

Solution

A

签到题。q 只需求个 min 就可以了，然后把 a 排序一路扫过去，能用就用。

B

dp 。先要转换一下思路，把答案分成若干份： ans = 前 1 个人能塞进去的概率 + 前 2 个人能塞进去的概率 + 前 3 个人能塞进去的概率 ……

然后就可以 dp 了。令 f[i, j, k] 表示前 i 个数中选了 j 个数，这 j 个数的和为 k 的方案数。然后枚举当前数选不选即可。

提供另一种思路：统计每个数字出现的次数，令这个数组为一个状态，每次枚举选哪个数。记忆化一下即可。

C

先把这个表打出来，统计每行的和，发现 m + 1 行的数的和为 2^g(m + 2) ，其中 g(x) 表示 x 的二进制表示中 1 的个数。然后就是一个简单的数位统计题了。

D

被卡常数了求破。

如果 t > maxb \|\| t > n ，那么显然可以直接输出 b 中不同数的个数。

这样就可以保证序列的长度不超过 nt 也就是 2 * 10^7 。然后暴力跑最长上升子序列即可。

注意时间复杂度的估计，不是 O(nt log nt) 的，而是 O(nt log ans) 的，而 ans < min(n, maxb) ，所以有一个 0.5 的常数。

我当时就是这么写的，但是这样是会 T 的。一个比较简单的剪枝是如果答案到达上限，那么就直接 break 掉。但是仍然会 T 。再加一个常数优化：对于位置 i ，这次二分的位置不会小于上次二分的位置，于是从上次二分的位置开始二分即可。加上这个常数优化就可以过了。

E

不会。挖坑

situation

首先看了 A 题，水之。

然后看完 B 第一反应不会做，第二反应是作业中的一道题，然后就有了这个 idea ，然后 dp 超好写的说。

接着看了 CDE 三个题，感觉都不太会。刷新一遍看到 C 有人出了，于是开 C 。

推了一下没推出啥结论，然后打表发现都是 2 的幂，瞬间想到二进制表示中 1 的个数，然后就有结论了。

写了好久过不了最大的样例，到最后才发现有个地方需要 + 1 我忘记了，浪费了好多时间 T_T 。

借助刚才想的思路，立马写 D 。然后写了个随机的 generator ，发现无压力，于是直接 submit 了。

YY 了一下 E ，暴力 dfs 发现所有合法的数并不多，但是没想到肿么处理。于是 cha 人去。结果一个人都没 cha 到。

然后发现 D FST 了。哭瞎。

后来优化了一下常数就过了。

现在 rank 是 20 ，如果 D 没挂，那么可以直接 rank 3 。第一次 CF 是 rank 1 ，第二次是 rank 2 ，第三次是 rank 3 该多好啊。T_T

others

liouzhou_101 D 题同样 FST ，TLE 11 比我还惨。

ryz 怒 cha 两人。

ryz 、XLk、shangjingbo、pty、hyy、ChnLich 一堆人中规中矩，过了 ABC 。

jzp、cwx、gsh、大叔只过了 AB 。

秋锅只过了 A 。

xiaodao 怒挂 B 。

nonsense

闲着无聊把 RSS 架了起来。有兴趣的同学不妨订阅一下嘛。（目测没谁有兴趣……）