face艹 megcup 2017

垃圾F，毁我青春

先把初赛题写了吧

谷歌识图 发现是个二维码，就想怎么把它写成标准的二维码

假想这个图是一个圆柱体的侧面，你正在往里面看，那么把圆柱体沿着$x$轴负半轴切一刀展开就成了我们想要的那个二维码

然后把输入图中的像素$(r\cos\theta,r\sin\theta)$映射到$(r,\theta)$就好了

其中$\theta$的取值范围是$(-\pi,\pi]$

然后这次做了一晚上F还没做出来。。韩红听了都想打人

放一些嘴巴向的题解吧

A

大模拟，每收到一个人的提交记录就重构整个图，求答案时用高斯消元，$f_j=\sum_if_i\frac{\delta(i,j)}{\sum_k\delta(i,k)}$。

B

对$A,B$，可以求出输入$A,B$作为参数之后生成的png图片与给定的图片的距离，距离就是什么像素差绝对值之和啥的，xjb定义就好

然后最小化这个东西 就可以乱搞了

我的策略是先随机撒点，撒出较好的初始解，然后爬山，其中需要各种调参。我用的是比较蠢的炼丹术。。就是先有一个比较粗糙的解，然后步长比较大地爬山，发现找不到更优解的时候就减小步长

到最后，距离比较小(几千——这意味着绝大多数像素一样)的时候，答案离当前点肯定很近，暴力就好

C

fuck♂you

UPD1:根据稳爷爷对别人程序的研究，这题的解法是这样的。。非常牛逼。。

大致就是。。因为网页的传输都是使用zip之类的压缩算法进行传输的，所以考虑传输一个sid和一个其他参数q，如果q是sid的子串那么传输的内容会小一些，只要能抓到传输内容的长度，就可以通过若干次传输大概摸清楚sid长什么样。

D

matrix67原题。。Google锈规作图第一个。。只是觉得不可写($|AC|$小的情况好麻烦啊>_<)

E

rank1的哥们居然是写随机撒点。。佩服，佩服。

考虑求出所有点的两两的中垂线，再考虑边框$(0,0)-(10000,10000)$，这$\binom{n}{2}+4$条线将平面分成若干区域，求出所有线两两的交点，就变成了一个$O(n^4)$个点的平面图。作为一个对平面图非常(you)熟(ban)练(zi)的人，当然轻松写完啦。

F

写了一晚上。。也不知道wa在哪里

就是高斯消元。。考虑$x_{i,j}$表示格子$(i,j)$的中心是否画十字，那么$x_{i,j}(1\le i\le 3)$即前三行的$(i,j)$作为变量，其他$(i,j)$都是能从这些推出来的。你考虑“格子$(i-3,j)$在画十字之前是白色”，就可以写出$x_{i,j}$的递推式，最终可以把所有$x_{i,j}$表示为前三行的线性组合。然后“格子$(i,j)(n-3<i\le n)$是白色”就是一个方程，解这个$3n$个变量$3n$个方程的方程组，就可以得到方案。

解可能不唯一，但是经过测验$n=2000$时只有$12$个自由元，所以爆搜就好了。

复杂度大概是立方级别。。可以压位。

UPD2:这一段话。。由于我的程序没过。。所以不保证准确。。

UPD3:好气哦

我原来主程序是对的啊 输入错了啊

把代码中的"1"和"0"对换，就对了啊

G

随机撒100或200个点，找到哪个点是小于你询问的点且最大的，顺着它一路往下走就是了。

这题很良心，允许你$25\%$的错误率，我就写wa了一次错了一个点，然后脸不好错了一个。

H

呵呵

嗨呀打一天的比赛累死了微积分还没做呢mdzz今天除了B题炼丹以外毫无收获吧这点时间还不如踢踢实况听听小黄曲