XV Open Cup named after E.V. Pankratiev. GP of Japan.

ABCDEFGHIJ

复盘人：rxd

开场叶队看A，gt看B，我看C。

看了一会儿之后叶队和我都不太会，gt有点会了。

叶队会了F，给我讲了下，需要个线段树。

我拉住叶队想A，一会儿之后会了。

0h40min，A(+0)。

然后叶队写J。

1h01min，J(+0)。

然后我和gt交替写C和B。写完都WA了。

我C是个不知道对不对的贪心，交上去WA 19，检查了下发现有个地方有点问题，改了改还是WA 19。

gt改了改B也还是WA 5。我怀疑C的贪心是错的，扔给叶队，去想H了。

2h17min，B(+2)。

叶队弄出了C的暴力做法，我们讨论了下之后我开始写。有点细节弄不太清楚，过了样例之后交了一发，还是WA 19。后来发现有东西算错了，经过一番漫长的萎来萎去之后终于过了。

3h01min，C(+3)。

叶队开始写G，gt给我讲了下D，讨论了下细节之后我开始写。

3h42min，D(+0)。

叶队继续写G，写完交了发，WA 4。我和gt讨论了下F的细节，发现还有一种情况。

我开始写F，写完一交WA 3，发现有个指针搞错了，再一交MLE 19，发现是m=0的时候线段树RE了。改完再交就过了。

4h42min，F(+2)。

最后我和gt帮叶队看了看G的细节，发现有个地方爆int了，改完一交还是WA 4。

A：两种情况：作为一个等腰直角三角形的斜边，或者放在一个1*k矩形里让它绕一绕，答案是k+1，判一下第二种情况可不可能就好了。

B：令f[l][r][x]表示[l,r]区间里的串,前x-1位相同的划分方案数,再维护g[l][r][x][y]表示[l,r]区间内前x-1位相同,第r个串的第x位是y的方案数.xjb转移一下就行了.

C：考虑哪些行之间有公共元素、公共元素是什么。同一种公共元素一定构成一个团，每个点的不同公共元素种数不能超过Ai。由于只有10条边，Bell(10)暴搜10条边的存在性及相等关系，算下答案就行了。

D：考虑维护奇数位置的序列和偶数位置的序列，每一层的操作都可以用Treap维护。\(O(n \log n)\)。

E：由于只有有限个1,那么相邻2w+1个格子的状态肯定是从0回到0.于是问题就变成了有些边有权值浮动,问是否存在一组合法的标号满足条件.直接差分约束即可.

F：选4个的只有互相垂直这种情况，否则一定是选3个，两两角度在(0,\(\pi\))。把每个向量取反也放进去，设成白色，相当于要找黑白黑，首尾小于180°。枚举第一个黑，拿线段树维护区间白黑的最小值就行了。\(O(n \log n)\)。

G（supplied by yjn）：sol (1)：Iter one point, calc 2 convex hull(with id<i & id>i). ans is impossible iff $\exists i $ s.t. intersection of these 2 convex hull is not only the point i. RZZ has told me an idea like this, I forgot it when training. The proof is obvious.

sol (2): Have a pen and draw on a paper, you can find there are only 2 ways making the axis siezed up. After reversing the sequence, there is only one case. i.e.  for  $i<j$, a beam from $j$ in direction of $(i,j)$ intersects the curve from $i$ to $j$ when segment $(i,i+1)$ and $(j-1,j)$ are on different sides of this beam(the order matters, check it yourself). Then just iter $j$ and calculate the winding number is ok.

I forgot the case of winding bottom-up in the contest.

sol (3): I just have a look of the standard code...... The constraints in sol(1) can be weaker. It's ok only to say "$\forall i:$ both convex hull doesn't contain $i$ strictly". Then the std code did it in a tricky way. Cause $i$ is on the boundary of the convex hull, you can find the "leftmost point" with respect to the order of outer product by one single "for" clause. If the constraint holds, it will be exactly the leftmost point. But if not, there will be no "leftmost point", thus you can find a counterexample by another "for" clause.

H：

I：首先暴力枚举所有的border集合,去重之后合法的集合在$M=50$时大约只有2k+个.然后考虑计算每种串的方案数.记$f_i$表示长度为$i$,末尾这种串第一次出现的方案数,枚举前一次出现位置容斥一下.然后计算这种串的个数也是枚举包含他的border集合暴力减一下.

J：

总结(by rxd)：

这场关键在前期节奏太崩。中后期其实还可以。

前期碰到不会做的不要马上跳过或者扔给别人，慢慢想一想讨论下。碰到C这种好像可以贪心的也不要直接上，讨论下靠不靠谱，有没有更靠谱的做法。B其实也我也应该想想做法、写法。

今天前4个签到题做完已经3个小时了。两个中期题D、F倒是还可以，讨论得比较充分，也没花多少机时。理想状态下应该更快过签到题，然后把G和H给出了。