前言题目链接：Codeforces；洛谷。题意简述你有一个长度为\(n\)的序列\(p\)满足\(p_i=i\)，你可以进行\(x\)次操作，每次操作找到两个不同的\(i,j\)并且交换\(p_i,p_j\)，问最终有几个可能的序列。分别求出\(x=1,\ldots,k\)时的答案。\(1\len\le10^9\)，\(1\lek\le

原题链接题解观察一个二分图会发现同一组的节点不直接相连二分图能够建立的最多的边等于\(n*m\)code#include<bits/stdc++.h>usingnamespacestd;#definelllonglongvector<ll>G[100005];lldepth[100005]={0};llodd=0,even=0;voiddfs(llnow,llfa){i

原题链接题解1.任意两条边在且仅在一条链上2.一定存在一条链使得其包含边权为0，1的边，这个时候我们要让2不在01所在的链上，即如下情况：此时01所在链答案为2，02所在链答案为一3.如果树退化成了链，那么不管怎么构造都一样由此得出，找出这样的T型节点，即含有三条边的节点，然后在它上

EhabandtheExpectedGCDProblemLuoguCF1174E题目描述\(p\)是一个排列，定义\(f(p)\)：设\(g_i\)为\(p_1,p_2,\cdots,p_i\)的最大公因数（即前缀最大公因数），则\(f(p)\)为\(g_1,g_2,\cdots,g_n\)中不同的数的个数。设\(f_{max}(n)\)为\(1,2,\cdots,n\)的所有排

https://codeforces.com/contest/1325/problem/D有一个非常经典的结论a+b=(a^b)+2(a&b)这个题就可以往上面靠，首先我们观察一下，对于两个数的情况，如果(v-u)mod2=1,必然无解，试着将它扩展一下，也是对的，因为最低一位没有进位。可以确定的是ans<=3仿照上面的式子，令a=u,b=c=((a+b

题目大意：给出长度为\(n(1\len\le10^5)\)的数组\(a\)，构造数组\(b\)使得\(a_i=MEX\{b_1,b_2,...,b_1\}\)首先考虑当\(b_1,b_2,...,b_n\)为什么数时，\(a_n=MEX\{b_1,b_2,...,b_n\}\)。然后再考虑当\(b_1,b_2,...,b_{n-1}\)为什么数时，\(a_{n-1}=MEX\{b_1,b_2,...,b_{n-1}\}\)。

X-OR题面翻译题目描述本题是交互题。有一个固定的长度为\(n\)的排列\(P\)，其值域为\([0,n-1]\)，你可以进行不超过\(4269\)次询问，之后你需要输出这个排列\(P\)。输入格式第一行有一个正整数\(n\)，表示排列的长度。保证\(3\len\le2048\)，\(0\leP_i\len-1\)。交互格

C.EhabandPath-eticMEXs对于成链的情况，\(\text{MEX}=n-1\)一般的，一定有一条路径包含0和1，则可以确定\(\text{MEX}\geq2\)，观察发现，对于度数\(\geq3\)的点，我们在他的三条边赋值为0,1,2使得其他路径的边有:0,1,...0,2,...1,2,...即一条路径上的边不能同时有0,1,

a[i]<=i，否则当a[i]>i时，需要1~i项有数字0~a[i]-1，这一共是a[i]个数字，而1~i项只有i个数字，需要的比拥有的数字多，不成立当a[i]!=a[i-1]时，说明Mex改变了，那么需要b[i]为a[i-1]才

MahmoudandEhabandtheMEXDr.EvilkidnappedMahmoudandEhabintheevillandbecauseoftheirperformanceintheEvilOlympiadinInformatics(EOI).Hedeci

传送门思路dfs树的一道出色的应用题令\(k=\lceil\sqrtn\rceil\)我们先按照遍历的顺序构建出dfs树对于一条返祖边\((u,v)\)，如果有\(dep_u-dep_v+1\gek\)，