2020.7.18 2020牛客暑假多校训练营（第三场） prob:8/8/12 rank:36/1174

2020.7.20 2020牛客暑假多校训练营（第四场） prob:4/5/10 rank:46/1111

树链剖分

2020.7.21 Codeforces Round #658 prob:5/5/6 rank:114

• Codeforces Round 657 C - Choosing flowers
  • 分类：贪心，二分，后缀和
  • 题目大意：你要买$n$朵花，有$m$种可以买，每种无限多，每种花买第一朵有$a_i$的收益，之后每一朵都是$b_i$的收益，最大化收益
  • 数据范围：多组数据，$T \le 1000$，$1 \le n,a_i,b_i \le 10^9$
  • 解题思路：显然某种花要买很多，其他花要么不买要么买一个获得$a_i$，所以枚举哪种花买最多，然后把$a_i$排序一下在里面二分判断，需要一个后缀和进行优化，时间复杂度为$O(m \log m)$
  • Comment：比较明显的贪心题，有些细节需要单独注意
• Codeforces Round 652 C - RationalLee
  • 分类：贪心，思维
  • 题目大意：你有$n$个数要给$k$个人，每个人严格给$w_i$个，每个人的收益是获得的数的最大值和最小值之和，最大化收益
  • 数据范围：多组数据，$T \le 10^4$，$1 \le k,w_i \le n$，$w_1+w_2+ \ldots +w_k=n$，$\sum n \le 2 \times 10^5$
  • 解题思路：贪心地想，如果$w_i=1$，那么肯定尽量给大的，如果$w_i > 1$，那么先给最大值和最小值，然后把剩下的尽量往小放，这样就可以使得大的尽量能够计算在收益中。
  • Comment：非常不错的贪心题，包含了特殊判断和贪心策略
• Codeforces Round 652 D - TediousLee
  • 分类：递推，预处理，思维
  • 题目大意：初始为一个点，每个点如果没有儿子，就多一个儿子，如果有儿子就多2个儿子，有3个儿子就不会再改变每一步的时候每个不满足的点都会改变，问第$n$种状态不重复最多找几个爪子
  • 数据范围：多组数据，$T \le 10^4$，$1 \le n \le 2 \times 10^6$
  • 解题思路：从$n=3$时开始往后递推，每次上一个所在的爪子下移一位，上上次的每个爪子的两边会各出现一个爪子，并且每向下移动三次最顶上就会多一个爪子，所以递推式是$f[i] = f[i-1] + 2 \times f[i-2] + 4 \times (i\ mod\ 3==0)$
  • Comment：一道不错的递推思维题

本周无

2020.7.21 Codeforces Round #658 prob:5/5/6 rank:42

• Atcoder Beginner Contest 173 D - Chat in a Circle
  • 分类：贪心，堆
  • 题目大意：n个数，自定顺序、位置，依次放进环，收益是与其相邻的两个中较小的。求最大收益
  • 数据范围：$2\le n \le 2\times 10^5$，$1 \le a_i \le 10^9$
  • 解题思路：从大往小依次放，每次挑收益最大的位置。用堆维护一下新的收益。
  • Comment：比较明显的贪心题

• Atcoder Beginner Contest 173 F - Intervals on Tree
  • 分类：递推，树
  • 题目大意：给定一棵树，节点编号为1-n。f(l,r)表示[l,r]的点所构成的联通块个数。求$\sum_{l=1}^n\sum_{r=l}^nf(l,r)$
  • 数据范围：$1 \le n\le 2\times 10^5$
  • 解题思路：f(n,n)显然等于1。设$g(i)=\sum_{r=i}^nf(i,r)$，$g(i)=g(i+1)+(n-i+1)-\sum_k (n-k+1)$。k为与i相连，且大于i的节点。时间复杂度O(n)。
  • Comment：非常不错的递推问题

• Atcoder Beginner Contest 172 E - NEQ
  • 分类：数学，容斥原理
  • 题目大意：给定n,m，求序列a,b的个数，满足a,b长度均为n且每个数都是1-m，$a[i]\neq b[i]$，$a[i]\neq a[j],b[i]\neq b[j]$
  • 数据范围：$1 \le n\le m \le 5\times 10^5$
  • 解题思路：不妨设a是1,2,3,…,n。然后对b用容斥原理，结果为$A_m^n-C_n^1A_{n-1}^{m-1}+C_n^2A_{n-2}^{m-2}-\ldots$。最终结果再乘一个$A_m^n$（也就是a的种类）
  • Comment：裸的数学题，感觉有点乏味。

• Atcoder Beginner Contest 171 F - Strivore
  • 分类：数学，计数
  • 题目大意：求长度为k，包含子序列s的，仅由小写字母构成的字符串个数。
  • 数据范围：$1 \le |s|,k-|s| \le 2\times 10^6$
  • 解题思路：设|s|=n。考虑字符串中字典序最小的s。设最后一位是第m位。之前的n-1位有$C_{m-1}^{n-1}$种，除这n-1个位置以外，其余m-n个位置，每个位置有25种选择（不能是它后面的那个字母，否则违反字典序最小）。而第m位往后的位置，每个位置有26种选择。因此最后一位是m的字符串有$C^{n-1}_{m-1}25^{m-n}26^{k-m}$种。枚举m即可。
  • Comment：很好的数学题，不好想，方法事实上很简洁。

• Atcoder Grand Contest 046 B - Extension
  • 分类：dp
  • 题目大意：初始有一个$a\times b$的白网格，每次操作扩充一行或一列，将扩充的格子里挑一个染黑。最终扩充为$c\times d$的格子。问最终结果有多少种染色可能
  • 数据范围：$1 \le a \le c \le 3000$，$1 \le b \le d \le 3000$
  • 解题思路：dp1[i][j]表示染$i\times j$的格子，且第j行有最多一个黑格子。dp2[i][j]表示染$i\times j$的格子，且第j行有至少两个黑格子。dp2[i][j]的最后一次一定是染第i行，所以$dp2[i][j]=dp1[i-1][j]+j\times dp2[i-1][j]$。dp1[i][j]的每种方案，一定可以通过最后一次加第j列得到。$dp1[i][j]=i\times(dp1[i][j-1]+dp2[i][j-1])$。最终答案为dp1[c][d]+dp2[c][d]。
  • Comment：很显然应该用dp，但这个状态确实不好想，转移其实也没那么显然。值一道600分的题

• Atcoder Beginner Contest 046 C - Shift
  • 分类：dp
  • 题目大意：给定一个长为n的01序列。每次可以选一个0，一个1,要求1在0的右侧（不一定是紧右侧），并把1移到0的紧左侧。问最多k次操作可以得到多少种结果
  • 数据范围：$n\le 300，k\le 10^9$
  • 解题思路：等价于有若干堆棋子（可以有一堆为0），每次将一枚棋子从右侧的一堆挪到左侧的一堆，问移k次有几种方案。显然，k大于300是没有意义的。我们可以要求每一堆要么只移入棋子，要么只移出棋子。dp[i][j]表示总共已经移了i枚棋子，当前还需要将j枚棋子移到左侧。初始将dp[i][i]赋成1，最后算\sum^k_{i=0}dp[i][0]。复杂度$O(n^4)$，前缀和优化后为$O(n^3)$。
  • Comment：感觉思维含量不如上一道题，而且这个前缀和优化有点麻烦（大概是我菜）。

林星涵：

陶吟翔：

郭衍培：

求长度为k，包含子序列s的，仅由小写字母构成的字符串个数。

$1 \le |s|,k-|s| \le 2\times 10^6$

设|s|=n。考虑字符串中字典序最小的s。设最后一位是第m位。之前的n-1位有$C_{m-1}^{n-1}$种，除这n-1个位置以外，其余m-n个位置，每个位置有25种选择（不能是它后面的那个字母，否则违反字典序最小）。而第m位往后的位置，每个位置有26种选择。因此最后一位是m的字符串有$C^{n-1}_{m-1}25^{m-n}26^{k-m}$种。枚举m即可。

很好的数学题，不好想，方法事实上很简洁。这种题做起来确实很舒爽。