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.

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

B：

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

D：二进制分解.

E：

F：

G：由于做到i时,a_i一定在某个序列中,则记录其在哪个序列中,另一个序列一定相应的是最大/最小.

H：

I：

J：

K：

Recommend