-
题意:给出一个n,可以有两个操作,第一个为删除其十进制位上的任一一位,操作次数 +1,第二个为在其右端(尾端)加入一个十进制整数,操作次数 +1,问至少操作几次,可以使得\(n = 2^x(x \geq 0)\)。
-
解析:首先预处理大概\(10^{18}\)内的\(2^x\),假设预处理的每个串为\(t_i\),然后我们的n可以to_string成一个字符串,接着用双指针来计算成功匹配的字符个数,这里的匹配举个例子:t = 1024,s = 1052,那么必须是s与t匹配必须根据t的字符顺序进行匹配,因为实际上s中的一些字符是可以去掉的,例如前两个字符为1、0,均匹配成功,但到第三个字符\(t_2 = 2,s_2 = 5\),此时并不匹配,说明这个字符肯定多余的(最后需要用删除操作将其删除),那么s串只能继续往下找是否存在2,然后发现\(s_3 = 2\),此时可以与\(t_2\)匹配,那么匹配成功的数量num = 3。相当于从s中抽出一些数,这些数组成的序列最多能匹配到t的第几位(必须从第一位开始匹配)。这时的操作数为:s的长度 - num + t的长度 - num。s.len - num 其实是删除字符操作,说明有这么多个字符是多余的,而t.len - num是有这么多个字符没匹配成功,需要从末尾加上去。
- ps:这里的整个过程有点贪心的性质,只要发现能按顺序进行匹配就匹配,否则丢弃该字符。
-
代码:
#include<iostream> #include<cstdio> #include<vector> #include<algorithm> using namespace std; typedef long long ll; vector<string> v; int t; string str_mk(ll x) { string str; if(!x) str += ‘0‘; else { while(x) { int t = x % 10; str += char(t + 48); //str = char(t + 48) + s可以直接把字符接在串前面 x /= 10; } } reverse(str.begin(), str.end()); return str; } void init() { for(int i = 0; i <= 60; i++) { ll x = (ll)1 << (ll)i; string str = str_mk(x); // to_string(x) v.push_back(str); } } int calc(string s, string t) //t为匹配的目标串 { int num = 0; for(int i = 0, j = 0; i < s.size() && j < t.size(); i++) { if(s[i] == t[j]) { num ++; j ++; } } return s.size() - num + (t.size() - num); } int main() { init(); cin >> t; while(t --) { string s; cin >> s; int res = 1000; //随便取个较大的数 for(int i = 0; i < v.size(); i++) { int cnt = calc(s, v[i]); res = min(cnt, res); } cout << res << endl; } return 0; }
Codeforces Round #739 (Div. 3) D. Make a Power of Two(字符串匹配、双指针、贪心)