Warning: session_start(): open(/tmp/sess_550010abc9e920ff2fb42beab3c674ec, O_RDWR) failed: No space left on device (28) in /data/wiki/inc/init.php on line 239

Warning: session_start(): Failed to read session data: files (path: ) in /data/wiki/inc/init.php on line 239

Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/auth.php on line 430

Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103

Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
2022-2023:teams:just_ridiculous:2022.07.25_牛客多校第三场

目录

2022.07.23 牛客多校第三场

题解

A

本题的重点在于:给一棵树,以及k个关键点,问去掉任意一个关键点后,剩下k-1个节点的lca的变化。

赛时观察到只有有限的情况下,lca会变化。

可以先求出k个点的lca,再统计其各个子树中有多少关键点。

赛后其他队伍更简单的做法:

  1. 统计前缀lca和后缀lca,去掉其中一个点后的lca就是一段前缀lca和一段后缀lca的lca。
  2. 若干点的lca等价于这些点中dfs序最小和dfs序最大的节点的lca。

C

排序字符串。对于串a和串b,若ab<ba则a排前面。

hint很坑人,以为不能用排序卡了好久。正解要用trie但是细节较多。

赛中记录 Replay

12:00~13:00

jrt,hqy讨论C题,被题目中的提示所误导,不敢写排序算法。jrt想到了一个trie做法尝试编写代码,但提交WA。

13:00~14:00

hqy开A题,有了思路但细节较多,之后上机写代码写了将近1h后AC。

14:00~15:00

再次思考C题。此时C题过题人数最多,hqy提出重新用排序算法试一下,幸运的是直接AC。

15:00~17:00

三人集中看J题,同时看看别的题是否可能有思路。J题是个图论,jrt提出直接用最短路算法求解,但是一直TLE。尝了许多小优化但还是没有解决问题。具体原因见Dirt。

不足之处 Dirt记录

J题,考场上的map用的是unordered_map,加上优先队列没有设置<pii,vector<pii>,greater<pii»导致一直超时