face艹 megcup 2017

r_64 posted @ 2017年3月26日 15:45 in 未分类 , 1100 阅读

垃圾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:好气哦

if aa[0] == 255 : s += "1"
else : s += "0"

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

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

G

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

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

H

呵呵


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


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter