[数据结构与算法]Codeforces Round #739 (Div. 3) 题解

旅行传送门

A. Dislike of Threes

题意：求这样一个序列：序列中不包含 $3$ 的倍数和以 $3$ 结尾的整数，输出这个序列中的第 $k$ 个数。

题目分析：打表，过

AC代码：

#include <bits/stdc++.h>
#define rep(i, x, y) for (register int i = (x); i <= (y); i++)
#define down(i, x, y) for (register int i = (x); i >= (y); i--)
const int maxn = 2005;

char buf[1 << 23], *p1 = buf, *p2 = buf, obuf[1 << 23], *O = obuf; // 或者用fread更难调的快读
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
inline int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while (!isdigit(ch))
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (isdigit(ch))
    {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}

int t, k, a[maxn];

void init()
{
    rep(i, 1, 2000) if (!(i % 3) || (i % 10 == 3))
        a[i] = 1;
}

int main(int argc, char const *argv[])
{
    init();
    t = read();
    while (t--)
    {
        k = read();
        int ans = 0;
        while (k)
            if (!a[++ans])
                --k;
        printf("%d\n", ans);
    }
    return 0;
}

B. Who’s Opposite?

题意：若干个数按顺时针排列成圆，且关于圆心一一对称，告诉你其中对称的一组数 $a$ 、 $b$ ，求与 $c$ 对称的数。

题目分析：不妨设 $a$ > $b$ ， $a、b$ 是对称数，两者间的差值 $tmp$ 即为每一对对称数间的差值，那么总人数即为 $2\times tmp$ ，由于编号从 $1$ 开始，所以总人数小于 $a、b、c$ 其中一个都无解，若有解，即为 $c\pm tmp$

AC代码：

#include <bits/stdc++.h>
#define rep(i, x, y) for (register int i = (x); i <= (y); i++)
#define down(i, x, y) for (register int i = (x); i >= (y); i--)

char buf[1 << 23], *p1 = buf, *p2 = buf, obuf[1 << 23], *O = obuf; // 或者用fread更难调的快读
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
inline int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while (!isdigit(ch))
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (isdigit(ch))
    {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}

int main(int argc, char const *argv[])
{
    int T = read();
    while (T--)
    {
        int a = read(), b = read(), c = read();
        if (a < b)
            std::swap(a, b);
        int tmp = a - b;
        int sum = 2 * (tmp - 1) + 2;
        if (sum < a || sum < b || sum < c)
        {
            puts("-1");
            continue;
        }
        printf("%d\n", c > (sum / 2) ? c - tmp : c + tmp);
    }
    return 0;
}

C. Infinity Table

题意：给你个矩阵，这个矩阵以某种方式填充数，问你第 $k$ 个数的坐标是多少？

题目分析：不难发现行首的数均为平方数，两行首之差即为一次循环 ← ↓ 所填充的数，设当前行为 $i$ ，这个差值为 $tmp=a[i][1]?a[i?1][1]$ ，则 < $\frac{tmp}{2}$ 的都在第 $i$ 列， > $\frac{tmp}{2}$ 的都在第 $i$ 行，再推一下 $k$ 与两行首的大小关系就能得到坐标了。

代码写得有些乱，见谅。

AC代码：

#include <bits/stdc++.h>
#define rep(i, x, y) for (register int i = (x); i <= (y); i++)
#define down(i, x, y) for (register int i = (x); i >= (y); i--)

char buf[1 << 23], *p1 = buf, *p2 = buf, obuf[1 << 23], *O = obuf; // 或者用fread更难调的快读
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
inline int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while (!isdigit(ch))
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (isdigit(ch))
    {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}

int vis[32000];

int main(int argc, char const *argv[])
{
    rep(i, 1, 32000) vis[i] = i * i;
    int T = read();
    while (T--)
    {
        int k = read(), pos = 0;
        rep(i, 1, 32000) if (k < vis[i])
        {
            pos = i;
            break;
        }
        if (k == vis[pos - 1])
        {
            printf("%d %d\n", pos - 1, 1);
            continue;
        }
        if (k == vis[pos - 1] + 1)
        {
            printf("%d %d\n", 1, pos);
            continue;
        }
        int tmp = vis[pos] - vis[pos - 1];
        if (k - vis[pos - 1] == tmp / 2 + 1)
        {
            printf("%d %d\n", pos, pos);
            continue;
        }
        if (k - vis[pos - 1] > tmp / 2)
        {
            int cha = vis[pos] - k;
            printf("%d %d\n", pos, cha + 1);
        }
        else if (k - vis[pos - 1] <= tmp / 2)
        {
            int cha = k - vis[pos - 1];
            printf("%d %d\n", cha, pos);
        }
    }
}

D. Make a Power of Two

题意：给你一个整数 $n$ ，你可以任意次进行下列操作之一:

• 移除数 $n$ 的任意一位
• 给 $n$ 的末尾加上一个数

问至少要经过几次操作，才能使得 $n$ 成为 $2$ 的幂。

题目分析：提前记下 $2$ 的所有幂次，开两个指针去逐个顺序匹配，匹配结果分三种情况：

• 数 $n$ 本就是 $2$ 的幂次，这种情况无需再进行任何操作
• 如果该幂次的每一位数 $n$ 中都包含，则答案为擦除其它位数所需的次数
• 否则，操作所需最少次数为第二种情况的答案加上未匹配位数的数目

说人话，假如 $n$ 为 $1052$ ，与 $1024$ 匹配有 $3$ 位匹配，那么对于当前次幂来说最少次数为擦除 $5$ 的一次加上末尾添上 $4$ 的一次。

遍历 $2$ 的所有幂次，不断更新迭代，即可找到最优解。

AC代码：

#include <bits/stdc++.h>
#define rep(i, x, y) for (register int i = (x); i <= (y); i++)
#define down(i, x, y) for (register int i = (x); i >= (y); i--)
const int inf = 0x3f3f3f3f;

char num[20];
char s[55][20] = {"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"};

int main(int argc, char const *argv[])
{
    int T;
    scanf("%d", &T);
    while (T--)
    {
        scanf("%s", num);
        int ans = inf;
        rep(i, 0, 54)
        {
            int match = 0;
            int p1 = 0, p2 = 0;
            while (num[p2])
            {
                if (num[p2] == s[i][p1])
                    ++p1, ++match;
                ++p2;
            }
            int len1 = strlen(s[i]), len2 = strlen(num);
            int dif = len2 - match;
            if (match ^ len1)
                ans = std::min(ans, dif + len1 - match);
            else
                ans = std::min(ans, dif);
        }
        printf("%d\n", ans);
    }
    return 0;
}

E. Polycarp and String Transformation

题意：假设有这样一个字符串 $s$ 和一个空字符串 $t$ ， 字符串 $s$ 可以执行下列操作直至其为空：

• 先令 $t=t+s$
• 再移除 $s$ 中所有的某字母

现在给你一个 $t$ 串，问你能否倒推出 $s$ 串和字母的删除顺序。

题目分析：

• 怎么确定删除顺序呢？字母的位置越靠后，说明它“存活”得越久，那么我们只需记录下每个字母最后出现位置的先后顺序，即可确定删除顺序。

• 怎么确定原串 $s$ 呢？我们可以这样想，若 $s$ 串最终可以拼出 $t$ 串，那么虽然 $s$ 每次删去的字母不同，但在某字母被删去前，其在 $s$ 中出现的次数是固定的，假设第 $i$ 次操作删去了字母 $a$ ，那么 $a$ 在 $t$ 中的出现次数一定为 $i$ 的倍数。否则就不存在能拼出当前 $t$ 串的 $s$ 串。

• 记录下字母 $a$ 的出现次数 $cnta$ ，即 $a$ 在原串中的出现次数为 $numa=cnta/i$ ，所有字母的 $num$ 之和即为原串 $s$ 的长度，那 $s$ 也就可以随之确定了

• 吗？答案是否定的，我们还要再模拟上述操作用目前得到的 $s$ 串试着能不能拼出 $t$ ，只有正推逆推都没问题，答案才合法。

AC代码：

#include <bits/stdc++.h>
#define rep(i, x, y) for (register int i = (x); i <= (y); i++)
#define down(i, x, y) for (register int i = (x); i >= (y); i--)
#define full(x, y) memset(x, y, sizeof(x))
using namespace std;

int flag, cnt[26], pos[26];
string ori, tmp, s, t, order;

struct node
{
    int ch, pos;
} lst[26];

void init()
{
    flag = 0;
    s.clear(), order.clear();
    rep(i, 0, 25) lst[i].ch = i, lst[i].pos = 0;
    full(cnt, 0), full(pos, 0);
}

inline bool cmp(node a, node b) { return a.pos < b.pos; }

int main(int argc, char const *argv[])
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;
    cin >> T;
    while (T--)
    {
        init();
        cin >> t;
        int len = t.length() - 1;
        rep(i, 0, len)
        {
            int c = t[i] - 'a';
            ++cnt[c];
            lst[c].pos = i + 1;
        }
        sort(lst, lst + 26, cmp);
        rep(i, 0, 25) if (lst[i].pos) order += lst[i].ch + 'a';
        len = order.length() - 1;
        rep(i, 0, len)
        {
            int c = order[i] - 'a';
            pos[c] = i + 1;
        }
        int sum = 0;
        rep(i, 0, 25)
        {
            if (!cnt[i])
                continue;
            if (cnt[i] % pos[i])
            {
                flag = 1;
                break;
            }
            sum += cnt[i] / pos[i];
        }
        if (!flag)
        {
            ori = t.substr(0, sum);
            tmp = ori;
            rep(i, 0, len)
            {
                s += tmp;
                tmp.erase(remove(tmp.begin(), tmp.end(), order[i]), tmp.end());
            }
            if (s.compare(t))
                flag = 1;
        }
        if (flag)
        {
            cout << "-1" << endl;
            continue;
        }
        cout << ori << " " << order << endl;
    }
    return 0;
}

题外话：前两天打HDU多校还在骂STL来着，今天string用起来又真香了。

F1. Nearest Beautiful Number (easy version)

题意：给你一个数 $n$ ，如果 $n$ 中不同的数 $\le k$ ，我们就称其为“美数”（我没在玩谐音梗），求 $\ge n$ 的最小的“美数” $x$ 。

一些闲话：分类讨论讨论得想死。。修锅修了一晚上。。分类情况写了删删了加。。提前体会以后上班写 $sh?t$ 山代码的感觉了。。。

题目分析：具体可以去看这位dalao的题解 → 旅行传送门 ，原谅我偷懒不想码字了(? -’`-)

嘛，细节有亿点多，像各种情况的处理顺序啊、各种找位置啊啥的，注意下就好。。

分类讨论不过是邪门歪道。。想看正解请移步 F2 Hard Version。

AC代码：

#include <bits/stdc++.h>
#define rep(i, x, y) for (register int i = (x); i <= (y); i++)
#define down(i, x, y) for (register int i = (x); i >= (y); i--)
using namespace std;

int vis[10];

int main(int argc, char const *argv[])
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;
    cin >> T;
    while (T--)
    {
        int k;
        string s, ans;
        cin >> s >> k;
        memset(vis, 0, sizeof(vis));
        int len = s.length() - 1;
        int dif = 0;
        rep(i, 0, len) if (!vis[s[i] - '0']) vis[s[i] - '0'] = 1, ++dif;
        if (dif <= k)
            cout << s << endl;
        else if (k == 1)
        {
            int flag = 0, pos = 0;
            rep(i, 1, len) if (s[i] != s[i - 1])
            {
                pos = i;
                break;
            }
            if (s[0] < s[pos])
                flag = 1;
            char c = flag ? s[0] + 1 : s[0];
            rep(i, 0, len) ans += c;
            cout << ans << endl;
        }
        else
        {
            int pos1 = 0, pos2 = 0;
            int num1 = s[0] - '0', num2 = 0;
            ans += s[0];
            rep(i, 1, len)
            {
                if (s[i] != s[pos1])
                {
                    pos2 = i;
                    num2 = s[i] - '0';
                    break;
                }
                ans += s[i];
            }
            int mx = std::max(num1, num2), mi = std::min(num1, num2);
            int pos3, num3;
            ans += s[pos2];
            rep(i, pos2 + 1, len)
            {
                if (s[i] != s[pos1] && s[i] != s[pos2])
                {
                    pos3 = i;
                    num3 = s[i] - '0';
                    break;
                }
                ans += s[i];
            }
            if (num3 < mi)
                rep(i, pos3, len) ans += mi + '0';
            else if (num3 < mx)
            {
                ans += mx + '0';
                rep(i, pos3 + 1, len) ans += mi + '0';
            }
            else
            {
                string tmp1 = ans, tmp2 = ans;
                ans = "999999999";
                int pos_min = 0;
                rep(i, 0, len) if (s[i] - '0' == mi && i < pos3) pos_min = std::max(pos_min, i);
                tmp2[pos_min] = mx + '0';
                rep(i, pos_min + 1, len) tmp2[i] = mi + '0';
                while (tmp2.length() <= len)
                    tmp2 += mi + '0';
                if (tmp2 > s)
                    if (ans > tmp2)
                        ans = tmp2;
                ++num2;
                mi = std::min(num1, num2);
                tmp2 = tmp1;
                tmp2[pos2] = num2 + '0';
                rep(i, pos2 + 1, len)
                    tmp2[i] = mi + '0';
                while (tmp2.length() <= len)
                    tmp2 += mi + '0';
                if (tmp2 > s)
                    if (ans > tmp2)
                        ans = tmp2;
                if (num1 == num2)
                {
                    tmp2 = tmp1;
                    tmp2[pos2] = num2 + '0';
                    rep(i, pos2 + 1, len) tmp2[i] = '0';
                    while (tmp2.length() <= len)
                        tmp2 += '0';
                    if (tmp2 > s)
                        if (ans > tmp2)
                            ans = tmp2;
                }
            }
            cout << ans << endl;
        }
    }
    return 0;
}

F2. Nearest Beautiful Number (hard version)

还是一些闲话：

队友钻研这题钻研了一天，摸索出了个DFS的写法，经不住我的再三要求，写下了本题题解，代码很简单，思路也很容易看懂，强烈建议阅读！！！

友情链接：无人问津的小羊圈

题目分析：

假设我们已经取得k个不同的、可以用于构造答案的数字，现在考虑如何使用这些数字来构造一个最小的、大于等于所给数字n的答案。

从最高位开始构造数字，我们可以得到以下两个贪心策略：

1. 如果该位可以使用一个更小的数字来满足大于等于n上相同位数字的条件，则使用更大的数字不会更优。
2. 如果所构造答案的某一位严格大于n上相同位的数字，则该位之后的每一位可以任意使用k个数字的其中一个。显然，选择k个数中最小的那个最优。

于是我们可以得出以下构造方式：

1. 从最高位开始向低位构造数字。
2. 对于每一位，从小到大依次尝试使用这k个数，直到某个数大于等于n上相同位的数字，将该数字填入该位。如果k个数都小于n上相同位的数字，则构造失败（这k个数无法构造出答案）。
3. 如果选取的数字严格大于n上相同位的数字，则使用k个数中最小的数字填入该位之后的所有位。否则，对下一位重复执行第2个步骤。

这个构造方法可以通过对每一位进行递归实现。

接下来，我们考虑如何选取这k个数。当k=2时（Easy version），我们可以枚举所有的取值情况，记录每一种取值情况的合法解，最后选取其中最小的解作为答案即可。

然而事实上，我们并不需要在递归求解之前就得到这k个数的取值，而是在对每一位递归的过程中逐渐取得这k个数。

让我们从最高位开始考虑，此时我们选中的数字个数为0，这意味着我们可以选择一个当前最优的数字加入k数字集合，然后直接使用该数字填入该位。当前最优的数字是什么？显然是n相同位上的数字，这是能满足大于等于n上相同位数字条件的最小值；如果通过递归求解发现填入该数字后无法构造出答案，那其加一后的值就是当前位最优的数字（满足大于相同位数字的条件，一定能够确保构造出答案）。

让我们将该取数方法扩展到其他位，当处理到第i位，此时选中的数字个数m小于k时，选择n相同位上的数字填入该位，并将该数加入k（注意去重），继续递归求解下一位；若递归求解下一位无法构造出答案，则将该数加一后填入该位，并将该数加入k（注意去重），然后递归求解下一位，此时能够保证构造出最优解。

AC代码：

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
int t, k, dignum;
bool vis[10]; // 用于标记某个数是否已被加入k数集合
char n[15], ans[15];
// ind: 当前构造的位数
// num: 已选择的k数数组
// len: 已选择的k数数量
// isok: 该位之前是否已经存在某一位严格大于n相同位的数字
bool dfs(int ind, int *num, int len, bool isok)
{
    if (ind == dignum)
        return true;
    // 已选择的k数个数小于k
    if (len < k)
    {
        int new_num[k] = {0}, new_num_len = len;
        for (int i = 0; i < len; i++)
            new_num[i] = num[i];
        // 如果k集合中没有该数，便加入该数并标记
        if (!vis[n[ind] - '0'])
            new_num[new_num_len++] = n[ind] - '0', vis[n[ind] - '0'] = true;
        ans[ind] = n[ind];
        // 递归求解，如果可以构造，则必为最优解
        if (dfs(ind + 1, new_num, new_num_len, isok))
            return true;
        // 从k集合中移除该数
        if (new_num_len != len)
            vis[n[ind] - '0'] = false;
        for (int i = 0; i < len; i++)
            new_num[i] = num[i];
        // 注意，如果加一后的值已经在集合中了，这意味着在集合未填满的情况下，我们获得了任意填写之后所有位的权利
        // 此时，当后续所有位填0时最优，因此，我们需要将0加入k集合。
        if (vis[n[ind] - '0' + 1])
            new_num[len] = 0;
        else
            new_num[len] = n[ind] - '0' + 1;
        ans[ind] = n[ind] + 1;
        // 若上述情况无法构造，则加一后填入必能构造出最优解
        return dfs(ind + 1, new_num, len + 1, true);
    }
    sort(num, num + len);
    // 先前已有某一位严格大于n相同位上的数字
    if (isok)
    {
        ans[ind] = num[0] + '0';
        return dfs(ind + 1, num, len, isok);
    }
    for (int i = 0; i < len; i++)
    {
        // 满足条件
        if (num[i] >= n[ind] - '0')
        {
            ans[ind] = num[i] + '0';
            // 递归求解下一位
            if (dfs(ind + 1, num, len, num[i] > n[ind] - '0'))
                return true;
        }
    }
    // 若该位无法继续构造答案，返回false表示构造失败
    return false;
}
int main()
{
    cin >> t;
    while (t--)
    {
        memset(vis, 0, sizeof(vis));
        cin >> n >> k;
        dignum = strlen(n);
        // 答案必为dignum位
        ans[dignum] = '\0';
        int num[k] = {0};
        dfs(0, num, 0, false);
        cout << atoll(ans) << endl;
    }
    return 0;
}