T1:
算是一个小数学题,但是要一些大胆的想法,就是答案不会很大,直接暴力即可。
PS:T1一般不会很难,如果感觉没思路可以尝试打表。
T2:
要求无权图最小环的数量,可以考虑环的求法,例如tarjan,dfs啥的,但还有一种求法:点法bfs,因为每次bfs扩展一层,可以很自然的找到队头和队尾的关系,不过仅限与无权图,若是有权图可以考虑断边dij找环。
T3:在 \(1->m\)构造每条边的权值,满足每条边的权值范围且前 \(n-1\) 条边是原图的最小生成树。
既然是最小生成树,那么考虑kus,可以发现非树边所连的两个端点所构成的链的权值在非树边权值确定前确定。
考虑只有树边,那么就是经典的任务分配问题:对每个时间点优先选取结束时间最早的任务。
那么在每条非树边所连的两个端点所构成的链的权值确定后,加入这条非树边作为新的任务( 但这样足够吗?
不够!!!
我们只满足了树边和非树边的先后顺序,并不能保证非树边有解,假如我们按照最小的结束时间来对树边分配,那么可能会使一个结束时间早的非树边很晚加入,无法保证得出答案。
那么,一条非树边对它所连的两个端点所构成的链的结束时间有影响,不妨用非树边的\(r\)来更新树边的\(r\),然而还是可能无解,为什么? 我们需要让非树边也有时间点分配,那么在树边分配后还要有一个时间点分配给非树边,所以要用\(r-1\)来更新链。可以用线段树合并维护每个联通块的非树边。
对称的还可以用树边的\(l+1\)来跟新非树边的\(l\),这样不需要合并,只要一个 dsu on tree 就OK了。
T4:
人类智慧构造题(这题12K+你敢信?
我不会。。。(听懂了,但不想写【doge】。
总结
-
感觉思路不对就立即换方向(T2用bfs搞出距离后思维定性,一直在考虑如何优化\(O(n^3)\)的算法,没有从距离自身下手,浪费大量时间。)
-
注意捕获那种灵光一闪的想法,再去考虑是否可做。