ByteDance - Moscow Workshops ICPC Programming Camp 2019. Day 6, The Final Contest.

ABCDEFGHIJKLMN

复盘人：rxd

开场我看了K，但是看错题意了，扔给gt。我看了L，发现是原题。

gt看完K给我，我写。

0h19min，K +0。

叶队上机干了D。

0h32min，D +0。

gt上机干出了E。我在纸上写L的dp。

0h40min，E +0。

0h48min，L +0。

三人讨论出了N。

1h01min，N +0。

gt上机干出了M。

1h17min，M +0。

我上机干出了F。

1h27min，F +0。

叶队搞出了I，WA了一发以后眼调了一会儿过了。

2h34min，I +1。FB

中途我搞了下C，但是是错的。

我和gt讨论出了J。WA了一发。

3h24min，J +1。

3.5h~4.5h，叶队在搞G，但是题意漏看了一句话最后才发现。

我和gt搞了好久A还是不会。

最后10min叶队秒了A但是来不及了。

赛后得知要是C题意漏看一句话就能过了。

A：考虑题中的性质，则新图是一个弦图.如能求出该图的完美消除序列,直接统计每个点向后面连边的个数即可.

      事实上,我们只需要一个排列,满足每个点向后面的连边都是团.那么考虑1,2,.....,n这个序列,则其就是一个合法的序列,于是问题就转化为计算每个点连出出的边数量.考虑从1开始,对每个点维护其出边的set集合,每次做完一个点时,将其所有出边都赋到它的出边集合中最小值处,利用一个set启发式合并即可.时间复杂度O(M log^2 N） (+0)

B：给定一个括号序列,每个括号有一个颜色0,1,2.现在可以修改任何括号的朝向,使得0+2,1+2这两个括号序列是合法的.求最小修改次数 N<=6000.

  令(为+1,)为-1.首先枚举颜色2的总和s,那么另两种颜色的总和均为-s.考虑采取最优变法调整括号序列,那么如果要(变),必定变化最右侧的一个(,另一种也类似.

 然后接下来就只能交换括号了.那么对于每个序列,我们可以依次从左往右取)和从右往左取左括号一一匹配.考虑到所有的区间都是嵌套结构,可以为每个颜色交换的对数设一个变量C_i.对于(0,2),(1,2)序列的每个位置$j$,可以看作是$min(C_0,D_j)+min(C_1,E_j) \geq -S_j$,其中D,E是包含每个位置的区间数量,S是前缀和.那么将min拆成4个不等式,然后爆算一下即可.

C：并不会证明提到的所有决策的最优性.考虑一个整数域下的该问题,则一种最优解是每次选取当前钱数的最低位bit,同时这个算法在不限制递增时也是最优决策.那么考虑求无附加条件的原问题.一种最优方案时如果<1/2就必然all in,否则选取1-x.暴力模拟计算贡献即可.

D：

E：设dp[l][r]表示[l,r]这段区间,且l-1,r+1都在[l,r]之后被删的方案数.每次枚举区间最后一个被删的点,然后左右两边方案数乘起来再乘组合数.选择的点需要保证和左右两个端点都不相同.

F：

G(by yjn)：$10^{228}$ can be reduced to $1$. Binary search the answer, paint the board in color white and black(i.e. top left corner is white, lower right corner is black). And you get a bipatite graph. Starting from the point $P=(x,y)$. If $P$ is white, 1p wins instantly. Or 1p will win iff every maximum matching contains $P$(proof is easy). The remaining task is to calculate the maximum matching of the original graph and the graph removed $P$ from it. Note that in bipatite graph, max matching = n+m-max independent set. It's easier to calculate maximum independent set of this bipatite graph. It's easy to prove there is a max independent set formed by a rectangle containing the top left corner and a rectangle containing the lower right corner. Check every possible lower boundary of the first rectangle is ok. Maybe use some simple data structure to update answer more quickly.

upd(by fz):实际实现的时候,枚举前i列变成黑色,对每一行,在不去掉某个格子时是一个分三段的函数,如果强制去掉一个格子最多分5段,利用前缀和直接算一下.

H：考虑假设修改一个数之后可以使得所有条件不满足,那么这个人一定能在第一天推断出自己不是某个数.以此类推,问题就转化成最少修改多少个数使得所有条件都不合法.利用三维偏序的做法求一个LIS即可.

I：

J：

K：