<span>模拟25A 题解</span>

A. Lighthouse

m的范围极小,显然的容斥。

总的方案数,减去受任意一个限制的方案数,加回受两个限制的方案数。

就能得到受所有限制的的方案数。

将选择的一些边所指向的点放在同一个联通块里。

方案数其实就是这些联通块的圆排列,再乘上$2^{不为1的联通块个数}$,

因为每个联通块都存在顺时针逆时针两种形态。

最后统一除2消除掉整体顺时针逆时针影响。

 

 

 

B. Miner

显然求欧拉路,向多出的奇数度的点之间连边。

主要存在多个联通块,不同联通块之间需要连边。

对求欧拉路的一个优化,已经走过的边不会再走,把表头head设为它的next。

 

 

 

C. Revive

暴力拆平方式子,dfs一遍出需要的信息,每次询问$O(n)$计算。

正解 点分治/线段树 不会打

全部评论

相关推荐

震撼沃玛一整年:查看图片
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务