求赞QAQ

A-Make it Beautiful

题目
一种重新排序的尝试是首先将数字降序排列，如果第一个数字不与第二个数字相同则直接输出,相同则先输出排完序后最小的数，再输出其他数.

例如

• 3,2,5,5,7可以转化为7,5,5,3,2
• 3,2,5,5可以转化为5,5,3,2 -> 2,5,5,3

code

B-Matrix of Differences

题目

真·偶然间发现规律(以$n = 3$为例),不过首先观察样例发现佳情况应该是将所有的差包括了的($n^2 - 1$个)
$$1\overset{+8}{\rightarrow}9\overset{-7}{\rightarrow}2\overset{+6}{\rightarrow}8\overset{-5}{\rightarrow}3\overset{+4}{\rightarrow}7\overset{-3}{\rightarrow}4\overset{+2}{\rightarrow}6\overset{-1}{\rightarrow}5$$

这样刚好就填完了所有数，而且包括了所有差，以上是可以枚举到一般形式

$$1\overset{+(n^2 - 1)}{\rightarrow}n^2\overset{-(n^2 - 2)}{\rightarrow}2\cdots$$

填数字的时候，可以利用dfs搜到底的特性将二维数组填好

code

C-Yet Another Tournament

题目
设a为其他n位选手的数组，b为a排序(从小到大)后的数组

• a数组可以告诉我们其他n位选手的胜场数
• b数组可以告诉我们，题目中的”我”最大的胜场数(优先与值小的打)

设我最大的胜场数为cnt

• 如果cnt == n,那么”我”必定是第一名

再考虑其他情况:

首先”我”最多能赢cnt场，而a[cnt](下标从0开始)这个人也能赢cnt场(甚至cnt + 1),那么”我”要考虑我是否可能与这个人并列某一名(a[cnt - 1]与a[cnt + 1]都不用考虑)

如果”我”要赢他，”我”可以将最后一场比赛的选手换成a[cnt]这个人，因为最后一场比赛我剩余的m最多

• 如果我赢了，那么我还是最终赢了cnt场，由于a[cnt]输了，他也只赢了cnt场，我和他名次数相同
• 如果我输了，那我就排在a[cnt]的后面

计算下排在”我”前面有多少人，就知道”我”最好能得到什么名次

code

D-Different Arrays

题目

我们发现绘制搜索树时(以1 1 1 1为例)，有两种情况出现

{:height=”300” width=”300”}

当中间数字是0，我们看到只会延申出一种情况，非0时则会延申出两种情况

这题数据范围，肯定不允许暴搜，但是可以用记忆化搜索

对于两个状态(搜索树的节点)，我们发现如果位于搜索树的同一层，而且当前枚举到的中间那个数字相等，可以知道，它们之后的延申是类似的，也就是这两个节点对应的方案数量相同。

基于此，设记忆化搜索时状态为LL dp(int pos,int sum)

• pos : 当前中间点的位置，代表着递归搜索树的层数
• sum : 当前中间点的值,注意本题sum可能是负数

code

E-Game of the Year

题目

这道题先模拟，再优化。

模拟的思路，就是先枚举所有可能的k，检测这个k是否满足让先手的人打完所有的boss

如样例:

4
1 4 3 2
3 3 4 1

首先，如果先手解决boss需要的轮数小于等于后者，那么这显然是满足题意的情况，我们考虑先手解决boss的轮数大于后者的情况

• k = 1时，由于先手需要4轮解决第二头怪兽，后者需要3轮即可，后者先计数到3，所以不满足题意，$k \ne 1$
• k = 2时，满足
• k = 3时，第二头怪兽，后者的3轮先被计数到，所以$k \ne 3$
• k = 4时，满足

模拟写法TLE代码

优化过程主要是考虑每次计数的时候，对于每头怪兽我们都要经历如下验证:

{:height=”300” width=”500”}

如果我们计数的位置落在上图的[3,4),或者[1,2)说明我们会先枚举到后者先击杀boss，那么此时的$k$不满足要求

可以看到，我们完全可以一次性进行检验，而不必对每一头怪兽分别计数，只要计数器落到了类似[3,4)的区间，则说明当前$k$不满足要求，那么如何在$O(1)$的时间内知道我们落在了指定区间

没错，使用差分数组f，对指定区间内的数全加1，重复加没有关系，我们只要判断当前计数器落到的区间的值是否大于0即可

这样我们将时间复杂度优化到
$$\lim_{n \to \infty} n + \frac{n}{2}+\frac{n}{3} +\cdots + 1 = n(\ln n + \gamma)$$

code

剩下的题目，看了tag有亿点懵，我还是老老实实刷提高课吧( •̀ ω •́ )y