AFAIK

Valar Morghulis

Problem

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

Read more »

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


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

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

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

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

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

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

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

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

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

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

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

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

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

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

“那就去爱人吧。”

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


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

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

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

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

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

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

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

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

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

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

谢总向总?鸟总要飞走,人总要离去。

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

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

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

Problem

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

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

Read more »

似乎我 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\]

Read more »

没想到坑的居然是 C 题 →_→

已填坑。

鼓起勇气用一次大号,结果……结果 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\)

Read more »

感觉再不发就要坑了。

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\) 性质的。

Read more »

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

Problem

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

Read more »
0%