警告

本 Blog 仅供蒟蒻 tiger0132 复习用。本蒟蒻

不对其内容正确性做任何保证。

若发现 Bug 请在评论区反馈。本蒟蒻欢迎一切形式的贡献。

点击屏幕以关闭。

「赛后总结」Codeforces Round #472 (Div. 2) (+2)

传送门:Codeforces Round #472 (Div. 2)

这次本来可以做D,可惜只做出AB

可惜C我想到了思路但没去做:cry:。

UPD:

  1. 2018-03-26 19:25:24:Initial Commit
  2. 2018-04-01 00:09:39:Add C

A

题意

现在有ABM三种颜色,?是空白。现在问你是否有多余一种方式填满所有的?,并且相邻两个颜色不相同

解法

很明显,如果?两边的颜色不同,那么这个肯定只有一种填法。

如果?在开头结尾,或者有几个连在一起,那么肯定有至少一种填法。

于是这就很简单了。只是细节很多。

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
#include <bits/stdc++.h>
using namespace std;

char last, bcount;
string s;
int n, f;

int main() {
cin >> n >> s;
for (int i = 0; i < n; i++) {
if (s[i] == last && s[i] != '?') {
puts("No");
return 0;
}
bcount += (s[i] == '?');
last = s[i];
}
if (!bcount) {
puts("No");
return 0;
}
for (int i = 0; i < n; i++) {
if (s[i] == '?') {
if (i == 0 || i == n - 1) f = 1;
else if (s[i - 1] == '?' || s[i + 1] == '?') f = 1;
else if (s[i - 1] == s[i + 1]) f = 1;
}
if (f == 1) {
puts("Yes");
return 0;
}
}
puts("No");
}

B

题意

\(n\)次操作,每一次可以选择一些行和列,然后把它们的交点全部染成黑色。

现在问你,给你一个黑白局面,问你能不能从白棋盘用\(n\)次得到它,并且满足所有操作中的行和列全部不重复

解法

如图,

显然如果紫色点有任意三个被选了,那么另外一个肯定会也是黑的。 对于所有两两的行和列,如果这样的紫色点有\(1\)个、\(2\)个或者\(4\)个,那么一定是Yes,否则是\(No\)

代码

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
#include <bits/stdc++.h>
using namespace std;

char rec[233][233];
int n, m;

int main() {
scanf("%d%d\n", &n, &m);
for (int i = 1; i <= n; i++) {
gets(rec[i] + 1);
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (i != j) for (int p = 1; p <= m; p++) {
for (int q = 1; q <= m; q++) {
if (p == q) continue;
int count = 0;
if (rec[i][p] == '#') count++;
if (rec[i][q] == '#') count++;
if (rec[j][p] == '#') count++;
if (rec[j][q] == '#') count++;
if (count == 3) {
puts("No");
return 0;
}
}
}
}
}
puts("Yes");
return 0;
}

C

题意

一串单调递增序列\(E\),要你选\(3\)个不相同的下标\((i,j,k),(i\le j\le k)\),满足\(E_k-E_i \le U\),并且满足\(\frac{E_k-E_j}{E_k-E_i}\)是所有满足条件的三元组中最小的。求出这个\(\frac{E_k-E_j}{E_k-E_i}\)

解法

固定\(i\)。那么\(j\)很明显应该等于\(i+1\)。那么\(k\)肯定是满足单调性的。那么只需要找出\(E_k\le E_i+U\)的最大的\(k\)。所以可以二分。时间复杂度\(O(n\log n)\)

其实还有个更好的办法——two-pointer。枚举\(i\),然后将\(i-1\)时的\(k\)用一次循环递增到当前\(i\)时最大的\(k\),然后再更新最终的答案。最终\(k\)移动的次数是\(O(n)\)量级的,所以复杂度降到了\(O(n)\)

代码

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
#include <bits/stdc++.h>
using namespace std;

int n, u, k, rec[100005];
int ai, aj, ak;
double loss;

int main() {
scanf("%d%d", &n, &u);
for (int i = 1; i <= n; i++) {
scanf("%d", rec + i);
}
loss = -1;
for (int i = 1; i < n - 1; i++) {
int j = i + 1;
k = max(k, i);
while (k + 1 <= n && rec[k + 1] - rec[i] <= u) k++;
if (k <= i + 1) continue;
double tl = 1. * (rec[k] - rec[j]) / (rec[k] - rec[i]);
loss = max(loss, tl);
}
if (loss == -1) puts("-1");
else printf("%.12lf", loss);
return 0;
}

D

题意

有条河,第\(i(1\le i\le n)\)天水的高度是\(undefined_i\)。如果某个\(undefined_i\)在以前没有出现过,那么就在那里打上标记。水不会冲掉标记。现在已知每一天河水以上(不包括当前标记)的标记数,求河水下(也不包括当前标记)最少有多少个标记。

解法

首先考虑这个思路:

弄一个变量\(m\),如果每出现一个数字大于\(m\),那么就m++(因为每多一个标记那么这时河水的位置一定在那时所有标记之前,并且还会增加一个标记)。

如果小于等于\(m\),那么直接ans += m - 高度

这个思路的问题是这样的数据就可以hack掉这个思路:

1
2
4
0 0 0 2

解决方案是把这种数据处理成这样:

1
2
4
0 0 1 2

再比如这个数据:

1
2
11
0 0 0 0 0 0 0 2 4 6 8

和这个就是等价的:

1
2
11
0 0 0 1 2 3 4 5 6 7 8

做法是先前缀最大值一遍,然后在再数据变得"平滑"。也就是把所有前缀最大值中相邻两项差不小于\(2\)的全部"整平"。

"整平"代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 输入
for (int i = 1; i <= n; i++) {
scanf("%d", rec + i);
}

// "整平"
for (int i = 1; i <= n; i++) {
smax[i] = max(smax[i - 1], rec[i]);
}
for (int i = n; i >= 1; i--) {
mrec[i] = t = max(smax[i], t - 1);
}
for (int i = 1; i < n; i++) {
mrec[i] = mrec[i + 1] - mrec[i];
}

其中mrec代表修改过的数组,smax代表前缀最大值。

代码

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
#include <bits/stdc++.h>
using namespace std;

int n, m, rec[100005];
int mrec[100005];
int smax[100005];
long long ans;
int t;

int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", rec + i);
}
for (int i = 1; i <= n; i++) {
smax[i] = max(smax[i - 1], rec[i]);
}
for (int i = n; i >= 1; i--) {
mrec[i] = t = max(smax[i], t - 1);
}
for (int i = 1; i < n; i++) {
mrec[i] = mrec[i + 1] - mrec[i];
}
for (int i = 1; i <= n; i++) {
ans += m - rec[i];
m += mrec[i];
}
printf("%lld", ans);
}