ByteDance - Moscow Workshops ICPC Programming Camp 2019. Day 5, Div A.

ABCDEFGHI

复盘人：fz

开场xjb看题,B,D都不太会。发现F只需要求四元环,但是不会，暂时搁置.

有人过A,看A感觉非常可做,想了一个贪心,和R爷讨论了一下以后R爷上机.

0:53，A AC(+1)。

有人过B,G,叶队表示G可以二维凸包,瞬间被Check it out秒叉(?).然后叶队上机,写了一会之后感觉没啥希望就下机了.

中期BFI三题同开,到2.5h时大约有了I的做法.阿爷写完了之后交了一发TLE on 4.底下测数据发现n=1000跑不出.

此时发现I的做法大概有问题(后来发现是没有问题的,复杂度多了一个log),改成直接在dfn序上二分.然后B也推出了3^Q*Q的弟弟做法.

4:08，I AC(+1)。

4:12，B AC(+1)。

最后40min我开始写F除了四元环以外的部分,叶队搞4元环.20分钟以后写完其他部分然后放弃了.R爷挣扎了一下H,发现做法有问题.就弃疗了.

感觉这一场的策略没有出什么太大的问题(因为根本就没有策略).唯一似乎能改进的地方就是在n=1000跑不出的时候如果能先看一下为什么跑不出可能会更好一些.

A：考虑第一个人决策固定时第二个人肯定是每次在[1,n]都出现的时候放在最后一个上.于是可以先构造一个[1,n]的排列,然后之后每次可以去掉之前的最后一个数.

B：记f[i][j]表示选了i个等价类,当前选择的集合为j的贡献.那么每次枚举一个子集计算贡献转移即可.复杂度O(3^n*n).

C：

D：

E：

F：一通容斥之后转化为求三元环和四元环.考虑每个点出现在几个四元环中。类比三元环的做法,在平行四边形中,考虑枚举标号最大点的对顶点x，枚举x的无向出边y,枚举y的有向出边z.那么(x,y,z)和(x,c,z)可以构成一个四边形.时间复杂度$O(M\sqrt M)$.

upd by yjn: search 2 layers from the most heavy point has time complexity $O(M\sqrt M)$, such that you only need to write at most 5 lines of C++ code to calculate the number of 4-membered circle or triangle. I told gt about it, but gt is so stubborn which makes me feel heart-breaking.

G：

H(by yjn)：Start from $0$, let $a_{-1}=-\infty,a_0=+X$. Do $x = \max(0,\min(x+a_i,S))$ one by one. The remaining problem is: modify one $a_i$, modify the ceiling $S$, query the final answer. If there are some $l,r$ s.t. $|\sum_{l\le i\le r} a_i|\ge S$, there will be a clamping. Find such maximal $l$, and a minimal $r$ of this $l$. So that the value of $x$ is $0$ at the time of $r$, and there will be only one kind of clamping after $r$. Suppose it will never touch the ceiling. Find $t$ minimizing the sum $\sum_{r<i\le t} a_i$, there will be no clamping after $t$. You can do all this operation in $O(\log n)$ using segment tree.

I：(1)考虑对所有叶子的dfn序做二分.可以注意到若将子树按照size递减排序,那么每次二分出一个长度为n的合法区间,至少可以去掉n/2个叶子.于是总复杂度就是O(N log N)

    (2)考虑对整棵树做整体二分,一个点若合法,则其子树都合法,否则它到根链上的点都不合法.可以注意到的是每个叶子至多会被访问O(log N)次，总复杂度O(N \log N).