2024.2
CF1096D
CF1096D Easy Problem
首先我们可以很自然的想到状态 $dp_{i,j}$ 表示前 $i$ 个字符只包含 “$hard$” 前 $k$ 的字串最少需要多少代价。然后就是分类讨论：首先是删除第 $i$ 个字符，直接用 $dp_{i,j} = min(dp_{i-1,j} + cost_i, dp_{i,j})$ 转移就行了；不删除第 $i$ 个数字，如果 $s_i$ 是 “$hard$” 的第 $k$ 个数字那么 $dp_{i,k} = min(dp_{i - 1,k - 1}, dp_{i,j})$，对于其他的位置只需要 $dp_{i,j} = min(dp_{i - 1,j}, dp_{i,j})$。最后答案就是 $max(dp_{n, 0},dp_{n, 1},dp_{n, 2},dp_{n, 3})$ ，其中 $n$ 是字符串 $s$ 的长度。时间复杂度为$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
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
| #include <iostream>
#include <vector>
#include <string>
using namespace std;
using i64 = long long;
const i64 inf = 1e16;
void solve() {
int n;
cin >> n;
string s;
cin >> s;
vector<i64> a(n + 1, inf);
vector<i64> f[4];
for(int i = 0; i < 4; i++) {
f[i] = vector<i64>(n + 1, inf);
}
f[0][0] = 0;
for(int i = 1; i <= n; i++) {
cin >> a[i];
for(int j = 0; j < 4; j++) {
f[j][i] = min(f[j][i - 1] + a[i], f[j][i]);
}
if(s[i - 1] == 'h') {
f[1][i] = min(f[0][i - 1], f[1][i]);
f[1][i] = min(f[1][i - 1], f[1][i]);
f[2][i] = min(f[2][i - 1], f[2][i]);
f[3][i] = min(f[3][i - 1], f[3][i]);
}
else if(s[i - 1] == 'a') {
f[2][i] = min(f[1][i - 1], f[2][i]);
f[0][i] = min(f[0][i - 1], f[0][i]);
f[2][i] = min(f[2][i - 1], f[2][i]);
f[3][i] = min(f[3][i - 1], f[3][i]);
}
else if(s[i - 1] == 'r') {
f[0][i] = min(f[0][i - 1], f[0][i]);
f[1][i] = min(f[1][i - 1], f[1][i]);
f[3][i] = min(f[2][i - 1], f[3][i]);
f[3][i] = min(f[3][i - 1], f[3][i]);
}
else if(s[i - 1] == 'd'){
f[0][i] = min(f[0][i - 1], f[0][i]);
f[1][i] = min(f[1][i - 1], f[1][i]);
f[2][i] = min(f[2][i - 1], f[2][i]);
}
else {
f[0][i] = min(f[0][i - 1], f[0][i]);
f[1][i] = min(f[1][i - 1], f[1][i]);
f[2][i] = min(f[2][i - 1], f[2][i]);
f[3][i] = min(f[3][i - 1], f[3][i]);
}
}
i64 ans = inf;
ans = min(ans, f[0][n]);
ans = min(ans, f[1][n]);
ans = min(ans, f[2][n]);
ans = min(ans, f[3][n]);
cout << ans << endl;
}
int main() {
solve();
}
|
2024.3
2024 ICPC Asia Pacific Championship E
2024 ICPC Asia Pacific Championship E
首先排列每一行至少修改一次， 排列每一列最少修改一次，我们不妨设排列的行数是 $N$ ，列数是 $M$ ，所以修改的次数不少于 $\max(m, n)$ ，然后我们再思考如何通过修改 $\max(m, n)$次来达到题目的要求。首先不妨另 $N \leq M$，然后设行排列的集合为 $r_N$， 列排列的集合为 $c_M$。我们可以通过将 $a_{r_i,c_i}$ 变成任意一个不等于它的数字，把问题转化成操作 $M - N$ 次把 $M - N $ 个列排列转化成非排列的列。对于这个问题，一种简单的方法是维护第一行的出现次数最多的数字 $a$，和出现次数第二多的数字 $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
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
90
91
92
93
94
95
96
97
98
99
100
101
102
103
| #include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using i64 = long long;
void solve() {
int n;
cin >> n;
vector<vector<int>> a(n + 1, vector<int>(n + 1));
for(int i = 0; i < n; i++) {
for(int j = 0 ; j < n; j++) {
cin >> a[i][j];
}
}
vector<int> r, c;
for(int i = 0; i < n; i++) {
vector<bool> vis(n + 1, 0);
bool flag = 1;
for(int j = 0; j < n; j++) {
if(vis[a[i][j]])
flag = 0;
vis[a[i][j]] = 1;
}
if(flag) {
r.push_back(i);
}
}
for(int j = 0; j < n; j++) {
vector<bool> vis(n + 1, 0);
bool flag = 1;
for(int i = 0; i < n; i++) {
if(vis[a[i][j]])
flag = 0;
vis[a[i][j]] = 1;
}
if(flag) {
c.push_back(j);
}
}
struct node {
int a, b, c;
};
vector<node> ans;
int N = r.size(), M = c.size();
if(N <= M) {
for(int i = 0; i < N; i++) {
int x = r[i], y = c[i];
a[x][y] = a[x][y] % n + 1;
ans.push_back((node){x, y, a[x][y]});
}
vector<int> cnt(n + 1);
cnt[0] = -1;
for(int i = 0; i < n; i++) {
cnt[a[0][i]]++;
}
int fir = max_element(cnt.begin(), cnt.end()) - cnt.begin();
cnt[fir] = -1;
int sec = max_element(cnt.begin(), cnt.end()) - cnt.begin();
for(int i = N; i < M; i++) {
int now = fir;
if(fir == a[0][c[i]]) {
now = sec;
}
ans.push_back((node){0, c[i], now});
}
}
else {
for(int i = 0; i < M; i++) {
int x = r[i], y = c[i];
a[x][y] = a[x][y] % n + 1;
ans.push_back((node){x, y, a[x][y]});
}
vector<int> cnt(n + 1);
cnt[0] = -1;
for(int i = 0; i < n; i++) {
cnt[a[i][0]]++;
}
int fir = max_element(cnt.begin(), cnt.end()) - cnt.begin();
cnt[fir] = -1;
int sec = max_element(cnt.begin(), cnt.end()) - cnt.begin();
for(int i = M; i < N; i++) {
int now = fir;
if(fir == a[r[i]][0]) {
now = sec;
}
ans.push_back((node){r[i], 0, now});
}
}
cout << ans.size() << endl;
for(auto [x, y, v] : ans) {
cout << x + 1 << ' ' << y + 1 << ' ' << v << endl;
}
}
int main() {
int t = 1;
cin >> t;
while(t--) {
solve();
}
return 0;
}
|
2024 ICPC Asia Pacific Championship G
2024 ICPC Asia Pacific Championship G
我们可以把每个学生抽象成一个点， 然后把一个相同的考试抽象成一个边，问题就等价于，是否存在两个点满足有 $k$ 条直接相连的边。我们可以发现，如果无解，最多只能连出 $(k - 1) \cdot n$ 条边。我们可以动态的加入每一个点，维护每一个边所连接的点，然后判断它们是否满足条件。如果前面的都不满足条件显然总和只有 $k \cdot n$ 个点，如果找到了满足条件的，那一次最多会比较 $n$ 次，因此时间复杂度为 $O(k \cdot n \cdot m)$
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
| #include <iostream>
#include <bitset>
#include <vector>
#include <string>
#include <set>
using namespace std;
void solve() {
int n, m, k;
cin >> n >> m >>k;
vector<vector<vector<int>>> v(m,vector<vector<int>>(26));
vector<string> s(n);
for(int i = 0; i < n; i++) {
cin >> s[i];
}
for(int i = 0; i < m; i++) {
if(s[0][i] != '.') {
v[i][s[0][i] - 'A'].push_back(0);
}
}
for(int i = 1; i < n; i++) {
vector<int> cnt(n, 0);
for(int j = 0; j < m; j++) {
if(s[i][j] == '.') {
continue;
}
for(auto x : v[j][s[i][j] - 'A']) {
cnt[x]++;
}
}
for(int j = i - 1; j >= 0; j--) {
if(cnt[j] >= k) {
cout << j + 1 << ' '<< i + 1;
return;
}
}
for(int j = 0; j < m; j++) {
if(s[i][j] != '.') {
v[j][s[i][j] - 'A'].push_back(i);
}
}
}
cout << -1 << endl;
}
int main() {
int t = 1;
while(t--) {
solve();
}
return 0;
}
|
2024 ICPC Asia Pacific Championship F
2024 ICPC Asia Pacific Championship F
首先考虑一下当分割成 $k$ 组的 $\max(s_i) \ \min(s_j)$ 的最大值是多少，我们可以枚举 $a_0$ 的位置得到答案。然后首先分割的数量 $k$ 必须要满足 $k$ 是 $n$ 的一个因数。一个数字有 $O(d(n))$ 个因数，其中$O(d(n)) \leq O(\sqrt n)$ ，但是会 $TLE$ ，所以我们需要再优化一下。我们可以观察到，如果 $a$ 是 $b$ 的一个因数，那么分割成 $a$ 个的结果优于分割成 $b$ 个的结果。所以我们只需要枚举 $n$ 的所有的质因数作为 $k$ ，时间复杂度为 $O(\omega(n)\cdot n \cdot \log n)$ 其中 $O(\omega(n)) \leq O(\log 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
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
| #include <iostream>
#include <set>
#include <numeric>
#include <vector>
using i64 = long long;
using namespace std;
struct fs {
i64 a, b;
fs(i64 a, i64 b) : a(a), b(b) {
i64 g = gcd(a, b);
(*this).a /= g;
(*this).b /= g;
}
bool operator < (fs f) const{
return a * f.b < b * f.a;
}
};
fs ans(1000000000, 1);
void f(int k, vector<i64>& a) {
int n = a.size();
multiset<i64> s;
vector<i64> cnt(k, 0);
for(int i = 0; i < n; i++) {
cnt[i % k] += a[i];
}
for(int i = 0; i < k; i++) {
s.insert(cnt[i]);
}
ans = min(fs((*s.rbegin()),(*s.begin())), ans);
for(int i = 1; i < n; i++) {
s.extract(cnt[(i + k - 1) % k]);
s.extract(cnt[i % k]);
cnt[(i + k - 1) % k] -= a[0];
cnt[(i + k - 1) % k] += a[i];
cnt[i % k] -= a[i];
cnt[i % k] += a[0];
s.insert(cnt[(i + k - 1) % k]);
s.insert(cnt[i % k]);
ans = min(fs((*s.rbegin()),(*s.begin())), ans);
}
}
void solve() {
ans = fs(1000000000, 1);
int n;
cin >> n;
vector<i64> a(n);
for(auto &x : a) {
cin >> x;
}
int now = n;
for(int i = 2; i * i <= n; i++) {
if(now % i == 0) {
f(i, a);
}
while(now % i == 0) {
now /= i;
}
}
if(now != 1)
f(now, a);
cout << ans.a << ' ' << ans.b << endl;
}
int main() {
int t = 1;
cin >> t;
while(t--) {
solve();
}
return 0;
}
|
2023 ICPC Asia Hangzhou Regional Contest D
2023 ICPC Asia Hangzhou Regional Contest D
构造题。给一个感性的思路。首先我们必须要能先观察到如果 $a_{2i−2} + a_{2i−1}$ 不是 $1$ 的话，乘积会非常大，很难找到一个与和相等的数字，所以我们应当构造一个 $a_{2i−2} + a_{2i−1} = 1$ 的情况，我们不妨构造成 $x, 2, -1, 2, -1…, 2, -1, y$ 。然后要使得条件成立，我们需要另 $x\cdot y = 2x - 2(n - 2) - y$ ，不妨另 $y = 1$ 解得 $x = 2n - 3$ 那么，一种构造的方案是 $2n - 3, 2, -1, 2, -1…, 2, -1, 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 <iostream>
using namespace std;
void solve() {
int n;
cin >> n;
cout << 2 * n - 3 << ' ' ;
for(int i = 1; i < n; i++) {
cout << 2 << ' ' << -1 << ' ';
}
cout << 1;
cout << endl;
}
int main() {
int t;
cin >> t;
while(t--) {
solve();
}
return 0;
}
|
