这里会放我写过的题的题解。
2024-7-7
-
修复公路
题意：给定\(n\)个点和\(m\)个边以及边连接的两个点和边的价值，让你选任意条边使得点都联通且选中的边的最大值最小。
分析：全部联通，选边最少的肯定是使其成为一棵树，又要边的最大值最小，所以就很自然的想到可以先把边按值排序，然后从小到大一次判断要不要选这个边（如果这个边是必要的树边就连，不是就不连），要想判断是不是树边，可以用一个并查集搞定，如果两点本就在同一集合，那就不必连，反之则连
总结：刚来重庆，心态有点不好，做做水题稳住心态。 -
无序字母对
题意：给定\(n\)个字母点对，每个点对的两个点的位置可以互换，让你求一个长度为\(n+1\)的字母序列使得包含所有给出的点对（点对互换位置与否都可以）要求序列字典序最小
分析：一看到这道题的时候毫无头绪，但是手磨一便样例就会发现这些合法的数据中的样例只需要将每次的点对连无向边，最后就会得到一个环，这个也很好证明：如果不是一个环那么必然有的地方会断掉那也就不能完成“包含所有点对”的要求了。所以只需要把点对连无向边，若不是环就无解，若是那就从字典序最小的一个开始跑一边欧拉路就行了
总结：题的思维量不大，但是需要想的细节有点多，而且需要熟悉怎么打欧拉路的板子我就是忘了怎么打板子才半天没做出来，这题是6t给我的jzp学长讲课的课件，做完我才发现这一页上面就是欧拉路/kk，要是看仔细点没准能写的更快。