Codeforces Round 1020 (Div. 3) A-D

A. Dr. TC

https://codeforces.com/contest/2106/problem/A

题目大意：

对输入字符串每个位置字符依次翻转（1->0 , 0->1)

比如: 101

        001 翻转位置1

        111                2

        100               3

题解：

观察数学特征：ans=n1*(n-1)+n0

t=int(input())for i in range(t):n=int(input())s=input()n1=s.count('1')n0=s.count('0')print(n1*(n-1)+n0)

B. St. Chroma 

https://codeforces.com/contest/2106/problem/B

题目大意：

需要构造长为n的数组a，包含0到n-1各一个

然后填涂一个新数组b：从左到右第 i 个位置等于MEX(a[ : i ]）

MEX:该序列中第一个未出现的非负整数

现在每个测试案例给n,x，要求b中x的最大可能数

题解：

贪心策略：前面尽快填补0到x-1，然后x得最后出

注意特判：n==x时，按照上面的贪心策略会导致多多余一个元素，正确做法是0到n-1按序填补

t=int(input())
for i in range(t):n,x=map(int,input().split())if n!=x:l1=[j for j in range(x)]l2=[j for j in range(x+1,n)]l3=l1+l2+[x]print(*l3)else:l=[j for j in range(n)]print(*l)

C. Cherry Bomb

https://codeforces.com/contest/2106/problem/C

题目大意：

每个案例输入n和k

再给a，b两个数组（n是他们的长度），其中a的元素已经固定，b中-1的位置表示可以随意变，范围是 [ 0 , k ] 左闭右开

要求a，b各个相对应的位置相加的和一致，输出有几种配合方式，如果没有可能就输出0

题解：

先过一遍统计一下b中不是-1的位置的和

如果不是一致的就可以直接输出0了，

如果一致也别开心太早：

由于a中元素x在添加[ 0 , k ]后区间为[ x , x + k ]，su要在这区间中

从极端情况考虑就是if mx<=mn+k and mx<=su[0]<=mn+k:（得利用and短路的特性，判断顺序不能换）

        可能a中最小值比和小或者最大值比和大：还是0

        否则的话就输出1，因为和已经固定了

如果没有一个和的话那就贪心：a中最大最小值限定了范围上下限，同时还被k限定

        观察后得到ans=k+mn-mx+1

t=int(input())for i in range(t):n,k=map(int,input().split())a=list(map(int,input().split()))b=list(map(int,input().split()))su=[]for j in range(n):if b[j]!=-1:su.append(a[j]+b[j])if su:if su[0]!=sum(su)/len(su):print(0)continueelse:mn=min(a)mx=max(a)if mx<=mn+k and mx<=su[0]<=mn+k:print(1)else:print(0)else:mx=max(a)mn=min(a)if mx>mn+k:print(0)else:print(k+mn-mx+1)

但是是错的

贪心个屁，还不如直接模拟 

t = int(input())for _ in range(t):n, k = map(int, input().split())a = list(map(int, input().split()))b = list(map(int, input().split()))target = Nonecnt_missing = 0for i in range(n):if b[i] != -1:curr_sum = a[i] + b[i]if target is None:target = curr_sumelif target != curr_sum:print(0)breakelse:cnt_missing += 1else:  # 没有break才会执行if target is None:  # b全是-1的情况max_a = max(a)min_a = min(a)if max_a > min_a + k:  # 差值太大，无解print(0)else:ans = min_a + k - max_a + 1print(max(0, ans))else:# 已知target，检查所有-1位置填入的值是否在范围内valid = Truefor i in range(n):if b[i] == -1:bi = target - a[i]if bi < 0 or bi > k:valid = Falsebreak'''mn=min(a)mx=max(a)if mn>target or mx'''print(1 if valid else 0)

D. Flower Boy

https://codeforces.com/contest/2106/problem/D

题目大意：

一个长度为n的数组a，一个长度为m的数组b，按左到右的顺序遍历a，选出m个数，选出的第i个不小于b[i]，现在有种只能进行一次的操作，可以在a中任意位置插入一个任意整数k，如果不插入就能选m个就输出0，如果插入后仍不能选m个就输出-1，否则求最小k

注意：题面说“从左到右”并不是连续，所以m朵花可以是跳跃的

题解：

首先构造check函数模拟选花的过程

判断原来数组不插入可以的话直接输出0

二分查找k值

枚举所有可插入位置

def solve():n, m = map(int, input().split())a = list(map(int, input().split()))b = list(map(int, input().split()))def check(arr, b):bi = 0for val in arr:if bi < len(b) and val >= b[bi]:bi += 1return bi == len(b)if check(a, b):print(0)returnleft = 1right = max(max(a), max(b))ans = -1while left <= right:mid = (left + right) // 2possible = Falsefor i in range(n + 1):temp_a = a[:]temp_a.insert(i, mid)if check(temp_a, b):possible = Truebreakif possible:ans = midright = mid - 1else:left = mid + 1print(ans)t = int(input())
for _ in range(t):solve()

做到D感觉就太累了，也许题面是中文、时间再早点还能a一下，我还是练太少了