【AtCoder解说】用Python控制ABC264的A、B、C、D、E问题!

ABC264的A、B、C、D、E 问题的,Python3我会尽可能仔细地解释它。

我们旨在解释满足以下三点的解决方法,而不仅仅是一种可以解决的方法。

简单:没有多余的想法 易于实施:错误和错误更少 花费更少的时间:提高性能并为以后的问题留出更多时间

有任何问题或意见吗?评论蚊子推特,棉花糖, 随意访问我们的 Discord 服务器!

推特:棉花糖:如果没问题LGTM或者扩散如果可以的话,我会很高兴的!

目录

ABC264 总结

提交总数:8422

表现 表现 啊C 分数 时间 等级(在额定范围内) 200 AB----- 300 47 分钟 排名 5917 (5659) 400 AB----- 300 14 分钟 4872 (4614) 600 AB-D---- 700 76 分钟 第 3969 次(第 3726 次) 800 AB-D---- 700 29 分钟 第 3125 次(第 2883 次) 1000 A B C D - - 1000 66 分钟 排名 2311 (2071) 1200 A B C D - - 1000 22 分钟 1673 (1434) 1400 ABCDE--- 1500 78 分钟 第 1151 次(第 936 次) 1600 ABCDE--- 1500 52 分钟 排名 782 (575) 1800 AB-DEF-- 1700 98 分钟 第 516 届(第 334 届) 2000 ABCDEF—— 2000 85 分钟 第 348 届(第 184 届) 2200 ABCDEF—— 2000 65 分钟 第 220 届(第 87 届) 2400 ABCDEF—— 2000 40 分钟 第 149 届(第 42 届) 颜色准确率 颜色 人数 一个 B. C。 D. 图片 F。 G。 图片 x 灰 2734 98.1% 82.6% 11.4% 33.5% 1.7% 0.1% 0.0% 0.0% 茶 1431 99.0% 95.4% 43.9% 69.5% 6.2% 0.3% 0.0% 0.1% 绿色 1149 98.3% 96.1% 76.6% 92.2% 31.1% 1.6% 0.1% 0.1% 水 678 97.9% 96.3% 91.9% 96.9% 79.9% 14.3% 0.9% 0.3% 蓝色的 404 95.5% 95.5% 94.8% 96.0% 93.8% 50.2% 7.9% 2.0% 黄色 196 86.2% 85.2% 83.7% 85.7% 85.7% 64.8% 33.7% 9.7% 橙 43 83.7% 81.4% 79.1% 81.4% 81.4% 79.1% 83.7% 44.2% 红色的 23 95.7% 95.7% 95.7% 95.7% 95.7% 95.7% 87.0% 73.9%

*展示率,不包括第一次参加骨灰的人

问题 A ""atcoder".substr()"

问题页面:灰编码器准确率: 98.1%茶编码器准确率: 99.0%绿色编码器准确率: 98.3%

考虑

您可以使用切片将atcoder 的$L$ 到$R$ 字符输出。

代码
L, R = map(int, input().split())
S = "atcoder"
print(S[L - 1:R])
问题 B “漂亮的网格”

问题页面:灰编码器准确率: 82.6%茶编码器准确率: 95.4%绿色编码器准确率: 96.1%

考虑 切比雪夫距离

中间的 $(8,8)$ 是白色的。一个外面是黑色的,外面是白色的。

如果 $k$ 是偶数,则中心外的颜色 $k$ 为白色,如果 $k$ 为奇数,则为黑色。这个$k$ 由$k=\max(|R-8|,|C-8|)$ 得到。 (这称为切比雪夫距离。)

嵌入方块

这很麻烦,但由于$15\times15$ 中只有$225$ 的方格,你可以通过手动输入方格来努力找出$(R,C)$ 的颜色。

S = ["###############",
     "#.............#",
     "#.###########.#",
     "#.#.........#.#",
     "#.#.#######.#.#",
     "#.#.#.....#.#.#",
     "#.#.#.###.#.#.#",
     "#.#.#.#.#.#.#.#",
     "#.#.#.###.#.#.#",
     "#.#.#.....#.#.#",
     "#.#.#######.#.#",
     "#.#.........#.#",
     "#.###########.#",
     "#.............#",
     "###############"]
代码 切比雪夫距离
def solve():
    R, C = map(int, input().split())
    dist = max(abs(R - 8), abs(C - 8))
    return "white" if dist % 2 == 0 else "black"


print(solve())
嵌入方块
S = ["###############",
     "#.............#",
     "#.###########.#",
     "#.#.........#.#",
     "#.#.#######.#.#",
     "#.#.#.....#.#.#",
     "#.#.#.###.#.#.#",
     "#.#.#.#.#.#.#.#",
     "#.#.#.###.#.#.#",
     "#.#.#.....#.#.#",
     "#.#.#######.#.#",
     "#.#.........#.#",
     "#.###########.#",
     "#.............#",
     "###############"]


def solve():
    R, C = map(int, input().split())
    R -= 1
    C -= 1
    return "white" if S[R][C] == "." else "black"


print(solve())
问题 C“矩阵减少”

问题页面:灰编码器准确率: 11.4%茶编码器准确率: 43.9%绿色编码器准确率: 76.6%

考虑

对要通过位全搜索擦除的行和列执行全搜索。

Yes 如果至少有一个橡皮擦匹配 $B$,No 如果没有。

代码

请使用 PyPy 发布。如果bit_r 的$1$ 站数等于$H_2$ 并且bit_c 的$1$ 站数等于$W_2$,Python 也将通过。

def solve():
    def judge(bit_r, bit_c):
        A2 = []
        for row in range(H1):
            if not (bit_r >> row & 1):
                continue
            V = []
            for col in range(W1):
                if bit_c >> col & 1:
                    V.append(A[row][col])
            A2.append(V)
        return A2 == B

    H1, W1 = map(int, input().split())
    A = [list(map(int, input().split())) for _ in range(H1)]
    H2, W2 = map(int, input().split())
    B = [list(map(int, input().split())) for _ in range(H2)]
    for bit_r in range(1 << H1):
        for bit_c in range(1 << W1):
            if judge(bit_r, bit_c):
                return True
    return False

print("Yes" if solve() else "No")
问题 D ""redocta".swap(i,i+1)"

问题页面:灰编码器准确率: 33.5%茶编码器准确率: 69.5%绿色编码器准确率: 92.2%

考虑

如果$2$相邻元素不是升序排列,则通过重复shuffle操作进行排序的算法为它被称为。

在这个问题中,目的是对atcoder进行排序,而不是按字母升序排序,而是通过将$S$的每个字符替换为数字a=0, t=1, c=2, o=3, d=4, e=5, r=6,用冒泡排序将数字序列升序排序[0, 1, 2, 3, 4, 5, 6]。然后,找出元素交换了多少次成为一个问题。

也就是说,你实际上可以对$S$的每个字符替换为$0$到$6$的列表进行冒泡排序,并计算元素被替换的次数。

代码
S = input()
P = "atcoder"
N = len(P)
L = [P.index(c) for c in S]

ans = 0
for i in range(N - 1):
    for j in range(N - i - 1):
        if L[j] > L[j + 1]:
            L[j], L[j + 1] = L[j + 1], L[j]
            ans += 1
print(ans)
评论

众所周知,冒泡排序中元素的排列次数等于翻转次数。因此,在没有实际进行冒泡排序的情况下,如果您计算翻滚次数,那将与答案相符。

如果你有一个图书馆询问跌倒次数,我认为这更容易。

def main():
    S = input()
    P = "atcoder"
    L = [P.index(c) for c in S]
    print(calc_inversion_number(L))


class FenwickTree:
    def __init__(self, n):
        self.__array = [0] * n
        self.__size = n + 1
        self.__container = [0] * (n + 1)
        self.__depth = n.bit_length()

    def add(self, i, x):
        """a[i]にxを加算"""
        self.__array[i] += x
        i += 1
        while i < self.__size:
            self.__container[i] += x
            i += i & (-i)

    def sum(self, r):
        """[0, r) の総和"""
        s = 0
        while r > 0:
            s += self.__container[r]
            r -= r & (-r)
        return s


def calc_inversion_number(A):
    N = len(A)
    ft = FenwickTree(N + 1)
    ret = 0
    for i, x in enumerate(A):
        ret += i - ft.sum(x)
        ft.add(x, 1)
    return ret


if __name__ == '__main__':
    main()
问题 E“停电 2”

问题页面:灰编码器准确率: 1.7%茶编码器准确率: 6.2%绿色编码器准确率: 31.1%

考虑

无需区分一个城市连接到哪个电站。此外,如果一个城市连接到 1 美元的发电厂,它就会有电。它是否连接到发电厂才重要,它不需要有关它连接到多少个发电厂的信息。

因此,我们将所有 $M$ 发电厂等同起来。具体来说,点 $N+1,N+2,\dots,N+M$ 是发电厂,但我们将所有这些点视为顶点 $N+1$。

那么给定时间有电的城市数量由数据结构给出联合查找, $(顶点的连通分量大小\N+1\) - 1$($-1$是电厂的顶点数)。

但是,UnionFind 不能删除边。因此,通过向后查看 $Q$ 事件,而不是断开线 $X_i$,我们应该假设线 $X_i$ 已连接。

代码

在讨论中,我们从 $1$ 开始计算顶点,但在代码中我们减去 $1$ 并从顶点 $0$ 开始计算。发电厂是顶点$N$。

import sys

readline = sys.stdin.readline  # 入力が多く時間がかかるので、inputより高速な入力を使います(800ms程度高速になります)


def main():
    N, M, E = map(int, readline().split())
    edge = []
    for i in range(E):
        u, v = map(int, readline().split())
        edge.append((min(u - 1, N), min(v - 1, N)))  # N以上なら発電所なので、すべてNに置き換える

    Q = int(readline())
    X = []
    connected = [True] * E  # Q個のイベントの後、残っている辺をつなげる
    for i in range(Q):
        x = int(readline())
        x -= 1
        connected[x] = False
        X.append(x)

    uf = UnionFind(N + 1)
    for i in range(E):
        if connected[i]:  # 切れてない辺なら接続
            u, v = edge[i]
            uf.unite(u, v)

    ans = [0] * Q  # 逆再生します
    for i in reversed(range(Q)):
        ans[i] = uf.size(N) - 1
        u, v = edge[X[i]]
        uf.unite(u, v)  # 逆再生なので、答えを求めてから接続します
    print(*ans, sep='\n')


from typing import List


class UnionFind:
    """0-indexed"""

    def __init__(self, n):
        self.n = n
        self.parent = [-1] * n
        self.__group_count = n

    def unite(self, x, y) -> bool:
        """xとyをマージ"""
        x = self.root(x)
        y = self.root(y)

        if x == y:
            return False

        self.__group_count -= 1

        if self.parent[x] > self.parent[y]:
            x, y = y, x

        self.parent[x] += self.parent[y]
        self.parent[y] = x

        return True

    def is_same(self, x, y) -> bool:
        """xとyが同じ連結成分か判定"""
        return self.root(x) == self.root(y)

    def root(self, x) -> int:
        """xの根を取得"""
        xc = x
        while self.parent[x] >= 0:
            x = self.parent[x]
        while xc != x:
            self.parent[xc], xc = x, self.parent[xc]
        return x

    def size(self, x) -> int:
        """xが属する連結成分のサイズを取得"""
        return -self.parent[self.root(x)]

    def all_sizes(self) -> List[int]:
        """全連結成分のサイズのリストを取得 O(N)"""
        sizes = []
        for i in range(self.n):
            size = self.parent[i]
            if size < 0:
                sizes.append(-size)
        return sizes

    def groups(self) -> List[List[int]]:
        """全連結成分の内容のリストを取得 O(N・α(N))"""
        groups = dict()
        for i in range(self.n):
            p = self.root(i)
            if not groups.get(p):
                groups[p] = []
            groups[p].append(i)
        return list(groups.values())

    @property
    def group_count(self) -> int:
        """連結成分の数を取得 O(1)"""
        return self.__group_count


if __name__ == '__main__':
    main()

原创声明:本文系作者授权爱码网发表,未经许可,不得转载;

原文地址:https://www.likecs.com/show-308623466.html

27人参与, 0条评论 登录后显示评论回复

你需要登录后才能评论 登录/ 注册