2021.11.5模拟赛总结

wuchangjian2021-11-05 13:16:17编程学习

时间安排

7 : 50 − 8 : 20 7:50-8:20 7:508:20 把四道题都看了一遍,T1看着很熟,因为我曾经写过一道类似的题独木桥,T2有点像最小生成树,T3没思路,T4有点像#888。
8 : 20 − 9 : 00 8:20-9:00 8:209:00 对于T1,由于我以前做过,所以知道一个结论:当两球相撞时,可以看成两球“穿过”对方,因为两球是没有区别的。所以可以预处理出每个球经过T秒后,方向向左的位置 q i , 0 q_{i,0} qi,0 和方向向右的位置 q i , 1 q_{i,1} qi,1,再标记所有的机关点,判断 T T T 秒后的位置上是否有机关,最后 2 n 2^n 2n 枚举每个球的方向即可。
9 : 00 − 9 : 40 9:00-9:40 9:009:40 对于T2,此题很像一道最小生成树的题,所以我就先按照x,y,z排序,把可用的权值放到堆里,每次取出堆顶再用并查集判断是否为一个连通块即可。
9 : 40 − 10 : 50 9:40-10:50 9:4010:50 对于T3,考虑图只有两种情况:原始图和翻转图,所以就想到了分层图,令 1 1 1 n n n 为原始图上的点, n + 1 n+1 n+1 2 n 2n 2n 为翻转图上相对应的点,每次连边判断一下是黑洞还是白洞,再连一下 i i i i + n i+n i+n 的边,然后跑一边最短路即可。
10 : 50 − 11 : 50 10:50-11:50 10:5011:50 对于T4,考虑如果你不删最短路上的边,那么对答案是没有影响的,因此必须删最短路上的边,所以先跑一遍最短路,然后开一个vector记录一下每个点的最短路都经过哪些边,最后暴力删最短路上的每一条边,再跑最短路然后记录最大的值即可,时间复杂度 O ( n m l o g   n ) O(nmlog\,n) O(nmlogn) (这里的m为从 1 1 1 n n n 的最短路所经过的边数)。

相关文章

eclipse中启动tomcat不报错,访问不到页面404

项目没有问题,tomcat启动也没问题,但是访问不到项目资源...

css常见问题--精灵技术sprite

目录         产生原因                 原理       ...

Javascript学习笔记:数组的连接、反转与排序

1.concat()将多个数字或元素连接起来 var 水浒...

YARN 的 工 作 机 制

YARN 的 工 作 机 制 1.提交一个任务:客户端向RM提交一个任务...

layui初始用

     ...

发表评论    

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。