Atcoder ABC411游记

无关紧要的彩蛋在后面，去看看今天的日期吧

没怎么写的原因一个是因为有事 一个是浏览量感人

Atcoder ABC411游记（A~G）

A.Required Length

题目描述

给你一个字符串$P$，判断这个字符串的长度是否大于等于$L$

思路

唐

代码

#include<bits/stdc++.h>
using namespace std;
int main()
{
    string s;
    int a;
    cin >> s >> a;
    cout << (s.length() >= a ? "Yes" : "No");
    return 0;
}

B.Distance Table

题目描述

在一条直线上有$N$个烟花，对于$(1 \leq i < n)$，第$i$个烟花与第$i+1$个烟花之间的距离为$d_i$。

对于满足$1 \leq i < j \leq n$每一对整数，输出第$i$个烟花与第$j$个烟花之间的距离。

思路

水 连前缀和都不用就能过

代码

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin >> n;
    n--;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            int ans = 0;
            for (int k = i; k <= j; k++) {
                ans += a[k];
            }
            cout << ans << ' ';
        }
        cout << '\n';
    }
    return 0;
}

C.Black Intervals

题目描述

问题陈述

有 $N$ 个方格，从左到右排成一行。起初，所有方格都涂成白色。

依次处理 $Q$ 个查询。 $i$ -查询给出了一个介于 $1$ 和 $N$ （包括首尾两个数）之间的整数 $A_i$ ，并执行以下操作：

从左边开始翻转 第$A_i$个 方格的颜色。

然后，求连续黑方格的段数。

思路

直接模拟必炸，注意到我们不需要知道黑色连续段的位置，所以只需要在每次操作时考虑这个操作可能对答案的影响

那不难想到分讨即可

我们在对第$i$个方格操作的时候首先看位置：

• 如果这个方格在第一个或者最后一个，那只需要判断与其相邻的那个方格的颜色，就可以判断答案会怎样变化了。具体来说，如果当前块相邻的方格是黑色的，那怎么更改都不会更改答案；如果是白色的，那就要考虑当前方格的颜色会使答案增加或减少了。

• 如果这个方格在中间，那其实也很好想，我们只需要讨论相邻两个方格的情况。我们假设这个方格要由白变黑，如果相邻的两个都是白的，这个方格就自成一段，那答案就加一；如果两个都是黑色，这个方格就相当于把两个段合并了，那答案就减一；那剩下的情况就是这一块延长了其中一段答案不变。我们按照这些情况同样也能推出这个方格由黑变白的情况。

这里N可能到1，那按照这个思路可能会写RE，我就把这个情况单独拿出来写了

代码

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n, T;
    cin >> n >> T;
    if (n == 1) {
        int a = 1;
        while (T--) {
            cout << a << '\n';
            a = 1 - a;
        }
        return 0;
    }
    vector<bool> a(n + 1, 0);
    int ans = 0;
    while (T--) {
        int x;
        cin >> x;
        if (!a[x]) {
            if (x == 1) {
                ans += (!a[2]);
            } else if (x == n) {
                ans += (!a[n - 1]);
            } else {
                if (!a[x - 1] && !a[x + 1]) {
                    ans++;
                } else if (!a[x - 1] ^ !a[x + 1]) {
                    ans;
                } else {
                    ans--;
                }
            }
        } else {
            if (x == 1) {
                ans -= (!a[2]);
            } else if (x == n) {
                ans -= (!a[n - 1]);
            } else {
                if (!a[x - 1] && !a[x + 1]) {
                    ans--;
                } else if (!a[x - 1] ^ !a[x + 1]) {
                    ans;
                } else {
                    ans++;
                }
            }
        }
        a[x] = !a[x];
        cout << ans << '\n';
    }
    return 0;
}

D.Conflict 2

题目描述

有$N$个电脑和一个服务器，每个电脑和服务器都有存储一个字符串，最初所有的字符串都是空串。

给你$Q$个操作，每个操作是以下$3$种其中的一种：

• 1 p 把第$p$个电脑的字符串替换成服务器的字符串

• 2 p s 在第$p$个电脑的后面添加$s$这个字符串

• 3 p 把服务器的字符串替换成第$p$个电脑的字符串

思路

被这题调教到红温了 具体看这个提交，这是我用map优化的某种玄学代码，除了UKEOLEILE其他几个状态都集齐了（

我还是拿我第一发过交的思路来讲，不难想到可以用块状链表轻松搞定

啊啊啊啊啊气死我了

代码

#include<ext/rope>
#include<bits/stdc++.h>
using namespace std;
using namespace __gnu_cxx;
int main()
{
    int n, T;
    cin >> n >> T;
    rope<char> s;           
    vector<rope<char>> pc(n + 1);
    while (T--) {
        int ch;
        cin >> ch;
        if (ch == 1) {
            int x;
            cin >> x;
            pc[x] = s;
        } else if (ch == 2) {
            int x;
            string tp;
            cin >> x >> tp;
            rope<char> ttp(tp.c_str(), tp.size());
            pc[x] = pc[x] + ttp;
        } else {
            int x;
            cin >> x;
            s = pc[x];
        }
    }
    cout << s.c_str();
    return 0;
}

E.

题目描述

思路

代码

F.

题目描述

思路

代码

G.

题目描述

思路

代码

彩蛋