Problem

三只蜘蛛想要在一个立方体上抓住一只虫子。已知虫子的最大速度是蜘蛛的最大速度的三倍，且蜘蛛和虫子都只能在棱上活动。对于任意的初始局面，蜘蛛是否都能抓到虫子？

UyHiP 的题目感觉很杂，相对来说 TOAD 就好玩多了嘛。

Problem

给定一个无向图，点有黑白两种颜色。每次你可以选择一个点，并把这个点以及所有和它相邻的点的颜色取反。初始时所有点的颜色是白色。

是否能在有限步内把所有的点全部变成黑色？

原题链接如下

这个题目似乎比较简单。

Problem

某国有 2kw 选民，国王的支持者只占 1% 。现在有一种“民主”的选举方式：我们将全部的选民分为 \(n_1\) 组（每组选民数目相同），每组内的选民再分为 \(n_2\) 组（仍然要求选民数目相同），再这样分下去，直至只剩一个人。每一组的投票结果为这一组分成的若干个小组的投票结果中，出现次数最多的候选人。如果有多个相同的，我们假定国王会输。

是否存在一种分组方式，使得国王通过一定的分配方案使得他获得整个选举的胜利？

少了个特判被 cha 好桑心……

1k 原题什么情况！我勒个去。

Solution

250 pts

结论： \(n\) 为奇数是先手必败。若 \(n = 2^k\) 则 \(k\) 奇先手必败 \(k\) 偶先手必胜，否则先手必胜。

证明的话还是归纳吧。不打表我真就不会做。

果然我被坑能力拔群。轻轻松松被 7k+ 坑 →_→

我提问发自真心。

500 pts

显然，对于一个元素来说，如果它不在一开始的位置，则在其他任何位置的概率是相同的。

于是我们可以递推出 \(k\) 次操作后，每个元素在初始位置的概率。不妨设 \(f_i\) 表示 \(i\) 次操作后的概率，可以得到递推式：

\[f_{i+1} = \frac{n-2}{n} f_i + \frac{2}{n} \frac{1}{n-1} (1-f_i)\]

前一半表示一开始就在这个位置的概率，后一半表示交换回来的概率。

如何计算答案？我们计算每个元素对答案的贡献。枚举每个元素，再枚举最后的位置 \(x\) ，则对答案做出的贡献是在这个位置的概率乘上这个数的值再乘上这个位置被子序列包含的概率。

1000 pts

原题什么的，我就只能说自己做题太少了。没坑好神奇

以下是 xiaodao （蒯）的方法，我觉得非常漂亮。

大家见过的构图大部分是 S -> x -> y -> T 这种图吧。这次的构图是 S -> x -> y -> x -> T 好奇葩。

我们把白点按照列数的奇偶分成两种白点。则黑点每次在两种白点中要各取一个。于是前一个 x 表示的是第一种白点，后一个 x 表示的第二种白点，中间的 y 表示黑点。为了保证一个黑点只会被流一次，我们需要将 y 再拆点，流量上限 1 。

这种建图的关键是每一个 L 形被一条增广路所表示，利用白点列数的奇偶性非常巧妙。写起来非常好写～（有 SAP 模板就是爽）

situation

首先看完 250 ，发现不会做。以前见过一个除法的，特水，分解质因数即可。减法的还真就不知道怎么做。

看了一下样例，感觉没啥思路。而且 \(n\) 的范围是 \(10^{18}\) ，普通分解方式还应付不了，所以不会是质因数分解这方面。决定赶紧写程序打表。表倒是好打，发现奇偶性很有规律的样子，于是把必胜/必败与 \(n\) 的奇偶性无关的提出来，发现一定是 2 的幂。然后就好了。

怒开 500 。看完第一段感觉很开心的样子，想到了 CF 某题，那个题是动态维护每个点最后在某个位置的概率。继续看下去发现有个啥还有个期望子段和，感觉就是这样了。再一想发现没具体给定交换，那么动态维护的矩阵一堆相同的数，不同的数只有 2 个 →_→ ……稍微推了下发现是可行的。怒写代码，430+ 分好爽。

然后开了 1000 pts 的，想了一下觉得没啥好做的，于是就坑了 →_→

Challenge 的时候发现 250 pts 的被 Cha 了，原因是忘记判 1 这个特殊条件了 T_T

幸亏过了 500 pts 否则就爆零了。

最后 #136 ，由于是小号还是可以涨的。只涨了 52 。（下次可以涨红吧？） 不要立 flag ！

others

Petr #1 rejudge #2 meret #3

wuzhengkai #15 。250 居然 FST 真是无语。

ChnLich #18 和我一样第一题被 cha 。

xiaodao #20 rating 和我一样了。上次 Seter 给 xiaodao 跌了蛮多的。

tourist #21 因为 1000 pts FST 了。

7k+ 居然用大号！cha 人 cha 的丧心病狂。#23

scottai #71 过前俩题正常节奏。

liouzhou_101 的 500 pts 只有 200+ 分，所以他俩题加起来没我一题多…… #143

秋锅第一题看错题了光荣爆零。

耀爷一开始说他不想做了，于是硬把他拉过来做……不过考到一半没网了好惨 →_→

nonsense

祝大家 CTSC 好运。

不能太颓废了，得开学习模式了呢。

似乎 Matrix67 大大已经翻译过了。

Problem

一个长度为 \(n\) 的 0/1 串，A/B 俩人博弈。每次操作如下：

1. 如果当前串首是 1 ，则放一个 0/1 到串尾，由 A 决定
2. 如果当前串首是 0 ，则放一个 0/1 到串尾，由 B 决定
3. 删除串首，重复以上过程

如果有限步内这个串全是 0 ，则 A 获胜，否则 B 获胜。

问什么情况下 A 必胜。

呼啦啦准备翻译完 TOAD 。这些题真心虐心啊……

今天说的这个题有一个众所周知的方法。但是还有一个非常漂亮的解法，我相信还是没多少人见过的。

Problem

有 \(n\) 个人坐在一张圆形桌子前，每个人面前有一盏灯。现在 A 和 B 博弈。流程如下：

1. A 选择若干个位置，并把选择的结果告诉 B
2. B 把桌子转一下
3. 把 A 选择的位置的灯的状态同时取反
4. 重复以上过程

游戏终止的条件是存在某一时刻，使得所有的灯都是亮的。游戏终止则 A 获胜，否则 B 获胜。

A 随时可以调整策略，即 A 每次决策的时候可以看到现在灯的状态，并做出反应。

问：什么情况下 A 可以获胜。

新生活。

看到一个很好玩的题，来源于 TOAD 。

Problem

给定一个正整数三元组 \((a, b, c)\) ，每次可以选择任意两个数，不妨假设选择 \(a, b\) ，且满足 \(a \leq b\) ，则可以把这个三元组变换到 \((2a, b - a, c)\) 。

求证：任意一个三元组经过若干次变换后，总可以使一个数为 0 。

一次多好的进前五的机会啊，居然被浪费了。

最近 FST 特别多，这状态怎么搞腾讯的比赛咯。

最后 #39 不算很坏的结果，但起码 E FST 了很桑心。

Solution

A

先把整个序列用 ab 染好，最后 \(k - 2\) 个从 c 开始赋。

当然，搜索也是可以的。

B

可以发现前 \(k\) 个与后 \(n - k\) 个是无关的。由于 \(k\) 特别小，直接搜索 \(2 - k\) 个值即可。复杂度 \(O(k^k)\) 。

C

不妨考虑 \(p_n\) 应该是多少。令 \(x\) 表示最小的不小于 \(n\) 的能表示成 \(2^k - 1\) 的形式的数，则 \(p_n\) 的最优解显然就是 \(x ^ k\) 。继续考虑下去，可以发现对于 \([x^n, n]\) 内的每个数我们都可以找到唯一的对应关系。剩下的数递归就好。

D

不妨设为有根树。考虑枚举 \(a\) 到 \(b\) 这条路径的 LCA \(t\)。我们要从 \(t\) 的子树中选出两个点，使得它们的 LCA 是 \(t\) 。这样的方案数是有 \({size_t \choose 2} - \sum_{x \textrm{is a child}} {size_x \choose 2}\) 。 \(t\) 的子树外我们任取两个点即可，方案数为 \({n - size_t \choose 2}\) 。考虑到如果两条路径分布在不同的子树，这种情况我们会计算两遍，所以我们还要把这种情况剪掉。然后就没了。

E

一个显然的数位 dp 。我们预处理两个值 \(f_i, g_i\) ，分别表示所有的 \(i\) 位幸运数相邻两个的积的和以及所有 \(i\) 位幸运数相邻两个的和的和。于是我们有如下递推式：

\[f_{i + 1} = 2 f_i + 65 * 100^i * (2^i - 1) + 11 * 10^i * g_i + (\frac{10^i - 1}{9} * 7 + 4 * 10^i) * (\frac{10^i - 1}{9} * 4 + 7 * 10^i)\] \[g_{i + 1} = 2 g_i + 22 * 10^i * (2^i - 1) + 11 * \frac{10^{i + 1} - 1}{9}\]

\(f\) 的递推式可以这么想：任意三个数 \(x, y, A\) ，我们有 \[(x + A)(y + A) = A^2 + (x + y)A + xy\]

那么当从 \(f_i\) 递推到 \(f_{i + 1}\) 时，我们需要加上 \(2^i - 1\) 个 \(A^2\) ， \(g_i\) 乘上 \(A\) ，以及 \(f_i\) 。 \(A\) 有两种取值，一种是 \(4 * 10^i\) ，一种是 \(7 * 10^i\) 。最后再考虑一下多出来的一个积即可。

\(g\) 的类似。

求出 \(f\) 和 \(g\) 后，剩下的就简单了。从前往后扫，每遇到一个 7 就计算对答案的贡献。

situation

今天真心不顺。

先是卡 A 卡了 12 min 。我想写贪心，但是各种怕特判，于是决定写搜。但是搜的一个地方忘记特判导致挂了……

看了 B 后觉得蛮简单的，写完后 A 掉。

看 C 。感觉这个题应该蛮简单的，但是没灵感，遂决定放到一边去。

看了 D 后第一想法是点分治。后面一项分什么治啊，直接 dfs 不就好了吗。我分了好几种情况，交了后发现 WA 了。怒决定写拍。发现拍比正解还难写啊。写完后发现我少考虑了几种情况。经过情况的合并后发现就两种情况嘛。和暴力拍了 20 以内的无误后交了。

然后转过去看 C 。第一想法是一位一位的来，然后就突然想到配对了。 \(2^i\) 显然是和 \(2^i - 1\) 配对嘛。按照这个思路下去就想到了那个构造，于是就好了。

现在大概还剩 50min 。发现 E 有人过我就去看了一下 E 。看完后瞬间就有想法了，于是推了一下公式后发现是可做的，怒写数位 dp 。写着写着发现只有 10+ min 了，我还没开始调试呢。最后在 1：58 的时候交了一个上去，过了 pretest ，对不对只能听天由命了。

结果 AE FST 了。如果任意一个都没 FST 的话应该可以红的。幸亏过了 D 。不然后果不堪设想呢。

最后 #39 被 liouzhou_101 怒踩。按照这 FST 率下去我真就只能专业算法三十年了。要搞 ACM 的话就找一个代码能力强的吧。

others

wjmsbmr 直接 #1 ，好强大……（现在 wjmsbmr 已经超过我大号了）

liouzhou_101 #38 。

只要 E FST 的人都没有好下场。

感觉第一题蛮好 cha 的。只可惜我没时间了。

感觉今天的 ABC 是主流吧。 squarefk、vfleaking、flydutchman、秋锅都是前三题，只不过速度差异有点大。

大叔只过了前两题，顺利跌回 div2 。

nonsense

今天腾讯打电话过来说进了区域赛了，到时候可以去免费深圳玩玩～

本来就只打算拿件 T-shirt 的。600 挂了就挂了吧。

或许按照这个趋势下去，我有淡出 ACM 届的趋势？还是专注算法三十年好了。

Solution

300

裸贪是不对的。

于是写 dp 吧。 \(f_{i, j}\) 表示前 \(i\) 个字母中，保留 \(j\) 个字母所组成的最优的 S 串，以及在 S 串最优的前提下最优的 T 串。转移枚举这个字母取不取就好了。

开黑什么的，还是不要搞的为好。

600

考场上写了个莫名其妙的搜索，当然是 FST 的命运。

考后想高斯消元应该可做啊，于是随手写了个高斯消元。连样例都没调，连我自己都觉得这是错的，结果发现居然过了？我勒个去。

首先特殊情况是 \(n > m\) 其中 \(m\) 表示有多少个已确定的元素。在这种情况下，一定存在一行一列使得这一行一列上没有已确定元素。于是除这一行一列外的其余的元素随便填，到最后还剩下这一行一列的时候，再枚举每行每列的和是多少，那么每个元素的值都会确定，并且一定存在一组可行解（显然），所以答案就是 \(10^{n^2 - 2n + 2 - m}\)

\(n \leq m\) 时的情况比较难处理。不过说到高斯消元大家应该就知道这题该怎么做了。为了解决 10 不是质数，我们利用 CRT 分解下就好。一行一列相等，这个可以表示成一个方程。一个变量的值确定了，我们也可以把它表示成一个方程组。那么共有 \(n^2\) 个未知数，有 \(n^2 + m\) 个方程。去掉其中线性相关的方程后，答案就是模的自由元次方。再判判无解什么的就好。

1000

看完题的第一眼觉得这是水题。仔细想想后发现不会做。经过文学巨匠 wzy 教导后觉得这题怎么还是水题，写完后发现这想法是错的，重新想发现是神题，写了好久总是过不了，调啊调调啊调调了一下午终于发现错误了—— LCM 要用 long long 存……我的天啊

看完题的第一想法是对每个不同的基分开统计。于是我们要求当 \(x\) 从 1 取到 \(A\) ， \(y\) 从 1 取到 \(B\) 时，共有多少个不同的 \(xy\) 。其中 \(A\) 的范围很小，只有 30 。 \(B\) 的范围是 \(10^9\) 。

文学巨匠的方法如下：对于一个 \(x\) ，它最小的质因子为 \(d\) ，则 \(x\) 对答案作出的贡献是 \(xB - \frac{xB}{d}\) 。加起来就好。显然这是错的可是我居然没发现。

考虑容斥。暴力 \(2^A\) 的容斥显然是不行的。于是考虑将若干个类似的状态一起表示出来。假设一个数 \(n\) 可以同时被表示成若干个 \(xy\) ，则 \(n\) 一定是所有 \(x\) 的公倍数。于是我们可以设计一个 dp ： \(f_{i, j, k}\) 表示前 \(i\) 个数中，我们选取了 \(j\) 个数，这 \(j\) 个数的 LCM 为 \(k\) 的方案数。 \(f\) 的转移很简单，枚举这个数字选不选就好了。由于 \(n\) 要能被表示出来的话，一定有 \(\frac{n}{\min \{x\}} \leq B\) ，于是我们可以从大往小 dp ，每选中一个数，那么它一定是已选中的数中最小的，在这个时候计算方案数即可。

一个小小的优化是对于只包含前若干个质数的数用 dp ，其余的数仍然爆搜。

然后就可以过了。

situation

开了 300 后感觉这是个水题啊，于是 YY 了个贪心，大概就是把上下的绑在一起，用一个栈处理一下。但是这样做是过不了样例的。瞬间想起了 dp 。然后就只有 260+ 分了。看起来样例蛮有良心的。

penicillo 你 299.80 分是什么心态。

然后开 600 。看完后第一想法是 \(n\) 大的话很好处理， \(n\) 小就不好搞了。于是我决定写搜。我的方法是找一个空格子，使得这个空格子所在的十字内的已选格子尽量少。然后爆搜出一个小矩形的，这个矩形的大小具体有多大我也不知道 = =|| ，但是肯定很小就是了。对于其余的格子，我猜解的数目等于 10 的自由元次方，但是这是错的 T_T 于是光荣 FST 了。

写了正解后发现正解比爆搜还好写些，什么心态。

1000 看完题目就溜了。

最后过了 300 #90 。由于是小号所以仍然可以涨 LOL 。

others

各种奇葩不忍直视。

tourist 前两题都好慢的说，但是靠 cha 人 cha 到了 #3 真是不忍直视……

有人只交了第一题 FST 后仍然有 300 分，丧心病狂。

wuzhengkai 被我怒压 0.03 分……

大部分人是过了第一题，scottai #205 edly #209 xujie #350

target 君 tomek 居然 #375 ，只交了 140+ 分然后怒 cha 错三个。

lyrically 被 cha * 1 FST * 1 最后靠 cha 人没爆零。

cgy4ever FST * 1 加上 cha 错一个导致爆负，太可怕了。

大叔又一次爆零了……但是令人惊悚是……他……居然……涨了……

没 TeX 心里痒痒的，用的真心不方便。其实用 TeX 的一大理由就是它的公式。显示的很漂亮。偏偏干这一行的公式比较多，特别是在复杂度那一块，没哪些题是不需要涉及到复杂度的。于是痛下决心看能不能支持 TeX 呢？首先可以用 MathJax 。但是 MathJax 太慢了，而且占网速，总之我不喜欢……

于是搜索一堆东西，首先对 Pandoc 有期望，然后发现不会用。后来在本地看到一个叫做 Marutex 的东西。 Maruku 是 jekyll 用的 markdown 渲染器。Marutex 会不会支持 TeX 呢？让我们拭目以待。

事实证明，在 blahtex 的帮助下，Maruku 是可以支持 TeX 公式的。 Blahtex 是一个转换器，调用了系统的 TeX 解析器，利用 dvips 转成 png。初看起来效果确实是不错。由于 png 支持透明，公式就像是普通文字，这点尤其舒服。

但是，很囧的一点，blahtex 生成的图片背景透明，文字是黑色的，而我 blog 背景默认也是暗色调的，因此公式看不太清，这点特别囧。于是我们有两种解决方案： 1. 换一个 blog 主题 2. 改动 png

由于这个主题是我比较满意的，特别是背景我特别喜欢（我个人比较喜欢这个风格的画），所以决定使用第二种方案，改动 png 。

由于最终免不了调用 TeX 的解析器，所以我们可以直接在 TeX 源文件上做文章。我的第一想法是用 color 函数，直接把字体颜色改成白色。看了 help 后发现可以直接用命令行参数来设置。由于我不知道 Maruku 在哪里设置 blahtex 的参数，于是我决定自己写个程序来实现。这就不免涉及到外部程序的调用。

据我所知，一个程序调用了外部程序，则被调用的程序的 stdin、stdout、stderr 均会继承父程序的。可是我写了程序后发现明明 stdin 被继承了，可是仍然输入不进。一个不到 1K 只有 20- 行的程序我看了好久硬是没看到哪里有问题。最后发现， execve 的第二个参数这个数组的第一个元素必须和第一个参数一样……浪费了好多时间囧……

中间有个插曲，某一次我在生成 png 的过程中，只生成了一个 hash 用的 txt ，png 没有生成。结果下次启动 jekyll 的时候总是报错，我一个一个包的排查最后发现把某个临时文件夹清空就好了。

好的，现在可以调用外部程序了。可是字体颜色怎么还是黑色呢？经过不断努力地尝试，我发现了原因： blahtex 会使用一个叫做 preview 的包。这个包会覆盖 color 函数所设置的颜色。于是我干脆就不使用 preview 这个包了。发现 jekyll 不断报错，实在没办法了我就只好去看 Maruku 调用 blahtex 的实现。又参考了一堆的 help ，原因是： blahtex 需要 preview 这个包才能提供生成的 png 文件的尺寸，而 Maruku 需要 blahtex 提供尺寸来进行 png 的缩放。

然后我又蛋疼的去查如何获取一个 png 的尺寸。又准备写程序了 = =||

最后实在无聊，我把直接修改 html ，把 html 代码中和 png 大小相关的东西全部删掉，发现 png 能够正常显示。那就这样吧。于是最后我决定直接把 Maruku 中所有和 png 大小相关的代码直接删掉。似乎终于可以了？看一下效果。

效果

这是传说中的行内公式： \(O(n \log n + n \sqrt{n})\) ……应该没大 bug 吧。再看看所谓的行间公式：

\[1 + 2 + \dots + n = \frac{1}{2} n(n + 1)\]

好吧就这样吧。

eggache

蛋疼是没有上限的。我又遇到了一个问题，github 仓库显然没有 blahtex ，如何在访问 github 的时候能看到这些图片呢？

于是最蛋疼的事是：我不得不新建一个 repo ，用来保存 blog 的源代码，然后原来的 repo 只存放生成的 html 以及图片。也就是说原来是 github 渲染 html ，现在是我上传 html 及其相关文档上去，github 只负责显示了。所以每次更新文章很蛋疼的：

git add *
git commit -m "xx"
git push origin master
jekyll --no-auto ../roosephu.github.com
cd ../roosephu.github.com
git add *
git commit -m "xx"
git push origin master

不过有了 TeX 的支持还是很不错的。