Codeforces Round #739 (Div. 3)

2023-11-27 22:23:40

补题真的很重要啊，然而我经常懒得补，所以试试写博客鼓励一下自己φ(*￣0￣)，下面是上一场 cf（Codeforces Round #739 (Div. 3)）的3道题目8

D. Make a Pow of Two

给出一个数，通过删除某位数或者在末尾添加数，以最少的操作将其转变为一个2的幂。

分析：

我是先打2的幂的表，然后暴力比较字符串，看2的幂的字符串中前几位（连续的）能够在给定字符串中按序找到，那么需要的步骤数就是给定字符串中剩下的（需要删除的）加上2的幂字符串中剩下的（需要添加的），上代码8。

AC源码：

#include <bits/stdc++.h>
#define ll long long
#define F freopen("in.txt", "r", stdin)
using namespace std;
string str[65] = {"1", "2", "4", "8", "16", "32", "64", "128", "256", "512", "1024", "2048", "4096", "8192", "16384", "32768", "65536", "131072", "262144", "524288", "1048576", "2097152", "4194304", "8388608", "16777216", "33554432", "67108864", "134217728", "268435456", "536870912", "1073741824", "2147483648", "4294967296", "8589934592", "17179869184", "34359738368", "68719476736", "137438953472", "274877906944", "549755813888", "1099511627776", "2199023255552", "4398046511104", "8796093022208", "17592186044416", "35184372088832", "70368744177664", "140737488355328", "281474976710656", "562949953421312", "1125899906842624", "2251799813685248", "4503599627370496", "9007199254740992", "18014398509481984", "36028797018963968", "72057594037927936", "144115188075855872", "288230376151711744", "576460752303423488"};
int getlen(string s, int i)
{
    int l = 0, r = 0, cnt = 0;
    int len = s.size(), len2 = str[i].size();
    while (l < len && r < len2)
    {
        if (s[l] == str[i][r])
        {
            l++, r++;
            cnt++;
        }
        else
            l++;
    }
    return len - cnt + len2 - r;
}
int main()
{
    //F;
    int t;
    cin >> t;
    while (t--)
    {
        int ans = 100;
        string s;
        cin >> s;
        for (int i = 0; i < 60; i++)
            ans = min(ans, getlen(s, i));
        cout << ans << endl;
    }
    return 0;
}

然而这题卡了我36min！C题打完standing900+，等D打完已经1300+......(ノへ￣、)当时没考虑到需要同pow(2,60)这么大的数进行比较，结果直接WA了，回来调试老久，只能说我还是太菜(QAQ)还有太吝啬，一开始把str数组开那么小...

E. Polycarp and String Transformation

字符串 s 和 t （ t 初始为空），重复一下两种操作之一直到 s 为空:

将现在的 s 接在 t 后面
从 s 中删去某种字符

现给出最终的 t ，问 s 的初始值，如果不存在，输出-1。

分析：

一开始看到的题目是这样的，没多想就去做F1了。然而...就在刚才，我发现题目看错了orz，上面两种操作是严格按照此顺序进行的，结果这题变成了一个数学题......

首先字母消除的顺序必定是在最终 t 串中从后往前字母第一次出现的顺序，于是知道了字母消除的顺序。假设一共 n 种字母，第i个被消除的字母在初始 s 串中出现 c_i 次，那么这些字母分别出现 i * c_i 次，emmm也就是可以轻松计算出 c_i 啦（除不尽就是没有解，-1给上）。

又因为初始的 s 必然是当前 t 的前缀，那么我们按刚才的 c_i去 t 那边收一波货，从 t 头部收 ∑c_i 个字母组成初始的 s ，反手算出 t 验证答案，然后就没有然后了（审题很重要嗷，QAQ这题根本没有*1800）

AC源码：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 int main()
 4 {
 5     //freopen("E.in", "r", stdin);
 6     int t;
 7     cin >> t;
 8     while (t--)
 9     {
10         int cnt[26], len = 0;
11         memset(cnt, 0, sizeof(cnt));
12         string t, typ;
13         cin >> t;
14         int lent = t.size();
15         for (int i = lent - 1; i > -1; i--)
16         {
17             if (!cnt[t[i] - ‘a‘])
18                 typ.push_back(t[i]);
19             cnt[t[i] - ‘a‘]++;
20         }
21         int ty = typ.size();
22         for (int i = 0; i < ty; i++)
23             len += cnt[typ[i] - ‘a‘] / (ty - i);
24         string s = t.substr(0, len);
25         string t2(s), tmp(s);
26         for (int i = ty - 1; i > 0; i--)
27         {
28             string tmp2;
29             for (int j = 0; j < tmp.size(); j++)
30                 if (tmp[j] != typ[i])
31                     tmp2.push_back(tmp[j]);
32             tmp = tmp2;
33             t2 = t2 + tmp2;
34         }
35         reverse(typ.begin(), typ.end());
36         if (t2 == t)
37             cout << s << " " << typ << endl;
38         else
39             cout << -1 << endl;
40         //cout << s << " " << t2 << endl;
41     }
42     return 0;
43 }

F1. Nearest Beautiful Number (easy version)

找到由 k 种数字组成的比给定数字 n 大的最小整数（k为1或2）

分析：

由于n必定小于等于9999...，因此所求整数位数一定与n相等，考虑暴力，k=1 时直接枚举，k=2时枚举组成的数字 a，b，从第一个小于b的数字开始增加，并将后面的数字全部变成a，更新答案。

代码：

#include <bits/stdc++.h>
using namespace std;
string solve(string s, int k)
{
    int n = s.size();
    string ans(n, ‘9‘);
    for (char c = ‘8‘; c >= ‘0‘; c--)
    {
        string tmp(n, c);
        if (tmp >= s)
            ans = tmp;
    }
    if (k == 2)
    {
        for (char a = ‘0‘; a <= ‘8‘; a++)
            for (char b = a + 1; b <= ‘9‘; b++)
            {
                int flag = 1;
                for (int i = 0; i < n; i++)
                {
                    if (s[i] < b)
                    {
                        string t(s);
                        if (t[i] < a)
                            t[i] = a;
                        else
                            t[i] = b;
                        for (int k = i + 1; k < n; k++)
                            t[k] = a;
                        //cout << "a:" << a << " b:" << b << " i:" << i << endl;
                        //cout << t << endl;
                        if (ans > t)
                            ans = t;
                    }
                    if (s[i] != b && s[i] != a)
                    {
                        flag = 0;
                        break;
                    }
                }
                if (flag)
                    return s;
            }
    }
    return ans;
}
int main()
{
    //freopen("F11.in", "r", stdin);
    int t;
    cin >> t;
    while (t--)
    {
        string n;
        int k;
        cin >> n >> k;
        cout << solve(n, k) << endl;
    }
    return 0;
}

总结

感觉后面两题难度不大（至少没有*1800~*1900），不能被题目给吓住鸭，不过说起来后面这两题可能都算是找规律构造/分析，找到规律之后其实比这个D还要简单（确信?(′▽｀)）

Codeforces Round #739 (Div. 3)

码农公寓

D. Make a Pow of Two

E. Polycarp and String Transformation

F1. Nearest Beautiful Number (easy version)

总结

相关文章