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:4/5/6 rank:599

*Codeforces Round 658 D - Unmerge

• 分类：贪心
• 题目大意：给你一个 &2*n& 的序列，问你能否将其分为两个长度为 $n$ 的序列，令其归并后的序列和原序列相同。
• 数据范围：多组数据，$t \le 1000$，$1 \le n \le 2000$
• 解题思路：我们可以发现，一个数后面如果连续出现比他小的数，那么他们必定是被分到一个序列中的，利用这个性质我们将大区间拆成多个长度不等的小区间做 0，1 背包看能否构成 $n$ 长度的序列即可。
• Comment：利用归并性质进行贪心的题，思路较好。

树链剖分

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：感觉思维含量不如上一道题，而且这个前缀和优化有点麻烦（大概是我菜）。

林星涵：

===Codeforces Round 658 C2 - Prefix Flip (Hard Version)

给两个0，1串 $a,b$ ，能进行的操作是将一个前缀的0，1交换并前后翻转，求从 $a$ 到 $b$ 的操作数不超过 $2*n$ 的序列。

$ n \le 100005 $

此题构造思路较为清晰，如果原本相同，便不做改动，如果不同则看第一位是否相同，不同则直接翻转，否则先翻转第一位再翻转。

难点在于如何维护，涉及到区间翻转比较直接的想法是splay,但实际上由于该翻转操作的特殊性只要记录首尾进行交换等操作即可。

构造思路清晰，维护方式巧妙简洁。（而且我数组开小fst了。。。）

陶吟翔：

郭衍培：

求长度为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即可。

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