已填坑。

鼓起勇气用一次大号，结果……结果 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\) 相交多少次。

好久没更了。

Problem

给定一个 0/1 序列 \(S\) ，执行 \(S \leftarrow S + inv(S)\) 无数次后，证明小数 \(0.S\) 一定是无理数。 \(inv(S)\) 表示将 \(S\) 中的每个 0 变 1 1 变 0 ，例如 \(inv(0111) = 1000\) 。

呼啦啦啦终于回来了。这几天借着腾讯马拉松去深圳玩了一趟，马拉松后顺便在深圳玩了半天。

4-19

早上从长沙出发，大概在下午三点的时候到了深圳。腾讯有人在接送。由于长沙有高铁还是比较方便的，于是我就坐高铁了。CSU 还有几个人也是同一辆车，可是我不知道他们在哪个车厢囧。由于还有人没来，我们就在深圳北站等。等的时候无聊，于是工作人员就要我举着哪个啥腾讯马拉松的牌子摇啊摇，还录了像囧，居然还保留进了最后的视频里面大囧。

接下来就去酒店。我去的时候室友已经来了，中山一中 wzm。由于两人习惯的语言问题，导致语言交流有一定的困难……不过普通话说慢一点还是可以的。吐槽酒店有一个 wifi 叫做 MapleLeafHotel ，但是连不上……于是还要建立一个 wifi 热点。

晚上有个啥破冰活动。我居然看到了 cqx ……重点是他居然认识我，我和他基本上没有交集的……当时我就蹭在 cqx 旁边。我感觉我、wzm、cqx 三个人真就是当时的业界毒瘤，cqx 应该就是毒王了。一开始自我介绍的时候 cqx 基本上是主持人提个问题就回答一个，而且回答的都非常囧。我和 cqx 大概是“被”自我介绍地最多的两个人了。

想起一件事：主持人在上面讲，我和 cqx 在下面聊天，于是主持人对 cqx 吐槽：你怎么就只看着他不看我呢？你们两个是不是有什么秘密？cqx 回应：那是因为你魅力不够。

有个活动是把一首歌的各句歌词拆开，给每人一句，要求根据歌词把组分好，每组内的歌词是同一首歌的。于是看到这些歌我的眼睛彻底瞎了。有些啥啊，《春天在哪里》《卖报歌》《读书郎》《小燕子》。要不是我 xx 我还真就组不上来呢。拜托都是大学生了你还要别人唱这东西。求求你换首歌吧。

还记得 cqx 没有交某个表格，上面要填一个 idea 。于是我就随口说了句一键卸载 360 ，然后 cqx 还真就写上去了，我的三观……

cqx 说他没有带衣服过来换洗，于是向工作人员申请多拿了件衣服，于是我也跟着蹭了件衣服 2333 （其实是给某某带的一件）。话说最后 AC 说他那件衣服穿不下问我要不要，于是我又获得衣服一件真是开心。本来就是去蹭衣服的嘛……

晚上有场 CF#180 。看了前两题后没啥好的想法，于是就没交了。后来看到成绩真是惨不忍睹。完全是靠 AB 两题的手速来混的，CDE 基本上没人出啊。

4-20

于是昨天晚上莫名其妙和别人聊天聊到凌晨两点。然后又喜闻乐见失眠了，然后 6 点就醒了，好囧 →_→

一开始由于 wzm 看错时间以为餐馆在 7 点钟以前开，所以我们 6 点多就起来了……

早上还有些精力。到了腾讯公司后每个人要将自己的创意是吧，于是我随手又 YY 了个创意，希望不要坑队友呢。前面是一堆 ACMer，后面是一堆设计师。ACMer 各种没创意，设计师各种 TLE →_→ 然后每个人要投票，选出几个最喜欢的项目以及自己最想要的人。我只能期望不坑队友了。

吃完中饭后就开始干活了。不得不说这里的便当还真不错，起码比学校食堂的好 →_→ 由于腾讯精心选择时间导致这天下午是 MS 的复赛，于是我就蛋疼了。看了题目后本来想做一做的，但是无奈开始犯困毫无状态做不下去，于是在两点半的时候把账号给了 XLk ，请他帮我做做，XLk 令人感动地帮我进了 onsite （XLk 你真是太好了）……我一直在看看题目没啥好想法，我们组内有人到外面去逛了一圈，发现旁边一个房间的两个组全体做 MS 真是让人感动。

一开始我负责的是 Gale-Shapley Algorithm 的实现，这个很快就搞好了，但是我们队没前端很不给力。每个队有 3 * ACMer + 1 * 设计师，我们队有两个坑爹的家伙（我和 wzm ），还剩一个人根本就没写过网页 →_→ 于是一开始还准备用 WordPress 。前一段时间在写 OJ 的时候接触过 Bootstrap ，感觉一个简单的 HTML 够了，于是写完 Gale-Shapley Algorithm 后转型前端开始鼓捣 HTML 。然后原来的前端师变后台了……

cqx 和我吐槽 MS 。他一开始想写 20 + 20 的，结果 B 的 20 没写出来，怎么交怎么 WA ，于是就……爆零了……事实证明只要 20 + 8 就可以了……

晚上还有场 TCO 的。我这个渣状态居然也想去参加 TCO ？怒爆一零人民群众喜闻乐见，刚刚红起来的小号又黄了。XLk 也混了件 T-shirt 吧。然后莫名奇妙又聊天聊到两点，设计师无奈表示果然我是天坑。

4-21

果然封闭开发不是好受的，简直是在用生命在码代码啊……TCO 后聊了下天然后又开始码 HTML 。其实我很大一部分是在等设计师的图。我们在讨论的时候各种囧，都是尽量简单地想，啥东西不好实现了，就放一张图片算了，反正是 demo 嘛……于是我就只好慢慢等设计师的图片了。

设计师要各种效果，没办法啥都不会只好问问腾讯的 NPC 。CSS 不会啊！！HTML 不会啊！！Bootstrap 不会啊！！由于笔记本上没有 IDE 只好用 Emacs 充上去了。于是怒学 CSS →_→ 由于设计师给我的全是图片，我完全不会定位，于是 HTML 里满天的绝对定位真心丑爆了。

看到设计师还要一段时间才能给出图片，于是我就小憩了一会……小朋友在 HN 省选呢。PYX 打电话过来时真心困死了，随口应了几句他发现了就没说啥了。

下午是产品演示，我就不好吐槽啥了。首先我们的服务器是架构在台式机上的，要演示的话得接到大屏幕上去，于是很囧的那个显示器很久没用了导致我们鼓捣了半天还是没结果，收获了评委的一致吐槽：你们就不能准备充分点吗？然后我在演示的时候，一不小心按过头了把浏览器关了于是搞到一半又要重新来过。接着是 wzm 的繁体中文导致我不得不用 gbk 编码然后在 Chrome 里面还得手动设置编码，屏幕上显示的是一堆乱码囧爆了。还有在提交前的一个小时后台决定改改一个网页结果发现更丑了……于是要产品没产品要创意没创意得到了评委的一致吐槽：其实收养制度和中国的社会体制相关 balabala 于是被轰下台了囧。

晚上有个晚宴，在某个湘菜馆吃的，我表示毫无压力，旁边 wzm 和 AC 表示亚历山大，不得不说这辣味还是够可以的，只可惜饭量太小吃不了多少囧。想起了一件搞笑的事：我们坐车的时候 AC 坐在前面，我和 cqx 坐在后面，cqx 喊 AC 但是 AC 似乎听见了以为是错觉继续听歌。于是 cqx 很蛋疼的打开手机给 AC 打电话：喂是 AC 大神吗？我是 cqx ，你可不可以坐到后面来啊……

晚上就是各自搞各自的事了，不过不得不说腾讯的服务还是挺周到的。

4-22

其实早上就可以走了，但是好不容易来次深圳当然不能啥都没干就走是不，于是托老爸找熟人，找了个地方去玩玩。我去的地方是锦绣中华，等我在一边逛了几个小时后发现还有一半没逛，真是太大了……相机电源表示亚历山大。于是我就只好很囧的半路掏出笔记本给相机充电。抱着个笔记本走路真是奇葩 →_→

晚上有场 CROC R2 。我就不说 onsite 要求 #50 我就是 #51 23333 不过不得不说状态还是回来了，起码还睡了个懒觉的呢，调一个题还半路下了个几何画板一个一个数格子呢。GuyUpLion 都可以涨我就不说啥了。主要是外接键盘手感好吧。

4-23

我勒个去回来的时候被人称作“叔叔”，老了啊 →_→

居然自己做出来了所以说还是很简单的 23333

Problem

定义布尔的乘运算为 AND ，加运算为 OR 。定义一个 DNF （析取范式）为一个布尔函数，返回值为若干个若干个变量的积的和，例如 \(f(x_1, x_2, x_3) = x_1 x_2 + x_2 x_3\) 即为一 DNF 。注意这里定义的 DNF 没有 NOT 。

定义一个对称函数为：接受若干个布尔量，返回一个布尔量，且参数的顺序与返回值是无关的。例如 \(f(x_1, x_2) = x_1 x_2\) 即为一对称函数。

我们说一个函数 A 能用另一个函数 B 表达，当且仅当存在一组参数列表之间的对应关系 \(y_1 = x_{a_1}, y_2 = x_{a_2}, \dots, y_m = x_{a_m}\) ，使得 \(A(x_1, x_2, \dots, x_n) = B(y_1, y_2, \dots, y_m)\) 。例如函数 \(A(x_1, x_2, x_3)\) 表示求 \(x_1, x_2, x_3\) 的众数，可以得到 \(A(x_1, x_2, x_3) = x_1 x_2 + x_2 x_3 + x_3 x_1\) ，令 \(B(x_1, x_2, x_3, x_4, x_5, x_6) = x_1 x_2 + x_3 x_4 + x_5 x_6\) ，可以知道 A 能被 B 表达。

现在有两个问题：

1. 对于所有的 DNF ，都可以找到一个对称函数使得其能表达这个 DNF ？
2. 对于所有的对称函数，都可以找到一个 DNF 使得其能表达这个对称函数？

题目似乎很绕……→_→

有点线性代数的味道。

Problem

有一个 \(n \times n\) 的矩阵，每个格子内有一个数。你每次可以查询一个子矩阵的权值和，求找出主对角线上点的权值和的最少需要多少次查询。