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缩点后进行分类讨论