CVBB ACM Team

本页面只读。您可以查看源文件，但不能更改它。如果您觉得这是系统错误，请联系管理员。
====== 2022.07.23 牛客多校第三场 ======
===== 题解 =====
==== A ====
本题的重点在于：给一棵树，以及k个关键点，问去掉任意一个关键点后，剩下k-1个节点的lca的变化。

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

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

  * 若只有一个子树有关键点，则lca自身必为关键点，此时只有去掉lca自身，剩下的lca才会改变。

  * 若只有两个子树有关键点，则只有去掉只含一个关键点的子树才会改变lca。

  * 若更多子树有关键点则lca不会变化。

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

  -  统计前缀lca和后缀lca，去掉其中一个点后的lca就是一段前缀lca和一段后缀lca的lca。
  -  若干点的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>>导致一直超时
CVBB ACM Team

用户工具

站点工具

页面工具
