Problem

有一个 \(n \times n\) 的矩阵，你可以任选 \(k < n\) 个格子并控制它们。任意时刻对于任意一个格子，如果它周围有不小于两个格子被控制，那么这个格子也会被控制。问是否存在一种初始选择 \(k\) 个格子的方案使得最后 \(n \times n\) 个格子都被控制？

心情随笔，不喜勿看，自行 Ctrl-W。

最近一段时间重新翻开了高一时“某人”写的一篇文章，《无尽的远方，无数的人》。这句话出自鲁迅的《这也是生活》，原文是：“无尽的远方，无数的人，都与我有关。”。最近由于某些原因（情感问题？不要在意这些细节）突然之间想起了这篇文章。当初这篇文章是 2011 北约作文题，老李于是要我们写这篇作文。“某人”的这篇文章，看了后真的难以忘记。

一群人、几个人、两个人、一个人，生命的历程就是这样。

一群人只是生命中的过客。你与他擦肩而过，不留下一点痕迹。最后的回忆也只剩一句：哦，我似乎听过这个人。但是周围的那些人终究散去，只留下几个人愿意等你。

于是这几个在你的回忆中留下了一丝痕迹。他们或多或少会给你一些关心与帮助。但是几个人也终将离去，只剩下两个人的世界。

于是你愿意将兴趣爱好分享给他，你愿意将喜怒哀乐告诉他，你也愿意和他一起欢乐，一起悲伤。两个人的世界总是美好的。

所以有这句话：生命纯属偶然，所以每一个生命都要依恋另一个生命，相依为命，结伴而行。我更愿意把这句话理解为朋友之间的友谊。有人结伴而行，生活不会孤单。

可是……一切构建在时间之外的友情都是破碎的？

可是……一切构建在共同点之外的友情都是破碎的？

不管是谁，总有分开的一天。所以最后，我们还是孤独的一个人。

人生注定是场孤独的旅程。

所以老李在高一第一节课中说道：要做一个耐得住寂寞的人——或者说，要做一个内心强大的人。

一直自认为内心强大，却也耐不住寂寞。享受孤独？我没能这么强大。所以说我渴望友情，倒不如说是害怕孤独。

孤独是“灵魂渴望被理解的持久的诉求”，所以我才觉得孤独吧。

所以也有这句话：生命纯属偶然，所以每一个生命都不属于另一个生命，像一阵风，无牵无挂。

“那就去爱人吧。”

第一次读完这篇文章后，最引起我注意的就是这句话。爱人，是面对孤独的最终解决方案。与生俱来的孤独不能驱散，悲悯之心却会给你力量。

不管怎样，我都渴望一个人，一个能真心交往的朋友。

不得不想起 lyd 和 shy 。我更愿意把他们看成是一对知心朋友而不是一对情侣。

自然有些人是生命中的过客。

自然有些人看起来关系很铁但只是一层纸。

自然有些人是可望而不可即的。如 fanhq 。

自然有些人是你想却总也交不上的。如 XLk 。

本性自然是极好的，但是本性只能高考。梦想着贵系的男人啊，加油吧。

“某人”？你会只是我生命中的一个普通过客吗？

“某某人”？好久不见不知道还记不记得我呢。

某盾能容忍我的小把戏——却是早已上大学。

谢总向总？鸟总要飞走，人总要离去。

我很感激那些给过我关心与帮助的人。只是——

我还是孑然一人，一个被孤独困住的人。

天之涯，地之角，知交半零落。

Problem

Alan 和 Danny 在一座山的两边。初始时两人均在海平面上。他们想在山上的某个位置碰面，并且任意时刻两人所在地的海拔高度都相同。这是否总是可行的？

山就是一条折线段，保证一个 \(x\) 只对应一个 \(y\) ，山上每个点均在海平面上，且山两段海拔为 0 。

似乎我 YY 出一个不同的方法？

Problem

无穷平面上有两个点 \(A, B\) ，两点距离为 \(D\) 。\(A\) 一步可以移动到距离不超过 1 的地方。而且 \(A\) 移动后可以知道距离 \(B\) 是远了还是近了。求一种方法使得 \(A\) 移动 \(D + o(D)\) 步后两点距离不超过 1 。\(f(x) = o(g(x))\) 表示 \[\lim_{x \to \infty} \frac{f(x)}{g(x)} = 0\] 。

已填坑。

鼓起勇气用一次大号，结果……结果 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 就不做了 →_→

Problem

有两个多重集 \(A, B\) ，每个多重集内有 \(n\) 个元素，所有元素都是 1 到 \(n\) 之间的整数。

求证：一定存在两个多重集 \(a \subseteq A, b \subseteq B\) ，使得 \(\sum_{x \in a} x = \sum_{y \in b} y\)

感觉再不发就要坑了。

TC 你的官方 solution 真是慢到家了。于是看别人的代码外加自己 YY 把题目搞完了。没坑真是太开心了。

小号回红了不错。

Solution

250 pts

把距离不超过 \(d\) 的两个 v 连一条边，则同一个联通块内的点必定都是鹅或都是鸭。然后 dp 或者直接计算都可以。

500 pts

这个题有个很简单的 dp 。

令 \(f_{i, j}\) 表示最后的两只狼的位置分别是 \(i, j \quad (i < j)\) 的方案数。枚举下一只狼在哪里即可。由于需要判断是否有一只区间内包含了三只狼，我们可以对于每个位置 \(i\) ，预处理出假如 \(i\) 是倒数第三只狼，最后一只狼的位置至少是多少。这就是一个简单的区间覆盖问题了。

代码超好写，我一开始想丑了 T_T

1000 pts

容易知道，一定存在一条边，使得最优的两棵子树在这条边的两端，且其中一棵子树的根是这条边的一个端点。我们枚举这条边，再枚举这个端点是 \(a\) ，再枚举另一棵最优解的子树的根 \(r\) 。

于是我们的问题变成：给定两棵有根树，要求给这两棵树删掉一些子树，使得删掉子树后的两棵树同构。由于枚举了根，判断两棵树同构的条件可以简化为点是否一一对应，即：根是否对应，根的每个儿子是否一一对应，根的儿子的儿子是否一一对应……

考虑 dp 。令 \(f_{i, j}\) 表示在第一棵树中子树 \(i\) 对应为第二棵树中子树 \(j\) ，最多可以对应多少个点。首先根肯定与根对应，对于 \(i\) 的每个孩子 \(x\) 与 \(j\) 的每个孩子 \(y\) ，将子树 \(x\) 对应为子树 \(y\) 的最大数目为 \(f_{x, y}\) 。于是这就变成了一个匹配问题：如何合理选择配对方式，使得总数目最大？费用流即可。

SPFA 都可以写错我真是没救了。

situation

早上八点起床八点半到机房。前一段时间的 TX 对我的身体（特别是视力）造成了极大的摧残 →_→ 所谓封闭开发简直是用生命在开玩笑。

刚好 ryz 也准备做，早上 9 点的 TC 不多见的。

开场后先开了 250 ，发现是大水题，于是开写发现各种脑残。本来只要并查集就好了的我还建了个图 →_→ 最后就只剩 180+ 了。

然后开 500 。第一反应居然是如果包含了其余线段那么这根线段没用（有没有发现这个想法完全倒了？）。顺着这个错误思路继续想居然想到了 dp 。然后考虑预处理发现我这个想法是错的 233 ，应该是被其余线段包含则没用了。于是发现预处理好写极了～于是发现 dp 也好写极了～但是前面一段时间蛋疼的绕了很久于是分数很低 T_T 果然写之前应该想清楚么。

1000 pts 的看了就没啥想法。考后看了 CLJ 的程序看到用了费用流，又想起以前一道题，两个想法合起来发现就可以做了。复杂度神马都是浮云～

最后没有 FST 真是太开心了。

others

WJMZBMR 过了 1000 pts 于是 #5 大涨。目测快要 target 了～

我似乎前两题手速不差混到了 #30 啦啦啦回红了。（可是我明明两个题都脑残了好久的，特别是第二题…… XLk 要做的话目测可以 #10-）

scottai #31 被怒踩 233

cgy FST * 2 真是太凄凉了。 #129

ryz 第一题手残导致大部分时间都在第一题上了于是 500 pts 的没写完 #171

似乎 liouzhou_101 爆零了。他最近一段时间都没状态？

湖南卫视《成人礼》需要友情观众，所以我就去酱油一把好爽～

不过各位就不要期望在电视上看到我了，茫茫人海肯定看不到我的 233

晚上回来已经是 11 点了，共计耗时 5h 。

我居然看到了 pty 和 zzx ？但是没看到雅礼和一中的诶。

参加成人礼的大部分人都不是 18 岁的我就不吐槽了。

有同学说“我的梦想是成为海贼王”，于是心生邪念想起了以前的一个老哽：“我一定要当/上海/贼王”。于是被黑成了上海贼王。

老师要求穿校服，校衣校裤都要穿。等我们到现场后，主持人说——你们把外衣脱了吧……更囧的是，大部分人把外衣（秋季校服）一脱，里面还是件校服（夏季校服）。

一开始屹大王说想换座位，因为宣誓的时候两个领誓人一左一右在他旁边。我说要不我和你换吧，于是屹大王果断不肯，我这个位置据说更惊险 →_→

我就不吐槽了旁边坐着两个托了。我在想，两个托坐在一堆穿校服的人中间真是格外显目啊。

投票什么的都是假的，只需要我们一个认真投票的表情就好了，出卖感情 →_→

有个残疾人来演讲，对此我唯一的想法是——他是来骗掌声的么，说几句话就要停一下，然后友情观众就要鼓掌。

周鸿祎居然来了！要不要怒提一问：如何一键卸载 360 ？

最后收获一个 U 盘作为礼物——

也算得上是与时俱进更新了一回，上个月的 UyHiP 居然被我想出来了真是让人开心～

Problem

对于一个函数 \(f\) ，我们说 \(f\) 是 \(k\) 性质的，当且仅当存在一对正整数 \((a, d)\) 满足 \(f(a) < f(a + d) < f(a + 2d) < \cdots < f(a + kd)\) 。

现在请找出所有的正整数 \(k\) ，使得所有的 \(N^+ \to N^+\) 的双射函数 \(f\) 均是 \(k\) 性质的。

似乎是一个比较简单的题目。

Problem

一个正交平面网格，只能向上/向右走，求从 (0, 0) 到 \((n, n)\) 期望与直线 \(y = x\) 相交多少次。