BIT 2021.5 Monthly Contest 总结&题解

image-20210509230028002

居然用的是Yandex Contest,没有用牛客的,不知道它的优势在哪儿?(界面简洁没广告倒确实挺好的。。

其实整体还行,rank 6,solved 8/11。

B题讨论了太久,结果exgcd都没搞出来。E题看着是个计算几何,就放弃了,但听说很简单(?)J题一看没人开于是我都没读题。。

还有就是罚时,H题的脑瘫错误找了老半天贡献了-2。

感觉写题面太花时间了,以后干脆就直接复制题面,把它跟代码一样默认折叠。

A. 大Y吃小Y

Statement

image-20210509232855423

把所有 $y_i$ 扔到multiset里,然后轮流每次找最大的,累加到 $x$ 并删除,复杂度 $O(n\log{n})$。

Code

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
/*
* @date:2021-05-09 08:59:29
* @source:
*/
#include <bits/stdc++.h>

using namespace std;

int n;
long long x[2];
vector<long long> v;
multiset<long long> s;

int main() {
scanf("%d%lld%lld", &n, &x[0], &x[1]);
v.resize(n);
for (auto &x : v) scanf("%lld", &x);
for (auto x : v) s.insert(x);
int cur = 0;
while (!s.empty() && *s.begin() < max(x[0], x[1])) {
auto it = s.lower_bound(x[cur]);
if (it != s.begin()) {
x[cur] += *--it;
s.erase(it);
}
cur = (cur + 1) % 2;
}
if (x[0] == x[1]) puts("ZYW and YHW YIYANGJUAN.");
else if (x[0] < x[1]) puts("ZYW is JUANBAOLEed!");
else puts("YHW is JUANBAOLEed!");
return 0;
}

B. 台球

Statement

image-20210509232926758

C. 字符串大师mlcd

Statement

image-20210509232942086

这是一个KMP的Next数组应用题,好在我之前在驾校学车的时候闲着没事儿刷OI-wiki的时候看到了。。

Code

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
/*
* @date:2021-05-09 09:12:50
* @source:
*/
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 2000000 + 5;

string s;
int Nxt[MAXN];
long long F[MAXN];

long long getNext() {
for (int i = 1; i < s.size(); ++i) {
int j = Nxt[i];
while (j && s[j] != s[i]) j = Nxt[j];
Nxt[i + 1] = s[i] == s[j] ? j + 1 : 0;
}
long long ans = 0;
for (int i = 1; i <= s.size(); ++i) {
F[i] = F[Nxt[i]] + 1;
ans += F[i];
}
return ans;
}

int main() {
ios_base::sync_with_stdio(false);
cin >> s;
reverse(s.begin(), s.end());
cout << getNext() << endl;
return 0;
}

D. 迫近的迫近

Statement

image-20210509233236656

虽然我过了,复杂度也相同,但是我的做法实在过于脑瘫。。

正常的做法:

正着求一遍LIS,反着求一遍LDS。用 $f[i]$ 表示正向以 $a_i$ 为结尾的LIS,$g[i]$ 表示反向以 $a_i$ 为结尾的LDS,若 $f[i]+g[i]=LIS+1$,则说明 $a_i$ 位于某个最长上升子序列中,复杂度 $O(n\log{n})$。

我赛时的做法:

正着求一遍LIS,用 $f[i]$ 表示正向以 $a_i$ 为结尾的LIS,用vector $v[i]$ 存储所有 $f[j]=i$ 的下标 $j$。

记序列的LIS的长度为 $m$,显然 $v[m]$ 中的所有下标都是答案。

对于所有 $v[m-1]$ 中的下标 $j$,若它后面存在一个比 $a_j$ 大而且属于 $v[m]$ 的数的话,则它也是答案。

以此类推,一直到 $v[1]$ 截止。维护起来比较麻烦,不过复杂度也是 $O(n\log{n})$。

Code 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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
/*
* @date:2021-05-09 23:33:10
* @source:
*/
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 5e5 + 5;

int N;
vector<int> f, g;
int A[MAXN], L[MAXN], R[MAXN];

int main() {
scanf("%d", &N);
for (int i = 1; i <= N; ++i) {
scanf("%d", &A[i]);
int x = A[i];
if (f.empty() || x > f.back()) {
f.push_back(x);
} else {
*lower_bound(f.begin(), f.end(), x) = x;
}
L[i] = lower_bound(f.begin(), f.end(), x) - f.begin() + 1;
}
for (int i = N; i >= 1; --i) {
int x = -A[i];
if (g.empty() || x > g.back()) {
g.push_back(x);
} else {
*lower_bound(g.begin(), g.end(), x) = x;
}
R[i] = lower_bound(g.begin(), g.end(), x) - g.begin() + 1;
}
int ans = 0;
for (int i = 1; i <= N; ++i) {
if (L[i] + R[i] == f.size() + 1) ++ans;
}
printf("%d\n", ans);
return 0;
}

Code 2

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
/*
* @date:2021-05-09 09:57:04
* @source:
*/
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 5e5 + 5;

int N;
int A[MAXN], F[MAXN];
vector<int> v, f[MAXN];
multiset<int> s[2];

int main() {
scanf("%d", &N);
for (int i = 1; i <= N; ++i) {
scanf("%d", &A[i]);
int x = A[i];
if (v.empty() || x > v.back()) {
v.push_back(x);
} else {
*lower_bound(v.begin(), v.end(), x) = x;
}
int p = lower_bound(v.begin(), v.end(), x) - v.begin() + 1;
f[p].push_back(i);
}
for (auto x : f[v.size()]) s[1].insert(A[x]);
int ans = s[1].size();
for (int i = v.size() - 1, t = 0; i >= 1; --i, t ^= 1) {
s[t].clear();
int p = 0;
for (auto x : f[i]) {
for (; p < f[i + 1].size(); ++p) {
if (f[i + 1][p] < x) {
if (s[t ^ 1].count(A[f[i + 1][p]])) s[t ^ 1].erase(s[t ^ 1].find(A[f[i + 1][p]]));
}
else break;
}
if (s[t ^ 1].upper_bound(A[x]) != s[t ^ 1].end()) {
++ans;
s[t].insert(A[x]);
}
}
}
printf("%d\n", ans);
return 0;
}

E. 迫近的Deadline

Statement

image-20210509235322567

F. 环游世界

Statement

image-20210509235343633

开始没看到 $r\leq i-1$,还以为是什么神题。。

转移方程是 $f_i=\max\limits_{l\leq j\leq r}{(f_j+j-i)}+a_i$,分离变量,用线段树维护 $f_j+j$ 的区间最大值。

复杂度 $O(n\log{n})$。

Code

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
/*
* @date:2021-05-09 10:56:16
* @source:
*/
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 100000 + 5;

int N;
long long F[MAXN];
long long Mx[MAXN << 2];

void update(int rt, int l, int r, int p, long long x) {
if (l == r) {
Mx[rt] = x;
return ;
}
int m = (l + r) >> 1;
if (p <= m) update(rt << 1, l, m, p, x);
else update(rt << 1 | 1, m + 1, r, p, x);
Mx[rt] = max(Mx[rt << 1], Mx[rt << 1 | 1]);
}

long long queryMax(int rt, int l, int r, int a, int b) {
if (a <= l && r <= b) return Mx[rt];
int m = (l + r) >> 1;
long long ans = LLONG_MIN;
if (a <= m) ans = max(ans, queryMax(rt << 1, l, m, a, b));
if (m < b) ans = max(ans, queryMax(rt << 1 | 1, m + 1, r, a, b));
return ans;
}

void init(int rt, int l, int r) {
if (l == r) {
Mx[rt] = LLONG_MIN;
return ;
}
int m = (l + r) >> 1;
init(rt << 1, l, m);
init(rt << 1 | 1, m + 1, r);
Mx[rt] = LLONG_MIN;
}

int main() {
scanf("%d", &N);
for (int i = 1; i <= N; ++i) {
scanf("%lld", &F[i]);
}
init(1, 1, N);
update(1, 1, N, 1, F[1] + 1);
for (int i = 2, l, r; i <= N; ++i) {
scanf("%d%d", &l, &r);
F[i] += queryMax(1, 1, N, l, r) - i;
update(1, 1, N, i, F[i] + i);
}
printf("%lld\n", F[N]);
return 0;
}

G. 敏感的朋友

Statement

image-20210509235629629

$O(nm^2)$ 的DP,$f[i][j]$ 表示给前 $i$ 个人分 $j$ 块糖果的最大好感度,$f[i][j]=\max(f[i][k]+\frac{j-k}{m-k})$。

Code

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
/*
* @date:2021-05-09 10:58:52
* @source:
*/
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 500 + 5;

double F[MAXN][MAXN];
int N, M;

int main() {
scanf("%d%d", &N, &M);
for (int i = 1; i <= N; ++i) {
for (int j = 0; j <= M; ++j) {
for (int k = 0; k <= M - j; ++k) {
F[i][j + k] = max(F[i][j + k], F[i - 1][j] + 1.0 * k / (M - j));
}
}
}
printf("%lf\n", F[N][M]);
return 0;
}

H. 天才麻将少女mlcd

Statement

image-20210509235814385

签到题,然而写的时候不仔细,连WA两发。。

Code

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
/*
* @date:2021-05-09 10:38:45O
* @source:
*/
#include <bits/stdc++.h>

using namespace std;

int n, m;
string s, t, name[4] = {"dong", "xi", "nan", "bei"};
set<string> st;

int main() {
cin >> s >> n;
int type = 0;
for (int i = 0; i < 4; ++i) {
if (name[i] == s) type = i;
}
for (int i = 0; i < n; ++i) {
cin >> t;
st.insert(t);
}
cin >> m;
for (int i = 0; i < m; ++i) {
cin >> t;
if (st.count(t)) {
if (i % 4 == type) {
cout << "zimo!" << endl;
} else {
cout << name[i % 4] << endl; // 忘了%4 !!!!
}
return 0;
}
}
cout << "gan" << endl;
return 0;
}

I. 迫近的NPY

Statement

image-20210509235933002

离散化所有点,然后对每行每列分别维护vector,存该行/列的点坐标。

枚举正方形的左下角和右上角,用set判断左上角和右下角的点是否存在。

至于它边上的限制,在正方形所在的行和列,upper_bound 左侧/下方的角坐标,如果得到的结果刚好是正方形的另一个角,说明这两个角之间没有其他点。

设正方形左下角坐标为 $(x_i,y_i)$,右上角坐标为 $(x_j,y_j)$。以正方形下面那条线举例,它处于第 $x_i$ 行,左下角坐标为 $y_i$,那么在第 $x_i$ 行存储的所有 $y$ 坐标中upper_bound $y_i$,若结果是 $y_j$,说明 $y_i$ 到 $y_j$ 之间没有其他点,也就是说这条边上没有其他点。

复杂度 $O(n^2\log{n})$。

Code

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
/*
* @date:2021-05-09 11:22:11
* @source:
*/
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 5000 + 5;

int N;
int X[MAXN], Y[MAXN];
vector<int> vx, vy;
vector<int> Ax[MAXN], Ay[MAXN];
set<pair<int, int>> Exist;

int getIdX(int x) {
return lower_bound(vx.begin(), vx.end(), x) - vx.begin();
}

int getIdY(int x) {
return lower_bound(vy.begin(), vy.end(), x) - vy.begin();
}

int main() {
scanf("%d", &N);
for (int i = 1; i <= N; ++i) {
scanf("%d%d", &X[i], &Y[i]);
vx.push_back(X[i]);
vy.push_back(Y[i]);
}
sort(vx.begin(), vx.end());
sort(vy.begin(), vy.end());
vx.erase(unique(vx.begin(), vx.end()), vx.end());
vy.erase(unique(vy.begin(), vy.end()), vy.end());
for (int i = 1; i <= N; ++i) {
Ax[getIdX(X[i])].push_back(Y[i]);
Ay[getIdY(Y[i])].push_back(X[i]);
Exist.insert({X[i], Y[i]});
}
for (int i = 0; i < vx.size(); ++i) sort(Ax[i].begin(), Ax[i].end());
for (int i = 0; i < vy.size(); ++i) sort(Ay[i].begin(), Ay[i].end());
int ans = 0;
for (int i = 1; i <= N; ++i) {
for (int j = i + 1; j <= N; ++j) {
int ii = i, jj = j;
if (X[ii] > X[jj]) swap(ii, jj);
if (Y[ii] >= Y[jj]) continue;
if (Y[jj] - Y[ii] != X[jj] - X[ii]) continue;
if (!Exist.count({X[ii], Y[jj]}) || !Exist.count({X[jj], Y[ii]})) continue;
bool flag = 0;
int idx = getIdX(X[ii]);
auto it = upper_bound(Ax[idx].begin(), Ax[idx].end(), Y[ii]);
if (*it == Y[jj]) flag = 1;
idx = getIdX(X[jj]);
it = upper_bound(Ax[idx].begin(), Ax[idx].end(), Y[ii]);
if (*it == Y[jj]) flag = 1;
int idy = getIdY(Y[ii]);
it = upper_bound(Ay[idy].begin(), Ay[idy].end(), X[ii]);
if (*it == X[jj]) flag = 1;
idy = getIdY(Y[jj]);
it = upper_bound(Ay[idy].begin(), Ay[idy].end(), X[ii]);
if (*it == X[jj]) flag = 1;
if (flag) ++ans;
}
}
printf("%d\n", ans);
return 0;
}

J. 合成玉

Statement

image-20210510000548882

K. ZYW的神奇背包

Statement

image-20210510000600151

贪心取即可,优先拿重量小的。

Code

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
/*
* @date:2021-05-09 09:49:53
* @source:
*/
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e6 + 5;

int n, w, c;
int A[MAXN];

int main() {
scanf("%d%d%d", &n, &w, &c);
for (int i = 1; i <= n; ++i) {
scanf("%d", &A[i]);
}
sort(A + 1, A + n + 1);
long long sum = 0, ans = 0;
for (int i = 1; i <= n && w >= A[i]; ++i) {
if (sum + A[i] > c) break;
ans += w - A[i];
sum += A[i];
}
printf("%lld\n", ans);
return 0;
}