Petrozavodsk Winter-2018. Jagiellonian U Contest.

---

复盘人：rxd

第一个小时我一直在写签到题，gt和叶队讨论、看别的题。

0h10min：B(+0)。
0h11min：I(+0)。
0h17min：F(+0)。
0h35min：E(+0)。
0h45min：L(+0)。

gt和叶队讨论出了K的好写做法。gt写完稍微调了一会儿。

1h14min：K(+0)。

然后他们在想A，我开始写C。C是个裸的3维偏序，我以为树状数组套线段树，7s肯定跑的出，就写了个，结果T了，加了若干剪枝，FastIO也加上去了还是T。
然后只能绝望地删掉改成CDQ。又写了20分钟，写完一测极限数据只要4s，比树套树快好多，有点颠覆我的认知。

2h06min：C(+3)。

写完C我听gt讲了下他的A做法，思考了下感觉是对的。然后开写，写完决定先拍再交。然后果然拍出错了，调了半天发现是暴力把min写成max了。交上去就过了。

2h42min：A(+0)。

然后大家纷纷开始吃饭，划了至少半个小时。

回来之后我想H，gt想D，叶队想J。
然后叶队突然发现G会做了，其实感觉不是很难。我写完OJ崩了交不上去，就先拍一下，拍了果然萎了，然后发现是bfs要一层一层做，改了改还是没拍上（实际上是改得有点问题），为贪图方便直接去把n log n条边都拿出来排序了。结果拍是拍上了，交上去MLE，改来改去都在MLE和TLE之间来回徘徊。最后火死了弃疗了。

赛后稍微又改了下这个G就过了，好端端地去一层一层bfs也过了。

 

A：设所有数异或和为sum，可以发现sum为0的那些位完全不影响答案。而sum是1的最高位必然是两个集合一个1，一个0，设1的集合为X，0的集合为Y。先求个线性基，然后把最大的放进X里。现在只要最大化Y的异或和就可以了（因为奇数位Y为1时X为0），那么拿线性基算一下最优的Y，令X=S\Y就行。

 

B：每次取最小的数，把相应的子集和删了就行了。

 

C：CDQ分治，由于dp要按时间顺序做，合并又要按照A的顺序合并，需要一开始按A排完序，按编号分治下去，做完再按A归并上来。复杂度\(O(n \log^2 n)\)。如果用树状数组套线段树会贴着时限TLE。

 

D(by fz)：赛场上极度弱智.给一个n和a,第i个人可以送礼物给(i-n+a,i+a)里的其中一个人,问每个人恰好送到一个礼物的方案数.n<=10^6,a<=200

考虑如果从左往右一个一个分配,那么要计算一个人的区间里有多少被选过的人.考虑最后a个人的区间是一个后缀,前面的人是一个前缀.考虑计算出一个f[i]表示最后a个人,同时在[1,a]中被前面n-a个人选走了i个人的方案数,g[i]表示n-a个人在[1,a]中选了j个的方案数.第一部分可以通过多记录空格的数量在O(a^3)时间内计算,后面部分可以矩乘,直接O(na)暴力也能过.

 

E：\(O(3^mm)\)DP。

 

F：输出\(\pi r^2\)。

 

G：\(2^m\)每个数朝它二进制改一位连边。令\(pt[x]\)表示x这个二进制数最先被谁bfs到，bfs过程中碰到一条末端\(pt\)不为空的就把\((pt[x],pt[y])\)加进MST里。注意直接bfs的话距离为4的可能会在距离为3之前被bfs到，要先搞跟上一层的边，再搞跟这一层的边。\(O(2^mm)\)。

 

H：首先注意到图形是唯一确定的，可以根据行列把图形弄出来然后算方案，但是这样不容易判无解。标程的做法很简单：考虑两条从左上到右下的路径，每次挑小的一个点走，则一定可以根据行或列确定应该往哪个方向走。复杂度\(O(n)\)。

 

I：输出 n&1?"B":"A"。

 

J：Sol 1:注意到比n小的最大质数若不在里面,则k必然很小,否则n距离最大质数很近,那么考虑暴力枚举这些不多的组合数,判断一下,复杂度O(m log^2 n).

     Sol 2:通过log直接估计组合数的大小,固定k之后找出区间里最接近的两个数,利用hash判断是否合法.时间复杂度O(m).

     第一种有正确性保证但是可能过不了,补题的时候写的是第二种.

 

K：HOTEL加强版.记f[i][j]表示i向下深度为j的点的个数.g[i][j]表示i子树中,需要一个深度为j的点来和它们匹配的对的个数.从重链继承过来,其他直接暴力即可.

 

L：枚举两个串匹配位置的坐标差，\(O(n)\)扫一遍就行了。