题目传送门首先考虑排列怎么做，排序时显然是可以将1移到下标为1的位置，然后把下标为1的位置移到它所应到的位置……直到点应到的位置为1原来的位置，就可以操作一次，使得这些点都归位。于是建图\(G=\langleV,E\rangle,V=\{i\|\1\lei\len\},E=\{(i,a_i)\|\1\le

2024.6.18T1题面给定若干个自然数\(a_{1\simn}\)。你需要选出其中一些数，然后将你选出的数划分为若干个集合。你需要最大化每个集合mex的异或和，输出这个值。\(1\lea_i\len\le10^6\)解法找出所有的\(0\to1\to2\to\cdots\tox\)链，每一个链对应集合\(\{0,1,\cdots,

前言\(2024.10.19\)日校测\(T4\)，思维太庙，被薄纱了，遂哭弱，写题解以记之。简要题意给你一个长度为\(2n\)的序列\(A,\foralla_i\in[1,n]\)，其中\(1\)到\(n\)每个数都出现了两次，现在需要把相同的两个数排到一起，每次操作只能交换相邻两个数，在保证操作次数最小的情况下求出现

加塞rnk7，\(100+30+10+15=155\)。题目来源：2022牛客OI赛前集训营-提高组（第三场）T1一般图最小匹配说的很复杂，实际水题。就是从\(n\)个数中选\(2m\)个数，两个两个求差后，求这个差的和的最小值。显然排序之后求差是最小的，但显然不能直接贪心，考虑DP。先排序，然后设\(\mathit

注意到如果把每一对胜者败者连边，可以得到一颗树：（例子）但是因为胜者每次只能和一个败者打，所以要用类似多叉转二叉的方法，让有不止一个孩子的节点变成有一个孩子和一个虚点。如图，原来\(1\)有三个儿子\(2,3,4\)，通过转换，变成了上图。上图可以直接变成对战图（\(x2\tox1\to1）\)：（原

车站分级：很好的拓扑排序题，细节有点多。图论建模首先观察对于一条线路，我们可以从中直接得到什么信息：假设这条线路的开头为\(st\)，结尾为\(ed\)，那么在\([st,ed]\)的车站中，没有被选入线路的点一定比选入线路的点的级数至少少\(1\)。对于这一点条件，我们就可以建模了。

前言比赛链接。一点部分分没打感觉要被D了。赛时题面和数据好像有出了点问题，不过我T3没做换数据不关我的事，但是T1还特殊考虑了\(a_i<0\)的情况，实则不用。T2理解错题了硬控\(2\)个多小时，发现之后改改就过了，但T3、T4没时间看了。但是这次终于不挂分了。T1简

无根树分治一般常见于树上路径问题(计数,最优化等).常见题目如无权树树上距离为k(对1到n-1求)的路径数量.点分黑白且可以改,求两端都是黑点的最远路径.以我的理解,三种分治都是无法互相平替的,对于每种分治我尝试给出一道只能用这个分治的题目.三种分治复杂度均为logn*T(n).

原题分析本题由于从一个节点发信息，同一个集合内的所有点都会收到信息，显然是一道要求维护各节点间关系的题，因此采用并查集的数据结构进行求解。但由于维护关系的同时还要维护权值，所以采用带权并查集，它是一种能维护某个节点与其祖宗节点之间关系的数据结构。带权并查集找父亲的

原题链接：Problem-G-Codeforces思路：根据题意可知相同颜色的边一定是联通的，那么就可以设置虚点，例如1-2，2-3，3-4边的颜色都是相同的，那么就可以设置一个特殊的点例如设置为10，那么这三条边就可以改成1-10，10-2，2-10，10-3，3-10，10-4，从点到虚点需要1的代价，但是从虚点到其他点不需要代价，

F-TeleporterSetting题意：给出n个顶点和一些边，其中一些边两个端点确定，另一些边只有一个端点确定，对于每个i，令其为所有这些不确定的边的另一个端点，问1到n的最短距离是多少。建立一个虚点，然后f,g分别表示1，n到x的最短距离，分别计算两种经过i的情况，以及可能不经过i的情况即可。#i

前言：这次还行，今年的最后一场比赛，300pts，rank4T1赛时摆烂了，没有牢记“正难则反”，打了暴力，还挂了正解从后往前考虑，考虑在这个点对后面的点的影响，发现就是p乘上了一个系数，直接从后往前算的时候乘上即可，最后再考虑初始的wT2发现取权值连续的一段数一定是最优的，随便维护一下即可T3

原题：http://222.180.160.110:1024/problem/30291考虑建图找最短路很容易想到以每个点作为结点，对同一行，同一列的点连边。但是这样建图边数最大能达到\(1e9\)很经典的操作就是对每一行，每一列，建一个虚点。每个点都连向其对应的行、列的虚点。这样的话，就比同一行（列）的点两两连边更

A如果有\(()\)那么肯定是不合法的有两种很简单的构造，()()()()...()和((((...))))，如果一个串是第一种构造的子串那么一定不是第二种构造的子串，反之亦然。使用python取之B把\(m\%k\)的余数补齐，再把多出来的\(1\)价格regularcoins\(m\)个一组f使用python取之C

P9535「YsOI2023」连通图计数非常好题目，爱来自湖南。\(m=n-1\)等价于给定度数求树的个数，这是一个经典题，在「HNOI2004」树的计数有描述，即利用Prufer序列得到答案为\(\binom{n-2}{(d_1-1)(d_2-1)\ldots(d_n-1)}\)。\(m=n\)即基环树，对于整个大环建立一个虚点，该点向环上的所

Kruskal重构树1.概念在进行Kruskal算法求解最小生成树时，添加若干虚点，使求得的树成为二叉树，二叉树的叶子节点为原图中存在的节点，且每个虚点都有一个权值，为左子树中的点到右子树中的点的简单路径的最大边权。2.实现方法仍然按照Kruskal算法按照边权从小到大加入边：1.新建n个集

我原以为弹弓较难在中距离上实现精确射击，因为当时我采用的是竖握瞄打方式，具体是左手竖握弓体，让弹丸，弓门中点和目标处于一条直线上，用右眼进行校准。这种方式因为弓门中点是虚点，超过3米就容易失去准头。后来我接触了横握瞄打，发现中距离也能实现较精准射击。具体来说是左手横握弓体，让

妈的，做的题怎么这么少2.26[JOI2020Final]火事-洛谷想法：前三档部分分小孩子不懂事出着玩的。第四档部分分所有点只会经历一次\(1\)到\(2\)的过程，询问排序后

Link题解首先需要学习边分治。边分治和点分治都属于树分治，但点分治是找重心，边分治是找“重心边”（即两端子树\(\text{size}\)最大值最小的边）。然而直接找重心边复杂度

E：简单最短路，加一维表示当前是否翻转所有边的状态即可。CodeF：先考虑简化版本，如果\(\left\{A\right\}\)中没有\(0\)，如何判定。重新表述一下条件，令\(mn_i,mx_i\)分

假设当前位于$A(x,y)$，将坐标系按上下左右、(左/右)(上/下)分为八块引理：存在一组最优解，每次均移动到某一块中距离$(x,y)$最近的某点记$d(A,B)$为$A$到$B$的切比雪夫距离，

ABC-270F-Transportation(kruskal)考虑等价转换，建立两个虚点(分别表示airport和harbor的中转站)。这样就可以把点统一为边权问题。对于操作1和操作2，就是等价于向虚点连边

这次还是很逊，又考炸，T1都没签上到，T4没\(longlong\)->0，数据都没看清T1死在了边界条件，真烦，不过这也说明自己不够细心，以后需要注意才是T2是一道挺好想的东西，但T1调试过久，故