2021-03-26 15:02 字节跳动_客户端开发工程师

关注

【题解】Codeforces Round #710 (Div. 3)

A. Strange Table

原题链接： A. Strange Table

题意：

对于一个 $n \times m$ 的矩阵，按行编号指从第一行第一列开始从左往右依次编号，编号为正整数，从 $1$ 开始递增，当这一行填满时从下一行的第一列继续填，直至填满整个矩阵。
按列编号指从第一行第一列开始从上往下依次编号，当这一列填满时从下一列的第一行继续填。

$T$ 组测试数据，每次给出一个 $n$ 行 $m$ 列的矩阵，询问按行编号时为 $x$ 的单元格，按列编号时为几？ $T \leq 10^4$ ； $n, m \leq 10^6$ ； $x \leq n \times m$

考虑行列以及单元格都从 $0$ 开始编号，按行编号则第 $i$ 行第 $j$ 列的单元格编号为 $i * m + j$
按列编号则第 $i$ 行第 $j$ 列的单元格编号为 $j * n + i$

可以先对 $x - 1$ 然后求出行列，再求另一个编号最后 $+ 1$

#include<cstdio>

typedef long long LL;

int main()
{
    int _;
    scanf("%d", &_);
    while(_ --)
    {
        LL n, m, x;
        scanf("%lld%lld%lld", &n, &m, &x);
        x --;
        printf("%lld\n", x % n * m + x / n + 1);
    }
    return 0;
}

B. Partial Replacement

原题链接： B. Partial Replacement

题意：

有一个长度为 $n$ 的字符串只包含.和*
现在要求你把其中的第一个*和最后一个*必须变成x
其他的*可以选择其中一些变成x
问最少需要把几个*变成x使得相邻的两个x之间距离不超过 $k$
数据保证有解 $T \leq 500$ 组测试数据； $n, k \leq 50$

贪心

首先找到第一个和最后一个*的位置，从第一个*开始，把它变成x，然后尽可能找到最靠右的满足距离不超过 $k$ 的*，然后把它也变成x，直到它到最后一个的距离也不超过 $k$ 为止。

数据范围很小，找这一步可以从距离不超过 $k$ 的最靠右的字符倒着往回遍历

#include<cstdio>

typedef long long LL;

const int N = 200010;

char s[N];

int main()
{
    int _;
    scanf("%d", &_);
    while(_ --)
    {
        int n, k;
        scanf("%d%d%s", &n, &k, s + 1);
        int op = 0, ed = 0;
        for(int i = 1; i <= n; i ++)
            if(s[i] == '*')
            {
                if(!op)  op = i;
                ed = i;
            }

        if(op == ed)
        {
            puts("1");
            continue;
        }

        int res = 2, i = op;
        while(i + k < ed)
        {
            for(int j = i + k; j > i; j --)
                if(s[j] == '*')
                {
                    i = j;
                    break;
                }
            res ++;
        }
        printf("%d\n", res);
    }
    return 0;
}

C. Double-ended Strings

原题链接： C. Double-ended Strings

题意：

给出两个字符串 $a, b$ 每次可以删掉 $a$ 或 $b$ 的第一个字符或最后一个字符，问最少删几个字符使得两个字符串相等 $T \leq1 00$ 组测试数据； $len(a), len(b) \leq 20$

枚举

题目等价于对于两个子串分别找到一个最长的子串使得他们相等

暴力枚举子串长度，起点，暴力判断相等

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>

using namespace std;

typedef long long LL;

const int N = 200010;

char a[N], b[N];

int main()
{
    int _;
    scanf("%d", &_);
    while(_ --)
    {
        scanf("%s%s", a, b);
        int n = strlen(a), m = strlen(b);

        int res = n + m;
        for(int len = 0; len <= n and len <= m; len ++)
            for(int i = 0; i + len - 1 < n; i ++)
            {
                for(int j = 0; j + len - 1 < m; j ++)
                {
                    bool flag = true;
                    for(int k = 0; k < len; k ++)
                        if(a[i + k] != b[j + k])
                        {
                            flag = false;
                            break;
                        }
                    if(flag)  res = min(res, n + m - len * 2);
                }
            }
        printf("%d\n", res);
    }
    return 0;
}

D. Epic Transformation

原题链接：D. Epic Transformation

题意：

给出一个长度为 $n$ 整数序列 $a$ ，每次可以任选两个不相同的数都删掉，问最少剩下几个数 $n \leq 2 \times 10^5$ ； $1 \leq a_i \leq 10^9$

结论题

emmm显然 $n$ 为奇数时最少剩下 $1$ 个，然后如果有一个数特别多，比其他所有数加起来都多，设这个数的数量为 $num$ 最多就能删掉 $n - num$ 对数

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>

using namespace std;

typedef long long LL;

const int N = 200010;

int n;
int a[N];

int main()
{
    int _;
    scanf("%d", &_);
    while(_ --)
    {
        scanf("%d", &n);

        int num = 0;
        map<int, int> cnt;
        for(int i = 0; i < n; i ++)
        {
            int x;
            scanf("%d", &x);
            num = max(num, ++ cnt[x]);
        }

        int res = 0;
        if(n & 1)  res = 1;
        res = max(res, num - (n - num));
        printf("%d\n", res);
    }
    return 0;
}

E. Restoring the Permutation

原题链接：E. Restoring the Permutation

题意：

有一个长度为 $n$ 的排列 $p$ ，现在给出排列 $p$ 的前缀最大值序列，求字典序最小和最大的排列 $p$
$n \leq 2 \times 10^5$

就可以……设前缀最大值序列为 $a$ ，当 $a[i] != a[i - 1]$ 时 $p[i] == a[i]$ ，否则字典序最小的话就取没用过的最小的数，字符串最大的话就取没用过的最大的不超过 $a[i]$ 的数。
用一个 $set$ 维护没用过的数就可以了

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<set>

using namespace std;

typedef long long LL;

const int N = 200010;

int n;
int a[N];

int main()
{
    int _;
    scanf("%d", &_);
    while(_ --)
    {
        scanf("%d", &n);
        for(int i = 1; i <= n; i ++)  scanf("%d", &a[i]);

        set<int> S;
        for(int i = 1; i <= n; i ++)  S.insert(i);
        for(int i = 1; i <= n; i ++)
        {
            if(a[i] != a[i - 1])
            {
                printf("%d ", a[i]);
                S.erase(a[i]);
            }
            else
            {
                auto it = S.begin();
                printf("%d ", *it);
                S.erase(it);
            }
        }
        puts("");

        for(int i = 1; i <= n; i ++)  S.insert(i);
        for(int i = 1; i <= n; i ++)
        {
            if(a[i] != a[i - 1])
            {
                printf("%d ", a[i]);
                S.erase(a[i]);
            }
            else
            {
                auto it = S.lower_bound(a[i] + 1);
                it --;
                printf("%d ", *it);
                S.erase(it);
            }
        }
        puts("");
    }
    return 0;
}

F. Triangular Paths

原题链接：F. Triangular Paths

题意：

有一个 $n$ 行，第 $i$ 行有 $i$ 个元素的下三角矩阵
当 $i + j$ $mod$ $2 == 0$ 时 $(i, j)$ 有一条通往 $(i + 1, j)$ 的边，否则 $(i, j)$ 有一条通往 $(i + 1, j + 1)$ 的边
可以花费 $1$ 的代价令某一个点的出边在抵达 $(i + 1, j)$ 和 $(i + 1, j + 1)$ 之间互换

现在给出一个 $n$ 个点的点集，求从 $(1, 1)$ 出发最少花费多少代价可以遍历到这些点，数据保证有解 $n \leq 2 \times 10^5$

找规律

首先这个矩阵一开始是这样的：
QQ图片20210326104203.jpg

数据保证有解的话我们假设某个点坐标为 $(x, y)$ ，从上往下走 $x$ 必然是递增的，由于两条边要么是 $x + 1$ ， $y$ 不变，要么是 $x + 1, y + 1$ ，所以 $y$ 的增幅必然小于等于 $x$ 的增幅

可以发现在 $x - y$ 为奇数时可以一直往右下方向走，为偶数时想往右下方向走就需要修改路径上每一条边
如果想往下走需要打通一些向下的通道

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>

#define x first
#define y second

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int N = 200010;

int n;
PII e[N];

int main()
{
    int _;
    scanf("%d", &_);
    while(_ --)
    {
        scanf("%d", &n);
        for(int i = 1; i <= n; i ++)  scanf("%d", &e[i].x);
        for(int i = 1; i <= n; i ++)  scanf("%d", &e[i].y);
        e[0].x = e[0].y = 1;
        sort(e + 1, e + n + 1);

        int res = 0;
        for(int i = 1; i <= n; i ++)
        {
            int dx = e[i].x - e[i - 1].x, dy = e[i].y - e[i - 1].y;
            int t = dx - dy;

            if(!t)
            {
                if((e[i].x - e[i].y) % 2 == 0)  res += dx;
            }
            else
            {
                if((e[i - 1].x - e[i - 1].y) % 2)  res += t + 1 >> 1;
                else  res += t >> 1;
            }
        }
        printf("%d\n", res);
    }
    return 0;
}

G. Maximize the Remaining String

原题链接：G. Maximize the Remaining String

题意：

给出一个长度为 $n$ 的只包含小写字母的字符串要删掉其中的所有重复字符（每个字符必须留一个），使留下来的字符串字典序最大，输出留下的字符串。 $n \leq 2 \times 10^5$

枚举

由于字符集比较小，最后留下的字符串长度一定不超过 $26$ ，可以从前往后枚举留下的字符串的第几个字符应该可以填的最大的字母，要保证填上这个字母之后，后面依然有数量足够的字母可以填。

时间复杂度 $O(26^2n)$

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>

#define x first
#define y second

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int N = 200010;

char s[N];
bool st[N][26], dele[N];
int sum[N];

int main()
{
    int _;
    scanf("%d", &_);
    while(_ --)
    {
        scanf("%s", s);
        int n = strlen(s);

        sum[n] = 0;
        for(int i = 0; i < 26; i ++)  st[n][i] = 0;
        for(int i = 0; i <= n; i ++)  dele[i] = 0;

        for(int i = n - 1; i >= 0; i --)
        {
            sum[i] = sum[i + 1];
            for(int j = 0; j < 26; j ++)
                st[i][j] = st[i + 1][j];
            if(!st[i][s[i] - 'a'])
            {
                st[i][s[i] - 'a'] = true;
                sum[i] ++;
            }
        }

        int m = sum[0], op = 0;
        for(int l = 1; l <= m; l ++)
        {
            for(char c = 'z'; c >= 'a'; c --)
            {
                if(!st[op][c - 'a'])  continue;

                bool flag = false;
                for(int i = op; i < n; i ++)
                {
                    if(flag)
                    {
                        if(st[i][c - 'a'])
                        {
                            st[i][c - 'a'] = false;
                            sum[i] --;
                        }
                        if(s[i] == c)  dele[i] = true;
                    }
                    if(dele[i])  continue;

                    if(s[i] == c)
                    {
                        int cnt = sum[i + 1];
                        if(st[i + 1][c - 'a'])  cnt --;
                        if(cnt >= m - l)
                        {
                            flag = true;
                            op = i + 1;
                        }
                    }
                }
                if(flag)
                {
                    putchar(c);
                    break;
                }
            }
        }
        puts("");
    }
    return 0;
}