ABC202

ABC202 题目

• D

求：由x个A，y个B组成的第K大序列是？

• ME：由x个A，y个B组成的序列共有(x+y)!/(x)!/(y)!个，再从高位开始逐位计算该位选a还是b，逐步缩小上下限；PS:需要高精度。
  AC代码
  核心代码（无高精度）
• 官方：我们如何确定答案的第一个字符是a还是b?可以这样判断:如果有大于等于K个以a开头的字符串，则为a，否则为b。需要提前预处理出dp[i][j]（表示i个A，j个B的排列总数量）代码

---

• E

给你一颗树，询问u的子节点（包括u）中，有多少个点深度为d。

• 题解：dfs序将树变为序列，再开个桶存每种深度的点dfs序上出现位置；lower_bound查询区间值为d的点数量。代码