「考试总结」ZROI-21-NOIP冲刺-TEST17 总结
#屑在前面
由于身体原因及某几场考试的 T3、T4 不可补,于是中间就咕咕咕了几篇,补不补随缘吧/wq
#T1 博弈
Time Limit: 1s | Memory Limit: 512MiB | 题目连接
#大体思路
首先显然开环的顺序由先手决定,考虑大于等于四个结的环,如果后手不选择交换,先手一定只能拿到 4 个,如果选择交换那么先手一定一个都拿不到,所以显然先手会选择从小到大开环,然后我们 DP 一遍即可,时间复杂度为
数据范围只有
就离大谱...
#Code
1 | #define ll long long |
#T2 齿轮
Time Limit: 1s | Memory Limit: 512MiB | 题目连接
#大体思路
注意到在同一连通块中的任意两个齿轮之间的转速关系仅与两者的齿数有关,中间的所有齿轮的影响都可以被抵消掉,于是我们可以将一个连通块中的所有齿轮根据旋转方向的不同分为两个不交的集合(是二分图),考虑将两个齿轮咬合后连通块锁死当且仅当两者咬合前在同一连通块且所属集合相同,于是我们需要维护每个齿轮所属的连通块及所属的集合。
当两个连通块合并时,采用启发式合并,将齿轮数小的集合并到较大的集合中,若其中一方锁死,则整体锁死,否则当咬合的两个齿轮咬合前所属的集合相同时,应当将较小的集合中的所有点所属的集合取反,均摊后时间复杂度为
对于修改齿数及询问直接处理即可,整体时间复杂度为
#Code
1 | #define ll long long |
#T3 排班方案
Time Limit: 2s | Memory Limit: 512MiB | 题目连接
#大体思路
简单颓一颓柿子不难得到:
#Code
1 | const int N = 10000010; |
#T4 简单的数据结构题
Time Limit: 3s | Memory Limit: 512MiB | 题目连接
#大体思路
考虑将询问离线,然后维护以
#Code
1 | #define ll long long |
Gitalk 加载中 ...