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%3==0)$
  • Comment：一道不错的递推思维题

林星涵：

陶吟翔：

郭衍培：