type
status
date
slug
summary
tags
category
icon
password
A. Square Counting
有 个数,每一个数 满足: 或
给你 和 ,问有多少个
- 若有 个,,
- 若有 个,,
- 若有 个,,
答案显然易见
B. Quality vs Quantity
在数组 中分别找 个数属于 集合, 个数属于 集合,
问是否存在 ,
集合都选最大的, 集合都选最小的
C. Factorials and Powers of Two
给你一个数,问它最少由多少个在 集合中的元素构成
思路是广搜,向 x 递减的方向搜
D. Weight the Tree
树形
有一个显而易见的结论, 如果当前节点是好节点, 那么它的相邻节点一定不是好节点,树大小为 的时候需特判
: 节点是好节点,以 为根的子树最多好节点的数量
: 节点不是好节点,以 为根的子树最多好节点的数量
费用计算:不难发现不是好节点的 为 ,好节点的 为相邻边数时,总和最小
注意:不能在 的时候直接储存好节点,这样会炸内存的,具体做法就是再进行一遍 ,找到好节点
E. Power Board
求
显而易见的是只有最小底数相同的才有可能相同,例如, 和 底数不相同, 和 和 的底数相同
那我们把底数相同的单独摘出来
以底数 举例
2 | 4 | 8 | 16 | … | 2m |
4 | 16 | 64 | 256 | … | 4m |
8 | 64 | 512 | 4096 | … | 8m |
都写成最小底数形式
21 | 22 | 23 | 24 | … | 2m |
22 | 24 | 26 | 28 | … | 22m |
23 | 26 | 29 | 212 | … | 23m |
既然底数都一样,那就不看他了
1 | 2 | 3 | 4 | … | m |
2 | 4 | 6 | 8 | … | 2m |
3 | 6 | 9 | 12 | … | 3m |
底数 的矩阵最后也能化成这样的矩阵
底数 的矩阵最后也能化成这样的矩阵
那么只需要求这个矩阵有多少个不同的元素就好了,跟底数是多少没有关系