这几天都忙着高考送考（以及考后狂欢）去了。一年毕业季，一年别离时。

（祝在高考这天生日的同学年年有今日，岁岁有今朝 23333）

IPSC 2013

IPSC 的题感觉蛮好玩的，但是非常难……

我一开始还没组队，然后 dyh 拉我组了一队，然后我就把 xlk 拉了进去。事实证明把 xlk 拉进去是个非常正确的决定。

practice

P

easy：不说了 - -

hard：看了 solution 才发现坑爹啊……居然连 l33t 语都出现了……我还是不吐槽了 >__<

Q

easy： 显然很水 - -

然后我就不会 hard 了 - -

hard：显然平均数是可以被忽略的。我们要构造的是方差，也就是找到一组 \(a_{1, \dots, n}\) 使得 \(\sum a_i = 0\) 且 \(\sum a^2_i = nv\) 。

考虑如下构造：序列长度为 \(2n\) ，且 \(a_{2k - 1} = -a_{2k}\) ，那么第一个限制显然就满足了，第二个限制直接贪心就好。

R

easy 也不难，(a-z)*25+a 就可以了。

然后 YY 了好久的 hard 没想法。于是我把很小的 n 的解的长度打出来放到 OEIS 上搜，发现了 这个序列 。OEIS 上还顺便提了一下某种较优解的构造方法，然后就没有然后了。

题解也是用的这种构造……

formal contest

完全不会啊亲……

所以你是来看题解的话是找不到任何东西的哈哈哈哈。

待我先去研究一番题解……

A

其实我没看题 2333

B

看了一眼后发现……这不是某个经典结论吗亲……

这个题我曾经 YY 过一个证明方法：令一个数 \(n\) 的势能 \(\phi(n) = \frac{n^2}{2}\) 。那么将 \(n\) 分成 \(x + y = n\) 两份时，释放的能量为 \(\phi(n) - \phi(x) - \phi(y) = xy\) ，这表示将 \(n\) 分成若干个数，释放的能量与具体分法是无关的。那么将 \(n\) 分成若干个 1 ，无论怎么分，释放的能量总为 \(\phi(n) - n \phi(1) = \frac{n(n - 1)}{2}\) 。

我以前一位同学 YY 出另外一个证法：考虑图 \(K_n\) ，把 \(n\) 分成 \(x+y = n\) 对应着图上选择两个点集，大小分别为 \(x, y\) ，并将这两个点集之间的 \(xy\) 条边的删掉。那么初始的时候有 \(\frac{n(n-1)}{2}\) 条边，结束的时候没有边（ \(n\) 个孤立的点），所以一共删了 \(\frac{n(n - 1)}{2}\) 条边。

C

easy ：你把函数 t 的值打出来，可以发现 \(t(n) = \phi(n) + 1\) ， \(\phi\) 为欧拉函数。

然后就可以直接跑了。这样会输出一个指令，然后照着这个指令依次做下去就好了。

为啥我和 dyh 都跑不出指令，就 xlk 可以？

hard ：可以得到当 \(b > 500\) 时， \(g(b)\) 一定是 1 。然后每次求 \(g\) 就可以 \(O(1)\) 求，然后会输出一堆点的坐标。然后就不会了……

题解如是说：把这些点的坐标全部画出来，然后可以得到一个二维码，用手机扫描可以得到一句话：88767->7123398 ，然后就是 easy 的节奏了。

D

easy： 就是昨天 R 的 checker 。首先我们想怎样检验一个排列是否出现过？肯定是每次选择最近的一个下一个字母。所以这样就可以 dp 了。 \(f_S\) 表示集合 \(S\) 中的所有元素按照一定顺序全部出现，所有的顺序中，最后一个字母出现的位置最靠后的一个位置是什么。转移的话枚举下一个字母就好了。

我写的比较渣，跑了 10min 才跑出来 >__<

hard：如果继续按照这个思路去做的话， \(f_{S, t}\) 表示集合 \(S\) 的排列中，最后一个元素出现的位置是 \(t\) 的方案数，内存会受不了 >__< 然后我也不会了...

E

居然没人出。。。

F

首先注意到，每次查询有 50+% 的正确率。

easy：三分。我们将序列分成 LMR 三段，每次查询 25 次 L 和 M 的关系，25 次 M 和 R 的关系，然后就可以确定在 \(L, R, M\) 中的哪一个，4 次就可以找到了。

hard：不会……

题解：我的理解是每次随机比较任意 83 枚与 83 枚，最后枚举那个是答案，用概率最大的？ @dyh 你怎么看……我都不好说什么了。

G

参见 Keshavarz-Kohjerdi, Fatemeh, Alireza Bagheri, and Asghar Asgharian-Sardroud. ”A linear-time algorithm for the longest path problem in rectangular grid graphs.” Discrete Applied Mathematics 160.3 (2012): 210-217.

呵呵呵呵呵呵

H

看了半天的 pdf 没找到答案啊……

easy：看网页源代码去 - -

hard：看 response header. 随便设置个包含 chocolate 的 cookie 发送过去，然后就会有一个问题，然后再发送一个 request ，修改 request header 使之包含答案，然后 response 里面就有答案了。

I

。。。

J

easy：xlk 如是说：由于 NAND gate 是 unversal unary gates ，J1。。随便取两个变量 与非 或者是 或非 ，然后就有六种了。然后看xy一不一样，如果一样返回xz的与非，否则随便返回一个。

hard：我想了一下，似乎可以直接爆搜所有函数？想起来都觉得好麻烦啊 >__<

题解如是说：不满足以下五个条件中的任意一个的函数就是 universal 的：

1. 如果输入全是 1 那么输出 1
2. 如果输入全是 0 那么输出 0
3. 如果把某个输入的 0 改为 1 ，则输出的结果不会由 1 变为 0
4. 如果把所有输入取反，那么结果也会取反
5. 每个输入要么总与输出相关，要么总与输出无关

K

easy：分开计算，直接乘起来。

hard：直接考虑下来的一步，如果这一步有 1 个格子，则上去有 1 种方案；有两个格子，则上去有 2 种方案；etc。然后还是递推一下就好。

L

easy：手玩吧哈哈哈哈

hard：不会……

我居然没去看看 hard 的形状，罪过罪过。

这就是个 3-SAT 问题啊……然后自己写个程序爆搜或者直接找第三方程序吧。

我以前一直很喜欢玩这种东西的啊，居然没发现 >__<

M

不会