信息
- ID
- 37
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 5
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者
容易发现,对于所有 n 都一定能表示(指用 30,31,…),不过不一定是恰好 k 个数。那我们可以求出最少和最多用多少个数表示,再看看能否累加或减少到 k 个。
首先最多一定是 n=30×n,即使用 n 个 1;最少则是 n 在三进制下的非零数位个数,不妨设其为 m。
观察到我们可以进行这样的拆分:3i=3i−1+3i−1+3i−1,即进行一次拆分可以使原本的个数 m 增加 2。而 n≥k,所有 30 一直拆分下去,一定有一个时刻个数 ≥k。因此只需要判断 m,k 的奇偶性是否相同,即 (k−m) 是否为偶数即可。