写在前面的话

首先致歉一下，M题数据弱了导致放过了部分错误解法，之后会将M题数据加强（但不重测），大家可以尝试重新提交。

这场题目以考察思维为主，另外比较考察选手的代码实现能力。

难度方面（同档次难度升序）：

easy：A D B G

mid：E M J H

hard：C F L

very hard: K I

level 1 A.茕茕孑立之影

题意：给定一个数组，找到一个正整数，使得和数组中的元素互不为倍数关系。

知识点：数学

难度：800

思路：如果数组中包含1，则不存在答案。否则输出任意一个比大的素数（比如1e9+7）即可。

level 1 D.双生双宿之决

题意：给定一个数组，判断是否为双生数组，即元素种类数为2、且出现次数相同。

知识点：模拟，排序/stl

难度：800

思路：直接将所有元素扔进map即可。也可以通过排序，check前一半和后一半是否相同，中间两元素不同。

level 1.5 B.一气贯通之刃

题意：给一棵树，找到一条路径经过所有节点。

知识点：树

难度：900

思路：判断这棵树是不是一条链，如果是则输出链上最远的两个节点，否则输出-1。

判断链的方式可以通过度数来判定：恰好存在两个点度数为1，其余点度数为2。输出两个度数为1的节点即可。

level 2 G.井然有序之衡

题意：给一个数组，每次操作可以使一个元素加1，另一个元素减1，问变成排列的最小操作次数。

知识点：贪心、排序

难度：1100

思路：可以先将给定的数组排序，之后对应位置的元素变成1~n即可。我们需要分别统计加的总和以及减的总和，如果这两个相等则有解，否则无解。

level 2.5 E.双生双宿之错

题意：给定一个数组，每次操作可以使得一个元素加1或者减1，问最小操作几次可以变成双生数组，即元素种类数为2、且出现次数相同。

知识点：排序，中位数定理

难度：1300

首先大家需要了解中位数定理：给定一个数组，每次操作加1或者减1，将所有元素变成相同的最小操作次数则是将所有元素变成中位数即可。

对于这道题而言，我们可以先将数组排序，对于前半部分我们将这些元素变成前半部分的中位数，后半部分我们将这些元素变成后半部分的中位数。注意需要特判这两个中位数相等的情况，解决方案是要么将前半部分变成中位数减1，要么将后半部分变成中位数加1，枚举这两种方案分别统计取最优。

level 2.5 M.数值膨胀之美

题意：给定一个数组，可以选择一个区间将所有元素乘2，问操作后的最小极差。

知识点：贪心，模拟

难度：1400

思路：显然我们优先将最小值翻倍。如果想要扩大区间，我们则选择“包含最小值和次小值”的最小区间，以此类推。

那么，模拟方式是，我们首先得到每个元素的下标，然后维护区间两个端点和，当我们需要翻倍的区间增大的时候（比如从最小值到次小值），只需要将向左移动或者将向右移动，直到包含当前需要选择的元素。举个例子，假设当前我们翻倍的区间是[6,8]，这时下一个待翻倍的最小值位置在11，这时我们需要将第9,10,11这三个数同时翻倍。

可以参考以下代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
pair<int,int>a[202020];
int b[202020];
signed main(){
    int n,i;
    cin>>n;
    for(i=0;i<n;i++){
        cin>>a[i].first,a[i].second=i;
        b[i]=a[i].first;
    }
    a[n].first=2e9;
    sort(a,a+n);
    int l=a[0].second,r=a[0].second;
    int ma=max(a[0].first*2,a[n-1].first);
    int res=ma-min(a[0].first*2,a[1].first);
    for(i=1;i<n;i++){
        while(a[i].second<l){
            l--;
            ma=max(ma,b[l]*2);
        }
        while(a[i].second>r){
            r++;
            ma=max(ma,b[r]*2);
        }
        res=min(res,ma-min(a[0].first*2,a[i+1].first));
    }
    cout<<res;
}

level 3 J.硝基甲苯之袭

题意：给定一个数组，问有多少对元素满足它们的gcd等于xor。

知识点：位运算，数论

难度：1500

思路：对于一个数而言，它和任意一个数的gcd一定是它的某个因子。

那么本题可以通过枚举每个元素的每个因子，作为它和其他元素的“假想gcd”，然后我们去检测是不是等于真正的即可。如果确实相等，那么证明就是真正是gcd，我们直接用map计算出现的次数。

level 3 H.井然有序之窗

题意：构造一个排列，满足每个元素都在一个指定的区间内。

知识点：贪心

难度：1600

思路：我们先将所有区间排序，用一个优先队列来维护“可选的区间右端点”。当我们指定某个区间为的时候，我们首先将所有以为左端点的区间加入优先队列，然后尽量选择目前最小的那个右端点即可。

level 3.5 C.兢兢业业之移

题意：矩形地图中给定一些箱子，将所有箱子移动到左上角的四分之一区域。

知识点：模拟/最短路

难度：1800

思路：我们只需要保证每个箱子的起点到终点的路程上没有其他箱子即可。下面给出两种做法：

做法1：对于一个需要放箱子的空位，我们先从当前位置左往右扫，扫到第一次某一列存在箱子时，向上或向下遇到任意一个箱子即可。如果扫不到，再从上往下扫，扫到第一次某一行存在箱子时，向左或向右遇到任意一个箱子即可。

做法2：对于一个需要放箱子的空位，直接用bfs跑最短路，遇到的第一个箱子路径上一定没有其他箱子，通过路径还原即可。

做法1思维难度更大，代码简单；做法2代码较难写。具体选择哪个可以自行权衡。

level 4.5 F.双生双宿之探

题意：给定一个数组，问有多少连续子数组是双生数组，即元素种类数为2、且出现次数相同。

知识点：双指针

难度：2000

思路：首先我们需要用双指针统计区间元素种类恰好为2的情况。当恰好有两种元素时，我们假设x对应1，y对应-1，那么也就是询问“有多少区间元素和为0”的问题，这样就转化为了前缀和查询。

level 4.5 L.一念神魔之耀

题意：给定一个01串，每次可以选择长度或者长度的连续子串取反，输出一个操作序列变成全1。

知识点：模拟，数论

难度：2100

思路：由于本题有 ，因此根据裴蜀定理，我们一定可以通过若干次操作达成"翻转长度"子串的效果（因为区间向右扩展的时候一定不会到达边界）。

具体的操作方式是：我们不断进行和这两种操作，当长度小于的时候进行加，否则减：假设我们需要处理的"翻转长度"这部分区间在左边部分，那么当前区间时，对应的就是翻转区间；对应的就是翻转区间。同理，在右边部分时也可以用相似的方式处理。该做法复杂度为，可以通过本题。

level 5 K.硝基甲苯之魇

题意：给定一个数组，问有多少区间满足，区间内的元素的gcd等于xor。

知识点：位运算，数据结构

难度：2200

思路：首先有一个结论：对于固定左端点的情况，移动右端点时，区间gcd的变化次数最多只有log级别。我们可以通过st表+二分找到这些区间gcd的改变点。

那么本题可以转化为以下问题：固定左端点时，有多少右端点满足区间xor的值恰好等于。

这部分我们可以通过查询区间中，异或前缀和数组里有多少恰好等于。只需要用某一种数据结构解决即可（树状数组二分/主席树/字典树等等）。

level 6 I.井然有序之桠

题意：构造一个排列，满足。

知识点：数论，构造

难度：2400

思路：本题的本质其实是构造一个排列满足。

首先如果较大，我们可以先令直到小于当前剩余未确定元素数量。

对于这个未确定元素，我们可以尝试使得其中个元素满足，那么剩余一个元素满足。

如果是偶数，那么直接令即可，对于剩下的未确定元素，我们从大到小两两一组，，由于是偶数，显然这些两两一组的元素都是互素的，那么无论是奇数还是偶数，最终最多只会剩下一个1不会被分进组。我们将对应每一组的元素交换位置，就能满足这些位置的，最终得到了一个合法的排列。

如果是奇数，显然不能直接令，因为这样不会等于1。但可以令且，这样最终达成了和一样的效果，并且仍然满足两两一组的元素互素，用类似方式两两组队后交换位置即可。

值得注意的是的特判，我们没办法采用上述方式同时赋值和，解决方案是，令且即可。这样由于，恰好达成了令的效果，同时满足剩余能组成两两一组的元素互素。