在WC划水后的第一篇博客,算是庆祝戊戌年的到来(依然在划水) 题目大意 给你一个无向带权连通图,每条边是黑色或白色。让你求一棵最小权的恰好有need条白色边的生成树。 题目保证有解。 Solution 最小生成树?kruskal?prim?应该都可以。我使用了方便的kruskal。 然而有一个限制: …

题目传送门 大概看了一下题目一脸懵逼,后缀数组?怎么维护修改、插入??仔细看题目好像不是这样的。。。用splay维护字符串,同时维护hash值,然后询问时只要二分+hash判定就好了。时间复杂度O(n lg² n)。主要是代码细节比较多,还有卡常。。。 code #include<cstdio …