竞赛讨论区 > 【题解】Wannafly挑战赛2
头像
牛客网小运营
编辑于 2018-12-27 14:42
+ 关注

【题解】Wannafly挑战赛2

(题解由比赛出题人提供,点击右侧“本文相关内容”的题目即可开始做题)
T1    Cut

采取逆向思维。问题就变成我们采取不断合并的策略,使得总代价最大。于是变成了经典的哈夫曼树题。每次从剩下的元素中挑选两个最大的进行合并,直至剩下一个元素。此题得解。


T2    Travel

通过一些观察可得:节点 u 到节点 v 的最短路肯定为以下两种情况之一:

1、不经过额外的 m 条边直接从 u 到 v。

2、从 u 先走到某个为额外边端点的 x,再从 x 走到某个同样为额外边端点的 y,最后从y 走到 v。

预处理所有额外边的端点间两两最短路,询问时暴力枚举 x、y 更新答案即可。

时间复杂度: O(M 3 + N + Q ×M 3 。


算法二:

进一步观察可得,以上第二种路径可进一步化简为:从 u 先走到第一个为特殊边端点的x,再从 x 走到最后一个为特殊边端点的 y,最后从 y 走到 v,这样的 x 和 y 都是与 u 和 v 相邻的。

故我们只需要预处理出与 u 相邻的两个 x 和与 v 相邻的两个 y,就可以计算出答案了。时间复杂度: O(M 3 + N + Q) 。


T3     Butterfly

        用 d[i][j]表示从(i, j)位置向下连续有多少个 X,用 dr[i][j]表示从(i, j)位置向右下连续有多少个 X,用 dl[i][j]表示从(i, j)位置向左下连续有多少个 X,设 f[i][j] = min(d[i][j], dr[i][j]),v[i][j] = min(d[i][j], dl[i][j]),枚举蝴蝶的左上角(i, j),问题就变成了找到对应的右上角(i, k),使得 f[i][j] >= k – j + 1 且 v[i][k] >= k – j + 1 且 k 最大。移一下前面的式子,即我们要在区间(j, f[i][j] + j – 1)里找到最大的 k,使得满足 j >= k - v[i][k] + 1。我们把 k 按照 k - v[i][k] +1 排序,随着 j 从左到右枚举,一点一点把 k 加进考虑的范畴,于是问题变成了在一段区间里找一个最大的 k,随便怎么弄都可以啦!std选择了线段树,也可以使用并查集路径压缩大法。复杂度 O(nmlogm)


T4    Delete

考虑到图是 DAG 形态,那么删掉一个点 N 以后会发生什么呢?考虑拓扑序,一定有一条边从 N 的左边连接到 N 的右边。我们可以枚举所有的边(x,y),用 dist(S, x) + v(x, y) + dist(y, T)更新拓扑序中(x, y)区间的最小值。查询的时候线段树里找一找就可以啦!


T5     Mod
将【P,Q】这个区间询问拆成两个前缀询问,【L,R】不动。问题形如x+kSmodT属于【0,P),k属于【L,R),将x,S模去T答案不变,因此可考虑对S和T进行辗转相除。令S'=Smod T,P'=min(P,T),原问题中的x+kSmodT属于【0,P) x+kS' =jT+y x-jT=-kS'+y.其中y属于【0,P')。因为每个k至多对应一组(j,y),所以这就是求这个三元不定方程在限制下有多少组解。通过k,y的范围,算j的范围:

其他疑问可加以下交流群(加入一个即可啦~)
牛客多校算法训练营1:453799454
牛客全国算法训练营2:330766563
牛客多校算法训练营3:934889305

全部评论

(0) 回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐