SDOI2024（二进制思想好题）

link.
我草这题只有橙我草这题只有橙我草这题只有橙我草这题只有橙我草这题只有橙我草这题只有橙我草这题只有橙我草这题只有橙我草这题只有橙我草这题只有橙我草这题只有橙我草这题只有橙我草这题只有橙我草这题只有橙我草这题只有橙我草这题只有橙。
考场上想的分解质因数直接偏离航线了……
记录一下正确做法。
我们发现每次遇到奇数就会犹豫，所以我们应该尽可能降低奇数的出现次数，体现在二进制上就是为 \(1\) 的位尽可能的少。
偶数的情况我们当然不用考虑，这里考虑奇数的时候到底是加 \(1\) 还是减 \(1\)。
我们考虑加 \(1\) 会发生什么，答案是将一个二进制奇数末尾连续的一串 \(1\) 变成 \(0\)，并且将最低位的一个 \(0\) 变 \(1\)。
减一只会把末位的 \(1\) 变成 \(0\)。
这是不难发现当且仅当这个数末位只有一个连续的 \(1\) 时减优于加。
首先充分性很好证，口胡一下必要性。
如果末尾的连续的 \(1\) 大于等于 \(2\) 个时，加 \(1\) 会至少减少 \(2\) 个 \(1\)，另外制造一个 \(1\) 出来，所以至少减少一个 \(1\)，但是减 \(1\) 顶多减少一个 \(1\)，得证。
可以采取记忆化搜索的方式降低复杂度。

#define int long long
unordered_map < int ,int > m ; // m[a] 表示有 a 只猫猫的最少犹豫次数 
int t ;
inline int out (int x) {
	if (x == 0) {
		return m[0] = 0 ;
	} 
	if (x == 1) {
		return m[1] = 1 ;
	}
    // 0/1 可以直接特判
	if (m.find (x) != m.end ()) {
		return m[x] ;
	} // 记搜
	if (x & 1) { // 奇数
		int a = x + 1 >> 1 ,b = x - 1 >> 1 ; // a/b 表示加/减 1
		return out ((x & 3) == 3 ? a : b) + 1 ; // 注意 3 的二进制是 11，要是 &3=3 说明末尾至少有两个连续的 1，别忘了把犹豫次数加 1
	}
	return out (x >> 1) ;
}