Codeforces Round #662 (Div. 2)
/ / 阅读耗时 18 分钟 Codeforces Round #662 (Div. 2)。
A. Rainbow Dash, Fluttershy and Chess Coloring
答案就是$\lfloor\frac {n}{2}\rfloor+1$。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
using namespace std;
const int N = 10000 + 5;
typedef long long ll;
int main()
{
int T;
scanf("%d", &T);
while (T--) {
int n;
scanf("%d", &n);
printf("%d\n", n / 2 + 1);
}
return 0;
}
B. Applejack and Storages
容易想出一个用堆维护的做法。通过用堆来维护每一个种类的数量（从大到小），然后判断其符不符合。需要在堆上更新。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
using namespace std;
const int N = 200000 + 5;
typedef long long ll;
int heap[N], num[N], id[N], sz, n, m;
void down(int x)
{
int x1 = x << 1, x2 = x << 1 | 1, maxn = x;
if (x1 <= sz && num[heap[x1]] > num[heap[maxn]]) maxn = x1;
if (x2 <= sz && num[heap[x2]] > num[heap[maxn]]) maxn = x2;
if (maxn != x) swap(heap[maxn], heap[x]), swap(id[heap[x]], id[heap[maxn]]), down(maxn);
}
void up(int x)
{
if (x == 1) return;
if (num[heap[x]] > num[heap[x >> 1]]) {
swap(heap[x], heap[x >> 1]);
swap(id[heap[x]], id[heap[x >> 1]]);
up(x >> 1);
}
}
void insert(int x)
{
heap[++sz] = x, id[x] = sz, up(sz);
}
int top()
{
if (sz == 0) return -1;
int x = heap[1];
id[x] = 0;
if (sz > 1) {
heap[1] = heap[sz--], id[heap[1]] = 1, down(1);
} else {
--sz;
}
return x;
}
int check()
{
int s1 = top(), s2 = top(), s3 = top();
// cout << s1 << " " << s2 << " " << s3 << endl;
if (s1 != -1) insert(s1);
if (s2 != -1) insert(s2);
if (s3 != -1) insert(s3);
if (s1 != -1 && num[s1] >= 8) return 1;
if (s1 != -1 && num[s1] >= 6 && s2 != -1 && num[s2] >= 2) return 1;
if (s1 != -1 && num[s1] >= 4 && s2 != -1 && num[s2] >= 4) return 1;
if (s1 != -1 && num[s1] >= 4 && s2 != -1 && num[s2] >= 2 && s3 != -1 && num[s3] >= 2) return 1;
return 0;
}
int main()
{
scanf("%d", &n);
for (int i = 1, x; i <= n; i++) {
scanf("%d", &x), ++num[x];
if (id[x] == 0) {
insert(x);
} else {
up(id[x]);
}
}
// cout << sz << endl;
scanf("%d", &m);
while (m--) {
char opt;
int x;
scanf(" %c%d", &opt, &x);
if (opt == '+') {
++num[x];
if (id[x] == 0) {
insert(x);
} else {
up(id[x]);
}
} else if (opt == '-') {
--num[x];
down(id[x]);
}
if (check()) {
printf("YES\n");
} else {
printf("NO\n");
}
}
return 0;
}
C. Pinkie Pie Eats Patty-cakes
这题最好想的方法是二分答案加贪心。二分一个答案，然后贪心地判断其正确性。假设答案是$x$，每一次都放在前$x$位没有出现过，并且剩余数量最多的那一个种类，用$set$维护，复杂度$O(nlog^2n)$。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
using namespace std;
const int N = 200000 + 5;
typedef long long ll;
int num[N], n, vis[N], op[N];
inline int check(int x)
{
set<pair<int, int>, greater<pair<int, int>>> ssp;
for (int i = 1; i <= n; i++) num[i] = 0;
for (int i = 1; i <= n; i++) ++num[op[i]];
for (int i = 1; i <= n; i++) {
if (num[i]) ssp.insert({num[i], i});
}
for (int i = 1; i <= n; i++) {
if (i >= x + 1 && num[vis[i - x]]) ssp.insert({num[vis[i - x]], vis[i - x]});
if (ssp.empty()) return 0;
vis[i] = ssp.begin()->second;
ssp.erase(ssp.begin());
--num[vis[i]];
}
return 1;
}
int main()
{
int T;
scanf("%d", &T);
while (T--) {
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", op + i);
int l = 1, r = n, mid;
while (l < r) {
if (r == l + 1) {
printf("%d\n", l - 1);
break;
}
mid = (l + r) >> 1;
if (check(mid)) {
l = mid;
} else {
r = mid;
}
}
}
return 0;
}
另外本题有$O(n)$做法，设出现次数最多的数出现的次数为$a$，出现次数最多的数种类有$b$个，则答案为$\lfloor\frac {n-ab}{a-1}\rfloor+b-1$。其中$n-ab$是出现次数没这么多的数的数量，可以作为隔板，然后隔开$a-1$个空位，剩下的$b-1$也作为空位，这样就能得到答案。有了这个结论，我们可以用数据结构维护动态变化的序列的答案。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
using namespace std;
const int N = 100000 + 5;
typedef long long ll;
int num[N], op[N], n;
int main()
{
int T;
scanf("%d", &T);
while (T--) {
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", op + i), num[i] = 0;
for (int i = 1; i <= n; i++) ++num[op[i]];
int maxn = *max_element(num + 1, num + n + 1), ss = 0;
for (int i = 1; i <= n; i++) ss += num[i] == maxn;
if (maxn == 1) {
printf("0\n");
} else {
printf("%d\n", (n - ss * maxn) / (maxn - 1) + ss - 1);
}
}
return 0;
}
D. Rarity and New Dress
一个$DP$，注意到阶梯状的最大大小是可以递推出来的，这样只需要完成四次$dp$即可。复杂度$O(nm)$。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
using namespace std;
const int N = 10000 + 5;
typedef long long ll;
int dp1[2005][2005], dp2[2005][2005], dp3[2005][2005], dp4[2005][2005];
int n, m;
char op[2005][2005];
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) scanf("%s", op[i] + 1);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (op[i - 1][j] != op[i][j] || op[i][j - 1] != op[i][j]) {
dp1[i][j] = 1;
} else {
dp1[i][j] = min(dp1[i - 1][j], dp1[i][j - 1]) + 1;
}
}
}
for (int i = 1; i <= n; i++) {
for (int j = m; j >= 1; j--) {
if (op[i - 1][j] != op[i][j] || op[i][j + 1] != op[i][j]) {
dp2[i][j] = 1;
} else {
dp2[i][j] = min(dp2[i - 1][j], dp2[i][j + 1]) + 1;
}
}
}
for (int i = n; i >= 1; i--) {
for (int j = m; j >= 1; j--) {
if (op[i + 1][j] != op[i][j] || op[i][j + 1] != op[i][j]) {
dp3[i][j] = 1;
} else {
dp3[i][j] = min(dp3[i + 1][j], dp3[i][j + 1]) + 1;
}
}
}
for (int i = n; i >= 1; i--) {
for (int j = 1; j <= m; j++) {
if (op[i + 1][j] != op[i][j] || op[i][j - 1] != op[i][j]) {
dp4[i][j] = 1;
} else {
dp4[i][j] = min(dp4[i + 1][j], dp4[i][j - 1]) + 1;
}
}
}
long long ans = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
ans += min(min(dp1[i][j], dp2[i][j]), min(dp3[i][j], dp4[i][j]));
}
}
printf("%lld", ans);
return 0;
}
E. Twilight and Ancient Scroll
好题，强烈建议一做。
首先可以想到一个$dp$，规定$dp(i,j)$表示前$i$个串，删去了$i$串的第$j$位，前$i$个串不减的方案数。这里很快就会遇到一个问题：如果串$i$不删如何操作？此时我们只需要在所有串的末尾加上字符$\sharp$，该字符总是小于英文字符，不删的时候删去它即可。注意加$\sharp$这种方法是有漏洞的，下文再提。
考虑一下时间复杂度。设所有串的总长度为$L$，那么状态数有$L$个，枚举前驱状态是$L$个，比较大小$L$，时间复杂度$O(L^3)$。
考虑对每个串，删去其第$j$个字符，可以得到若干个新串，对这些串排序，我们就可以根据单调性使用双指针省去枚举前驱状态的复杂度，这样$dp$的复杂度降至$O(L^2)$，排序带来的额外复杂度是$O(L^2logL)$。
现在的主要优化方向便是降低比较字符串大小的复杂度。容易想到哈希配合二分，这样可以将字符串比较大小的复杂度降至$O(logn)$，从而此时$dp$复杂度$O(LlogL)$，排序复杂度$O(Llog^2L)$。
其实排序是可以做到$O(L)$复杂度的。我们预处理$nxt$数组，$nxt[i]$表示$i$右侧与其不同的第一个位置，这可以$O(L)$预处理出来。
假设当前处理的字符串区间是$[a,b]$，排名区间是$[l,r]$。
若$S_a>S_{nxt[a]}$（这里$S_i$是取第$i$个字符）。可知删去$a$这一位会导致$S_{nxt[a]}$提前，而它较小，其它串都不会提前，于是删去$a$的这一个串是字典序最小的，它的排名是$l$。
若$S_a<S_{nxt[a]}$，则同理可得它的字典序是$r$，这样就可以递推到$[a+1,b],[l+1,r]$或者$[a+1,b],[l,r-1]$的情况。
于是我们有了$O(L)$排序的方法。此时排序复杂度$O(L)$，$DP$复杂度$O(LlogL)$。
回到我们之前说的漏洞。当两个串有前缀关系时，$\sharp$可能会影响两者的大小比较。比如$aa\sharp$和$aa$，两者本质上是相等的，但是如果根据朴素的比较大小的方法，会认为前者字典序更大。这种情况只需要在比较时处理一下即可，但是要知道有这样的情况发生。不注意会导致$easy$版$WA$第14个测试点。
1 |
|