[abc复盘] abc297 20230409

一、本周周赛总结

• 这次学了个nim游戏-sg函数。
• A 模拟。
• B 模拟。
• C 贪心模拟。
• D GCD模拟。
• E堆模拟-超级丑数。
• F 不会。
• G nim游戏-sg函数。

A - Double Click

链接: A - Double Click

1. 题目描述

2. 思路分析

按题意模拟即可。

3. 代码实现

def solve():n, d = RI()a = RILST()for i in range(n - 1):if a[i + 1] - a[i] <= d:return print(a[i + 1])print(-1)

B - chess960

链接: B - chess960

1. 题目描述

2. 思路分析

• 模拟，学了个单词parties：奇偶性。

3. 代码实现

def solve():s, = RS()d = defaultdict(list)for i, c in enumerate(s):d[c].append(i)k = d['K'][0]x, y = d['R']if not x < k < y:return print('No')x, y = d['B']if x % 2 == y % 2:return print('No')print('Yes')

C - PC on the Table

链接: C - PC on the Table

1. 题目描述

2. 思路分析

• 直接遇到合法就替换即可。不会更差。

3. 代码实现

def solve():h, w = RI()for _ in range(h):s, = RS()p = list(s)j = 0while j < w - 1:if s[j] == s[j + 1] == 'T':p[j] = 'P'p[j + 1] = 'C'j += 1j += 1print(*p, sep='')

D - Count Subtractions

链接: D - Count Subtractions

1. 题目描述

2. 思路分析

• 如果研究过循环相减法和辗转相除法，会知道循环相减法的劣势在于:当a,b差特别大时，a每次减少的幅度很小，需要更多的时间；辗转相除法可以一次把a中可能减去的b全部减完，节省了时间。
• 因此用辗转相除法模拟即可。

3. 代码实现

# Problem: D - Count Subtractions
# Contest: AtCoder - AtCoder Beginner Contest 297
# URL: https://atcoder.jp/contests/abc297/tasks/abc297_d
# Memory Limit: 1024 MB
# Time Limit: 2000 msimport sysRI = 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/abc297/tasks/abc297_d
输入a,b(1<=a,b<=1e18)
你可以执行以下操作直到a==b- 如果a>b,令a=a-b- 如果a<b,令b=b-a
问能执行多少次操作
"""
"""发现就是gcd操作，直接用取模模拟即可。
"""#       ms
def solve():a, b = RI()if a < b:a, b = b, aans = 0while b:c = a // bans += ca %= ba, b = b, aprint(ans - 1)if __name__ == '__main__':solve()   

E - Kth Takoyaki Set

链接: E - Kth Takoyaki Set

1. 题目描述

2. 思路分析

• 跟超级丑数一个套路，用小顶堆模拟，每次用堆顶的最小值拿出来，和每种价格组合一下入堆。注意记录vis数组。。

3. 代码实现

PROBLEM = """https://atcoder.jp/contests/abc297/tasks/abc297_e
输入n(<=10),k(<=1e5),然后输入长度为n的数组a(1<=a[i]<=1e9)，a[i]代表第i种章鱼烧的价格。
每种章鱼烧可以取任意个，你可以选任意个章鱼烧组合起来计算总价，请问能组合成的第k小总价是多少。
"""
"""跟超级丑数一个套路，用小顶堆模拟，每次用堆顶的最小值拿出来，和每种价格组合一下入堆。注意记录vis数组。
"""#       ms
def solve():n, k = RI()a = RILST()a.sort()h = [0]p = {0}for i in range(k):x = heappop(h)for v in a:c = x + vif c not in p:p.add(c)heappush(h, c)print(heappop(h))

G - Constrained Nim 2

链接: G - Constrained Nim 2

1. 题目描述

2. 思路分析

• nim游戏可以用SG函数解决。
• SG(x) = mex{SG(y)|y是局面x的所有后记局面}
• SG定理：
  • g是总体局面，它可以分成n个互相独立的局面：在本题就是n堆石子。
  • g = g1+g2+g3_…+gn
  • SG(g) = SG(g1)^SG(g2)…^SG(gn)
• 当SG(g)=0的时候，这个局面的玩家必败。
• 对一堆石子打表一下找规律，发现循环节是(l+r),且从0向上增长，每l个一跳，就再除以l。

3. 代码实现

PROBLEM = """https://atcoder.jp/contests/abc297/tasks/abc297_g
nim游戏2，输入n(<2e5) l r(l,r<1e9),和长为n的数组a(a[i]<1e9)。a[i]代表第i堆石子的数量
First和Second两名玩家做游戏，轮流从任意一堆石子中取走l~r个石子，不能完成操作的玩家失败。
最优操作下问谁赢。
"""
"""nim游戏可以用SG函数解决。
SG(x) = mex{SG(y)|y是局面x的所有后记局面}
SG定理：- g是总体局面，它可以分成n个互相独立的局面：在本题就是n堆石子。- g = g1+g2+g3_..+gn- SG(g) = SG(g1)^SG(g2)^..^SG(gn)
当SG(g)=0的时候，这个局面的玩家必败。
对一堆石子打表一下找规律，发现循环节是(l+r),且从0向上增长，每l个一跳，就再除以l。
"""#  163 ms
def solve():n, l, r = RI()a = RILST()s = 0def sg(x):return x % (l + r) // lfor v in a:s ^= sg(v)if s:print('First')else:print('Second')

六、参考链接