2020.7.12 2020牛客暑假多校训练营（第一场） prob:4/7/10 rank:56/1115

2020.7.13 2020牛客暑假多校训练营（第二场） prob:4/9/11 rank:162/1158

无

2020.07.11 AIsing Programming Contest 2020 prob:4/5/6 rank:590

• atcoder E - Camel Train
  • 分类：贪心
  • 题目大意：对于一个队列，里面每个元素有 $li,ri,ki$ 三个量。当期排在前 $ki$ 时价值为 $li$, 否则为 $ri$, 求一个序列最大化价值。
  • 题目解法：我们对其按 $li-ri$ 正负进行分类再按k从小到大/从大到小排序，并分别从前后用小根堆来进行贪心即可（随时保证堆内元素小于等于 $ki$ 个或是 $n-ki$ ）

LCA问题

2020.07.11 AIsing Programming Contest 2020 prob:4/5/6 rank:933

• Educational Codeforces Round 91 C - Create The Teams
  • 分类：贪心
  • 题目大意：有$n$个程序员要进行分组，每个程序员有能力值$a_i$，现在要求一个组能力值最低的程序员的能力乘以总人数至少要有$x$，问最多能分几个组
  • 数据范围：多组数据，$T \le 1000$，$1 \le n \le 10^5$，$1 \le a_i,x \le 10^9$
  • 解题思路：显然每个组人越少越好，所以我们从大到小开始贪心，能一个人就一个人，不能就看能不能两个人、三个人，以此类推即可，时间复杂度$O(n \log n)$
  • Comment：比较简单的贪心题
• Educational Codeforces Round 91 D - Berserk And Fireball
  • 分类：分类讨论，模拟
  • 题目大意：有$n$个士兵排成一排，每个士兵有能力值$a_i$且各不相同，你可以进行两种操作，一种是花费$x$消灭连续的$k$个士兵，一种是花费$y$使两个相邻的士兵中能力值较低的被消灭，问能不能把给出的士兵消灭成特定位置的士兵留下来的排列，如果能，最小化花费
  • 数据范围：$1 \le k \le n \le 2 \times 10^5$，$1 \le x,y \le 10^9$
  • 解题思路：由于保证了士兵能力值各不相同，我们先确定哪些士兵被留下了，然后以区间的形式消灭不留下的。对于一个区间，如果长度小于$k$，那么区间两端的值必须有一个大于最大值，否则删不干净，这时只能用第二种操作。如果区间长度大于等于$k$要分类讨论，如果$y \times k < x$，那么显然应该用最大值一直删，否则把区间长度删成$k$的倍数然后删光，这时还是要判断能不能用最大值删干净，如果不行就必须删到只剩$k$然后用一次第一种操作
  • Comment：题目本身的操作并不是很难，只要从士兵能力值各不相同的条件能够想到以区间为单位删掉不用留下的士兵，接下来就只需要注意细节了
• Codeforces Round #654 (Div. 2) D - Grid-00100
  • 分类：思维，模拟
  • 题目大意：给出$n$和$k$，要求构造一个$n \times n$的01矩阵，矩阵中有$k$个1，且$(max\{R[i]\} - min\{R[i]\})^2+(max\{C[i]\} - min\{C[i]\})^2$最小，$R[i]$表示第$i$行有几个1，$C[i]$表示第$i$列有几个1
  • 数据范围：多组数据，$T \le 100$，$1 \le n \le 300$，$1 \le k \le n^2$，$\sum n^2 \le 10^5$
  • 解题思路：显然我们要同时使每一行和每一列的1的个数都尽量平均，首先想到的就是先往从左上到右下的对角线上放，之后多试几次就会发现可以依然按照这个规律来放，先放右上方的$n-1$个，剩下一个放到左下角，然后以此类推可以保证答案最小
  • Comment：一道不错的思维题，代码难度也比较低，不过感觉放在D题有点偏简单（1600分的题）

矩阵树定理

2020.07.11 AIsing Programming Contest 2020 prob:4/5/6 rank:826

• Codeforces Round #655 (Div. 2) C - Omkar and Baseball
  • 分类：思维
  • 题目大意：给定一个1到n的排列，一次操作选中连续的一段，改变其中每个元素的位置（不能还在原来的位置）。问最少几次操作使其递增。
  • 数据范围：$1 \le n \le 10^5$
  • 解题思路：对任意一段，我们一定可以通过一次操作使得$a_i\neq i$
  • Comment：不是很难

• Codeforces Round #655 (Div. 2) D - Omkar and Circle
  • 分类：思维
  • 题目大意：给定一个长度为2n+1的环。每次操作，可以选中一个数，用它两边的数之和代替这个数，并删除它两边的数。最终只会剩一个数，问这个数最大是多少
  • 数据范围：$1 \le n \le 10^5$
  • 解题思路：显然，最终的结果一定是这个序列中若干元素之和。可以证明，这些元素最多有一组在原先数列中是相邻的。所以只需要看是哪组相邻，然后剩下的隔一个选一个。
  • Comment：结论很难想

• Codeforces Round #655 (Div. 2) E - Omkar and Circle
  • 分类：区间dp
  • 题目大意：n行m列的方格，每行被划分为连续的若干块。在每块中选一个地方填1。设第i列有$q_i$个1，使得$\sum^n_1q_i^2$最大。求这个最大值
  • 数据范围：$1\le m,n\le 100$
  • 解题思路：大致的思路是区间dp。dp[i][j]表示所有完整包含在[i,j]列的块所能做出的贡献，最终答案即为dp[1][m]。首先证明，在最优策略中，对于[i,j]区间，一定存在一列k，满足所有完整包含在[i,j]列且覆盖k的块都在k填了1。因为我们显然希望1尽量地聚集，我们选择1最多的一列，将其他列的1移到这一列，一定使结果变优。所以$dp[i][j]=max\{dp[i][k-1]+dp[k+1][j]+(num[i][j]-num[i][k-1]-num[k+1][j])^2\}$，其中num[i][j]表示在[i,j]列内的块数。
  • Comment：很好的区间dp

林星涵：

题目链接

题目大意：给一个 $N \le 200000$ 位的二进制数，定义 $f(x)$ 为这个数除以其二进制中 1 的个数的余数。问依次将其每位的0、1互换，得到的数需要经过几次 $f(x)$变为0.

解题方法：我们不难发现这种变的方式 1的个数只会进行正负1的变化，这样的话我们只用对两个模数进行预处理。第一次取模之后数据范围变小便可以进行暴力处理。

推荐理由：这种表面上范围很大的题目，很多时候可以考虑第一步的特殊情况进行处理，达到从第二步开始范围就缩小的效果。这种思想极其重要，运用也较为广泛（像是区间取根号）。

陶吟翔：传送门

题目大意：有一个区间$[1,n]$，现在可以进行操作把区间$[l,r]$变成$[l-1,r],[l,r-1],[l+1,r]$或$[l,r+1]$，但是一旦区间变成$[l,l]$就不能再变，现在有$m$个选择，你可以花费$c$把某一个区间$[l,r]$向$[l-1,r]$或$[l,r-1]$的操作禁止，问能不能完全避免把区间变成$[l,l]$，如果能，最小花费

数据范围：$2 \le n \le 500$，$0 \le m \le n(n-1)$，$1 \le c \le 10^6$

解题思路：可以把整个过程看作在一个$n \times n$的网格上从$(1,n)$走向对角线，我们可以断开其中某些地方使得不能从起点走到对角线上，这显然是一个最小割模型，考虑到这道题数据规模较大而图又比较规则，所以我们可以采取建对偶图的方式求解

推荐理由：这道题看似是一道区间题，但是可以通过转化将其与最小割模型建立联系，考察了做题者对模型进行转化和理解的能力，并且本题建立对偶图虽然有多种方式，但是都必须要保证从起点到终点所经过的一条路径能够组成一组割，考察了做题者对对偶图的理解。

郭衍培：

题目链接

题目大意：n行m列的方格，每行被划分为连续的若干块。在每块中选一个地方填1。设第i列有$q_i$个1，使得$\sum^n_1q_i^2$最大。求这个最大值

数据范围：$1\le m,n\le 100$

解题思路：大致的思路是区间dp。dp[i][j]表示所有完整包含在[i,j]列的块所能做出的贡献，最终答案即为dp[1][m]。首先证明，在最优策略中，对于[i,j]区间，一定存在一列k，满足所有完整包含在[i,j]列且覆盖k的块都在k填了1。因为我们显然希望1尽量地聚集，我们选择1最多的一列，将其他列的1移到这一列，一定使结果变优。所以$dp[i][j]=max\{dp[i][k-1]+dp[k+1][j]+num[i][j][k]^2\}$

推荐理由：这道题其实不难想要采用区间dp，但在dp过程中，状态和转移都不太好想，尤其是转移。转移需要一个结论，而这个结论我一开始没有想到。事实上，这刚看到题解的时候（题解无证明），我甚至还感到惊讶。但仔细一想，其实并不是很难，这需要对这个模型有一定的理解，发现取到最优情况时的一个性质。