Codeforces Round #739 (Div. 3) D. Make a Power of Two(字符串匹配、双指针、贪心)

  • 题目:Make a Power of Two

  • 题意:给出一个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(字符串匹配、双指针、贪心)

上一篇:阿里云服务器选择及使用体验!


下一篇:22.认证服务