<span>模拟96 题解</span>

A. 求和

显然可以将式子中的行列贡献分开考虑。

于是问题转化为等差数列求和。

然而模数比较大,为了避免高精度可以用慢速乘。

 

 

 

B. 分组配对

显然问题具有单调性,于是可以二分答案,然而这个算法并没有什么用。

考虑使用基于倍增的二分。

然后用个归并排序,因为$\sum \limits_{i=1}^{k}i*2^i$与$k*2^k$是同级别的,

所以可以保证每次倍增大小至与最终的区间大小复杂度呈一个$log$的关系。

所以总的复杂度是$O(nlogn)$。

这题是李煜东原题

 

 

 

C. 城市游戏

设$f_i$表示从$i$到$n$这一段路径中用过封路权限,最优决策下的路径长度。

因为封路权限只有一次,设$d_{i,j}$表示封掉$(i,j)$这条边之后,$i$走到$n$的最短路。

那么有$f_i=\min\limits_{link(i,j)}(max(d_{i,j},f_j+w_{i,j}))$。

表面上,里面的取$max$,表示B有一次作出限制的机会,外面的取$min$则表示小$A$的最优决策。

实际上这个式子似乎并没有想象的那么简单。

B只有一次作出限制的机会,也就是说

当$d_{i,j}>f_j+w_{i,j}$,B只能取一次$max$,表示割掉这条边。

但对于一个$i$,取了多次$max$,这显然是存在错误的。

正确的做法应该是取出所有的$f_j+w_{i,j}$,B的最优决策应当是限制其中最小的一个,也就是只对最小的一个取$max$。

之后小$A$会再取其中最小的一个,视作取$min$。

然而对于存在环的转移,这种实现方法似乎并不现实。

实际上题解中给出的式子是可行的,因为$f_i>=dis(i,n)$

所以$d_{i,j}>f_j+w_{i,j}$仅当$(i,j)$是$i \rightarrow n$最短路径上的边,

如果求出最短路树,$i \rightarrow n$之间存在唯一路径,

也就是说$d_{i,j}>f_j+w_{i,j}$仅有一次,所以题解中简单的取$max$操作是正确的。

所以这个$f$数组可以用最短路求出,问题在于如何求$d$数组。

仍然考虑上面提到的最短路树,设$dis_i$表示从$n$到$i$的最短路的路径,即树上的唯一路径。

显然割掉非树边,$i$仍然会沿着树边走到$n$,问题是简单的。

对于割掉树边,设连接的两个点为$(u,v)$,会形成两个联通块。

设$u$在$n$所在联通块中,$a$在$n$所在联通块中,$b$在$v$所在联通块中,$a,b$相连。

显然$b$在$v$的子树中。

最优路径为$n \rightarrow a \rightarrow b \rightarrow v$

即$d_{v,u}=dis_a+w_{a,b}+dis_b-dis_v$

发现这个式子与$(a,b)$相关的项太多了,只要枚举这条边$(a,b)$,可以更新一条链的答案。

用树上差分的思想,可以用一个$multiset$维护出现了哪些值,可以做到查询最大值。

当然这里要用启发式合并,来保证复杂度是正确的。

当然也可以用一些树链剖分之类的操作进行区间取$max$操作。

实际上这个还可以用类似并查集的结构实现。

发现一个边只要被最小的元素更新就可以了。

所以可以用类似并查集的结构维护每个点已经更新到哪个父亲,之后可以暴力跳父亲,更新$d$值。

全部评论

相关推荐

三年之期已到我的offer快到碗里来:9硕都比不上9本
点赞 评论 收藏
分享
评论
点赞
收藏
分享
牛客网
牛客企业服务