#MXCSPJ0102. MXCSP-J第一套模拟卷T2 拆分数字(split)
MXCSP-J第一套模拟卷T2 拆分数字(split)
T2 拆分数字(split)
容易发现,对于所有 都一定能表示(指用 ),不过不一定是 个数。那我们可以求出最少和最多用多少个数表示,再看看能否累加或减少到 个。
首先最多一定是 ,最少则是 在三进制下的非零数的个数,不妨设其为 。如果 ,一定无解, 有解。 则需要尝试拆分调整。
观察到我们可以进行这样的拆分:,即进行这样的一次拆分可以使原本的 增加 。而 ,所有 一直拆分下去,一定有一个时刻 。只需要判断 的奇偶性是否相同即可。