Atcoder ABC391游记

Atcoder ABC390个人游记（A~C,E）

比赛链接

妙啊，比taqingqiu都要苗妙妙

这次比赛是不是有个印度选手用ai三分钟一道f被atcoder封了（

乐子重开吧

话说你们是不是也不能用deepl了

A - Lucky Direction

问题陈述

您将得到一个字符串 $D$ ，表示八个方向（北、东、西、南、东北、西北、东南、西南）中的一个。方向和它们的表示字符串之间的对应关系如下。

-北：‘ N ’

-东：“E”

-西方：“W”

-南方：“S”

-东北：“NE”

-西北：“NW”

-东南：“SE”

西南：“SW”

打印与 $D$ 表示的方向相反的字符串。问题陈述

您将得到一个字符串 $D$ ，表示八个方向（北、东、西、南、东北、西北、东南、西南）中的一个。方向和它们的表示字符串之间的对应关系如下。

-北：‘ N ’

-东：“E”

-西方：“W”

-南方：“S”

-东北：“NE”

-西北：“NW”

-东南：“SE”

西南：“SW”

打印与 $D$ 表示的方向相反的字符串。

思路

EASY

代码

#include<bits/stdc++.h>
using namespace std;
int main()
{
    map<char,char> mp;
    mp['S'] = 'N';
    mp['N'] = 'S';
    mp['E'] = 'W';
    mp['W'] = 'E';
    string s;
    cin >> s;
    for (int i = 0; i < s.length(); i++) {
        cout << mp[s[i]];
    }
    return 0;
}

B - Seek Grid

问题陈述

您将得到一个 $N \times N$ 网格 $S$ 和一个 $M \times M$ 网格 $T$ 。从顶部算起的第 $i$ 行和从左侧算起的第 $j$ 列的单元格用 $(i,j)$ 表示。

$S$ 和 $T$ 中的单元格的颜色分别由 $N^2$ 字符 $S_{i,j}$ （ $1\leq i,j\leq N$ ）和 $M^2$ 字符 $T_{i,j}$ （ $1\leq i,j\leq M$ ）表示。在网格 $S$ 中，如果单元格 $S_{i,j}$ 为’，则单元格 $(i,j)$ 为白色。‘，如果 $S_{i,j}$ 为’ # '，则显示黑色。这同样适用于网格 $T$ 。

在 $S$ 中查找 $T$ 。更精确地说，输出满足以下条件的整数 $a$ 和 $b$ ( $1 \leq a,b \leq N-M+1$ )：

-每 $i,j$ （ $1\leq i,j \leq M$ ）对应 $S_{a+i-1,b+j-1} = T_{i,j}$ 。

思路

EASY 小匹配

代码

#include<bits/stdc++.h>
using namespace std;
int n, m;
char s[55][55], t[55][55];
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> s[i][j];
        }
    }
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> t[i][j];
        }
    }
    for (int i = 1; i <= n - m + 1; i++) {
        for (int j = 1; j <= n - m + 1; j++) {
            bool check = 1;
            for (int k = i; k <= i + m - 1; k++) {
                for (int l = j; l <= j + m - 1; l++) {
                    if (s[k][l] != t[k - i + 1][l - j + 1]) {
                        check = 0;
                        break;
                    }
                }
            }
            if (check) {
                cout << i << ' ' << j;
                return 0;
            }
        }
    }
    return 0;
}

C - Pigeonhole Query

问题陈述

有编号为 $1$ 到 $N$ 的 $N$ 鸽子，有编号为 $1$ 到 $N$ 的 $N$ 巢。最初，鸽子 $i$ 在 $1\leq i\leq N$ 的巢 $i$ 中。

您将得到 $Q$ 查询，您必须按顺序处理这些查询。有两种类型的查询，每种查询都以以下格式之一给出：

-“1 P H”：移动鸽子 $P$ 到巢 $H$ 。

—“2”：输出包含一只以上鸽子的巢的数量。

思路

首先肯定不能上来就无脑模拟，我们把每只鸽子现在的巢和每个巢有的数量记录一下，搭配起来用就拿捏了。

代码

#include<bits/stdc++.h>
using namespace std;
int now[1111111], sum[1111111];
int ans = 0, n, T;
int main()
{
    cin >> n >> T;
    for (int i = 1; i <= n; i++) {
        sum[i] = 1;
        now[i] = i;
    }
    while (T--) {
        int ch;
        cin >> ch;
        if (ch == 1) {
            int p, h;
            cin >> p >> h;
            if (now[p] == h) {
                continue;
            }
            int from = now[p];
            int next = h;
            now[p] = h;
            sum[from]--;
            sum[next]++;
            if (sum[from] == 1) {
                ans--;
            }
            if (sum[next] == 2) {
                ans++;
            }
        } else {
            cout << ans << '\n';
        }
    }
    return 0;
}

D - Gravity

说出来让你们开心开心

我做的时候发现样例能过结果$ac*10,wa*15$我以为因为没开longlong，结果连ull都开了也死活没条出来。因为我先做的e，d的时间不太够，到赛后2分钟才调出来 难绷

这里我不想讲了，你们自己做吧（

E - Hierarchical Majority Vote

问题描述

对于长度为 $3^n$ （ $n \geq 1$ ）的二进制字符串 $B = B_1 B_2 \dots B_{3^n}$ ，定义如下操作来获取长度为 $3^{n-1}$ 的二进制字符串 $C = C_1 C_2 \dots C_{3^{n-1}}$ ：

-将 $B$ 的元素划分为 $3$ 的组，并从每组中取多数值。也就是说，对于 $i=1,2,\dots,3^{n-1}$ ，让 $C_i$ 作为 $B_{3i-2}$ 、 $B_{3i-1}$ 和 $B_{3i}$ 中出现频率最高的值。

您将得到一个长度为 $3^N$ 的二进制字符串 $A = A_1 A_2 \dots A_{3^N}$ 。设 $A' = A'_1$ 为对 $A$ 应用上述运算 $N$ 得到的长度- $1$ 字符串。

确定要更改 $A'_1$ 的值必须更改的 $A$ 的最小元素数（从 $0$ 到 $1$ 或从 $1$ 到 $0$ ）。

思路

奇妙的树形$dp$

这里$n$不会超过$13$，所以我们可以用$n^3$的时间复杂度枚举。

我们用树模拟一下数的合并，分值或者递归就差不多了。

打字好累啊

代码

#include <bits/stdc++.h>
using namespace std;
struct Info
{
    int finalBit;
    int costFlip0to1;
    int costFlip1to0;
};
string A;
Info buildTree(int l, int r)
{
    int len = r - l;
    if (len == 1)
    {
        Info ret;
        ret.finalBit = (A[l] - '0');
        if (ret.finalBit == 0)
        {
            ret.costFlip0to1 = 1;
            ret.costFlip1to0 = 0;
        }
        else
        {
            ret.costFlip0to1 = 0;
            ret.costFlip1to0 = 1;
        }
        return ret;
    }
    int seg = len / 3;
    Info c1 = buildTree(l, l + seg);
    Info c2 = buildTree(l + seg, l + 2 * seg);
    Info c3 = buildTree(l + 2 * seg, r);
    int bits[3] = {c1.finalBit, c2.finalBit, c3.finalBit};
    int cnt1 = (bits[0] == 1) + (bits[1] == 1) + (bits[2] == 1);
    int majorityBit = (cnt1 >= 2) ? 1 : 0; 
    auto costToMake = [&](int wantBit)
    {
        int ans = INT_MAX;
        for (int mask = 0; mask < 8; mask++)
        {
            int newBits[3];
            int costSum = 0;
            for (int i = 0; i < 3; i++)
            {
                bool flip = (mask & (1 << i)) != 0;
                if (!flip)
                {
                    newBits[i] = bits[i];
                }
                else
                {
                    if (bits[i] == 0)
                    {
                        costSum += (i == 0 ? c1.costFlip0to1 : i == 1 ? c2.costFlip0to1
                                                                      : c3.costFlip0to1);
                        newBits[i] = 1;
                    }
                    else
                    {
                        costSum += (i == 0 ? c1.costFlip1to0 : i == 1 ? c2.costFlip1to0
                                                                      : c3.costFlip1to0);
                        newBits[i] = 0;
                    }
                }
            }
            int cntW = 0;
            for (int i = 0; i < 3; i++)
            {
                if (newBits[i] == wantBit)
                    cntW++;
            }
            if (cntW >= 2)
            {
                ans = min(ans, costSum);
            }
        }
        return ans;
    };

    Info ret;
    ret.finalBit = majorityBit;
    if (majorityBit == 0)
    {
        ret.costFlip0to1 = costToMake(1);
        ret.costFlip1to0 = 0;
    }
    else
    {
        ret.costFlip1to0 = costToMake(0);
        ret.costFlip0to1 = 0;
    }
    return ret;
}
int main()
{
    int N;
    cin >> N;
    cin >> A;
    Info root = buildTree(0, A.size());
    if (root.finalBit == 0)
    {
        cout << root.costFlip0to1 << '\n';
    }
    else
    {
        cout << root.costFlip1to0 << '\n';
    }

    return 0;
}

我是不是写的有点太复杂了

彩蛋

xiaoguancairnmtqfuck

rangwobianchenglelezi