脚本宝典收集整理的这篇文章主要介绍了CF1560D Make a Power of Two 题解，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。

Content

给定一个整数 (n)。每次操作你可以做两件事情中的一件：

• 删去这个数中的一个数位（如果这个数只剩下一位，则可以把它删空）。
• 在这个数的右边添加一个数位。

你可以以任意顺序执行无限次操作。但请注意，在删去一个数位之后，这个数可能包含前导零（例如在删去 (301) 中的 (3) 这一位之后，这个数就会变成 (01) 而不是 (1)）。

你需要执行若干次操作，使得这个数最终变成一个 (2) 的次幂，或者说存在一个非负整数 (k) 使得这个数最终是 (2^k)。最终答案不能包含前导零。请求出需要执行的操作的最小次数。

数据范围：(t) 组数据，(1leqslant tleqslant 10^4)，(1leqslant nleqslant 10^9)。

Solution

这题目讲究的就是一个枚举。由于 (2) 的次幂是呈指数级增长的，因此在 (10^{18}) 的范围以内的 (2) 的次幂也只有 (59) 个。所以我们可以直接枚举每一个 (10^{18}) 以内的 (2) 的次幂，求出当前数修改成每个 (2) 的次幂需要的最小操作次数，取最小值即可。这种枚举方法在本题中亲测可过。

其次，如何求出当前数修改成 (2) 的次幂的最小操作次数？我们不妨将数转化为字符串，然后考虑尽量多地去做第一种操作，留下 (2) 的次幂或者 (2) 的次幂的一个前缀，因此这可以转化为求出第一个数字串的最长前缀子序列，直接拿一个指针比对即可。设第一个数字串的长度是 (l_1)，第二个数字串的长度是 (l_2)，求出的第一个串的最长前缀子序列的长度为 (len)，那么最小修改次数就是 (l_1+l_2-2cdot len)，因为需要 (l_1-len) 次第一种操作将不是子序列中的数字删除，另外还需要 (l_2-len) 次第二种操作将 (2) 的次幂的前缀变为 (2) 的次幂。

注意这里要枚举到 (10^{18})，因为它可能在这个数的右边添加一个数位，所以直接枚举到 (10^9) 显然无法枚举完整所有的情况。

Code

namespace Solution {
	const int N = 67;
	int cnt;
	string ans[N];
	
	inline string ll_to_str(ll x) {
		string ans = "";
		ll p = x;
		while(p) ans += (p % 10 + '0'), p /= 10;
		reverse(ans.begin(), ans.end());
		return ans; 
	}
	ii solve(string a, string b) {
		int lena = a.size(), lenb = b.size(), j = 0;
		F(int, i, 0, lenb - 1) if(b[i] == a[j]) ++j;
		return lenb + lena - 2 * j;
	}
	
	iv Main() {
		for(ll i = 1; i <= 1e18; ans[++cnt] = ll_to_str(i), i <<= 1ll);
		MT {
			string s; cin >> s;
			int res = 0x3f3f3f3f;
			F(int, i, 1, cnt) res = min(res, solve(ans[i], s));
			println(res);
		} 
		return;
	}
}

脚本宝典总结

以上是脚本宝典为你收集整理的CF1560D Make a Power of Two 题解全部内容，希望文章能够帮你解决CF1560D Make a Power of Two 题解所遇到的问题。

如果觉得脚本宝典网站内容还不错，欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。