NOI2021-线上 游记
nxt_permutation · · 个人记录
前言:深刻体会到了与金钩大佬间的差距
Day1
T1
- 看到题面“轻重边”后想到了树链剖分,但是由于只会基础的树链剖分的思路,所以并没有想出合适的用树链剖分的方法。
考场思路:判定一条边为重边的标准是:它的边权等于它连接的两个点的点权,否则则为轻边。
- 操作1:每次修改为轻边的操作只要将那个经过的点的点权加上1,然后再对操作路径上所有的边权加为其连接的两个点的点权,即可改为重边。
- 操作2:暴力搜索统计即可。
- 复杂度为
O(nm) ,实际上真正写的时候比这个还暴力,测试点1,2用了O(n^2m) 的算法,因为代码实现能力不是很好,所以花了4h左右的时间才搞定,导致7,8的测试点的线段树没来得及写完,有些可惜吧。题解-Luogu①:对点进行涂色(常用树剖/线段树套路)
- 操作1对于路径上的点进行新颜色的染色,这样必然保证轻边连的两个点的颜色是不同的,路径上的边(重边)连的两个点的颜色是相同的。
- 操作2直接查询邻点颜色相同的对数即可。
- 线段树操作与线段树最大子段和的思想类似,维护区间最左颜色,区间最右颜色以及区间内符合的个数维护,在进行具体的实现。
- 复杂度为
O(mlogn) 题解-Luogu②:LCT(待写)
T2
由于T1做了4h+,导致T2T3只能写暴力分了QwQ 不过分还是没有骗到,有些细节处没有写对
考场思路(20分部分分)
- 暴力枚举即可,判断与给定的要求是否符合,直接统计逆序对数量即可。
题解-Luogu①:矩阵行列式(待写)
题解-Luogu②:LGV引理(待写)
T3
考场思路(16分部分分)
- k=0的情况下,用dfs或bfs直接暴力统计经过的城市的个数即可。
题解-Luogu①:tarjan缩点后进行分类讨论