AtCoder Beginner Contest 380 A~E

· · 题解

A - 123233

洛谷链接

AtCoder链接

题目

给你一个 6（位）正整数 N。

请判断 N 是否满足以下所有条件。

代码

#include <bits/stdc++.h>

using namespace std;

string s;
int a[3];

int main()
{
    cin >> s;
    for (int i = 0; i < s.length(); i ++ )
    {
        if (s[i] == '1')
            a[0] ++;
        else if (s[i] == '2')
            a[1] ++;
        else if (s[i] == '3')
            a[2] ++;
    }
    if (a[0] == 1 && a[1] == 2 && a[2] == 3)
        puts("Yes");
    else
        puts("No");
    return 0;
}

B - Hurdle Parsing

洛谷链接

AtCoder链接

题目

伊洛哈有一个长度为 N\ (N \ge 1) 的正整数序列 A=(A_1,A_2, \ldots ,A_N)。

她用 A 生成了如下字符串 S：

在生成的字符串 S 中，重建序列 A。

代码

题意就是求每对 | 中 - 的个数。

#include <bits/stdc++.h>

using namespace std;

string s;
int cnt;

int main()
{
    cin >> s;
    for (int i = 1; i < s.length(); i ++ )
    {
        if (s[i] == '-')
            cnt ++;
        else
        {
            cout << cnt << ' ';
            cnt = 0;
        }
    }
    return 0;
}

C - Move Segment

洛谷链接

AtCoder链接

题目

给你一个长度为 N 的字符串 S，它由 0 和 1 组成。

将 S 中开头的第 K 个 1 字块移动到第 (K-1) 个 1 字块的后面，并输出得到的字符串。

保证 S 至少包含 K 个 1 字块。

下面是更精确的描述。

思路

我们找到第 k-1 个段的结尾和第 k 个段的开头和结尾，当输出到第 k-1 个段的结尾时，输出第 k 个段，也就是第 k 个段的开头到结尾的 1，当输出到第 k 个段的开头时，直接跳到第 k 个段的结尾。

那么怎么找第 k-1 个段的结尾和第 k 个段的开头和结尾呢？遍历一遍字符串，当找到一个前面不是 1 的 1 时，当前段编号加 1；当找到一个 1 时，当前这段的结尾往后挪一个；当找到一个 0 的时候，把开头移到当前加 1，结尾移到当前，解释一下，因为当前是 0，所以只有当前加 1 有可能是 1，而到后面的 1 时会把结尾往后移动一个，所以结尾要提前往前一个，要不然已经是 l=r，即 l 到 l，有一个了，如果再在第一个往后移动一个就会多 1 个。

代码

可能会因无法输入 s + 1 而 CE，换一下 C++ 版本就好了。

#include <bits/stdc++.h>

using namespace std;

int n, k, qr, dl, dr, lx = 1, rx, op;
char s[500010];

int main()
{
    cin >> n >> k >> s + 1;
    for (int i = 1; i <= n && op <= k; i ++ )
    {
        if (s[i] == '1')
        {
            if (s[i-1] != '1')
                op ++;
            rx ++;
            if (op == k - 1)
                qr = rx;
            if (op == k)
            {
                dl = lx;
                dr = rx;
            }
        }
        else if (s[i] == '0')
        {
            lx = i + 1;
            rx = i;
        }
    }
    for (int i = 1; i <= n; i ++ )
    {
        if (i == dl)
        {
            i = dr;
            continue;
        }
        cout << s[i];
        if (i == qr)
        {
            for (int j = dl; j <= dr; j ++ )
                cout << 1;
        }
    }
    return 0;
}

D - Strange Mirroring

洛谷链接

AtCoder链接

题目

有一个由大写和小写英文字母组成的字符串 S。

我们对 S 进行以下运算 10^{100} 次：

回答 Q 查询。第 i 次查询如下：

思路

我们可以发现，每次长度都会变成原来的两倍，那么如果我们对半砍，如果在一半的后面就给它对应到前一半的对应位置，记一次翻转，直到对应到 1 或 2 的位置。好像不是很好理解是不是，但其实就是这样了，那么我们看一个图，重讲一遍。

我们知道，这一个序列是同时变动的，所以我们可以把序列认为是一个字符，把 k 对 n 取余，就是序列的第几个位置，把 k 除以 n 上取整就是在第几个序列，那么图片中每一个 0 就是代表了一个序列，红色代表原序列，绿色代表翻转了的序列。

假设我们要找的位置时在四号三角形的那个序列里的，那么它一定三号三角形那个序列翻转后得到的，那么三号序列就是二号三角形那个序列翻转后得到的，直到第二个（一号）序列。这样是翻转了三次，加上它是第二个本来就翻转了一次，一共是四次，但是翻转四次和没翻转没有区别，所以就是原序列的那个位置，如果是奇数次翻转，那么就是原序列的那个位置转换一下大小写即可。

这时已经对上面的简洁的描述有了一定的理解，我们继续理解一下为什么是在一半的后面。如果是在五号序列的话，那么我们会直接到二号序列，在第二次对半砍的时候并不会有变化，那么如果我们仍然记了一次翻转，就会多翻转一次。 那么大部分需要理解的内容就结束了，那么怎么实现对半砍呢？我们可以发现每次对半砍完长度都是除以 2 了，那么我们只需要找到这个数（假设为 x ）满足条件的 y：2^y \le x \le 2^{y+1}，那么我们就可以从 2^y 开始砍（这里对砍的定义是把这个位置化成小于这个长度的一个位置）。

那么我们现在解决了从多长开始砍，那么具体怎么砍呢？我们只要判断当前位置是否大于当前要砍的长度，如果不大于就行了，如果大于就减去这个长度，翻转次数加 1 即可。再将长度除以 2，再继续砍。

最后判断一下翻转次数的奇偶性，翻一下即可。

代码

可能会因无法输入 s + 1 而 CE，换一下 C++ 版本就好了。

#include <bits/stdc++.h>

using namespace std;

char s[200010];
long long q, n, w[200010], cn, k, g, gk, t, a, c;

char bian(long long x)
{
    if (x >= 'a' && x <= 'z')
        return x - 'a' + 'A';
    else
        return x - 'A' + 'a';
}

int main()
{
    cin >> s + 1 >> q;
    n = strlen(s + 1);
    while (q -- )
    {
        cn = 0;
        scanf("%lld", &k);
        g = (k + n - 1) / n;
        gk = k % n;
        if (gk == 0)
            gk = n;
        t = g;
        a = 1;
        while (t)
        {
            w[++ cn] = a;
            t >>= 1;
            a *= 2;
        }
        c = 0;
        for (long long i = cn; i > 1; i -- )
        {
            if (g > w[i])
            {
                g -= w[i];
                c ++;
            }
        }
        if (g == 2)
            c ++;
        c %= 2;
        if (c == 1)
            cout << bian(s[gk]) << ' ';
        else
            cout << s[gk] << ' ';
    }
    return 0;
}

E - 1D Bucket Tool

洛谷链接

AtCoder链接

题目

一行中有 N 个单元格，编号为 1 至 N。

在每个 1 \le i < N 单元格中，i 和 i+1 单元格相邻。

最初，i 单元格被涂上了颜色 i。

给您 Q 个查询。请按顺序处理它们。每个查询属于以下两种类型之一。

思路

用并查集维护几个信息：f_i，代表 i 的父亲；l_i，代表 i 所在颜色块的左端点；r_i，代表 i 所在颜色块的右端点。

其他再记录几个信息：col_i，代表 i 的颜色；cnt_i，代表颜色 i 的个数。

那么初始化都是很好做的。

为了方便，我们使一个点的正确左右端点存储在它的终极祖先（也就是 find(x) 的结果）中，也就是说，这个点本身的左右端点（l_i 和 r_i），不一定是正确的，可能会比原来的小（补充一下：不会比原来的大，因为我们如果要改变颜色，是这个点左右的一个颜色块一起改变，不会说一个颜色块内的一部分颜色改变，颜色块缩小，只会和这个颜色块的外部一样颜色合并起来，颜色块变大），而这个点的终极祖先的左右端点（l_{find(i)} 和 r_{find(i)}）一定是正确的。

对于操作 2，直接输出 cnt_c 即可。

操作 1 稍微有点复杂，但也比较好理解。首先，我们让 x 成为 x 的终极祖先（因为各种信息 x 的终极祖先都有）。

其次，我们把原来颜色的个数减少颜色块长度个，要改变到的颜色的个数加上颜色块长度个，把 x 的颜色改变一下。

然后我们判断一下这个颜色块和左右颜色是否变得相同了，如果颜色一样了，就合并到一起。

那么如何合并呢？首先，肯定要把一个的父亲赋成另一个，然后我们把那个在上面那个（终极祖先）的左右端点改变一下（左端点赋成两个左端点靠前的那个，右端点赋成两个右端点靠后的那个）。

代码

#include <bits/stdc++.h>

using namespace std;

int n, q, op, x, c, f[500010], cnt[500010], col[500010], l[500010], r[500010];

int find(int x)
{
    if (x == f[x])
        return x;
    else
        return f[x] = find(f[x]);
}

void merge(int x, int y)
{
    x = find(x);
    y = find(y);
    f[x] = y;
    l[y] = min(l[y], l[x]);
    r[y] = max(r[y], r[x]);
}

int main()
{
    scanf("%d %d", &n, &q);
    for (int i = 1; i <= n; i ++ )
    {
        f[i] = col[i] = l[i] = r[i]= i;
        cnt[i] = 1;
    }
    while (q -- )
    {
        scanf("%d", &op);
        if (op == 1)
        {
            scanf("%d %d", &x, &c);
            x = find(x);
            cnt[c] += r[x] - l[x] + 1;
            cnt[col[x]] -= r[x] - l[x] + 1;
            col[x] = c;
            if (l[x] > 1 && c == col[find(l[x] - 1)])
                merge(l[x]-1,x);
            if (r[x] < n && c == col[find(r[x] + 1)])
                merge(r[x] + 1, x);
        }
        else
        {
            scanf("%d", &c);
            cout << cnt[c] << '\n';
        }
    }
    return 0;
}