# # Codeforces Round 662 (CF1393) 题解

## # Problem A - Rainbow Dash, Fluttershy and Chess Coloring (opens new window)

### # 题解

#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;
printf("%d\n", n / 2 + 1);
}
};

int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int 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

## # Problem B - Applejack and Storages (opens new window)

### # 题解

• $8$$A$
• $6$$A$$2$$B$
• $4$$A$$4$$B$
• $4$$A$$2$$B$$2$$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;
vector<int> a(n);
set<pair<int, int>, greater<>> s;
vector<int> cnt(100005);
for (int i = 0; i < n; ++i)
for (int i = 1; i < 100005; ++i)
if (cnt[i])
s.insert({cnt[i], i});
int tot = n;
for (int i = 0; i < q; ++i) {
char c;
int x;
cin >> c;
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

## # Problem C - Pinkie Pie Eats Patty-cakes (opens new window)

### # 题目描述

$n$个数，要求找出一种排列方式，让相同数之间的间隔的最小值最大。求出这个最大的最小值。

### # 题解

#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;
vector<int> a(n), cnt(n + 1);
for (int i = 0; i < n; ++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;
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

## # Problem D - Rarity and New Dress (opens new window)

### # 题解

#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;
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