Codeforces Round 345(Div. 2)

Codeforces Round #345 (Div. 2) A、B、C、D、E 解题报告

一时兴起,准备在暑假前做满39场 CF Div.2,并写题解发布在Blog上。

这是第一场!题目在此。

A. Joysticks

题目大意

现有两个游戏手柄,初始电量(百分数)分别为 $a_1$,$a_2$。每一分钟你可以选择为其中一个手柄充电 1%(电量可超过100%),同时另一个手柄将会耗电 2%。当有任意一只手柄的电量降低到0,游戏结束。问游戏最长时间。
$(1 \leq a_1, a_2 \leq 100)$ 时限 $1s$。

解题思路

贪心。每次选择电量较低的手柄进行充电,由于数据较小可直接模拟。
Ps:官方题解说还可以直接 $O(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
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAXN = 1e5 + 10;

int main()
{

int n, m;
while( ~scanf("%d %d", &n, &m) ) {
int cnt = 0;
while( n > 0 && m > 0 ) {
if( n > m ) swap(n, m);
n ++;
m -= 2;
cnt++;
}
if( n < 0 || m < 0 ) cnt--;
printf("%d\n", cnt);
}
return 0;
}


B. Beautiful Paintings

题目大意

给定一组数列 $a_1, a_2, …, a_n$,要求通过调整位置使得 $a_i < a_{i+1}$ $(1 \leq i \leq n - 1)$ 对数最多。输出最大对数。
$(1 \leq n \leq 1000, 1 \leq a_i \leq 1000)$ 时限 $1s$。

解题思路

贪心:排序+二分。将数列按从小到大进行排序,然后对于每一个 $a_i$,二分找第一个比它大的数,若找到答案+1,并将找到的数删除(之后依然要进行遍历)。这样的复杂度是 $O(nlogn)$ 的。

$O(n)$的做法是,统计相同权值出现的最大次数,答案就是 $n-most$。算法原理是对于其他权值都可以与出现次数最多的权值组成一对,然后最大对数就是 $n-most$ 啦。

解题代码

$O(nlogn)$:

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
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAXN = 1e5 + 10;

int a[MAXN];
multiset<int> ms;

int main()
{

int n;
while( ~scanf("%d", &n) ) {
ms.clear();
for( int i = 0; i < n; ++ i ) {
scanf("%d", a + i);
ms.insert(a[i]);
}
sort(a, a + n);
int cnt = 0;
multiset<int>::iterator itk;
for( int i = 0; i < n; ++ i ) {
itk = ms.upper_bound(a[i]);
if( itk == ms.end() ) break;
ms.erase(itk);
cnt++;
}
printf("%d\n", cnt);
}
return 0;
}

$O(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
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAXN = 1e5 + 10;

int a[MAXN];

int main()
{

int n;
while( ~scanf("%d", &n) ) {
int most = 0, x;
for( int i = 0; i < n; ++ i ) {
scanf("%d", &x);
a[x]++;
most = max(most, a[x]);
}
printf("%d\n", n - most);
}
return 0;
}


C. Watchmen

题目大意

在二维平面上,给定 $n$ 个点,问有多少对点对满足点对之间的曼哈顿距离等于欧几里得距离。
$(1 \leq n \leq 2*10^5, |x_i|,|y_i| \leq 10^9)$ 时限 $3s$。

解题思路

显然满足条件的点对要么 $x$ 坐标相同,要么 $y$ 坐标相同。由此可以统计相同 $x$ 坐标的点数和相同 $y$ 坐标的点数以及重合点的点数。然后直接排列组合+容斥搞搞就可以了。
统计:If we use TreeMap/sort then solution will run in $O(nlogn)$ and if unordered_map/HashMap then in $O(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
33
34
35
36
37
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> P;

const int MAXN = 1e5 + 10;

int n;
map<int, int> mp_x, mp_y;
map<P, int> mp_xy;

int main()
{

while( ~scanf("%d", &n) ) {
int x, y;
for( int i = 0; i < n; ++ i ) {
scanf("%d %d", &x, &y);
mp_x[x]++;
mp_y[y]++;
mp_xy[P(x, y)]++;
}
ll ans = 0;
for( auto i : mp_x ) {
ans += (ll)i.second * (i.second - 1) / 2;
}
for( auto i : mp_y ) {
ans += (ll)i.second * (i.second - 1) / 2;
}
for( auto i : mp_xy ) {
ans -= (ll)i.second * (i.second - 1) / 2;
}
printf("%I64d\n", ans);
}
return 0;
}


D. Image Preview

题目大意

你在翻阅手机照片,初始在照片 1 的为位置,共 $n$ 张照片,首尾相连。向左向右切换照片需要消耗 $a$ 秒,如果没看过某张照片,消耗 1 秒观看(不能直接跳过没看过的照片),如果照片旋转方向(横或竖)不对,观看前消耗 $b$ 秒旋转。问 $T$ 秒时间内最多能看多少张照片。
$(1 \leq n \leq 5 * 10^5, 1 \leq a,b \leq 1000, 1 \leq T \leq 10^9)$ 时限 $1s$。

解题思路

显然最优解只有4种情况:

  1. 一直向右
  2. 一直向左
  3. 先向右再向左
  4. 先向左再向右
    由此我们使用两个指针,一开始左指针在初始位置,右指针一直向右扫,当右指针扫到极限时,将左指针一步一步往左移,相当于用类似尺取的方法进行求解。这种算法的复杂度是 $O(n)$ 的,不过细节问题很容易出错。

更简单的方法是枚举左端点 + 二分右端点,比较容易写(看起来?),不过复杂度是 $O(nlogn)$。

解题代码(多揣摩)

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
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAXN = 5e5 + 10;

char s[MAXN];

int main()
{
int n, A, B, T;
while( ~scanf("%d %d %d %d %s", &n, &A, &B, &T, s) ) {
int ans = 0, l = n;
while( l && T > 0 ) {
--l;
T -= A + 1;
if( s[l] == 'w' ) T -= B;
}
T += A + 1;
if( s[l] == 'w' ) T += B;
++l;
for( int i = 0; i < n; ++ i ) {
if( i ) T -= A + 1;
else --T;
if( s[i] == 'w' ) T -= B;
while( l <= i || l < n && T - A * min(i, n - l) < 0 ) {
T += A + 1;
if( s[l] == 'w' ) T += B;
l++;
}
if( T - A * min(i, n - l) >= 0 ) ans = max(ans, n - l + i + 1);
}
printf("%d\n", ans);
}
return 0;
}


E.Table Compression

题目大意

给定一个 $n * m$ 的表格,要求找到同样大小的表格,并满足:

  1. 每行每列中:各格子上的数字大小关系和原表格中的一样。
  2. 特别地,每行每列数字相同的格子,在新表格中也必相同。
  3. 表格上的最大的数字尽量小。

$(1 \leq n, m$ $and$ $n * m \leq 10^6, 1 \leq a_{i,j} \leq 10^9)$ 时限 $4s$。

解题思路

并查集+拓扑排序。将每行每列上的数字分别排序,然后相邻位置(防止不必要的连边)按从小到大进行连边。这样就可以造出一个DAG,直接跑拓扑排序就可以了——每次取出入度为0的点,更新其到出边上点的距离的最大值。或者也可以每次都一次性取出所有入度为0的点,然后进行赋值,不过这样比较麻烦,而且更耗时间。

然后对于题目的第二个条件,一开始我的做法是按上面排完序后,对于每个值二分找到行和列中第一个与其相等的值,然后合并成一个点,再继续二分寻找…然后就是一直 $Wrong$ $answer$ $on$ $test$ $46$…(虽然知道这样写很挫但不明白为什么会错)

后来改成并查集才AC的。也就是排完序后将每行每列相同权值的直接进行合并。注意要先跑完并查集才可以开始连边,原因也是显而易见的。

解题代码

AC代码

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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> P;

const int MAXN = 1e6 + 10;

int n, m;
int in[MAXN], pa[MAXN], dp[MAXN];
map<int, int> mp;
set<P> sx[MAXN], sy[MAXN];
set<P> st;
vector<int> G[MAXN];

int findPa(int x)
{

return pa[x] == x ? x : pa[x] = findPa(pa[x]);
}
void uniteSet(int u, int v)
{

u = findPa(u), v = findPa(v);
if( u != v ) pa[v] = u;
}
void addEdge(int u, int v)
{

G[u].push_back(v);
in[v]++;
}
void Mapping(bool isU, set<P> st)
{

set<P>::iterator ite, itk;
for( ite = st.begin(); ite != st.end(); ++ ite ) {
itk = ite++;
if( ite == st.end() ) break;
if( isU && (*itk).first == (*ite).first ) uniteSet((*itk).second, (*ite).second);
else if( !isU && (*itk).first != (*ite).first ) addEdge(findPa((*itk).second), findPa((*ite).second));
ite = itk;
}
}
void topoSort()
{

queue<int> que;
int sum = (n - 1) * m + m;
fill(dp, dp + sum, 1);
for( int i = 0; i < sum; ++ i ) {
if( !in[i] ) que.push(i);
}
while( !que.empty() ) {
int u = que.front(); que.pop();
for( int i = 0; i < G[u].size(); ++ i ) {
int v = G[u][i];
if( !(--in[v]) ) que.push(v);
dp[v] = max(dp[v], dp[u] + 1);
}
}
}
int main()
{

while( ~scanf("%d %d", &n, &m) ) {
int x, sum = (n - 1) * m + m;
for( int i = 0; i < sum; ++ i ) pa[i] = i;
for( int i = 0; i < n; ++ i ) {
for( int j = 0; j < m; ++ j ) {
scanf("%d", &x);
mp[i * m + j] = x;
sx[i].insert(P(x, i * m + j));
}
Mapping(1, sx[i]);
}
for( int j = 0; j < m; ++ j ) {
for( int i = 0; i < n; ++ i ) {
int u = i * m + j;
sy[j].insert(P(mp[u], u));
}
Mapping(1, sy[j]);
}
for( int i = 0; i < n; ++ i ) {
Mapping(0, sx[i]);
}
for( int j = 0; j < m; ++ j ) {
Mapping(0, sy[j]);
}
topoSort();
for( int i = 0; i < n; ++ i ) {
for( int j = 0; j < m; ++ j ) {
printf("%d%c", dp[findPa(i * m + j)], " \n"[j == m - 1]);
}
}
}
return 0;
}

错误代码(求帮找错QAQ)

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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
// Wrong answer on test 46
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> P;

const int MAXN = 1e6 + 10;

int n, m, num;
int in[MAXN], va[MAXN];
vector<int> G[MAXN];
map<P, int> mp;
map<P, int> mpv;
//set<P> st;
set<P> sx[MAXN];
set<P> sy[MAXN];

void topoSort()
{

queue<int> que;
fill(va + 1, va + num, 1);
for( int i = 1; i < num; ++ i ) {
if( !in[i] ) que.push(i);
}
while( !que.empty() ) {
int u = que.front(); que.pop();
for( int j = 0; j < G[u].size(); ++ j ) {
int v = G[u][j];
--in[v];
if( !in[v] ) que.push(v);
va[v] = max(va[v], va[u] + 1);
}
}
}
void add_edge(int u, int v)
{

G[u].push_back(v);
in[v]++;
}

queue<P> pque;
// Wrong answer on test 46
void bfs(int x, int y, int fx)
{

pque.push(P(x, y));
mpv[P(x, y)] = num;
while( !pque.empty() ) {
P p = pque.front(); pque.pop();
int u = p.first, v = p.second;
set<P>::iterator ite;
ite = sx[u].upper_bound(P(fx, v));
if( ite != sx[u].end() && (*ite).first == fx && !mpv[P(u, (*ite).second)] ) {
mpv[P(u, (*ite).second)] = num;
pque.push(P(u, (*ite).second));
}
ite = sy[v].upper_bound(P(fx, u));
if( ite != sy[v].end() && (*ite).first == fx && !mpv[P((*ite).second, v)] ) {
mpv[P((*ite).second, v)] = num;
pque.push(P((*ite).second, v));
}
}
num++;
}
int main()
{

while( ~scanf("%d %d", &n, &m) ) {
num = 1;
int x;
for( int i = 0; i < n; ++ i ) {
for( int j = 0; j < m; ++ j ) {
scanf("%d", &x);
mp[P(i, j)] = x;
sx[i].insert(P(x, j));
}
}
for( int j = 0; j < m; ++ j ) {
for( int i = 0; i < n; ++ i ) {
sy[j].insert(P(mp[P(i, j)], i));
}
}
for( int i = 0; i < n; ++ i ) {
for( int j = 0; j < m; ++ j ) {
if( !mpv[P(i, j)] ) {
bfs(i, j, mp[P(i, j)]);
}
}
}
for( int i = 0; i < n; ++ i ) {
set<P>::iterator ite, itk;
for( ite = sx[i].begin(); ite != sx[i].end(); ++ ite ) {
itk = ite++;
if( ite == sx[i].end() ) break;
int u = (*itk).second, v = (*ite).second;
int l = mpv[P(i, u)], r = mpv[P(i, v)];
if( l != r ) add_edge(l, r);
ite = itk;
}
}
for( int i = 0; i < n; ++ i ) sx[i].clear();

for( int j = 0; j < m; ++ j ) {
set<P>::iterator ite, itk;
for( ite = sy[j].begin(); ite != sy[j].end(); ++ ite ) {
itk = ite++;
if( ite == sy[j].end() ) break;
int u = (*itk).second, v = (*ite).second;
int l = mpv[P(u, j)], r = mpv[P(v, j)];
if( l != r ) add_edge(l, r);
ite = itk;
}

}
for( int j = 0; j < m; ++ j ) sy[j].clear();

topoSort();
for( int i = 0; i < n; ++ i ) {
for( int j = 0; j < m; ++ j ) {
printf("%d%c", va[mpv[P(i, j)]], " \n"[j == m - 1]);
}
}
}

return 0;
}


附上一份官方题解

如果您觉得这篇博文对您有所帮助,可以考虑请我吃颗糖哦!