AtCoder 競プロ典型 90 問 做题记录

只有日语版的AtCoder才能看到这个题集,没有英语翻译。。

吐槽下,日语真难翻译,各个翻译器翻译出来的都不是人话。。

001 - Yokan Party(★4)

在一个长为 $l$ 的绳子上有 $n$ 个点,坐标依次为 $a_i$,可以选择其中 $k$ 个点将绳子分成 $k+1$ 段,长度分别为 $b_i$,其得分为 $\min{b_i}$,求得分的最大值。

$k\leq n\leq 100000,l\leq 10^9$

二分答案,复杂度 $O(n\log{l})$。

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
/*
* @date:2021-05-04 23:19:28
* @source:https://atcoder.jp/contests/typical90/tasks/typical90_a
*/
#include <bits/stdc++.h>

using namespace std;

int N, L, K;
vector<int> v;

bool check(int l) {
int lst = 0, num = 0;
for (int i = 0; i <= N; ++i) {
if (v[i] - lst >= l) {
++num;
lst = v[i];
}
}
return num >= K + 1;
}

int main() {
scanf("%d%d%d", &N, &L, &K);
v.resize(N);
for (auto &x : v) scanf("%d", &x);
v.push_back(L);
int l = 0, r = L, ans;
while (l <= r) {
int m = (l + r) / 2;
if (check(m)) {
l = m + 1;
ans = m;
} else {
r = m - 1;
}
}
printf("%d\n", ans);
return 0;
}

002 - Encyclopedia of Parentheses(★3)

输入 $n$,输出所有长度为 $n$ 的合法括号序。

$n\leq 20$

爆搜就完了。。

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
/*
* @date:2021-05-04 23:36:01
* @source:https://atcoder.jp/contests/typical90/tasks/typical90_b
*/
#include <bits/stdc++.h>

using namespace std;

int N;
char s[105];

void dfs(int x, int num) {
if (x == N) {
if (num) return ;
printf("%s\n", s);
return ;
}
s[x] = '(';
dfs(x + 1, num + 1);
if (num) {
s[x] = ')';
dfs(x + 1, num - 1);
}
}

int main() {
scanf("%d", &N);
if (N & 1) return 0;
dfs(0, 0);
return 0;
}

003 - Longest Circular Road(★4)

给定一棵树,边权皆为 $1$。可以任意插入一条边 $(u,v)$,新图的权值为图中最大环的边数。求新图权值的最大值。

$n\leq 10^5$

复习了一下树的直径。。

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
/*
* @date:2021-05-05 09:56:51
* @source:https://atcoder.jp/contests/typical90/tasks/typical90_c
*/
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 100000 + 5;

int N;
vector<int> E[MAXN];
int Depth[MAXN];

void dfs(int x, int fa) {
for (auto v : E[x]) {
if (v == fa) continue;
Depth[v] = Depth[x] + 1;
dfs(v, x);
}
return ;
}

int main() {
scanf("%d", &N);
for (int i = 1, x, y; i < N; ++i) {
scanf("%d%d", &x, &y);
E[x].push_back(y);
E[y].push_back(x);
}
dfs(1, 0);
int mx = 1;
for (int i = 1; i <= N; ++i) if (Depth[i] > Depth[mx]) mx = i;
Depth[mx] = 0;
dfs(mx, 0);
mx = 0;
for (int i = 1; i <= N; ++i) mx = max(mx, Depth[i]);
printf("%d\n", mx + 1);
return 0;
}

004 - Cross Sum(★2)

给定二维数组 $A[1\cdots n][1\cdots m]$,求二维数组 $B$,其中 $B[i][j]$ 为与 $A[i][j]$ 同一行或同一列的所有数之和。

$N\leq 2000$

预处理第 $i$ 行的和 $R[i]$,第 $j$ 行的和 $C[j]$,则 $B[i][j]=R[i]+C[j]-A[i][j]$。

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
/*
* @date:2021-05-05 10:29:09
* @source:https://atcoder.jp/contests/typical90/tasks/typical90_d
*/
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 2000 + 5;

int N, M;
int A[MAXN][MAXN], C[MAXN], R[MAXN];

int main() {
scanf("%d%d", &N, &M);
for (int i = 1; i <= N; ++i) {
for (int j = 1; j <= M; ++j) {
scanf("%d", &A[i][j]);
R[i] += A[i][j];
C[j] += A[i][j];
}
}
for (int i = 1; i <= N; ++i) {
for (int j = 1; j <= M; ++j) {
printf("%d ", C[j] + R[i] - A[i][j]);
}
puts("");
}
return 0;
}

005 - Restricted Digits(★7)

求 $n$ 位数中,$m$ 的倍数有多少个,要求 $n$ 位数的每一位都由 $c_1,\cdots,c_k(c_i\leq 9)$ 构成。

$n\leq 10^{18},m\leq 1000$

Subtask1:$n\leq 10000,m\leq 30$ 1pts

Subtask2:$m\leq 30$ 3pts

Subtask3:完整数据范围 3pts

Subtask1

数位DP, $f_{x,y}$ 表示 $x$ 位数中,$\bmod m=y$ 的数有多少个,则 $f_{x,y}$ 可以转移到 $f_{x+1,(10\times y+c_j)\bmod m}$。

答案为 $f_{n,0}$,复杂度 $O(nmk)$。

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
/*
* @date:2021-05-05 10:38:49
* @source:https://atcoder.jp/contests/typical90/tasks/typical90_e
*/
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 10000 + 5;
const int MAXB = 30 + 5;
const int MOD = 1e9 + 7;

int N, B, K;
vector<int> v;
int F[MAXN][MAXB];

int main() {
scanf("%d%d%d", &N, &B, &K);
v.resize(K);
for (auto &x : v) scanf("%d", &x);
F[0][0] = 1;
for (int i = 0; i < N; ++i) {
for (int j = 0; j < B; ++j) {
if (!F[i][j]) continue;
for (auto x : v) {
F[i + 1][(j * 10 + x) % B] += F[i][j];
F[i + 1][(j * 10 + x) % B] %= MOD;
}
}
}
printf("%d\n", F[N][0]);
return 0;
}

Subtask2

发现每次转移的系数是确定的,即 $f_{x,y}\rightarrow f_{x+1,z}$ 的所有 $(y,z)$ 每次都是相同的。

因此可以预处理出来一个 $(m+1)\times (m+1)$ 的转移矩阵 $a$,$a[i][j]=x$ 表示有 $x$ 种方法,从上一位 $\bmod m=i$ 转移到下一位 $\bmod m=j$。

对 $a$ 做矩阵快速幂,复杂度 $O(\log{n}\times m^3)$。

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
/*
* @date:2021-05-05 10:38:49
* @source:https://atcoder.jp/contests/typical90/tasks/typical90_e
*/
#include <bits/stdc++.h>

using namespace std;

const int MAXB = 1000 + 5;
const int MOD = 1e9 + 7;

long long N;
int B, K;
vector<int> v;

struct Matrix {
int A[MAXB][MAXB], n, m;
Matrix() {
memset(A, 0, sizeof A);
}
Matrix(int n, int m) {
this->n = n;
this->m = m;
memset(A, 0, sizeof A);
}
Matrix operator * (const Matrix &x) {
Matrix c = Matrix(n, x.m);
for (int i = 1; i <= c.n; ++i) {
for (int j = 1; j <= c.m; ++j) {
for (int k = 1; k <= m; ++k) {
c.A[i][j] += 1ll * A[i][k] * x.A[k][j] % MOD;
c.A[i][j] %= MOD;
}
}
}
return c;
}
} a;

Matrix poww(Matrix x, long long t) {
Matrix y = x;
for (--t; t; t >>= 1) {
if (t & 1) y = y * x;
x = x * x;
}
return y;
}

int main() {
scanf("%lld%d%d", &N, &B, &K);
v.resize(K);
for (auto &x : v) scanf("%d", &x);
Matrix a = Matrix(B + 1, B + 1);
for (int i = 0; i < B; ++i) {
for (auto x : v) {
int y = (i * 10 + x) % B;
a.A[y + 1][i + 1]++;
}
}
a = poww(a, N);
Matrix b = Matrix(B + 1, 1);
b.A[1][1] = 1;
a = a * b;
printf("%d\n", a.A[1][1]);
return 0;
}

Subtask 3

倍增的想法是正确的,但是没必要通过矩阵乘法的形式。想复杂了,尴尬。。

设 $f[i][j]$ 表示 $2^i$ 位数中 $\bmod m=j$ 的方案数,则 $f[i][j]\rightarrow f[i+1][(j*10^{2^i}+k)\bmod m]$。

每次转移的复杂度是 $O(m^2)$ 的,整体复杂度为 $O(\log{n}\times m^2)$。

用FFT可以做到单次转移 $O(m\log{m})$,不过我不太会。

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
/*
* @date:2021-05-05 10:38:49
* @source:https://atcoder.jp/contests/typical90/tasks/typical90_e
*/
#include <bits/stdc++.h>

using namespace std;

const int MAXB = 1000 + 5;
const int MOD = 1e9 + 7;
const int LOG = 70;

long long N;
int B, K;
vector<int> v;
vector<long long> f;
long long P[LOG];

vector<long long> trans(vector<long long> &f, vector<long long> &g, int len) {
static vector<long long> h(B + 1);
fill(h.begin(), h.end(), 0);
for (int i = 0; i < B; ++i) {
for (int j = 0; j < B; ++j) {
h[(i * P[len] + j) % B] += f[i] * g[j] % MOD;
h[(i * P[len] + j) % B] %= MOD;
}
}
return h;
}

long long poww(vector<long long> &f, long long t) {
vector<long long> g(f);
int ff = 1;
for (--t; t; t >>= 1) {
if (t & 1) g = trans(g, f, ff);
f = trans(f, f, ff++);
}
return g[0];
}

int main() {
scanf("%lld%d%d", &N, &B, &K);
v.resize(K);
P[1] = 10 % B;
for (int i = 2; i < LOG; ++i) P[i] = P[i - 1] * P[i - 1] % B;
for (auto &x : v) scanf("%d", &x);
f.resize(B + 1);
for (auto x : v) f[x % B]++;
printf("%lld\n", poww(f, N));
return 0;
}

006 - Smallest Subsequence(★5)

给定长为 $n$ 的字符串 $s$,求长度为 $k$ 的字典序最小的子序列。
$k\leq n\leq 100000$

既然是字典序最小,贪心取每一位就好了。

只要保证取完当前这位,假设是 $s[p]$ 作为第 $q$ 位子序列,满足 $n-p\geq k-q$ (即后面的字符串还有足够的长度用来取余下的子序列)。

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-05 11:42:53
* @source:https://atcoder.jp/contests/typical90/tasks/typical90_f
*/
#include <bits/stdc++.h>

using namespace std;

int N, K;
string S;

int main() {
cin >> N >> K >> S;
int cur = K, mn = 0;
for (int i = 0; i < N; ++i) {
if (N - i < cur) {
cout << S[mn];
i = mn;
mn = i + 1;
--cur;
} else if (S[mn] > S[i]) mn = i;
}
cout << S[mn] << endl;
return 0;
}

007 - CP Classes(★3)

给定一个长为 $n$ 的序列 $v$ 。$m$ 次查询,每次给定一个数 $x$,求 $\min{|x-v_i|}$。

$n,m\leq 300000$

给 $v$ 排序,然后二分呗。。

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
/*
* @date:2021-05-05 11:54:57
* @source:https://atcoder.jp/contests/typical90/tasks/typical90_g
*/
#include <bits/stdc++.h>

using namespace std;

int N, M;
vector<int> v;

int main() {
scanf("%d", &N);
v.resize(N);
for (auto &x : v) scanf("%d", &x);
sort(v.begin(), v.end());
scanf("%d", &M);
for (int i = 1, x; i <= M; ++i) {
scanf("%d", &x);
auto it = lower_bound(v.begin(), v.end(), x);
if (it == v.end()) printf("%d\n", x - *--it);
else if (it == v.begin()) printf("%d\n", *it - x);
else {
int ans = *it - x;
printf("%d\n", min(ans, x - *--it));
}
}
return 0;
}

008 - AtCounter(★4)

给定一个长为 $n$ 的字符串 $s$,求 $s$ 有多少个子序列可以组成atcoder

$n\leq 10^5$

暴力转移就好,$f[i][j]$ 表示 $s$ 的前 $i$ 位匹配到atcoder 的第 $j$ 位的方案数,然后发现还能滚动第一维。

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
/*
* @date:2021-05-05 12:08:36
* @source:https://atcoder.jp/contests/typical90/tasks/typical90_h
*/
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e5 + 5;
const int MOD = 1e9 + 7;

int N;
char s[MAXN], *t = "atcoder";
int F[10];

int main() {
scanf("%d%s", &N, s);
int ans = 0;
for (int i = 0; i < N; ++i) {
for (int j = 0; j < 7; ++j) {
if (s[i] == t[j]) {
if (j) F[j] = (F[j] + F[j - 1]) % MOD;
else F[j]++;
}
}
}
printf("%d\n", F[6]);
return 0;
}