小红书9.29笔试ak分享

第一题 容斥原理 
 定义集合 A 和 B：
A：比 max_p 大的数字集合 A_size = 9 - max_p
B：比 min_p 小的数字集合 B_size = min_p
 ans=10^n−(10−A_size)^n−(10−B_size)^n+(10−A_size−B_size)^n
第二题  

解释：

生成勾股数三元组 (generate_pythagorean_triplets):

使用欧几里得生成法，遍历所有满足条件的 m 和 n，生成原始的（不可约的）勾股数三元组。

对每个原始三元组，生成其倍数版本，直到总和超过 max_sum。

将所有生成的三元组存储在一个列表中，并按总和、然后按 a, b, c 排序。

预计算答案 (precompute_answers):

创建一个答案数组 ans，其中 ans[k] 存储的是满足 a + b + c >= k 的最小勾股数三元组。

遍历排序后的三元组列表，对于每个三元组，将其分配给所有尚未分配且 k 小于等于当前三元组总和的位置。

确保每个 k 只被分配一次，以保证选择的是最小的总和，并在总和相同时选择字典序最小的三元组。

第三题 树上dp
状态定义

定义 dp[x][k][j] 表示在以节点 x 为根的子树中，购买 k 件商品，j代表是否使用优惠券，商品间的依赖关系构成了树的边