NOI Online 提高组第三题题解

T3.最小环题面：给定一个长度为 nnn 的正整数序列 aia_iai，下标从 111 开始编号。我们将该序列视为一个首尾相邻的环，更具体地，对于下标为 i,j(i≤j)i,j(i\le j)i,j(i≤j) 的两个数 ai,aja_...

NOI Online 提高组第一题题解

介绍这次的 NOI Online 可以说是非常难了，可以说入门组的难度已经和提高组持平。不过提高组的三道题都是很有技术含量的，需要长时间的思考才能得出正解，这也体现了提高组应有的风格。下面我们还是按照入门组研究题目的方法，硬干一下提高组...

T2.冒泡排序题面：给定一个 1−n1-n1−n 的序列 pip_ipi，接下来有 mmm 次操作，操作共两种：交换操作：给定 xxx，将当前排列中的第 xxx 个数与第 x+1x+1x+1 个数交换位置。询问操作：给定 kkk...

Description\huge{\texttt{Description}} Description 1.O(n!)O(n!)O(n!) 想法首先，N≤8N\le 8N≤8，所以说标准做法就是一个一个枚举。你当然可以用 C++ 的 ST...

1.定义：奇点度数为奇数的点欧拉路径一笔画路径欧拉回路一笔画且能回到起点的路径欧拉图图GGG能一笔画而且可以回到起点半欧拉图图GGG能一笔画但路径的起点和终点不相同哈密尔顿环 ...

1.割点的定义，相关知识和性质在一个无向图GGG中，如果有一个顶点集合，删除这个顶点集合以及这个集合中所有顶点相关联的边以后，图的连通分量增多，就称这个点集为割点集合。特别的，如果GGG联通，则是删除这个顶点集合以及这个集合中所有顶点相关...

一 · LCA的定义给定一颗有根树，若结点ZZZ是XXX和YYY的祖先，则称ZZZ为XXX，YYY的公共祖先。在XXX，YYY的公共祖先中，深度最大的一个结点Z′Z'Z′为XXX，YYY的最近公共祖先，称作LCALCALCA...

例题：给定一棵顶点带权的树，有如下的操作。修改某条路径上所有点的权值询问某条路径上所有点的权值和分析：如果树是链，那么就可以用区更区查的线段树解决。那么树该怎么办？我们用树链剖分。 1.什么是树链剖分将树上的点按照...