Harbour.Space Scholarship Contest 2023-2024 (Div. 1 + Div. 2)（A-

开头介绍：这场题目的思维考察真的很多，如果思维量不够的话，做起来确实很容易翻车，大家如果发挥失常的话，也不用很担心，思维题本来就是方差比较大，然后题解可能写的比较繁琐，主要是昨天也有同学有点疑问，所以写的稍微长点。

A题：

题目大意：给你x，y，n的值，你需要构造一个长度为n的数组a，其中你的构造需要满足以下几个条件：

1、满足

2、满足，注意这里使用的是小于号，所以是严格小于。

3、对于所有，可以得到，你需要满足。

注意构造可能存在很多种情况，你可以输出任意一组情况，但是如果没有正确的构造方式，请输出-1。

输入描述：第一行输入x，y，n，描述如上文。1

输出描述：若存在构造情况，输出任意一组，如果不存在则输出-1.

例子解释：

1 4 3

对于这个例子，我们给出1 3 4的构造，可以发现其b的值为2，1满足严格递减，a的值为1,3,4也满足严格递减。

思路分析：

对于这个问题，我们可以发现从点出发不好解决，因为我们无法假设的值，以及后面会怎么样的变化，在这里我们发现如果要保证2条件和3条件，那么我们的值得要大于等于n-1,因为根据3条件，我们的b每次都要至少下降一个值，根据我们的2条件，可以发现b不能等于0。但是我们无法确定这样的做法会使得最后一个a是y。所以我们反向思考。

从开始思考，显然我们可以发现这个最少为1，而且如果我们的b取小了，那么多余的值可以赛给最前面的b，那么其实就已经发现了如何构造。

构造方式：从开始，让以此类推，直到最后算出来使得构造满足的最大的值，如果x小于等于，那么问题不大，反正可以增大，如果x大于，那么这样的构造便不存在，直接输出-1.

代码部分：

B题：

题目大意：现在存在一个长度为n的字符串s，然后你会知道k的值是多少，现在你可以进行任意次数的下述操作，你需要使得给定的字符串字典序尽可能最小。

1、对于所有的情况，交换和。

2、对于所有的情况，将的所有字符全部逆序。

请输入得到字典序最小的情况。

输入描述：第一行输入n，k，代表字符串长度和k值。第二行输入字符串。

输出描述：输出经过任意次操作得到的上述字典序最小的字符串。

例子解释：（题目例子解释的很好，不是我偷懒）

4 2

nima

思路分析：首先我们可以思考一下这个问题，乍一看感觉非常难，因为实际上我们并没有什么直观的贪心做法，但是各位千万别急，想一想这题才只是b题，怎么可能那么难，所以我们可以往简单方面考虑。

首先我们发现第一个操作，实际上只能交换下标奇偶性质相同的字符，那么第二个操作，如果可以交换下标奇偶性质不同的字符，那么这个字符串我们想怎么变化就怎么变化，反正可以变回来。于是我们分析第二个操作。

第二个操作，如果对于一个奇数区间，可以发现我们的交换，实际上还是让每个奇偶性质相同的元素之间在交换，那么我们最好的构造方式，就是分开奇偶位置，每次把字典序最小的字符放在最前面，然后再把奇偶合在一起。如果对于一个偶数区间，我们发现每次可以交换奇偶性质不同的字符，那么我们字符串可以任意构造，那实际上就是对字符串进行排序。

代码部分：

C题：

题目大意：给你一个x，现在你需要对x进行操作，使得x最后的值变为1，对于操作的描述如下：

选择任意一个能够整除x的值（除了x本身），将这个值称为d，然后x需要减去d。（需要注意每一个值，d都只能选择不超过2次）

例如 x==5

现在你需要输出你的构造过程，如果有多个构造，输出任意一个构造即可。

输入描述：输入x的值，描述见上文。

输出描述：第一行输出整个构造的长度（你所输出的长度不能超过1001），第二行输出每个操作的时候x的值。

思路分析：这题也是一道思维题，首先注意到选择一种类型的d，不能超过两次，以及这道题目提到的整除，那么我们可以尝试往二进制的方向思考。

首先我随便胡诌一个二进制数字，1101101，对于这个二进制数字，我们可以发现我们能够把右边的1一个一个删掉，比如1101101可以被1整除，后面变成1101100，然后发现可以被100整除，然后变为1101000，以此类推，可以变为1000000，然后对于这个数字实际上我们可以考虑每次减半，比如1000000可以被100000整除，那么他会变成100000，以此类推，我们发现一个值最多选两次，很好地解决了这个问题。

D题：

题目大意：首先给你一个n*n的01矩阵，在这个矩阵中，我们可以对一个点进行一种操作，对操作进行描述，具体描述如下：

选定（i，j）这个点，然后对于所有的点，只要其y坐标满足，那么我们就对这些点进行翻转（0->1，1->0）。

请问我们需要最少多少次操作才可以使得这个01矩阵变成全部为0.

如果你还不理解上述的操作，存在更直观的方式，看例子。

对于如上的这个例子，实际上就一次操作，也就是选择第一行的第三个点，然后下方所有的1点都会翻转。

输入描述：第一行输入n的值，后面输入整个矩阵。

输出描述：请输出最少需要多少次操作把全的值都变成0.

思路分析：实际上这道题目非常像一道经典的题目，《费解的开关》，大家可以去搜索一下，其中有个很重要的想法，就是每一行的操作实际上都是知道的，因为我们第一行实际上只能影响到第二行以后的，以及自己这个点，所以我们可以确定哪些点需要进行这个操作。那么问题来一个点会影响的点会非常多，那么我们又怎么去解决多更改情况呢？显然每次更新一个点暴力的更新是一定会超时的，那么如何解决这个问题？

我们可以发现对于一个点更改，我们可以给一些点打上标记，每次访问到的时候，再对其进行更新，由此我们可以保证其复杂度。关于一个点操作之后，给哪些点打上标记，大家可以想一想，代码部分中我们也会提到。

代码部分中，说道下下方点抵消影响，实际上就是当左下有点，和右下有点，中间会有一个部分被操作两字，翻转两次等于没有翻转，所以要在下下点进行记录抵消

代码部分：

E题：

题目大意：现在有一个长度为n的数组a，现在我们从中随机选择两个数字，然后我们进行以下操作。（和的值可能相同）

令。

1、将的值告诉Alice

2、将的值告诉Bob

3、，将的值告诉Alice和Bob（|表示按位或）

然后以Alice率先开始，随后Bob循环回合。

Alice和Bob要做的事情就只有一个，就是猜对面的数字和自己数字的大小关系，换句话说，假如我们是Alice，只要我们可以确定a<b，a>b，a=b其中一种，那么游戏就结束。

在每个人的回合中，如果一个人已经确定了大小关系，他就会说出来，然后游戏结束，如果不确定大小关系的话，那么就会告诉对方我不知道大小关系。

现在你需要算出来游戏结束的期望轮数。

结果对于998244353取模。

输入描述：第一行输入n，第二行输入数组中的元素，

输出描述：输出游戏结束的期望轮数。

思路分析：很好发现的是，我们要算期望，实际上我们知道有多少种组合，那么我们只用把所有组合情况的轮次和算出来，最后再用分数取模，就可以计算出答案。但是为了解决计算所有组合情况下轮次和，我们其实需要分析清楚两个问题。

问题1：知道了两个数字如何计算他们要进行多少轮？

问题2：这题的数据范围是2e5，两两个数字组合一共有4e10种，显然得要有更高效的解决方式。

首先考虑问题1，以Alice的视角来看，我们得到两个数字，那么什么时候我们可以立刻判断出关系呢？我们将数字分解为二进制来看，显然当中存在一个没有的高位1，那么这个1只可能来自于，因为是高位的1，那么自然也就知道。我们将这个想法延伸，我们可以发现，如果一开始不能判断，实际上就是和的最高位置1在同一位置，不确定中是否存在这个高位的1。然后轮次交换，实际上大家都已经互相知道对方的最高位是几了，所以每次回合都是在判断目前的高位1，自己手上的元素，在这里是不是1，如果是就结束，如果不是就轮换。

我们来介绍一个例子，a=2,b=3,c=3。

先转化为二进制a=10，b=11，c=11。

Alice：首先a和c的第一个位置都是1，无法确定b的第一个位置是几，Alice说不知道

Bob：由于上面Alice说不知道，所以a的第一个位置肯定是1，但是b的第一个位置也是1，无法确定，然后再看第二个位置，我们发现b和c的第二个位置都是1，无法确定a的第一个位置是几，Bob说不知道。

Alice：首先Bob说不知道，那么b的第二个位置一定是1，现在我们确定了b的值，所以Alice说出了我知道！

上述例子的过程为3个轮次，判断轮次过程大概就是这样子的思路。

然后我们考虑问题2，首先不可能两个两个全部枚举出来，但是我们发现，由于我们解决问题1中得到的性质，我们发现先枚举一个数字，他和别的数字之间的轮次是多少，其实和二进制的形式有关，比如说10和所有大于等于100的值，永远都是10可以立刻发现大小关系，实际上我们可以通过二分去解决这个问题，快速找出一个次数下有多少个情况满足。需要注意的是，要经过多少个轮次，实际上和现在前面有多少个1有关，因为有0直接判断出来，有1的话，则是不确定。

那么根据这个想法就可以写出代码了。

代码部分：

E题应该也有其他的解法，但是up比较菜鸡，只能想出这种方法，希望大家见谅。

注意第四个例子的答案实际上是187，大家可以去根据这个例子改一改。

F题：

还没看，如果会写就去补了