Codeforces Round #600 (Div. 2)

A - Single Push

如果两个序列相等,那么直接输出YES。然后用第二个序列减第一个序列,记新得到的序列为c。如果c中出现负数,那么直接输出NO。否则判断一下c中是否只存在一个连续的区间有相同的数字,其余部分为0.

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <iostream>
using namespace std;
int a[100005], b[100005], c[100005], n;
int main()
{
int t;
cin >> t;
while (t--)
{
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
for (int i = 1; i <= n; i++)
cin >> b[i];

bool allequal = true;
for (int i = 1; i <= n; i++)
allequal &= a[i] == b[i];
if (allequal)
{
cout << "YES" << endl;
continue;
}

bool allpositive = true;
for (int i = 1; i <= n; i++)
{
c[i] = b[i] - a[i];
allpositive &= c[i] >= 0;
}
if (!allpositive)
{
cout << "NO" << endl;
continue;
}

bool ok = true;
int l = 1;
while (c[l] == 0 && l <= n)
l++;

int r = l + 1;
while (c[r] == c[l] && r <= n)
r++;

for (int i = r; i <= n; i++)
ok &= c[i] == 0;
cout << (ok ? "YES" : "NO") << endl;
}
return 0;
}

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <iostream>
#include <vector>
#include <unordered_set>
#include <unordered_map>
#include <cstring>
using namespace std;
constexpr int MAXN = 100000;
int n, a[MAXN + 5];
int main()
{
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];

bool ok = true;
int cnt = 0;
unordered_set<int> member;
unordered_map<int, bool> in;
vector<int> ans;
for (int i = 1; i <= n; i++)
{
if (a[i] > 0)
{
if (member.find(a[i]) == member.end() && !in[a[i]])
member.insert(a[i]);
else
{
ok = false;
break;
}
}
else
{
a[i] = -a[i];
if (member.find(a[i]) != member.end())
{
member.erase(a[i]);
in[a[i]] = true;
}
else
{
ok = false;
break;
}
}
cnt++;

if (member.empty())
{
ans.push_back(cnt);
cnt = 0;
in.clear();
}
}
if (!member.empty())
ok = false;

if (ok)
{
cout << ans.size() << endl;
for (int a : ans)
cout << a << ' ';
}
else
cout << -1 << endl;
return 0;
}

C - Sweets Eating

首先根据排序不等式显然是先吃糖分高的。问题就来到怎么通过递推来找到所有的答案。

升序排序后,记$fi$为只吃前i颗的答案。观察到从$f_i$转移$f{i+1}$时只需要加上$(i-1) \mod m + 1$开头,步长为$m$的子序列和。那么就按每m个为一组计算答案即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
int n, m;
ll a[200005], ans[200005], p[200005];
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i++)
cin >> a[i];
sort(a + 1, a + 1 + n);
for (int i = 1; i <= n; i += m)
{
for (int j = 0; j < m && i + j <= n; j++)
{
p[j] += a[i + j];
ans[i + j] = ans[i + j - 1] + p[j];
}
}
for (int i = 1; i <= n; i++)
cout << ans[i] << ' ';
return 0;
}

D - Harmonious Graph

用并查集维护连通块。对所有连通块记录最大与最小的编号,然后对所有的连通块逐一处理:记最大值为$maxi$,最小值为$mini$,则将编号在$(mini,maxi)$开区间内的所有点扔到队列里等待检查。之后将队列的点逐一拿出来检查,如果该点不在该连通块内,则将该点所在的连通块挂在正在处理的连通块下,并将答案+1。注意到合并两连通块后,最大最小值可能会改变。此时再把新的最大最小值与旧的最大最小值之间的点扔到队列里等待检查。

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <iostream>
#include <cstring>
#include <unordered_set>
#include <queue>
using namespace std;
int n, m;
int fa[200005], mini[200005], maxi[200005];
bool inque[200005];
int findfa(int a)
{
if (fa[a] == a)
return a;
else
return fa[a] = findfa(fa[a]);
}
void join(int b, int a)
{
a = findfa(a);
b = findfa(b);
fa[a] = b;
mini[b] = min(mini[b], mini[a]);
maxi[b] = max(maxi[b], maxi[a]);
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i++)
fa[i] = i, maxi[i] = mini[i] = i;
for (int i = 1; i <= m; i++)
{
int a, b;
cin >> a >> b;
join(a, b);
}

int ans = 0;
for (int r = 1; r <= n; r++)
{
if (fa[r] != r)
continue;
queue<int> wait;
for (int i = mini[r] + 1; i <= maxi[r] - 1; i++)
{
wait.push(i);
inque[i] = true;
}
while (!wait.empty())
{
int v = wait.front();
wait.pop();

if (findfa(v) != r)
{
int oldmaxi = maxi[r], oldmini = mini[r];
join(r, v);
ans++;
for (int i = oldmaxi; i <= maxi[r] - 1; i++)
{
if (!inque[i])
{
wait.push(i);
inque[i] = true;
}
}
for (int i = oldmini; i >= mini[r] + 1; i--)
{
if (!inque[i])
{
wait.push(i);
inque[i] = true;
}
}
}
}
}
cout << ans << endl;
return 0;
}
Author: ssttkkl
Link: https://ssttkkl.github.io/Codeforces/2019/11/Codeforces-Round-600-Div-2/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.