A. Passing the Ball考点模拟思路其实就是找连续段的R有多少个就行了最后加上一个L的值输出即可。复杂度O(n)import sys input sys.stdin.readline tint(input()) for _ in range(t): nint(input()) sinput().strip() cnt0 for v in s: if vR: cnt1 else: break print(cnt1)B. Right Maximum考点模拟思路这题不能真的去暴力模拟我们可能换一种思路正着去想题目要求的是去掉每次最右边最大的数往后的所有数包括自己本身。那我们可以换成正向走设s为一个很小的值如果当前值xs的时候说明这里肯定要分一块就将这个s更新为当前x并且计数1。复杂度O(n)import sys input sys.stdin.readline tint(input()) for _ in range(t): nint(input()) alist(map(int,input().split())) ans-(10**9) cnt0 for x in a: if xans: cnt1 ansx print(cnt)C. Spring考点容斥原理思路按题意可知我们可以先分别将三人中两两去取水的三种情况求出来很明显可以看出是用m天除以他们的最小公倍数。然后一个人打水是加6升两个人打水是加3升三个人打水是加2升。所以我们可以用容斥原理来做。Ar6*A-3*AB-3*AC2ABCBr6*B-3*AB-3*BC2ABCCr6*C-3*AC-3*BC2ABC复杂度O(1)import math import sys input sys.stdin.readline def lcm(a,b): return (a*b)//math.gcd(a,b) tint(input()) for _ in range(t): a,b,c,mmap(int,input().split()) Am//a Bm//b Cm//c ABm//lcm(a,b) ACm//lcm(a,c) BCm//lcm(b,c) ABCm//lcm(lcm(a,b),c) Ar6*A-3*AB-3*AC2*ABC Br 6 * B - 3 * AB - 3 * BC 2 * ABC Cr 6 * C - 3 * BC - 3 * AC 2 * ABC print(Ar,Br,Cr)D. Alternating Path考点二分图BFS思路由题目可知从v出发偶数层点的所有邻边都要从它流出。奇数层点的所有邻边都要流入它。于是整个连通块会被强制分成两类点而且边只能连在这两类之间。这是一个非常典型的二分图的定义。复杂度O(nm)import sys inputsys.stdin.readline from collections import deque tint(input()) for _ in range(t): #建图和入图 n,mmap(int,input().split()) g[[] for _ in range(n)] for _ in range(m): u,vmap(int,input().split()) u-1 v-1 g[u].append(v) g[v].append(u) #颜色数组和答案 color[-1]*n#表示第i个点染成什么颜色-1表示没染0和1表示两种不同颜色 ans0 for i in range(n): if color[i]!-1: continue #BFS开始染色 qdeque([i])#把起点放进队列 color[i]0#起点先染成0色 cnt0,cnt11,0 okTrue #BFS遍历这个连通块 while q: xq.popleft() #遍历x的所有邻居y for y in g[x]: if color[y]-1: color[y]color[x]^1 if color[y]0: cnt01 else: cnt11 q.append(y) #邻居已经染色过了 elif color[y]color[x]: okFalse #计算这个连通块处理完后统计贡献 if ok: ansmax(cnt0,cnt1) print(ans)
Educational Codeforces Round 188 (Rated for Div. 2)
A. Passing the Ball考点模拟思路其实就是找连续段的R有多少个就行了最后加上一个L的值输出即可。复杂度O(n)import sys input sys.stdin.readline tint(input()) for _ in range(t): nint(input()) sinput().strip() cnt0 for v in s: if vR: cnt1 else: break print(cnt1)B. Right Maximum考点模拟思路这题不能真的去暴力模拟我们可能换一种思路正着去想题目要求的是去掉每次最右边最大的数往后的所有数包括自己本身。那我们可以换成正向走设s为一个很小的值如果当前值xs的时候说明这里肯定要分一块就将这个s更新为当前x并且计数1。复杂度O(n)import sys input sys.stdin.readline tint(input()) for _ in range(t): nint(input()) alist(map(int,input().split())) ans-(10**9) cnt0 for x in a: if xans: cnt1 ansx print(cnt)C. Spring考点容斥原理思路按题意可知我们可以先分别将三人中两两去取水的三种情况求出来很明显可以看出是用m天除以他们的最小公倍数。然后一个人打水是加6升两个人打水是加3升三个人打水是加2升。所以我们可以用容斥原理来做。Ar6*A-3*AB-3*AC2ABCBr6*B-3*AB-3*BC2ABCCr6*C-3*AC-3*BC2ABC复杂度O(1)import math import sys input sys.stdin.readline def lcm(a,b): return (a*b)//math.gcd(a,b) tint(input()) for _ in range(t): a,b,c,mmap(int,input().split()) Am//a Bm//b Cm//c ABm//lcm(a,b) ACm//lcm(a,c) BCm//lcm(b,c) ABCm//lcm(lcm(a,b),c) Ar6*A-3*AB-3*AC2*ABC Br 6 * B - 3 * AB - 3 * BC 2 * ABC Cr 6 * C - 3 * BC - 3 * AC 2 * ABC print(Ar,Br,Cr)D. Alternating Path考点二分图BFS思路由题目可知从v出发偶数层点的所有邻边都要从它流出。奇数层点的所有邻边都要流入它。于是整个连通块会被强制分成两类点而且边只能连在这两类之间。这是一个非常典型的二分图的定义。复杂度O(nm)import sys inputsys.stdin.readline from collections import deque tint(input()) for _ in range(t): #建图和入图 n,mmap(int,input().split()) g[[] for _ in range(n)] for _ in range(m): u,vmap(int,input().split()) u-1 v-1 g[u].append(v) g[v].append(u) #颜色数组和答案 color[-1]*n#表示第i个点染成什么颜色-1表示没染0和1表示两种不同颜色 ans0 for i in range(n): if color[i]!-1: continue #BFS开始染色 qdeque([i])#把起点放进队列 color[i]0#起点先染成0色 cnt0,cnt11,0 okTrue #BFS遍历这个连通块 while q: xq.popleft() #遍历x的所有邻居y for y in g[x]: if color[y]-1: color[y]color[x]^1 if color[y]0: cnt01 else: cnt11 q.append(y) #邻居已经染色过了 elif color[y]color[x]: okFalse #计算这个连通块处理完后统计贡献 if ok: ansmax(cnt0,cnt1) print(ans)
