• Solved 3 out of 11 problems
• Rank 255 / 1033 in official records
• Solved 4 out of 11 afterwards

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

$\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 暴力，后面直接解码即可。

直接用一个 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//\;\;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}$

ptw:

• 可惜这个一血 G 了
• 今天这个 E 应该早点写，应该就过了。或者应该更早考虑打表。
• 再再再次提醒我们注意模板的鲁棒性 （I）
• 建议引入 double-check 机制，一个做法写之前由第二个人验证（除极水的水题）
• 小 心 数 据 范 围（K）
• 小 心 Python 大 常 数（K）
• 罚时还是很贵的，三发罚时等于晚过一小时
• 自强不息，稳中求胜，一起加油