[atc复盘] abc296 20230401

一、本场总结

• 第一次打atcoder，abc做到F。
• A 模拟。
• B 下标计算。
• C 哈希表。
• D 数学贪心枚举。
• E 看似是博弈其实是拓扑排序。
• F 模拟/逆序对。
• 
• 
  

二、 A - Alternately

链接: A - Alternately

1. 题目描述

2. 思路分析

• 直接枚举每个相邻对是否不同即可。

3. 代码实现

# Problem: A - Alternately
# Contest: AtCoder - AtCoder Beginner Contest 296
# URL: https://atcoder.jp/contests/abc296/tasks/abc296_a
# Memory Limit: 1024 MB
# Time Limit: 2000 msimport sys
import bisect
import random
import io, os
from bisect import *
from collections import *
from contextlib import redirect_stdout
from itertools import *
from array import *
from functools import lru_cache
from types import GeneratorType
from heapq import *
from math import sqrt, gcd, infif sys.version >= '3.8':  # ACW没有combfrom math import combRI = lambda: map(int, sys.stdin.buffer.readline().split())
RS = lambda: map(bytes.decode, sys.stdin.buffer.readline().strip().split())
RILST = lambda: list(RI())
DEBUG = lambda *x: sys.stderr.write(f'{str(x)}\\n')MOD = 10  9 + 7
PROBLEM = """https://atcoder.jp/contests/abc296/tasks/abc296_a
给你整数n和长为n的字符串s
s由M/F两种字母组成代表男女。
检测s是否是男女交替的。
"""def solve():n, = RI()s, = RS()for i in range(n - 1):if s[i] == s[i + 1]:return print('No')print('Yes')

三、B - Chessboard

链接: B - Chessboard

1. 题目描述

2. 思路分析

• 枚举找下标，转换一下下标即可。

3. 代码实现

PROBLEM = """https://atcoder.jp/contests/abc296/tasks/abc296_b
给你一个8*8的棋盘。由'.*'两种字符组成。
棋盘上只有一个*，找出*的坐标。
其中横坐标从下往上编码为1-8；纵坐标从左到右编码为a-h。
"""#       ms
def solve():g = []for _ in range(8):s, = RS()g.append(s)for i in range(8):for j, c in enumerate(g[i]):if c == '*':a = chr(ord('a') + j)print(f"{a}{8 - i}")

四、C - Gap Existence

链接: C - Gap Existence

1. 题目描述

2. 思路分析

• 直接把a转成set。
• 枚举每个数，检查和它差为d的数据是否在set里。

3. 代码实现

PROBLEM = """https://atcoder.jp/contests/abc296/tasks/abc296_c
给你整数N(2<=N<=2e5)，X(-1e9<=X<=1e9)，和长为N的数组A。
请问A中是否存在两个数差值为X。这两个数可以是同一个数。
"""#       ms
def solve():n, x = RI()a = set(RILST())for v in a:if v - x in a or v + x in a:return print('Yes')print('No')

五、D - M<=ab

链接: D - M<=ab

1. 题目描述

2. 思路分析

• 由于数据范围大，直接枚举肯定不行。可以先考虑无解的情况：
• 如果n*n<m肯定无解，因为即使a、b都取到n，乘积也够不到m。
• 如果n*n=m，那ab只能都取到n，任意数再小都不够m，则乘积只能是m。
• 若m<=n，显然ab可以是1 m,最小就是m，返回m即可。
• 其它情况(n*n>m&&n<m)则需要遍历尝试：
  • 首先初始化ans上界，起码ab可以取到n*n，这个数是满足条件的答案。我们枚举找比它更小的答案。
  • 枚举乘积答案肯定是不行的，考虑枚举因子a/b里小的那个（因为乘法满足交换律，枚举哪个都可以）,设为a。
  • a显然不会超过sqrt(m),这时可以计算b=ceil(m/a)。上取整后就可以保证a*b>=m。
  • 因此这么枚举，只需要保证ab<=n即可更新答案。

• 补充一下为什么不需要枚举>sqrt(m)的部分：
  • 如果a>sqrt(m)，那么当b=sqrt(m)则乘积一定超过m，为了取到最小的b=ceil(m/a)，b只会更小，那这个b一定在之前枚举过了(作为a枚举)，或者说这个数对已经被枚举过了。

3. 代码实现

PROBLEM = """https://atcoder.jp/contests/abc296/tasks/abc296_d
给你两个正整数n,m(1<=N,M<=1e12)。
找到一个最小的x，使x满足:
1.x>=m
2.x可以被分解为两个数ab的乘积，其中1<=a,b<=n
"""#       ms
def solve():n, m = RI()if n * n < m:return print(-1)if n * n == m:return print(m)if m <= n:return print(m)s = int(m  0.5)ans = n * nfor a in range(2, min(s, n) + 1):b = (m + a - 1) // aif b <= n:ans = min(ans, b * a)print(ans)

六、E - Transition Game

链接: E - Transition Game

1. 题目描述

2. 思路分析

这题读题没读懂，就去做F了，赛后补的E。主要是没看懂那个x是哪来的，后来知道写在黑板上的数就是x。而且黑板上每次只有一个数。

• 手玩一下发现：替换操作就是把数字沿着值作为下标->值这个路径往后走，路径可以用图考虑。
• 把整个数组按这个操作建图，图中会存在环，n个节点n条边；而且这个图是内向的，因为出度最多是1.即进了环就出不来。
• 由于第i轮操作的目标数字是知道的，即i，B的目标是让路径的终点是i，那么若i在环上，B可以调整起始点的位置，使ki步后正好到达i。(因为在环上代表前边步数可以无限)
• A的目标是让i不在终点，那么对于所有没进环上的i，可以设置ki>=n足够大，使终点进环。
• 因此对于所有在环上的i，B必赢；不在环上的点，A必赢。
• 找所有环上的点数量不好弄；反过来求不在环上的点，用拓扑排序即可。

3. 代码实现

PROBLEM = """https://atcoder.jp/contests/abc296/tasks/abc296_e
给你N和长度为N的数组a，其中1<=a[i]<=N,下标从1开始。
A和B做N轮游戏，轮数下标从1开始。在第i轮，玩法如下：
1. A指定一个正整数ki,告诉B。
2. B指定一个1~N之间的数，写在黑板上。
3. 做如下操作ki次:把黑板上的数字x替换成a[x]。
操作结束后，如果黑板上的数字是i，B赢；否则A赢。
请问在A和B都做最优操作的情况下，B能赢多少次。
"""#       ms
def solve():n, = RI()a = RILST()g = [[] for _ in range(n + 1)]degree = [0] * (n + 1)for i, v in enumerate(a, start=1):g[i].append(v)degree[v] += 1q = deque([i for i, v in enumerate(degree) if i and v == 0])ans = nwhile q:ans -= 1u = q.popleft()for v in g[u]:degree[v] -= 1if degree[v] == 0:q.append(v)print(ans)

七、F - Simultaneous Swap

链接: F - Simultaneous Swap

1. 题目描述

2. 思路分析

群里大佬说正解是逆序对，我没看懂，直接找性质做的。没想到直接交就TLE了，优化了一下就过了
这里吐槽一下for x in set:break 是会TLE的，看来虽然提前break但没用，依然是O(n)。

• 首先a和b的元素对应数量必须相同，用sorted(a) != sorted(b)特判。
• 手玩发现，如果有1个元素出现两次，那么按照case1的方法交换，一定可以使另外一个位置相同，此时必Yes。
• 然后是模拟验证所有元素只出现一次的情况：
  • 使第一个位置元素相同，只需找到一个还没处理的数字，找到它在ab分别的位置，把这个元素换过来。
  • 然后依次处理第2\\3\\4…个位置。如果遇到本来就相同就不用动。
  • 直到处理完倒数第三个位置，这时后两个位置如果不同则不行，如果完全相同才行，因为他们无法做出有用的交换了。

• 逆序对做法：如果ab的逆序对数奇偶性相同，则可以交换；否则不能交换。
• 当然前几个特判依然需要。

3. 代码实现

PROBLEM = """https://atcoder.jp/contests/abc296/tasks/abc296_f
给你N(3<=N<=2e5)，和两个长度为n的数组a,b。
你可以做如下操作任意次或不做：
选下标j!=i!=k，同时交换：在a中交换a[i]a[j].再b中交换b[i]b[k]
若可以使a完全等于b输出Yes，否则输出No。
"""#       ms
def solve():n, = RI()a = RILST()b = RILST()if a == b:return print('Yes')if sorted(a) != sorted(b):return print('No')if len(set(a)) < n:return print('Yes')posa = {v: i for i, v in enumerate(a)}posb = {v: i for i, v in enumerate(b)}left = set(a)def get(x, y):s = set()ans = 0nonlocal leftfor _ in range(3):p = left.pop()if x != p != y:ans = ps.add(p)left |= sreturn ansfor i in range(n - 2):if a[i] == b[i]:left.remove(a[i])else:v = get(a[i], b[i])pa = posa[v]pb = posb[v]left.remove(v)posa[a[i]] = paposb[b[i]] = pba[pa] = a[i]b[pb] = b[i]if a[-1] == b[-1] and a[-2] == b[-2]:return print('Yes')print('No')

土地资源文秘网