Codeforces Round #662 (Div. 2)

        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
#include <bits/stdc++.h>
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
#include <bits/stdc++.h>
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
#include <bits/stdc++.h>
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
#include <bits/stdc++.h>
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
#include <bits/stdc++.h>
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
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
#include <bits/stdc++.h>
using namespace std;
const int N = 100000 + 5, P = 131, mod = 1e9 + 7;
typedef unsigned long long ull;
vector<int> vec, rk[N], dp[N];
vector<ull> hs[N];
int n, len[N], nxt[N * 10];
char s[N * 10];
ull bin[N * 10];
inline ull getHash(int x, int at, int l)
{
if (at > l) return hs[x][l];
ull s = at == 0 ? 0 : hs[x][at - 1];
return s * bin[l + 1 - at] + hs[x][l + 1] - hs[x][at] * bin[l + 1 - at];
}
inline int getChar(int x, int at, int l)
{
if (at > l) return l == 0 ? hs[x][0] : hs[x][l] - hs[x][l - 1] * P;
return hs[x][l + 1] - hs[x][l] * P;
}
inline int cmp(int x1, int a1, int x2, int a2)
{
int l = -1, r = min(len[x1], len[x2]) - 2, mid;
while (l < r) {
if (r == l + 1) break;
mid = (l + r) >> 1;
if (getHash(x1, a1, mid) == getHash(x2, a2, mid)) {
l = mid;
} else {
r = mid;
}
}
//cout<<r<<endl;
if (getChar(x1, a1, r) < getChar(x2, a2, r)) return 1;
if (getChar(x1, a1, r) > getChar(x2, a2, r)) return 0;
int l1 = a1 == len[x1] - 1 ? len[x1] - 1 : len[x1] - 2;
int l2 = a2 == len[x2] - 1 ? len[x2] - 1 : len[x2] - 2;
return l1 <= l2;
}
void DP(int x)
{
if (x == 1) {
for (int i = 0; i < len[1]; i++) dp[1].push_back(1);
return;
}
DP(x - 1);
int sum = 0, p = -1;
for (int i = 0; i < len[x]; i++) {
while (p + 1 < len[x - 1] && cmp(x - 1, rk[x - 1][p + 1], x, rk[x][i])) {
++p, sum = (sum + dp[x - 1][p]) % mod;
}
dp[x].push_back(sum);
}
}
int main()
{
bin[0] = 1;
for (int i = 1; i <= 1000000; i++) bin[i] = bin[i - 1] * P;
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%s", s), len[i] = strlen(s), s[len[i]] = '#', ++len[i];
int l = 0, r;
while (l < len[i]) {
r = l;
while (r + 1 < len[i] && s[r + 1] == s[l]) ++r;
for (int i = l; i <= r; i++) nxt[i] = r + 1;
l = r + 1;
}
for (int j = 0; j < len[i]; j++) rk[i].push_back(0);
l = 0, r = len[i] - 1;
for (int j = 0; j < len[i]; j++) {
if (l == r) {
rk[i][l] = j;
} else if (s[j] < s[nxt[j]]) {
rk[i][r] = j, --r;
} else {
rk[i][l] = j, ++l;
}
}
for (int j = 0; j < len[i]; j++) hs[i].push_back(0);
hs[i][0] = s[0] - '#';
for (int j = 1; j < len[i]; j++) hs[i][j] = hs[i][j - 1] * P + s[j] - '#';
}
DP(n);
int ans = 0;
for (int j = 0; j < len[n]; j++) ans = (ans + dp[n][j]) % mod;
printf("%d", ans);
return 0;
}
0%