2024 ICPC 昆明邀请赛

比赛链接

Problems AC
A. Two-star Contest
B. Gold Medal
C. Stop the Castle 2
D. Generated String
E. Relearn through Review
F. Collect the Coins 待补
G. Be Positive
H. Subarray
I. Left Shifting 2
J. The Quest for El Dorado
K. Permutation
L. Trails
M. Italian Cuisine 待补

E gcd 的性质

给定一个长为 n 的数列 a[n], 和一个非负整数 k。
可以至多一次 选择数列的一个区间 +k
求最大化的序列 gcd 和

赛时盯着这道题盯了一个小时然后写了个假算法

赛时想到了 gcd 是单调不增的,也想到了 gcd 最多会减少 logX 次

一段数同时加上 k 以后,gcd 和他们的差有关

明明都知道了这三个关键的性质,还是没得出正解。

假如把整个序列写成一个柿子,答案就非常明了了

$ \gcd(a[1]…a[n]) = $

$\gcd(\gcd(a[1]…a[l - 1]), \gcd(\left|a[l] - a[l + 1]\right|
…\left|a[r - 1] - a[r]\right|), a[r] + k, \gcd(a[r + 1]…a[n])) $

假如 r 确定,则后两项都确定了。至于前两项,都只和原数组有关。

至于原数组,结合 gcd 前缀只有 logX 个的性质,本质不同的只有 logX 个,枚举 logX 个分界点即可

note:注意 ans 的初值

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
void solve() {
int n = read(), k = read();

vector<int> a(n + 1);
for (int i = 1; i <= n; i++) {
a[i] = read();
}

vector<int> pre(n + 1), suf(n + 2);
for (int i = 1; i <= n; i++) {
pre[i] = std::__gcd(pre[i - 1], a[i]);
}
for (int i = n; i >= 1; i--) {
suf[i] = std::__gcd(suf[i + 1], a[i]);
}

int ans = pre[n];

for (int i = 1; i <= n; i++) {
if (pre[i] == pre[i - 1]) continue;

int g = 0;

for (int j = i; j <= n; j++) {
g = std::__gcd(g, a[j] + k);
ans = max(ans, std::__gcd(pre[i - 1], std::__gcd(g, suf[j + 1])));
}
}
cout << ans << '\n';
}

J 最短路 RMQ

给一张无向图,每条边有长度和颜色。从节点 $1$ 开始一共要走 $k$ 轮,每一轮可以一次性走完颜色均为 $a_i$ 且总长不超过 $b_i$ 的边。问 $k$ 轮走完以后能走到哪些点。
$n, m, k \le 5 \times 10^5$

以走到了第 r 轮为第一关键字,这一轮走了距离 d 为第二关键字,作为最短路的距离。

当拓展一条边 (c, len) 时如果 $c = a_r$ 且 $d + len \le b_r$,则可以直接转移。

否则需要在 $[r + 1, k]$ 中找一个颜色为 $c$ 的且 $b_nr \ge len$ 的最早的一个 $nr$ 转移过去。

每个颜色开个 rmq,在 rmq 上二分即可。

复杂度 $O(m (\log{m} + \log{k}) + k \log k)$

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
void solve() {
int n = read(), m = read(), k = read();

vector g(n + 1, vector<array<int, 3>>());
for (int i = 1; i <= m; i++) {
int u = read(), v = read();
int c = read(), w = read();

g[u].pb({v, c, w});
g[v].pb({u, c, w});
}

vector<std::array<int, 2>> tik(k + 1);

vector rmq(m + 1, vector(21, vector<int>()));
vector pos(m + 1, vector<int>());

for (int i = 1; i <= k; i++) {
tik[i][0] = read();
tik[i][1] = read();

rmq[tik[i][0]][0].eb(tik[i][1]);
pos[tik[i][0]].eb(i);
}

for (int c = 1; c <= m; c++) {
for (int j = 1; j <= 20; j++) {
rmq[c][j].assign(rmq[c][0].size() + 1, 0);
}
}

for (int c = 1; c <= m; c++) {
for (int j = 1; j <= 20; j++) {
for (int i = 0; i + (1 << j) - 1 < rmq[c][0].size(); i++) {
rmq[c][j][i] = max(rmq[c][j - 1][i], rmq[c][j - 1][i + (1 << (j - 1))]);
}
}
}

auto getrmq = [&](int c, int l, int r) {
int k = std::__lg(r - l + 1);
return max(rmq[c][k][l], rmq[c][k][r - (1 << k) + 1]);
};

auto search = [&](int l, int c, int len) {
if (pos[c].empty() or pos[c].back() < l) return -1;

l = std::lower_bound(pos[c].begin(), pos[c].end(), l) - pos[c].begin();

int res = -1;
for (int r = rmq[c][0].size() - 1; l <= r; ) {
int mid = l + r >> 1;
if (getrmq(c, l, mid) >= len) {
res = mid, r = mid - 1;
} else {
l = mid + 1;
}
}

if (res == -1) return -1;
return pos[c][res];
};

vector<int> vis(n + 1);
vector<array<int, 2>> dis(n + 1, {inf, inf});
std::priority_queue<array<int, 3>, vector<array<int, 3>>, std::greater<>> q;

dis[1] = {1, 0};
q.push({1, 0, 1});
while (!q.empty()) {
auto [r, d, u] = q.top();
q.pop();

if (vis[u]) continue;
vis[u] = 1;

for (auto [v, c, len] : g[u]) {
if (tik[r][0] == c and tik[r][1] >= d + len) {
if (dis[v][0] > r or dis[v][0] == r and dis[v][1] > d + len) {
q.push({r, d + len, v});
}
continue;
}

int nr = search(r + 1, c, len);
if (nr == -1) continue;
if (dis[v][0] > nr or dis[v][1] == nr and dis[v][1] > len) {
q.push({nr, len, v});
}
}
}

for (int i = 1; i <= n; i++) {
cout << vis[i];
}
puts("");
}

L LIS

二维平面每个整点 $(x, y)$ 都有连向 $(x + 1, y)$ 和 $(x, y + 1)$ 的两条无向路径。另外还有 $n$ 条特殊的无向路径连接 $(x_i, y_i)$ 和 $(x_i + 1, y_i + 1)$。

设 $f(x, y)$ 表示从 $(0, 0)$ 走到 $(x, y)$ 需要的最少路径数。给 $p$ 和 $q$,求 $\sum_{x = 0}^p\sum_{y=0}^{q}f(x,y)$

多组数据,$n \le 10^6$,$p, q \le 10^6$。

假如没有额外路径的话,$f(x, y) = x + y$

那么考虑上额外小径就是减去最多经过的额外小径数量

从贡献角度考虑,一个斜线 (x0, y0) -> (x0 + 1, y0 + 1) 会让 f(x > x0, y > y0) 这个矩形 -1。因此可以把所有斜线按 $x_i$ 为第一关键字升序,$y_i$ 为第二关键字降序排列。

这样走到 (x, y) 最多经过的斜线数量就等价于一个最长上升子序列的长度。

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
void solve() {
int n = read();
int p = read(), q = read();

using pii = std::pair<int, int>;
#define fi first
#define se second

vector<pii> a(n);
for (auto &[x, y] : a) {
x = read(), y = read();
}

std::sort(a.begin(), a.end(), [](pii x, pii y) {
return x.fi == y.fi ? x.se > y.se: x.fi < y.fi;
});

std::set<int> s;
int ans = p * (p + 1) / 2 * (q + 1)
+ q * (q + 1) / 2 * (p + 1);

int sum = 0, las = 0;
for (auto [x, y] : a) {
if (x >= p) break;
if (y >= q) continue;

if (las <= x) {
ans -= (x - las + 1) * sum;
las = x + 1;
}

if (s.empty() or y > *std::prev(s.end())) {
s.insert(y);
sum += q - y;
} else {
auto it = s.lower_bound(y);

sum -= q - *it;
sum += q - y;
s.erase(it);
s.insert(y);
}
}

if (las <= p) {
ans -= (p - las + 1) * sum;
}

cout << ans << '\n';
}
Author

TosakaUCW

Posted on

2024-10-11

Updated on

2024-10-18

Licensed under

Comments