# Codeforces Round 662 (CF1393) 题解
# Problem A - Rainbow Dash, Fluttershy and Chess Coloring (opens new window)
# 题目描述
两个人如图中所示轮流给棋盘染色,每次只能给当前与有颜色格子相邻的格子染色。问将棋盘染成两种颜色相间所需要的最少染色次数。
# 题解
简单尝试后可以总结出规律,答案为。
参考代码(C++)
#include <cstdio>
#include <iostream>
using namespace std;
template <typename T> void read(T &x) {
x = 0;
char c = getchar();
T sig = 1;
for (; !isdigit(c); c = getchar())
if (c == '-')
sig = -1;
for (; isdigit(c); c = getchar())
x = (x << 3) + (x << 1) + c - '0';
x *= sig;
}
class Solution {
public:
void solve() {
int n;
read(n);
printf("%d\n", n / 2 + 1);
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t;
read(t);
while (t--) {
Solution solution = Solution();
solution.solve();
}
}
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
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
# Problem B - Applejack and Storages (opens new window)
# 题目描述
有若干不同长度的木棍,每次查询会增加一根木棍,或减少一根木棍。要求在每次查询后,回答是否能用当前的木棍组成一个正方形和一个长方形。
# 题解
用一个set
维护当前每种木棍的数量。对于每次询问,假设当前数量最多的三种木棍依次为,考虑以下几种组合方式:
- 用个
- 用个,个
- 用个,个
- 用个,个,个
如果这些都不行,说明无法组成。
参考代码(C++)
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <set>
#include <vector>
using namespace std;
template <typename T> void read(T &x) {
x = 0;
char c = getchar();
T sig = 1;
for (; !isdigit(c); c = getchar())
if (c == '-')
sig = -1;
for (; isdigit(c); c = getchar())
x = (x << 3) + (x << 1) + c - '0';
x *= sig;
}
class Solution {
public:
void solve() {
int n, q;
read(n);
vector<int> a(n);
set<pair<int, int>, greater<>> s;
vector<int> cnt(100005);
for (int i = 0; i < n; ++i)
read(a[i]), cnt[a[i]]++;
for (int i = 1; i < 100005; ++i)
if (cnt[i])
s.insert({cnt[i], i});
read(q);
int tot = n;
for (int i = 0; i < q; ++i) {
char c;
int x;
cin >> c;
read(x);
s.erase({cnt[x], x});
if (c == '+')
cnt[x]++, tot++;
else
cnt[x]--, tot--;
if (cnt[x])
s.insert({cnt[x], x});
bool can = false;
if (tot >= 8) {
auto it = s.begin();
if (it->first >= 8)
can = true;
else if (it->first >= 6 && next(it) != s.end() && next(it)->first >= 2)
can = true;
else if (it->first >= 4 && next(it) != s.end() && next(it)->first >= 4)
can = true;
else if (it->first >= 4 && next(it) != s.end() &&
next(it)->first >= 2 && next(next(it)) != s.end() &&
next(next(it))->first >= 2)
can = true;
}
printf(can ? "YES\n" : "NO\n");
}
}
};
int main() {
Solution solution = Solution();
solution.solve();
}
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
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
# Problem C - Pinkie Pie Eats Patty-cakes (opens new window)
# 题目描述
有个数,要求找出一种排列方式,让相同数之间的间隔的最小值最大。求出这个最大的最小值。
# 题解
最优方案是把数量等于最大数量的种数按每种一个捆绑到一起,然后剩下的数在它们中间填空。此时的答案为,其中为最大数量。
参考代码(C++)
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;
template <typename T> void read(T &x) {
x = 0;
char c = getchar();
T sig = 1;
for (; !isdigit(c); c = getchar())
if (c == '-')
sig = -1;
for (; isdigit(c); c = getchar())
x = (x << 3) + (x << 1) + c - '0';
x *= sig;
}
class Solution {
public:
void solve() {
int n;
read(n);
vector<int> a(n), cnt(n + 1);
for (int i = 0; i < n; ++i)
read(a[i]), cnt[a[i]]++;
int hi = *max_element(cnt.begin(), cnt.end());
int k = 0;
for (int i : cnt)
k += i == hi;
int ans = (n - hi * k) / (hi - 1) + k - 1;
printf("%d\n", ans);
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t;
read(t);
while (t--) {
Solution solution = Solution();
solution.solve();
}
}
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
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
# Problem D - Rarity and New Dress (opens new window)
# 题目描述
求给定的方阵中,类似图中形状的图案的总数。要求图案内所有字母都相同。
# 题解
分左上、右上、左下、右下四个方向动态规划,最后每个位置处就取对应的四个数的最小值。
参考代码(C++)
#include <cstdio>
#include <iostream>
#include <vector>
#define MAXN 2005
using namespace std;
typedef long long ll;
template <typename T> void read(T &x) {
x = 0;
char c = getchar();
T sig = 1;
for (; !isdigit(c); c = getchar())
if (c == '-')
sig = -1;
for (; isdigit(c); c = getchar())
x = (x << 3) + (x << 1) + c - '0';
x *= sig;
}
int fa[MAXN][MAXN], fb[MAXN][MAXN], fc[MAXN][MAXN], fd[MAXN][MAXN];
class Solution {
public:
void solve() {
int n, m;
read(n), read(m);
vector<string> a(n);
for (int i = 0; i < n; ++i)
cin >> a[i];
ll ans = 0;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j) {
if (i == 1 || j == 1 || a[i - 1][j - 1] != a[i - 2][j - 1] ||
a[i - 1][j - 1] != a[i - 1][j - 2]) {
fa[i][j] = 1;
continue;
}
fa[i][j] = min(fa[i - 1][j], fa[i][j - 1]) + 1;
}
for (int i = 1; i <= n; ++i)
for (int j = m; j >= 1; --j) {
if (i == 1 || j == m || a[i - 1][j - 1] != a[i - 2][j - 1] ||
a[i - 1][j - 1] != a[i - 1][j]) {
fb[i][j] = 1;
continue;
}
fb[i][j] = min(fb[i - 1][j], fb[i][j + 1]) + 1;
}
for (int i = n; i >= 1; --i)
for (int j = 1; j <= m; ++j) {
if (i == n || j == 1 || a[i - 1][j - 1] != a[i][j - 1] ||
a[i - 1][j - 1] != a[i - 1][j - 2]) {
fc[i][j] = 1;
continue;
}
fc[i][j] = min(fc[i + 1][j], fc[i][j - 1]) + 1;
}
for (int i = n; i >= 1; --i)
for (int j = m; j >= 1; --j) {
if (i == n || j == m || a[i - 1][j - 1] != a[i][j - 1] ||
a[i - 1][j - 1] != a[i - 1][j]) {
fd[i][j] = 1;
continue;
}
fd[i][j] = min(fd[i + 1][j], fd[i][j + 1]) + 1;
}
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
ans += min(min(fa[i][j], fb[i][j]), min(fc[i][j], fd[i][j]));
printf("%lld", ans);
}
};
int main() {
Solution solution = Solution();
solution.solve();
}
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
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
# Problem E1 - Twilight and Ancient Scroll (easier version) (opens new window)
待补做。
# Problem E2 - Twilight and Ancient Scroll (harder version) (opens new window)
待补做。