codeforces_Round#600(Div2)

CF round 600

A. Single Push

题意:
给两个等长数组a,b,问能否给a中一个子串中的所有元素都加一个非负数,使得a和b相同

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
for _ in range(int(input())):
n = int(input())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
d = 0
pre = 0
for i in range(n):
if(a[i] == b[i]):
continue
else:
d = a[i] - b[i]
if d > 0:
break;
while(i < n and a[i] == b[i] + d):
b[i] = a[i]
i += 1
break
if a == b:
print("YES")
else:
print("NO")

B - Silly Mistake

题意:
set模拟

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
n = int(input())
L = list(map(int,input().split()))
ans = [-1]
s = set()
vis = set()
ok = True
for i in range(n):
c = L[i]
if c > 0:
if c in vis:
ok = False
break
vis.add(c)
if c in s:
ok = False
break
else:
s.add(c)
else:
if -c not in s:
ok = False
break
else:
s.remove(-c)
if len(s) == 0:
ans.append(i)
vis.clear()
if len(s) != 0:
ok = False
if not ok:
print(-1)
else:
print(len(ans)-1)
for i in range(1,len(ans)):
if i != 1:
print(" ",end = "")
print(" " + str(ans[i] - ans[i-1]),end = "")

C - Sweets Eating

有n颗糖果,甜度为$a_i$,一天能吃m个,第k天吃的糖果收获的甜度值是
$a_i*k$,输出n个数$S_k,k\in[1,n]$,$S_k$表示吃$k$个糖获得的最少甜度
==思路==:
看了别人的代码,太巧妙了也

1
2
3
4
5
6
7
8
9
n,m = map(int,input().split())
L = list(map(int,input().split()))
L.sort()
g = [0]*m
now = 0
for i in range(n):
g[i%m] += L[i]
now += g[i%m]
print(now,end=" ")

D - Harmonious Graph

题意:
给一个无向图,问需要添加多少条边,使得满足如下性质
若$s$到$n$可达,$s<n$,则$s$到$k$也可达$s<k<n$

==思路==:
见代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<bits/stdc++.h>
using namespace std;
vector<int>G[200020];
int n,m,ans,mx;
int vis[200020];
void dfs(int v){
mx = max(mx,v);
vis[v] = 1;
for(int i = 0;i < G[v].size();i++){
if(!vis[G[v][i]]){
dfs(G[v][i]);
}
}
}
int main(){
cin >> n >> m;
int a,b;
for(int i = 0;i < m;i++){
cin >> a >> b;
G[a].push_back(b);
G[b].push_back(a);
}
for(int i = 1;i <= n;i++){
if(!vis[i]){
if(i < mx){
ans++;
}
dfs(i);
}
}
cout << ans;
}