XIX Open Cup named after E.V. Pankratiev. Grand Prix of America, Division 1.

---

复盘人：rxd

开场我发现D是个最裸的类欧，但是没有现成的板子，就开始推。他们两个在讨论I。讨论出来会做了，又讨论出G也是傻逼题。然后gt跟榜过了J。我过了D。

0h24min：J(+0).
0h34min：D(+0).

叶队表示A也是傻逼题，上去写A。我和gt讨论出了M。我想了想G和M的细节。叶队写完没过样例先下机调了下，5min后过了。

0h49min：A(+0).
0h50min：M(+0).

我11分钟写完了G，交了一发WA3。发现题目里有x,y互不相同的限制，删了点代码再交还是WA3，然后一脸懵逼，对着题意读了3遍确认没有问题，对着代码看了5遍感觉都是对的，交给叶队看也看了好久也查不出哪里错了。这个时候gt在写I，写完也WA了。我断断续续地想了想E。
之后我终于想出了E，上机写E，gt下机帮我看G的代码，发现是树状数组里x-=x&-x打成了x-=x&=x，居然啥警告都没有。
I又经过几发WA之后也过了。
我的E写完也WA了，自己调了一个错误以后还是WA，我发现另一个地方以为是没事的，但gt告诉我是错的。改完终于过了。

2h05min：G(+3).
2h21min：I(+4).
2h37min：E(+2).

叶队上去写F了，写之前告诉了我们L的题意。
我和gt想了想L感觉不会。想了想B感觉会了。

3h26min：F(+0).

B写完又WA了……叶队会了L告诉我是个网络流+Tarjan，我开始写。gt帮我看B的代码。发现我有有个傻逼地方写错了，还有个情况没判。写完L叶队思考了下到底哪种是对的，告诉我之后交就过了。

3h56min：B(+1).
4h07min：L(+0).

最后一个小时叶队去想K了，gt在写C，我帮gt造了个样例调了一下。之后过了样例交上去还是WA了。大概是算法错了，那就没办法了。

 

---

A：傻逼期望。展一下式子注意一下精度。

B：倒着做，记灰点表示既可以是黑点也可以是白点。每次相当于考虑一个黑点，如果它行列没有黑点，就可以把它变白，行列都变灰。注意到操作后只会在那行那列产生新的决策点，并且可以贪心地能做就做，那就bfs一下就行了。最后看看染灰的行列交叉点处必须至少有一个白点。其它位置必须对应相等。最开始如果已经相等了直接输1。

C：直接取log高斯消元.O\((yc)^3\).原来高斯消元消1000如此轻松.

D：变成求\(\sum_{i=1}^n pi-q\lfloor \frac{pi}{q}\rfloor \)。这就是个裸的类欧：\(solve(n,A,B,C)=\sum_{i=1}^n \lfloor \frac{Ai+B}{C} \rfloor \)。

ll solve(ll n,ll A,ll B,ll C){
	if (n==0) return 0;
	ll ans=0;
	if (B>=0){
		ans+=n*(B/C);
		B%=C;
	} else{
		ll t=(-B)/C+((-B)%C!=0);
		ans-=t*n;
		B+=t*C;
	}
	ans+=n*(n+1)/2*(A/C);
	A%=C;
	if (A==0) return ans;
	ll top=(A*n+B)/C;
	ans+=top*n;
	ans-=solve(top,C,-B-1,A);
	return ans;
}

E：枚举行之后相当于每两列都有一种颜色的边。设\(f_{i,col}\)表示做到\(i\)点，边的颜色为\(col\)时的答案。直接枚举边转移就行了。\(O(2^nn^2)\)。

F：维护PDF。因为定义域之后的那一段始终是$0$，而又只有变下限积分和逐点乘法，所以函数的支集是个区间。暴力积分卷积就好了。$O(n^3)$。

G：扫描线。

H：

I：考虑肯定是字符集从大往小依次选择,不够的时候找一个最大的后缀.

J：对每个左端点算出合法的右端点.

K：

L：ONTAK上一个经典题。tarjan一下。

M：考虑10...0和00...0，如果答案一样，说明一棵子树是空的，看看对应位置是否相同，递归下去就行。否则看看两个集合是否无交，递归下去就行。

---

总结 (by rxd)：

这场打的好的地方在我看来主要就是没有人挂机太久，也没人空机。我G萎住的时候一度气急败坏，后来还是听从叶队，去想E了。
gt爸爸帮我调出了3个题，感激不尽。
叶队干出了A、F、L三个题，功不可没。

要说有什么问题的话感觉罚时稍微高了点。这个主要是我的锅，感觉是这个G让我整个节奏都往后拖了一个小时。

以后就尽量保持不要空机，调的题如果要10min以上就下机调。早过题早解放出时间想后面的题。

点个赞！