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

---

复盘人：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：倍增。

---