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

A. 新的世界

显然与顺序无关,所以问题转化为最短路问题。

用$dijkstra$的思想贪心。

 

 

 

 

B. 邻面合并

看到这个数据范围,显然是状压。

矩形上的操作,考虑轮廓线/插头dp。

然而逐个转移似乎有些复杂,所以逐行转移,大力分类讨论。

压缩状态的方法有很多。

其实只要关注左侧开始的点,设为1就可以了。

当然也可以分别用编号表示。

 

 

 

C. 光线追踪

显然对于每个斜率答案是相同的。

将询问离线,开两棵线段树,分别维护每个询问的斜率$x$值和y值的最小值和$id$,

然后直接在修改操作时修改对应的斜率,

询问操作时单点查询两棵线段树最小值,比较一下就完了。

全部评论

相关推荐

lxylxy_:其实是美团卷起来了
点赞 评论 收藏
分享
评论
点赞
收藏
分享
牛客网
牛客企业服务