2020-2021:teams:mian:nowcoder_training:2020_multi-university_training_contest_8
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:mian:nowcoder_training:2020_multi-university_training_contest_8 [2020/08/03 18:29] grapelemonade |
2020-2021:teams:mian:nowcoder_training:2020_multi-university_training_contest_8 [2020/08/04 21:48] (当前版本) grapelemonade [G] |
||
|---|---|---|---|
| 行 1: | 行 1: | ||
| - | ====== 2020牛客暑期多校训练营（第七场） ====== | + | ====== 2020牛客暑期多校训练营（第八场） ====== |
| ===== Results ===== | ===== Results ===== | ||
| 行 12: | 行 12: | ||
| <table> | <table> | ||
| <style> | <style> | ||
| - | <!-- | ||
| td, th {text-align: center;} | td, th {text-align: center;} | ||
| .accepted {color: #0a0;font-weight: bold;} | .accepted {color: #0a0;font-weight: bold;} | ||
| 行 20: | 行 19: | ||
| .successfulChallengeCount {color: green;} | .successfulChallengeCount {color: green;} | ||
| .unsuccessfulChallengeCount {color: gray;} | .unsuccessfulChallengeCount {color: gray;} | ||
| - | --> | ||
| </style> | </style> | ||
| + | </table> | ||
| </HTML> | </HTML> | ||
| 行 28: | 行 27: | ||
| ^ Solved ^ A ^ B ^ C ^ D ^ E ^ F ^ G ^ H ^ I ^ J ^ K ^ | ^ Solved ^ A ^ B ^ C ^ D ^ E ^ F ^ G ^ H ^ I ^ J ^ K ^ | ||
| | Pantw | | | | | O | | √ | | | | | | | Pantw | | | | | O | | √ | | | | | | ||
| - | | Withinlover | | | | | | | | | √ | | √ | | + | | Withinlover | | | | | O | | | | √ | | √ | |
| - | | Gary | | | | | | | | | | | | | + | | Gary | O | | | | | | | | | | √ | |
| (√ for solved, O for upsolved, - for tried but not solved) | (√ for solved, O for upsolved, - for tried but not solved) | ||
| 行 39: | 行 38: | ||
| ===== A ===== | ===== A ===== | ||
| + | |||
| + | 相当于每一条边在一段时间内，将所有边加在线段树上，在线段树维护并查集以及记录并查集上的操作，返回上一层时撤销这些操作即可 | ||
| + | 场上想了LCT的做法，LCT上连边，如果已经是一棵树结构，就删掉树上最早要删除的边再加入该边，这样可以维护树结构，顺便统计连通块个数，然而码力太弱~ | ||
| ===== B ===== | ===== B ===== | ||
| 行 48: | 行 50: | ||
| ===== E ===== | ===== E ===== | ||
| + | $\Theta(n^2)$ 本地跑 14s，估计过不了，考虑打表。 | ||
| + | |||
| + | 打表输出长度 1.3 MB，远超限制，考虑压缩。 | ||
| + | |||
| + | 二分查询得到牛客代码限制约为 100KB。 | ||
| + | |||
| + | 将答案数列差分，发现奇偶项规律迥异，按奇偶项做二阶差分。 | ||
| + | |||
| + | 观察二阶差分序列，发现数字均很小（绝对值 100 以内）。 | ||
| + | |||
| + | 省去换行，二阶差分序列表长约 300KB。 | ||
| + | |||
| + | 依旧远超限制。现在考虑压缩。 | ||
| + | |||
| + | 我们按照这样的方法进行压缩： | ||
| + | |||
| + | <code cpp> | ||
| + | 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]); | ||
| + | } | ||
| + | </code> | ||
| + | |||
| + | 这样可以将大部分数字压缩到一个字符。 | ||
| + | |||
| + | 这样压缩之后表长达到了 140K。 | ||
| + | |||
| + | 这样我们直接把前三分之一砍掉即可。 | ||
| + | |||
| + | 前 36000 暴力，后面直接解码即可。 | ||
| ===== F ===== | ===== F ===== | ||
| ===== G ===== | ===== 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 ===== | ===== H ===== | ||
| 行 59: | 行 111: | ||
| ===== K ===== | ===== K ===== | ||
| + | |||
| + | 前缀和+单调递减序列 | ||
| + | 卡在爆long long上 | ||
| ------------- | ------------- | ||
| 行 65: | 行 120: | ||
| ptw: | ptw: | ||
| + | * 可惜这个一血 G 了 | ||
| + | * 今天这个 E 应该早点写，应该就过了。或者应该更早考虑打表。 | ||
| + | * 再再再次提醒我们注意模板的鲁棒性 （I） | ||
| + | * 建议引入 double-check 机制，一个做法写之前由第二个人验证（除极水的水题） | ||
| + | * 小 心 数 据 范 围（K） | ||
| + | * 小 心 Python 大 常 数（K） | ||
| + | * 罚时还是很贵的，三发罚时等于晚过一小时 | ||
| + | * 自强不息，稳中求胜，一起加油 | ||
| + | |||
| + | Withinlover: | ||
| + | * E 的暴力其实好好写就过了。 | ||
| + | * I 网络流是可过的，貌似是非递归的ISAP。（还不是你手上没板子了） | ||
| + | * 不要过度相信本地测试结果，本地TLE牛客AC（E） | ||
| + | Gary： | ||
| + | * K数据范围没仔细算，爆longlong了 | ||
| + | * K最开始写的线段树，虽然也能过，但是麻烦点而且线段树也写错了两处 | ||
| + | * A码力太弱了，LCT根本写不出来，看着自己的板子都手生，并查集+线段树也没想出来 | ||
| + | * H的串题最先看到，当时觉得要长度拓宽几倍在做，但是不太会证也没想到例子，尤其没人做就没细想了，感觉当时猜波结论枚举一下拓宽的倍数大概率就过了？ | ||
2020-2021/teams/mian/nowcoder_training/2020_multi-university_training_contest_8.1596450583.txt.gz · 最后更改: 2020/08/03 18:29 由 grapelemonade
