周赛吐槽炫技疗伤痛斥休息室 09/19/2020

分享心得。

痛斥还请文明用语。

过期关闭。

吐槽一下：最后一道题一看就是二分图边的最小权覆盖...为什么大家都在写状压DP。。。

稳3冲4的，结果3都没做出来，超时了。2看了第一眼，敌兵布阵，一套树状数组模版上去。然后发现不涉及区间和根本没必要上这么麻烦的数据结构，白费半小时。。最后排名1000+，GG

双周赛 就做出第一题 第三题 。。。。

前三题都可以 最后一题确实没有思路了。。那些十几二十分钟就做完了的人也太强了吧...

做了三题，第四题死活没有思路

第四题死活没思路，画也画不出来，哭惹

请问有大佬知道为什么第四题不能用Minimum Spanning Tree 的 Kruskal's Algo 做吗？大概就是 用PriorityQueue 存所有的edge，然后每次poll 最小的，如果两边都已经有connected 就move on下一个，否则就加入这条edge

syuan16 发表于 2020-9-21 01:44
请问有大佬知道为什么第四题不能用Minimum Spanning Tree 的 Kruskal's Algo 做吗？大概就是 用PriorityQue ...

一个简单的反例
[[1,3],[3,4]]

不能直接用kruskal贪心的主要原因是，有可能你会选择两条比较便宜的边，但是他们都只能各cover一个点，同时还有一个边可以cover他们两个且cost比那两条边的和要小

比赛中碰到一个非常奇怪的Runtime报错。

Exception in thread "main" java.lang.IllegalArgumentException: Comparison method violates its general contract! at java.util.TimSort.mergeHi(TimSort.java:899)

我写的比较器是直接减法。

1.     int[][] matrix = new int[10][2]; // given
   
2. 
   
3.     Arrays.sort(matrix, (a, b) -> a[0] - b[0]);
   

复制代码

然而数据是整数的全部范围。所以当-MAX减去MAX的时候就悲剧了。调试了很长时间才发现是这个地方。