개인 노트
18757 단어 Python시합 프로그램 설계AtCodertech
감상
완료
A - Simple Math 2
해설
https://atcoder.jp/contests/arc111/editorial/491
10^N의mod를 가져올 줄은 몰랐어요.
\lflowor\rac{10^N}\rflowor(mod\M)는 정수)면 k
이 공식은 0\equivkM\mod\M\(k\in\mathb{Z})(k는 정수)에서 다음과 같이 변형할 수 있습니다.
\lfloor\frac{10^N}{M}\rfloor
\equiv\lfloor\frac{10^N}{M}\rfloor-kM
\equiv\lfloor\frac{10^N-kM^2}{M}\rfloor
\equiv\lfloor\frac{10^N\mod\M^2}{M}\rfloor
\(mod\M)
산식mod의 작법이 틀릴 수 있습니다
N, M = map(int, input().split())
print(pow(10, N, M ** 2) // M % M)
B - Reversible Cards
해설
https://atcoder.jp/contests/arc111/editorial/519
대강 설명한 대로 설치하다
ans=(카드 색깔의 종류)=(정수리), 나무마다 ans에서 빼기
def dfs(n: int, parent: int):
"""木だったらtrue"""
# 頂点nが探索済みかつ直前の頂点の親でもない→閉路
if seen[n]:
return False
seen[n] = True
res = True
for i in G[n]:
# 次の頂点が直前の頂点(親)と一緒なら探索不要
if i == parent:
continue
res = res and dfs(i, n)
return res
N = int(input()) # 2*10**5
color = 4 * 10 ** 5 + 1 # color<=4*10**5
G = [[] for _ in range(color)]
V = set()
for _ in range(N):
a, b = map(int, input().split())
V.add(a)
V.add(b)
G[a].append(b)
G[b].append(a)
seen = [False] * color
ans = len(V)
for i in range(color):
if dfs(i, 0) and G[i]:
ans -= 1
print(ans)
다른 사람이 제출한 걸 봤는데 유니언-find가 써서 그쪽도 썼어요.class UnionFind:
"""Union-Findアルゴリズム(素集合データ構造(disjoint-set data structure)に対しての操作)"""
def __init__(self, n: int):
self.root = [-1] * n
self.edge = [0] * n
def find(self, x: int) -> int:
if self.root[x] < 0:
return x
self.root[x] = self.find(self.root[x])
return self.root[x]
def unite(self, x: int, y: int) -> bool:
x = self.find(x)
y = self.find(y)
if x == y:
self.edge[x] += 1
return False
if self.root[x] > self.root[y]:
x, y = y, x
self.root[x] += self.root[y]
self.root[y] = x
self.edge[x] += self.edge[y] + 1
return True
def same(self, x: int, y: int) -> bool:
return self.find(x) == self.find(y)
def size(self, x: int) -> bool:
return self.root[self.find(x)] * -1
def num_edge(self, x: int) -> int:
return self.edge[x]
N = int(input()) # 2*10**5
color = 4 * 10 ** 5 + 1 # color<=4*10**5
union = UnionFind(color)
for _ in range(N):
a, b = map(int, input().split())
union.unite(a, b)
ans = 0
for i in range(color):
if union.root[i] < 0:
ans += min(union.size(i), union.num_edge(i))
print(ans)
Reference
이 문제에 관하여(개인 노트), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://zenn.dev/m193h/articles/20210110sun140216m193harc111텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)