Ric_shooter
Table_bottom

Petrozavodsk Winter-2018. Jagiellonian U Contest.

Remilia posted @ 2019年3月05日 09:21 in 涂字 , 60 阅读

ABCDEFGHIJKL


复盘人: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)\)扫一遍就行了。
 

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter