Ric_shooter
Table_bottom

Petrozavodsk Summer-2017. Warsaw U Contest, XVII OpenCup Onsite

Remilia posted @ 2019年3月17日 16:30 in 涂字 , 57 阅读

ABCDEFGHIJK


复盘人:fz

开场看了A,感觉可以bitset一拨.阿爷觉得K是傻逼题直接过了.

00:12 K AC(+0)

跟了一下D的榜,是个傻逼题,交给阿爷写了一发.

00:16 D AC(+0)

上了一下A的bitset,写完发现题目看错,下机继续想,发现反着做是可以的,暂时先放置了.
跟了一下G的榜,写了一个奇怪的贪心,交了一发之后wa 2,找出反例把自己cha了.
ymm加入战场,开始想之前不太会的E.阿爷推完了H的式子,上去写了一发.我没注意到题目是个交互式题,背锅.

1:17 H AC(+1)

阿爷会了J,上去写了一发,中途我交换着写完了A的bitset版本,交了一发MLE,感觉bitset没救了.

2:19 J AC(+2)

叶队开始写E.获得了若干个wa 5,怀疑是精度有问题,让阿爷帮他卡精度.跟榜开了一下C.

3:21 C AC(+0)

阿爷突然搞出了G的做法,我上去写了一发,转移方程写错了wa了一发.

3:40 G AC(+2)

接下来ymm和阿爷继续调E,我想了一会A,搞了一个hash的做法,rush了一发又wa又mle又T.


复盘人:rxd

开场看了下H,感觉是个数论随便推下。
gt在看A,想了一会儿他感觉会了。我跟榜发现K是傻逼题,然后gt告诉我D是傻逼题。

0h12min:K(+0)。
0h16min:D(+0)。

gt上机写A,写完发现题目看错了。我在推H。gt上机写G。ymm加入战场看J。

1h02min:G -1。

gt发现G是错的。于是我上去写H。写完交了一发TLE 1了,仔细一看发现是交互题。改完过了。

1h20min:H(+1)。

叶队上去写J,我开始了漫长的想G的过程。一直在想怎么把最大值/最小值罗干掉然后规约成子问题。

1h44min:J -1。

叶队发现J题目看错了。于是先让gt写A的bitset做法。其实这里应该先算下空间再决定写不写的。
gt写完交了发MLE 1,然后发现要600多M,并开不下。
叶队跟我说J可以set贪心一下。我表示网络流看起来很对。他听了下也觉得对的。于是我写网络流。边随手开了个20000实际上不够,爆了一发。(WA 122,但Final的时候看不见是WA在第几个点,可能就傻逼了)

2h09min:A -1。
2h19min:J(+2)。

我又想了会儿G,好像终于搞出了一个感觉对的算法,给gt讲了下他也感觉对的,但看起来不像能过这么多队。我先开始写。
写到一半叶队推出了E,我直接在之前的暴力上改了下就过了样例。满心欢喜地一交,WA 5。发现n=1要特判,一改还是WA 5。搞了个python的Decimal,还是WA 5,然后就蛋碎了。

2h31min~2h59min:E -4。

我发现G啥约束都没有的时候好像就不对了,凄凉下机。gt会了C,上去写,一发过了。

3h21min:C(+0)。

我抛开之前所有的做法,往单调栈的方向想,终于想出了G。gt表示这个题他前几天刚讲过……于是交给他了。

3h40min:G(+2)。

然后我想了大概20分钟A,也只想到gt之前那个爆空间的做法。
最后一个小时我想有点贡献,于是就来搞叶队的E。一直在卡精度、试爆,遗憾搞到最后也没过。赛后发现是算法有点问题。
gt最后大概半个小时的时候会了A。然后一直写。map TLE了,unordered_map MLE了,改成手写Hash最后没写完。

滚粗了。


A:考虑某一个时刻相连的点对数量,将每个点在所有并查集里的祖先看作一个vector hash起来,那么答案就是每种相同hash值个数的平方.利用启发式合并保证改变次数.一定要用双关键字hash,否则会WA,一定要用hash table,否则会T.一定要手写各种东西,否则会MLE.

B:题目大意:交互题.要在各维都在[0,r]的d维空间中寻找一个点.每次你可以询问一个点.系统会返回这个点是否比上一个询问的点离答案点近.这里的距离定义为每一维差值的最大值,要求询问次数在100d之内.d<=100,r<=10^9

Sol:先在中心固定一个点,然后从这个点开始逼近.首先花费4d的时间,利用每维+1,-1找到每个最大值以及他们应该移动的方向.接下来,对于每个非最大维,由于我们控制了dis的范围至多为r/2,于是我们在这一维的两个边界上询问一下就知道该往哪里走.然后我们往反方向走,可以得出它到原点的距离是一个和最大值相关的一次不等式x-C[i].最后对于一个最大值,我们采用三分求出正确的x即可.

三分的次数是一个常数,在d=2的时候就够用了,但是d=1的时候次数不够,用一个二分特判一下.

C:考虑每种颜色只会恰好用一次,那么其实可以把序列分为层状的结构.每层里面是独立的,可以单独算.用一个区间dp,利用四边形不等式优化.

D:二进制分解.

E(by yjn):考试时忘记$p_i\ge 0$的限制了。做法反正都差不多……直接让$q_i^2=p_i$的话就是拉格朗日乘数法,然后限制一些$p_i$是$0$,一定是限制$a_i$最小的那些。或者带不等式限制的话,就是个凸优化,KKT条件写出来其实和上面是基本等价的。也是限制$a_i$最小的是0。

F:

G:1. (by fz):由于做到i时,a_i一定在某个序列中,则记录其在哪个序列中,另一个序列一定相应的是最大/最小.
     2.(by rxd):考虑从前往后做,我们希望上升序列的末尾尽量小,下降序列的末尾尽量大。那么把(上升末尾,下降末尾)搞出来,一定是同单调递增的。考虑加入一个新的数会发生什么,如果接在上升序列末尾,会把上升序列都改成i,那么下降的肯定只保留一个最大的。如果接在下降末尾,上升肯定只保留一个最小的。也就是说任意时刻只有最多2个有效状态。

H:枚举gcd,然后上取整、下取整都只有\(\sqrt n\)段,直接暴力就行了。取下整、取上整分别是\(\lfloor \frac{n}{\lfloor \frac{n}{x}\rfloor}\rfloor\)和\(\lceil \frac{n}{\lceil \frac{n}{x}\rceil -1}\rceil-1\)。

I:

J:把所有端点离散出来网络流。每个任务朝所有区间连流量为区间长度的边。这样如果有合法解一定可以摊开到每个时间上,不会出现一个时刻一个任务用2次的情况。

K:倍增。


 

 


登录 *


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