| 题目 |
A |
B |
C |
D1 |
D2 |
F |
| 通过情况 |
AC |
AC |
AC |
X |
X |
X |
| 难度 |
800 |
1000 |
1700 |
2300 |
2500 |
2700 |
小结
做出了前三题，比赛时第三题推导花了很长时间
不得不说，这次题的质量还是很高的
A. Find The Array
题面
对于一个数列各元素和$s$正数数列$a$，其中元素$a_i$满足$a_i=1$或$a_i-1$和$a_i-2$至少有个存在
求满足上述条件的数列元素个数的最小值
解法
显然1必须存在在这个数列中，接着不断贪心取当前能取到最大值，即min(当前最大值+2,剩余可取的值)，不难推导出答案为
$\begin{cases}
\lfloor \sqrt{s} \rfloor \,\, ,s\text{为完全平方数}\\
\lfloor \sqrt{s} \rfloor +1,s\text{不为完全平方数}\\
\end{cases}$
代码
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
|
#include <cstdio>
#include <algorithm>
#include <cstring>
#define maxn 100010
#define maxm 100010
#define FOR(i, l, r) for (int i = l; i <= r; i++)
#define PER(i, r, l) for (int i = r; i >= l; i--)
#define ll long long
using namespace std;
int read()
{
int p = 0, f = 1;
char c = getchar();
while (c < 48 || c > 57)
{
if (c == '-')
f = -1;
c = getchar();
}
while (c >= 48 && c <= 57)
p = (p << 1) + (p << 3) + (c ^ 48), c = getchar();
return p * f;
}
int main()
{
int t = read();
while (t--)
{
int cnt = 1;
int n = read();
for (; cnt * cnt <= n; cnt++)
;
cnt--;
if (cnt * cnt == n)
printf("%d\n", cnt);
else
printf("%d\n", cnt + 1);
}
return 0;
}
|
B. Maximum Cost Deletion
题面
给定只含01的长度为n的数列和权值$a,b$ ($1≤n≤100;−100≤a,b≤100$) ,选定任意长度$l$（$l$不为0）的连续0或1序列删除,得到$a\cdot l+b$分，之后删除的两端相接。
求删除到空时总分的最大值
解法
显然a做出的贡献一定为$a\cdot l$,分情况讨论b即可
代码
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
|
#include <cstdio>
#include <algorithm>
#include <cstring>
#define maxn 100010
#define maxm 100010
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, r, l) for (int i = r; i >= l; i--)
#define ll long long
using namespace std;
int read()
{
int p = 0, f = 1;
char c = getchar();
while (c < 48 || c > 57)
{
if (c == '-')
f = -1;
c = getchar();
}
while (c >= 48 && c <= 57)
p = (p << 1) + (p << 3) + (c ^ 48), c = getchar();
return p * f;
}
char s[200];
int main()
{
int t = read();
while (t--)
{
int n = read();
int f, cnt = 1;
ll a = read(), b = read();
scanf("%s", s + 1);
f = s[1];
rep(i, 2, n)
{
if (s[i] != f)
f = s[i], cnt++;
}
ll ans = a * n;
if (b < 0)
ans += (cnt + 2) / 2 * b;
else if (b > 0)
ans += n * b;
printf("%lld\n", ans);
}
return 0;
}
|
C. Manhattan Subarrays
题面
给定定义曼哈顿距离：$d\left( p,q \right) =\left| x_p-x_q \right|+\left| y_p-y_q \right|$
如果三个点$p$,$q$,$r$组成的三元组满足$d\left( p,q \right) =d\left( p,q \right) +d\left( p,q \right) $那么这个三元组是“坏”的
给定数列$A$,如果他的连续子序列是“好”的当且仅当不存在上述“坏”的三元组
补充定义：只含1个或2个的子序列是“好”的
求数列$A$“好”的连续子序列的个数
解法
需要发现以下两个个性质：
1.如果是“坏”的三元组那么其中一个点必然在其他两个点形成的矩形内
2.最长“好”的子序列的元素个数只能为4
之后枚举即可，单次复杂度为$O\left( n \right) $
代码
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
|
#include <cstdio>
#include <algorithm>
#include <cstring>
#define maxn 200010
#define maxm 100010
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, r, l) for (int i = r; i >= l; i--)
#define ll long long
using namespace std;
int read()
{
int p = 0, f = 1;
char c = getchar();
while (c < 48 || c > 57)
{
if (c == '-')
f = -1;
c = getchar();
}
while (c >= 48 && c <= 57)
p = (p << 1) + (p << 3) + (c ^ 48), c = getchar();
return p * f;
}
int a[maxn];
int check(int l, int m, int r)
{
if (abs(a[l] - a[r]) == abs(a[l] - a[m]) + abs(a[m] - a[r]))
return 1;
return 0;
}
int main()
{
int t = read();
while (t--)
{
ll n = read();
rep(i, 1, n)
{
a[i] = read();
}
if (n <= 2)
printf("%lld\n", n + n * (n - 1) / 2);
else
{
ll ans = 2 * n - 1;
rep(i, 3, n)
{
if (!check(i - 2, i - 1, i))
ans++;
}
rep(i, 4, n)
{
if (!check(i - 3, i - 2, i) && !check(i - 3, i - 1, i) && !check(i - 2, i - 1, i) && !check(i - 3, i - 2, i - 1))
ans++;
}
printf("%lld\n", ans);
}
}
return 0;
}
|
官方题解
https://codeforces.com/blog/entry/92864