目录

2020牛客暑期多校训练营（第八场）

Results

Summary

Member Distribution

Solved A B C D E F G H I J K
Pantw O √
Withinlover O √ √
Gary O √

(√ for solved, O for upsolved, - for tried but not solved)

Solutions

A

相当于每一条边在一段时间内，将所有边加在线段树上，在线段树维护并查集以及记录并查集上的操作，返回上一层时撤销这些操作即可 场上想了LCT的做法，LCT上连边，如果已经是一棵树结构，就删掉树上最早要删除的边再加入该边，这样可以维护树结构，顺便统计连通块个数，然而码力太弱~

B

C

D

E

$\Theta(n^2)$ 本地跑 14s，估计过不了，考虑打表。

打表输出长度 1.3 MB，远超限制，考虑压缩。

二分查询得到牛客代码限制约为 100KB。

将答案数列差分，发现奇偶项规律迥异，按奇偶项做二阶差分。

观察二阶差分序列，发现数字均很小（绝对值 100 以内）。

省去换行，二阶差分序列表长约 300KB。

依旧远超限制。现在考虑压缩。

我们按照这样的方法进行压缩： 

for(int i = 36000; i <= N; ++i) {
	if(diffff[i] >= -26 && diffff[i] <= -1) fprintf(out, "%c", 'a' - 1 - diffff[i]);
	else if(diffff[i] >= 10 && diffff[i] <= 35) fprintf(out, "%c", 'A' + diffff[i] - 10);
	else if(diffff[i] >= 0 && diffff[i] <= 9) fprintf(out, "%c", 35 + diffff[i]);
	else fprintf(out, "%lld,", diffff[i]);
}

这样可以将大部分数字压缩到一个字符。

这样压缩之后表长达到了 140K。

这样我们直接把前三分之一砍掉即可。

前 36000 暴力，后面直接解码即可。

F

G

直接用一个 unsigned long long can[256][256][4] 保存 $(i, j, k)$ 能否凑成一个 $\mathsf{set}$。

这个直接 $\Theta(n^3)$ 预处理即可。

后面查找的时候按照这样的算法查找即可：

$id := \left[encode(x)\;\;\mathtt{for}\;\;x\;\;\mathtt{in}\;\;input\right]$
$has := \varnothing$
$\mathtt{for}\;\;i\;\;\mathtt{from}\;\;1\;\;\mathtt{to}\;\;n$
$\qquad\mathtt{for}\;\;j\;\;\mathtt{from}\;\;i+1\;\;\mathtt{to}\;\;n$
$\qquad\qquad\mathtt{if}\;\;can[id[i]][id[j]]\cap card\neq\varnothing$
$\qquad\qquad\qquad\mathtt{output}(k, i, j)\qquad\qquad\qquad//\;\;id[k]\in can[id[i]][id[j]]\cap card$
$\qquad\qquad\qquad\mathtt{return}$
$\qquad\qquad\mathtt{end\;if}$
$\qquad\mathtt{end\;for}$
$\qquad has = has\cup\{id[i]\}$
$\mathtt{end\;for}$

H

I

J

K

前缀和+单调递减序列 卡在爆long long上

Comments

ptw:

Withinlover:

Gary：