电力与工业优化联盟（Alliance for Power and Industrial Optimization，APIO）参观记

· · 生活·游记

参观了电力与工业优化联盟，学习了许多优化电力和工业的方法，收获很多，比如说可以通过收少量参赛费，来获取经费。

Day -1

抵达省锡中，初看和“工业”，“电力”没有关系，倒是看到了许多意义不明的“信息学”等词，不知道是什么情况。

进入宿舍后，去饮水机接水，发现饮用水既不是外界传言的红色，也不是同学所说的黄色，而是白色。其中混有许多红色的颗粒物和黑色的粉末状物，十分美味。

不过由此，我才开始意识到什么是“工业优化”：

优化方法之一是减少成本，比如使用优质饮水机就是减少成本的方法之一。

当晚有试机，不知道为什么要试机，可能是为了展示工业和电力的最新成果，感觉确实挺优的，据说 set 跑 2\times 10^6 只需要 0.5 秒。可能这也是一种优化。

喝了十分好喝的饮用水，整个寝室都睡不着，聊到了一点。

Day 0

国家集训队成员带来了关于优化电力和工业的讲座，比如博弈论之类的。

博弈论挺难的，到“无穷小量”这一块就倒闭了，构造倒是听的很舒服。不过图论和集合幂级数完全听不懂。

话说我之前专门做了很多关于集合幂级数的题，Poly 也学了不少，不知道为什么听不懂，可能他讲的内容涉及到了优化吧。

还有神秘开幕式，主持人一直说“亚洲和太平洋地区信息学竞赛”，不知道是什么情况，可能主持人没有弄清楚 APIO 这四个字母的含义。

Day 1

不知道为什么突然告诉我，要我参加什么一场信息学比赛，不过好在我也是学过 OI 的，那就临场发挥吧。

先开第一题，发现是简单题，直接做。考虑如何给出一组数，使得交互库的回答不为 0，一个方法是给出 \{1, 2, 3, ......, m, 2m, 3m, ......, ([\frac{n}{m}]+1)m\}，容易证明这样的回答一定不为 0，因为一定存在 kc\mod n <m。事实上，只需要找出满足条件的最小的 k 以及 kc\mod n 即可。

考虑二分找出最小的 k，然后二分余数，这样的操作代价是 m\log_{2}\frac{n}{m}+m+\frac{n}{m}，求导得最小值在 m=8900 左右时取得。

很快写完，结果发现 pretest 一直报 CE，不知道为什么，搞了半小时终于好的，得了 58 分。

接下来看 T2，发现不可做，看 T3 发现不可做，遂回去继续做 T1。

发现在二分过程中，随着二分区间的减少，如果动态调整 m 能够更优，于是有如下做法：

假设已经知道 n\in [l, r]，如何判断 n 和 mid 的大小关系？ 只需要取 \{1, 2, ......, m\}\cup\{km|k\in \mathbb{Z},km\in[l, mid]\}，如果答案不为 0，则 n\leq mid，否则 n>mid。

有基本不等式得进行一次这样的判断代价为 \sqrt {2(r-l+1)}，每次操作长度减半，故总代价为 \sum_{i=-1}^{+\infty}\sqrt{2^{-i}\times n}，n=10^9 时级数大概收敛于 1.4\times 10^5 左右，得了 78 分。

此时还剩下 2.5h，按理说能够在 T2 和 T3 中拿到至少 130 分，从而得到金牌。然而此时我已经着急了，并且也觉得后两题都不可做，所以并没有看出 T3 是签到，也没有调出来 T2 的 e=m=3 情况，斩获 12+5 的高分。

总分 78+12+5=95，能得到这样的分数的我也是神人了。

下午讲题，完全没心情参加。

Day 2

讲了电阻网络，和电力及工业都很有关，但是可惜只听懂了马尔科夫链那一块。

晚上参加了闭幕式，领了铜牌，铜牌是纸制的，优化掉了制作铜牌的费用。