====== 2020牛客暑期多校训练营(第八场) ====== ===== Results ===== ==== Summary ==== * Solved 3 out of 11 problems * Rank 255 / 1033 in official records * Solved 4 out of 11 afterwards
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:
* 可惜这个一血 G 了
* 今天这个 E 应该早点写,应该就过了。或者应该更早考虑打表。
* 再再再次提醒我们注意模板的鲁棒性 (I)
* 建议引入 double-check 机制,一个做法写之前由第二个人验证(除极水的水题)
* 小 心 数 据 范 围(K)
* 小 心 Python 大 常 数(K)
* 罚时还是很贵的,三发罚时等于晚过一小时
* 自强不息,稳中求胜,一起加油
Withinlover:
* E 的暴力其实好好写就过了。
* I 网络流是可过的,貌似是非递归的ISAP。(还不是你手上没板子了)
* 不要过度相信本地测试结果,本地TLE牛客AC(E)
Gary:
* K数据范围没仔细算,爆longlong了
* K最开始写的线段树,虽然也能过,但是麻烦点而且线段树也写错了两处
* A码力太弱了,LCT根本写不出来,看着自己的板子都手生,并查集+线段树也没想出来
* H的串题最先看到,当时觉得要长度拓宽几倍在做,但是不太会证也没想到例子,尤其没人做就没细想了,感觉当时猜波结论枚举一下拓宽的倍数大概率就过了?