P3513 KON - Conspiracy
简要题意: 将一张无向图划分为两个非空点集 $S_1,S_2$，满足 $S_1$ 的导出子图为完全图，$S_2$ 的导出子图边集为空。求方案数。
数据规模: $2 \le n \le 5000$。
题解: 比较常见的做法是使用 2-SAT，并在建出的图上进行一些计数，大概是 $O(n^2)$。
实际上，还有一种关于 $n$ 线性的做法，并且无需读入边，只需要知道每个点的度数 $deg_i$ 即可。
假设给定的图 $G = (V,E)$。考虑点集 $S_1$，考察 $S_1$ 中的点的度数之和，即 $num = \sum_{u \in S_1} deg_u$。由于 $V = S_1 \cup S_2$，所以 $S_1$ 与 $S_2$ 之间的每条边对 $num$ 贡献 $1$ 次。而 $S_2$ 中没有边，$S_1$ 为完全图，所以 $S_1$ 的导出子图中的每条边对 $num$ 的贡献为 $2$。因此，$(S_1,S_2)$ 为合法的划分，当且仅当 $num = |E| + \binom{|S_1|}{2}$。
而考虑一个点集 $S_1$。即使所有的边都对 $num$ 的贡献为 $2$，由于没有重边存在，所以对于任意的点集 $S_1$，其对应的 $num$ 至多为 $|E| + \binom{|S_1|}{2}$。
因此，考虑枚举集合 $S_1$ 的大小 $|S_1|$。判断度数最大的 $|S_1|$ 个点，设为集合 $P$，是否满足其度数之和为 $|E| + \binom{|S_1|}{2}$。倘若满足，则可以将 $P$ 中度数最小的点替换成其他度数相同的点。具体地，若
$$
\begin{aligned}
d &= \min_{u \in P} deg_u \\
cnt &= \sum_{u \in P} [d = deg_u] \\
num &= \sum_{u \in V} [d = deg_u]
\end{aligned}
$$
则当前大小的 $S_1$ 集合对答案的贡献就是 $\binom{num}{cnt}$。
可以证明答案的量级是 $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
| using ll = long long;
const int N = 5e3 + 10, mod = 1e9 + 7;
int n, tot, deg[N], cnt[N], fac[N], ifac[N];
inline int binom(int n, int m) {
return 1LL * fac[n] * ifac[m] % mod * ifac[n - m] % mod;
}
signed main() {
read(n);
fac[0] = ifac[0] = ifac[1] = 1;
for (int i = 1; i <= n; ++i)
fac[i] = 1LL * fac[i - 1] * i % mod;
for (int i = 2; i <= n; ++i)
ifac[i] = 1LL * ifac[mod % i] * (mod - mod / i) % mod;
for (int i = 2; i <= n; ++i)
ifac[i] = 1LL * ifac[i - 1] * ifac[i] % mod;
for (int i = 1; i <= n; ++i) {
int k, x;
read(k);
tot += k, deg[i] = k;
while (k--)
read(x);
}
tot >>= 1;
sort(deg + 1, deg + n + 1, greater<int>());
for (int i = 1; i <= n; ++i)
++cnt[deg[i]];
int num = 0, ans = 0;
for (int i = 1, p = 1; i < n; ++i) {
num += deg[i];
if (deg[i] != deg[p])
p = i;
if (num != tot + i * (i - 1) / 2)
continue;
ans += binom(cnt[deg[i]], i - p + 1);
}
write(ans), putchar('\n');
return 0;
}
|
P3514 LIZ - Lollipop
简要题意: 有一个长度为 $n$ 的序列 $a_1,a_2,\cdots,a_n$，其中 $a_i \in \{1,2\}$。有 $q$ 个询问，每次询问是否存在一个连续的子段，满足其和为 $k$。输出方案。
数据规模: $1 \le n, q \le 10^6, \ 1 \le k \le 2 \times 10^6$。
题解: 看到这类构造方案的题，第一眼无从下手。不妨先从判断是否有解做起。
引理 $(1)$: 假设 $k > 2$，若 $k$ 可以被构造出，则 $k - 2$ 也可以被构造出。
考虑 $k$ 所对应的子段 $[l,r]$。若 $a_l = a_r = 1$，则可以用子段 $[l+1,r-1]$ 构造出 $k-2$。否则，$a_l$ 与 $a_r$ 中存在一个 $2$，将其去掉得到新的子段。
因此，我们可以按照奇偶性分类，先处理出最大的能构造出的奇数和偶数，设为 $mx_0$ 和 $mx_1$。假设 $s = \sum a_i$，则显然有 $mx_{s \& 1} = s$。新的问题变成如何求出 $mx_{! s \& 1}$。
引理 $(2)$: 一定存在 $a$ 的一段前缀或后缀，使得删去这段前缀/后缀之后，序列中剩余数的和为 $mx_{!s \& 1}$。
证明不妨考虑删去的数。必然是删去了若干个 $2$ 以及一个 $1$，否则一定能少删去若干 $1$ 并使得 $mx_{!s \& 1}$ 更小。
考虑删去的 $1$ 所在的位置 $p$。如果 $p$ 以前的位置上的 $2$ 都被删除，那么不删后缀一定更优；如果 $p$ 以后的位置上的 $2$ 都被删除，那么不删前缀一定更优。因此，能使得 $mx_{!s \& 1}$ 最大的删除方法一定是保留一段前缀/后缀。
那么只需要枚举一下保留的前缀/后缀长度，就可以求出 $mx_{!s \& 1}$ 了。
回答询问时，只需要先按照引理 $(1)$ 的证明，预处理出所有能构造出的 $k$ 对应的方案，即可 $O(1)$ 回答询问。
总体复杂度 $O(n + q)$。
代码:
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
| using ll = long long;
const int N = 1e6 + 10;
int n, q, tot, mx[2], a[N], prf[N];
char str[N];
pair<int, int> ans[N * 2];
signed main() {
read(n), read(q);
scanf("%s", str + 1);
for (int i = 1; i <= n; ++i)
a[i] = (str[i] == 'T') + 1, tot += a[i], prf[i] = prf[i - 1] + a[i];
mx[tot & 1] = tot;
ans[tot] = {1, n};
for (int i = 1; i < n; ++i) {
int ls = prf[i], rs = tot - prf[i];
if ((ls & 1) != (tot & 1) && ls > mx[!(tot & 1)])
mx[!(tot & 1)] = ls, ans[ls] = {1, i};
if ((rs & 1) != (tot & 1) && rs > mx[!(tot & 1)])
mx[!(tot & 1)] = rs, ans[rs] = {i + 1, n};
}
for (int s = 0; s < 2; ++s) {
int cl, cr;
tie(cl, cr) = ans[mx[s]];
for (int k = mx[s] - 2; k > 0; k -= 2) {
if (a[cl] == 2) {
++cl;
} else if (a[cr] == 2) {
--cr;
} else {
++cl, --cr;
}
ans[k] = {cl, cr};
}
}
while (q--) {
int k;
read(k);
if (k > mx[k & 1]) {
puts("NIE");
} else {
printf("%d %d\n", ans[k].first, ans[k].second);
}
}
return 0;
}
|
P3515 PIO - Lightning Conductor
简要题意: 给定一个长度为 $n$ 的序列 $\{a_n\}$，对于每个 $i\in [1,n]$ ，求出一个最小的非负整数 $p$ ，使得 $\forall j\in[1,n]$，都有 $a_j\le a_i+p-\sqrt{|i-j|}$。
数据规模: $1 \le n \le 5\times 10^{5}$，$0 \le a_i \le 10^{9}$ 。
题解: 经典题了属于是，移项一下发现要对每个 $i$ 求 $\max\{a_j - a_i + \sqrt{|i-j|}\}$。不妨将序列分为 $j \le i$ 以及 $j \ge i$ 两部分分别处理。
由于函数 $f(x)=\sqrt{x}$ 在 $x > 1$ 时的斜率 $\le 1$，因此以 $j \le i$ 为例，当 $i$ 增大时，让 $w(i,j) = a_j - a_i + \sqrt{|i-j|}$ 取到 $\max$ 的决策点 $j$ 一定不会往左移动。因此 $w(i,j)$ 满足决策单调性。使用分治维护即可。
~~板子题还写挂了，一开始 calc 函数没开 double。~~直接向上取整就会不满足决策单调性喽！
代码:
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
| using ll = long long;
const int N = 5e5 + 10;
int n, a[N], pre[N], nxt[N];
double calc(int i, int j) { return a[j] + sqrt(abs(i - j)) - a[i]; }
void solve1(int l, int r, int kl, int kr) {
int mid = (l + r) >> 1, k = 0;
for (int i = kl; i <= kr && i <= mid; ++i)
if (!k || calc(mid, i) > calc(mid, k))
k = i;
pre[mid] = k;
if (l < mid)
solve1(l, mid - 1, kl, k);
if (r > mid)
solve1(mid + 1, r, k, kr);
}
void solve2(int l, int r, int kl, int kr) {
int mid = (l + r) >> 1, k = 0;
for (int i = kr; i >= kl && i >= mid; --i)
if (!k || calc(mid, i) > calc(mid, k))
k = i;
nxt[mid] = k;
if (l < mid)
solve2(l, mid - 1, kl, k);
if (r > mid)
solve2(mid + 1, r, k, kr);
}
signed main() {
read(n);
for (int i = 1; i <= n; ++i)
read(a[i]);
solve1(1, n, 1, n), solve2(1, n, 1, n);
for (int i = 1; i <= n; ++i) {
int ans = (int)ceil(max(calc(i, pre[i]), calc(i, nxt[i])));
write(ans), putchar('\n');
}
return 0;
}
|
P3516 PRZ - Shift
简要题意: 有一个 $1 \sim n$ 的排列，每次操作可以将第 $3$ 个数移动到第 $1$ 个或者将第 $n$ 个数移动到第 $1$ 个。我们称连续进行 $k$ 次的相同操作为一个块。找到一个操作序列，使得进行操作之后，排列变成 $1,2,3,\cdots,n$，且块的数量 $m \le n^2$，或输出无解。
数据规模: $1 \le n \le 2000$。
题解: 感觉评黑有点虚高了。
首先考虑在何种情况下无解。由于操作相当于对数组进行排序，很套路地想到使用逆序对数量 $rev$。
假设序列为 $\{a_1,\cdots,a_n\}$。注意到，操作 $(1)$ 会使得 $a_3$ 向前移动 $2$ 格，并不改变 $rev$ 的奇偶性。操作 $(2)$ 将 $a_n$ 向前移动 $n-1$ 格，若 $n$ 为奇数，则不改变 $rev$ 的奇偶性，否则改变。
因此，容易发现无解的条件即 $n$ 为奇数且逆序对数量 $rev$ 为奇数。特判掉上述情况后，我们先默认序列有解，并尝试给出一种构造。
首先，若 $rev$ 为奇数，则进行一次操作 $(2)$，使得 $rev$ 变为偶数。下面只讨论 $rev$ 为偶数的情况。
考虑一个长度为 $3$ 的子区间 $a_i,a_{i+1},a_{i+2}$，我们可以通过若干次操作 $(2)$ 将这 $3$ 个数移动到序列的头部，并进行一次操作 $(1)$，再进行若干次操作 $(2)$ 将它们移动回原位置。这样以来，这个子区间就变成了 $a_{i+2},a_i,a_{i+1}$，而其他位置的数字不会改变。我们称一次这样的操作为操作 $(3)$。
注意到，一次操作 $(3)$ 可以将 $a_i,a_{i+1}$ 向后移动一格。我们考虑从后往前，依次将 $a_i$ 变成 $i$。容易发现这只是一个类似选择排序的过程，即找到序列中 $i$ 所在的位置 $p$，使用若干次操作 $(3)$ 将 $a_p$ 从 $p$ 移动到 $i$。
考虑计算答案次数的上界，由于选择排序的交换次数至多为 $\frac{n(n-1)}{2}$，所以操作 $(3)$ 的次数也至多为 $\frac{n(n-1)}{2}$。将相邻两次操作的 $(1)$ 操作进行合并，答案的上界不超过 $n^2$。
代码:
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
| using ll = long long;
using pii = pair<int, int>;
const int N = 2e3 + 10;
int n, a[N], pos[N];
vector<pii> ans;
struct binary_indexed_tree {
int bit[N];
void add(int x, int v) {
for (int i = x; i <= n; i += i & -i)
bit[i] += v;
}
int sum(int x) const {
int ret = 0;
for (int i = x; i; i -= i & -i)
ret += bit[i];
return ret;
}
int ask(int l, int r) const { return sum(r) - sum(l - 1); }
} bit;
void oper(int p, int k) {
for (int i = 0; i < k; ++i)
swap(a[p], a[p + 2]), swap(a[p + 1], a[p + 2]);
pos[a[p]] = p, pos[a[p + 1]] = p + 1, pos[a[p + 2]] = p + 2;
ans.push_back({0, n - p + 1}), ans.push_back({1, k}),
ans.push_back({0, p - 1});
}
signed main() {
read(n);
for (int i = 1; i <= n; ++i)
read(a[i]);
bool rev = 0;
for (int i = 1; i <= n; ++i)
rev ^= (bit.ask(a[i] + 1, n) & 1), bit.add(a[i], 1);
if ((n & 1) && rev)
return puts("NIE DA SIE"), 0;
if (rev) {
int tmp = a[n];
for (int i = n - 1; i; --i)
a[i + 1] = a[i];
a[1] = tmp, ans.push_back({0, 1});
}
for (int i = 1; i <= n; ++i)
pos[a[i]] = i;
for (int i = n; i >= 1; --i)
while (pos[i] != i)
oper(pos[i] > 1 ? pos[i] - 1 : pos[i], 1);
vector<pii> res;
for (int i = 0; i < (int)ans.size(); ++i) {
if (ans[i].first == 0)
ans[i].second %= n;
if (!ans[i].second)
continue;
if (res.empty() || res.back().first != ans[i].first) {
res.push_back(ans[i]);
} else {
int md = res.back().first ? 3 : n;
(res.back().second += ans[i].second) %= md;
if (!res.back().second)
res.pop_back();
}
}
printf("%lu\n", res.size());
for (int i = 0; i < (int)res.size(); ++i) {
printf("%d%c", res[i].second, (char)(res[i].first + 'a'));
putchar(" \n"[i == (int)res.size() - 1]);
}
return 0;
}
|
P3517 WYK - Plot
简要题意: 给定 $n$ 个点，要求把点 $1 \sim n$ 分成不多于 $m$ 段区间，使得求出每段中点的最小圆覆盖的半径后，最大的半径最小。
数据规模: $1 \le m \le n \le 10^5$。
题解: 不会最小圆覆盖的请先右转。$n$ 个点的最小圆覆盖，期望时间复杂度为 $O(n)$。
套路地对答案进行二分。现在检验是否能将 $n$ 个点分成 $m$ 段区间，每段的最小圆覆盖半径 $\le rad$。
考虑对于一段的左端点 $L$，我们要快速求出最靠右的右端点 $R$，使得区间 $[L,R]$ 的最小圆覆盖半径 $\le rad$。然后另新的 $L' \leftarrow R + 1$，重复次操作 $m$ 次，判断是否覆盖了所有 $n$ 个点。
不妨再套一个二分。对于左端点 $L$，在区间 $[L,n]$ 中二分其右端点。每次二分，$O(mid - L)$ 地跑一遍最小圆覆盖，判断区间 $[L,mid]$ 是否合法。
但是算一算复杂度，发现检验一次 $rad$ 是否合法需要对 $m$ 个左端点进行二分，总的复杂度就变成了 $O(nm \log n)$，直接爆炸。
有没有更好的方法呢？考虑在内层的二分之前进行一次倍增，即找到一个 $k$ 使得 $R \in [L + 2^{k-1}, L + 2^k)$，再该区间进行内层的二分。
分析一下这个复杂度。令 $sz = R - L + 1$，倍增的复杂度为 $O(\sum_{i=0}^{k}2^i) = O(2^k)$。容易知道 $2^k$ 不超过目标区间长度 $sz$ 的 $2$ 倍，可以认为倍增的总复杂度为 $O(sz)$。而接下来的二分由于运行了 $O(\log sz)$ 次，每次检验又是 $O(sz)$，最终的复杂度就是 $O(sz \log sz)$。
由于 $\sum sz \le n$，因此一次对 $rad$ 的检验可以做到 $O(n \log n)$。加上外层的二分，程序的复杂度就是 $O(n \log^2 n)$。
不要使用 std::hypot ！这玩意运行时间是直接平方后 sqrt 的 $10$ 倍左右！
代码:
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
104
105
106
107
108
109
110
111
112
113
| using ll = long long;
const int N = 1e5 + 10;
const double eps = 1e-6;
int n, m, rps[N];
mt19937 rng(19260817);
inline int sgn(double x) {
if (abs(x) <= eps)
return 0;
return x < 0 ? -1 : 1;
}
struct point {
double x, y;
point() = default;
point(double x, double y) : x(x), y(y) {}
point operator+(const point &p) const { return {x + p.x, y + p.y}; }
point operator-(const point &p) const { return {x - p.x, y - p.y}; }
point operator*(const double &k) const { return {x * k, y * k}; }
point operator/(const double &k) const { return {x / k, y / k}; }
double operator*(const point &p) const { return x * p.y - y * p.x; }
} pt[N];
struct line {
point p, v;
line() = default;
line(point p, point v) : p(p), v(v) {}
};
inline double dist(const point &p1, const point &p2) {
return sqrt((p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y));
}
inline point intersect(const line &s1, const line &s2) {
double d = ((s2.p - s1.p) * s2.v) / (s1.v * s2.v);
return s1.p + s1.v * d;
}
inline line bisector(const point &p1, const point &p2) {
point p = (p1 + p2) / 2;
point v = point(p1.y - p2.y, p2.x - p1.x);
return line(p, v);
}
tuple<double, double, double> outer_circle(const point &p1, const point &p2,
const point &p3) {
point p = intersect(bisector(p1, p2), bisector(p1, p3));
return make_tuple(p.x, p.y, dist(p, p1));
}
tuple<double, double, double> circle_cover(int kl, int kr) {
static point ps[N];
int sz = kr - kl + 1;
copy(pt + kl, pt + kr + 1, ps + 1);
shuffle(ps + 1, ps + sz + 1, rng);
double x = ps[1].x, y = ps[1].y, r = 0;
for (int i = 1; i <= sz; ++i) {
if (sgn(dist(point(x, y), ps[i]) - r) <= 0)
continue;
x = ps[i].x, y = ps[i].y, r = 0;
for (int j = 1; j < i; ++j) {
if (sgn(dist(point(x, y), ps[j]) - r) <= 0)
continue;
x = (ps[i].x + ps[j].x) / 2;
y = (ps[i].y + ps[j].y) / 2;
r = dist(ps[i], ps[j]) / 2;
for (int k = 1; k < j; ++k)
if (sgn(dist(point(x, y), ps[k]) - r) > 0)
tie(x, y, r) = outer_circle(ps[i], ps[j], ps[k]);
}
}
return make_tuple(x, y, r);
}
bool check(double rad) {
int num = 0;
for (int i = 1; i <= n; i = rps[i] + 1) {
int l = n, r = n, res = n;
for (int k = 2;; k <<= 1) {
int kr = min(n, i + k - 1);
if (sgn(get<2>(circle_cover(i, kr)) - rad) > 0) {
l = i + (k >> 1), r = kr, res = i + (k >> 1) - 1;
break;
}
if (kr == n)
break;
}
while (l <= r) {
int mid = (l + r) >> 1;
if (sgn(get<2>(circle_cover(i, mid)) - rad) <= 0) {
l = mid + 1, res = mid;
} else {
r = mid - 1;
}
}
rps[i] = res;
if (++num > m)
return false;
}
return true;
}
signed main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i)
scanf("%lf%lf", &pt[i].x, &pt[i].y);
double l = 0, r = 4e6;
while (r - l > eps) {
double mid = (l + r) / 2;
(check(mid) ? r : l) = mid;
}
check(r);
vector<pair<double, double>> ans;
for (int i = 1; i <= n; i = rps[i] + 1) {
auto res = circle_cover(i, rps[i]);
ans.push_back({get<0>(res), get<1>(res)});
}
printf("%.8lf\n", r);
printf("%lu\n", ans.size());
for (auto p : ans)
printf("%.8lf %.8lf\n", p.first, p.second);
return 0;
}
|
P3518 SEJ - Strongbox
简要题意: 有一个密码箱，$0$ 到 $n-1$ 中的某些整数是它的密码。且满足：若 $a$ 和 $b$ 是它的密码，则 $(a+b)\bmod n$ 也是它的密码（$a$，$b$ 可以相等）。某人试了 $k$ 次密码，前 $k-1$ 次都失败了，最后一次成功了。问该密码箱最多有多少种不同的密码。
数据规模: $1 \le k \le 250\ 000, \ k \le n \le 10^{14}$。
题解: 把题意转化一下，相当于求 $\bmod n$ 加法下的群 $G$ 的一个子群 $G'$，满足 $a_1,\cdots,a_{k-1}$ 都不在群中，而 $a_k$ 在群中。
若 $v$ 在群里，则 $\gcd(v,n)$ 也在群里，所有 $\lt n$ 且为 $\gcd(v,n)$ 倍数的数也在群里。容易通过裴蜀定理证明。
假设 $G'$ 中最小的数为 $mn$，则不同的密码种类为 $\frac{n}{mn}$。为了使得密码种类尽量多，需要使得 $mn$ 尽量小。令 $d = \gcd(a_k,n)$，显然 $mn$ 必须为 $d$ 的因数。并且对于 $i \neq k$，$mn$ 不能是 $\gcd(a_i,n)$ 的因数。
考虑列出 $d$ 的所有因数，对于 $i \neq k$，将 $\gcd(a_i,d)$ 标记。对于已经标记的数 $v$，枚举 $v$ 的质因子 $p$，将 $\frac{v}{p}$ 标记。可以使用 bfs 来处理。
关于答案，直接找到最小的未被标记的因数 $mn$，输出 $\frac{n}{nm}$ 即可。至于复杂度，精细实现可以做到 $O(\sqrt n + k \log n + d(n)\omega(n))$，其中 $d(n)$ 表示 $n$ 的因子个数，$\omega(n)$ 表示 $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
| using ll = long long;
const int N = 3e5 + 10;
int k;
ll n, d, a[N];
vector<ll> pri, fac;
ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
vector<ll> primes(ll n) {
vector<ll> res;
for (ll i = 2; i * i <= n; ++i)
if (n % i == 0) {
while (n % i == 0)
n /= i;
res.push_back(i);
}
if (n > 1)
res.push_back(n);
return res;
}
vector<ll> factors(ll n) {
vector<ll> res;
for (ll i = 1; i * i <= n; ++i)
if (n % i == 0) {
res.push_back(i);
if (i * i != n)
res.push_back(n / i);
}
return res;
}
signed main() {
read(n), read(k);
for (int i = 1; i <= k; ++i)
read(a[i]);
d = gcd(n, a[k]);
pri = primes(d), fac = factors(d);
sort(fac.begin(), fac.end());
vector<bool> vis(fac.size());
for (int i = 1; i < k; ++i) {
ll t = gcd(d, a[i]);
int p = lower_bound(fac.begin(), fac.end(), t) - fac.begin();
vis[p] = true;
}
queue<ll> que;
for (int i = 0; i < (int)fac.size(); ++i)
if (vis[i])
que.push(fac[i]);
while (!que.empty()) {
ll u = que.front();
que.pop();
for (auto p : pri) {
if (u % p != 0)
continue;
ll v = u / p;
int k = lower_bound(fac.begin(), fac.end(), v) - fac.begin();
if (!vis[k])
vis[k] = true, que.push(v);
}
}
for (int i = 0; i < (int)fac.size(); ++i)
if (!vis[i])
return write(n / fac[i]), putchar('\n'), 0;
return assert(0), 0;
}
|
P3519 ROZ - Difference
简要题意: 给一个字符串，求其中的一个子串，使得子串中能出现次数最多的字符与出现次数最少的字符的出现次数之差最大，求最大的差。
数据规模: $1 \le n \le 10^6$。
题解: 容易发现，假设子串中出现次数最多和最少的字符分别是 $a$ 和 $b$，那么非 $a$ 和 $b$ 的字符对答案的贡献可以忽略不计。
考虑枚举出现次数最多和最少的字符 $a,b$。将字符 $a$ 的权值设为 $1$，字符 $b$ 的权值设为 $-1$，其他字符的权值设为 $0$，字符 $a,b$ 对答案的贡献转化为序列的最大子段和。
需要注意的是，这里的最大子段和需要保证其中既出现 $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
24
25
26
27
28
29
30
31
| using ll = long long;
const int N = 1e6 + 10, M = 26;
int n, a[N];
char str[N];
vector<int> pos[M];
signed main() {
read(n), scanf("%s", str + 1);
for (int i = 1; i <= n; ++i)
a[i] = str[i] - 'a', pos[a[i]].push_back(i);
int ans = 0;
for (int c1 = 0; c1 < 26; ++c1)
for (int c2 = 0; c2 < 26; ++c2) {
int sz1 = pos[c1].size(), sz2 = pos[c2].size();
vector<int> vec(sz1 + sz2), pre(sz1 + sz2), prf(sz1 + sz2);
merge(pos[c1].begin(), pos[c1].end(), pos[c2].begin(), pos[c2].end(),
vec.begin());
for (int i = 0; i < sz1 + sz2; ++i)
vec[i] = (a[vec[i]] == c1) ? 1 : -1;
for (int i = 0; i < sz1 + sz2; ++i)
pre[i] = (i && vec[i] == vec[i - 1]) ? pre[i - 1] : i;
for (int i = 0; i < sz1 + sz2; ++i)
prf[i] = i ? prf[i - 1] + vec[i] : vec[i];
for (int i = 0, j = 0, mn = 1e9; i < sz1 + sz2; ++i) {
while (j < pre[i])
mn = min(mn, j ? prf[j - 1] : 0), ++j;
ans = max(ans, prf[i] - mn);
}
}
write(ans), putchar('\n');
return 0;
}
|
P3520 SMI - Garbage
简要题意: 某国的街道是一张 $n$ 个点和 $m$ 条边的无向图，某些道路很脏，需要清理。清理车的路径是一个简单环，清理完后，原本脏的街道变干净，干净的街道变脏。给出道路的初始状态和结束状态，构造一个合法的清理车方案，要求清理车数量 $\le 5m$。
数据规模: $1 \le n \le 10^5, \ 1 \le m \le 10^6$。
题解: 简直是[BalticOI 2014] 老年邮递员的翻版。
先考虑对原图进行一些转化。如果某条边的初始状态和结束状态相同，那么我们可以忽略这条边。
这是因为，如果这条边被某些简单环所包含，其被包含的次数一定是偶数。将这偶数个环两两配对，一定能够调整得到两个不包含这条边的简单环。
忽略这些边后，我们需要将残余的图分成若干个环，这可以使用欧拉回路。具体地，先对于每个连通块，求出一条欧拉回路，按照顺序遍历欧拉回路上的点。若某个点出现了多次，则将相邻两次出现位置之间的部分递归提取出来，作为新的回路，直到回路中没有重复的点出现即可认为是一个简单环。由此可以将整张图划分为若干个简单环。
代码:
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
| using ll = long long;
const int N = 1e5 + 10, M = 1e6 + 10;
int n, m, top, num[N], deg[N], sta[M * 2];
bool vis[N], ban[M * 2];
struct linked_list {
int etot = 1, hd[N], to[M * 2], nxt[M * 2];
void add_edge(int u, int v) {
to[++etot] = v, nxt[etot] = hd[u], hd[u] = etot;
to[++etot] = u, nxt[etot] = hd[v], hd[v] = etot;
}
} g;
void dfs(int u) {
vis[u] = 1;
for (int &i = g.hd[u]; i; i = g.nxt[i])
if (!ban[i])
ban[i] = ban[i ^ 1] = 1, dfs(g.to[i]);
sta[++top] = u;
}
signed main() {
read(n), read(m);
for (int i = 1, u, v, s, t; i <= m; ++i) {
read(u), read(v), read(s), read(t);
if (s != t)
g.add_edge(u, v), ++deg[u], ++deg[v];
}
for (int i = 1; i <= n; ++i)
if (deg[i] & 1)
puts("NIE"), exit(0);
vector<vector<int>> ans;
for (int s = 1; s <= n; ++s)
if (!vis[s]) {
int cur = 0;
top = 0, dfs(s);
static int tmp[M * 2];
for (int i = 1; i <= top; ++i)
if (!num[sta[i]]) {
tmp[++cur] = sta[i], ++num[sta[i]];
} else {
vector<int> vec;
vec.push_back(sta[i]);
while (tmp[cur] != sta[i])
vec.push_back(tmp[cur]), --num[tmp[cur--]];
ans.push_back(vec);
}
}
printf("%lu\n", ans.size());
for (auto &vec : ans) {
printf("%lu", vec.size());
for (auto p : vec)
printf(" %d", p);
printf(" %d\n", vec[0]);
}
return 0;
}
|
P3521 ROT - Tree Rotations
简要题意: 给定一个包含 $n$ 个叶节点的二叉树，非叶子结点一定有 $2$ 个儿子，叶节点的权值构成 $1 \sim n$ 的排列。可以任意交换每个非叶子结点的左右儿子，要求最终先序遍历叶节点得到的权值组成的排列中逆序对数量最小。求逆序对数量。
数据规模: $2 \le n \le 2 \times 10^5$。
题解: 显然，将某个非叶子节点的左右儿子交换，不会改变该子树内到其他子树内的逆序对数，同时也不会改变左右儿子对应的子树内的逆序对数。
因此考虑依次对于每个非叶子节点，确定其是否交换，将左右子树的逆序对数量加入答案。假设当前节点为 $u$，左右儿子分别为 $ls(u)$ 和 $rs(u)$，问题转化为求出 $x \in subtree(ls(u)), \ y \in subtree(rs(u)), \ a[x] > a[y]$ 的点对 $(x, y)$ 数量。
可以使用启发式合并，枚举左右儿子中 $size$ 更小的，使用树状数组计算逆序对数，做到 $O(n \log^2 n)$。或使用权值线段树合并做到 $O(n \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
| using ll = long long;
const int N = 2e6 + 10;
int n, cnt, tot, ls[N], rs[N], st[N], ed[N], id[N], siz[N], val[N];
ll answ;
struct binary_indexed_tree {
int bit[N];
void add(int x, int v) {
for (int i = x; i <= n; i += i & -i)
bit[i] += v;
}
int sum(int x) const {
int ret = 0;
for (int i = x; i; i -= i & -i)
ret += bit[i];
return ret;
}
int ask(int l, int r) const { return sum(r) - sum(l - 1); }
} bit;
int dfs1() {
int p = ++tot;
int x;
read(x);
if (x != 0) {
val[p] = x, siz[p] = 1;
} else {
ls[p] = dfs1(), rs[p] = dfs1();
siz[p] = siz[ls[p]] + siz[rs[p]];
}
return p;
}
void dfs2(int p) {
if (siz[p] == 1) {
id[st[p] = ed[p] = ++cnt] = val[p];
return bit.add(val[p], 1), void();
}
if (siz[ls[p]] < siz[rs[p]])
swap(ls[p], rs[p]);
ll rev = 0;
dfs2(rs[p]);
for (int i = st[rs[p]]; i <= ed[rs[p]]; ++i)
bit.add(id[i], -1);
dfs2(ls[p]);
st[p] = st[rs[p]], ed[p] = ed[ls[p]];
for (int i = st[rs[p]]; i <= ed[rs[p]]; ++i)
rev += bit.ask(id[i] + 1, n);
answ += min(rev, 1LL * siz[ls[p]] * siz[rs[p]] - rev);
for (int i = st[rs[p]]; i <= ed[rs[p]]; ++i)
bit.add(id[i], 1);
}
signed main() {
read(n), dfs2(dfs1());
write(answ), putchar('\n');
return 0;
}
|
P3522 TEM - Temperature
简要题意: 某国进行了连续 $n$ 天的温度测量，测量存在误差，测量结果是第 $i$ 天温度在 $[l_i,r_i]$ 范围内。求最长的连续的一段，满足该段内可能温度不降。
数据规模: $1 \le n \le 10^6, \ -10^9 \le l_i \le r_i \le 10^9$。
题解: 考虑一段区间 $[L,R]$，判断这段区间是否能够满足温度不降。从 $L$ 到 $R$ 枚举每一天 $i$，并贪心地让这一天的温度尽量小。容易发现第 $i$ 天的温度即为 $\max\limits_{j=L}^{i}l_j$。
因此，区间 $[L,R]$ 能够满足温度不降，当且仅当对于每个前缀 $[L,i]$，都满足前缀 $\max\limits_{j=L}^{i}l_j \le r_i$。那么考虑枚举右端点 $R$，用双指针和单调队列维护最靠左的左端点 $L$，统计答案，即可做到线性。
代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| using ll = long long;
const int N = 1e6 + 10;
int n, ls[N], rs[N], que[N];
signed main() {
read(n);
for (int i = 1; i <= n; ++i)
read(ls[i]), read(rs[i]);
int hd = 1, tl = 0, ans = 0;
for (int i = 1, p = 1; i <= n; ++i) {
while (hd <= tl && ls[que[tl]] <= ls[i])
--tl;
que[++tl] = i;
while (ls[que[hd]] > rs[i])
if (que[hd] == p++)
++hd;
ans = max(ans, i - p + 1);
}
write(ans), putchar('\n');
return 0;
}
|
P3523 DYN - Dynamite
简要题意: 给一棵树，树上有一些关键节点，要求你选 $m$ 个点，第 $i$ 个关键节点到这些点中每个点距离的最小值记为 $dis_i$，记这全部 $dis$ 的最大值为 $k$，现在要使 $k$ 最小，求这个 $k$。
数据规模: $1 \le m \le n \le 3 \times 10^5$。
题解: 容易想到进行答案的二分。二分最大值 $k$，问题转化为使用 $m$ 个点，每个点能够覆盖周围距离 $\le k$ 的所有点，判断是否能够覆盖所有关键点。
进一步地，我们希望计算出要覆盖所有关键点，至少需要使用多少个点，这个问题比较类似[POI2009] GAS，只不过是个超级弱化版。
考虑进行树上的贪心。对于每个节点 $u$，维护 $f_u$ 表示 $u$ 的子树内，未被覆盖的关键点中，到 $u$ 的最长距离。维护 $g_u$ 表示 $u$ 的子树内，被选出的节点中，到 $u$ 的最短距离。容易得到如下转移：
$$
\begin{aligned}
f_u =& \max_{v \in son(u)} f_v + 1 \\
g_u =& \min_{v \in son(u)} g_v + 1 \\
\end{aligned}
$$
递归考虑子树。现在考虑点 $u$ 的情况：
若 $u$ 为关键点，则更新 $f_u \leftarrow \max(f_u, 0)$。
使用 $u$ 子树内选出的节点覆盖剩余关键点，即如果 $f_u + g_u \le k$，则 $f_u \leftarrow -\infty$（与 $f_u = 0$ 进行区分）。
若上一步操作后，子树内仍存在关键点使得 $f_u = k$，则不得不选择 $u$ 这个节点。之后将 $f_u \leftarrow -\infty, \ g_u \leftarrow 0$。同时开一个全局变量 $num$ 表示使用的关键点数量，将其 $+1$。
最终，递归结束后，特判 $u=1$ 的情况，若 $f_u \neq -\infty$，则存在关键点未覆盖，将 $num \leftarrow num + 1$。
然后在外层的二分中，只需要判断是否 $num \le m$ 即可。时间复杂度 $O(n \log n)$，使用 vector 存图会被卡常。
代码:
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
| using ll = long long;
const int N = 3e5 + 10, INF = 0x3f3f3f3f;
int n, m, k, num, d[N], dp1[N], dp2[N];
struct linked_list {
int etot, hd[N], to[N * 2], nxt[N * 2];
void add_edge(int u, int v) {
to[++etot] = v, nxt[etot] = hd[u], hd[u] = etot;
to[++etot] = u, nxt[etot] = hd[v], hd[v] = etot;
}
} g;
void dfs(int u, int f) {
dp1[u] = -INF, dp2[u] = INF;
for (int i = g.hd[u]; i; i = g.nxt[i]) {
int v = g.to[i];
if (v == f)
continue;
dfs(v, u);
dp1[u] = max(dp1[u], dp1[v] + 1);
dp2[u] = min(dp2[u], dp2[v] + 1);
}
if (d[u])
dp1[u] = max(dp1[u], 0);
if (dp1[u] + dp2[u] <= k)
dp1[u] = -INF;
if (dp1[u] == k)
++num, dp1[u] = -INF, dp2[u] = 0;
}
bool check(int lim) {
k = lim, num = 0, dfs(1, 0);
return num + (dp1[1] >= 0) <= m;
}
signed main() {
read(n), read(m);
for (int i = 1; i <= n; ++i)
read(d[i]);
for (int i = 1, u, v; i < n; ++i)
read(u), read(v), g.add_edge(u, v);
int l = 0, r = n, ans = n;
while (l <= r) {
int mid = (l + r) >> 1;
if (check(mid)) {
r = mid - 1, ans = mid;
} else {
l = mid + 1;
}
}
write(ans), putchar('\n');
return 0;
}
|
P3524 IMP - Party
简要题意: 给定一张 $n$ 个点 $m$ 条边的图，其中 $n \equiv 0 \pmod{3}$。保证存在一个大小为 $\frac{2}{3}n$ 的团，要求输出一个大小为 $\frac{1}{3}n$ 的团。
数据规模: $3 \le n \le 3000, \ \frac{\frac{2}{3}n(\frac{2}{3}n-1)}{2} \le m \le \frac{n(n-1)}{2}$。
题解: 注意到，若某个点对 $(u, v) \notin E$，则 $u$ 和 $v$ 至少有 $1$ 个不在团中。
枚举不在边集 $E$ 中的点对，将这两个点删去。重复上述操作 $\frac{1}{3}n$ 次，保留下来的 $\frac{1}{3}n$ 个点一定形成一个团。
暴力枚举点对，判断并删除，复杂度 $O(n^2)$。
代码:
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
| using ll = long long;
const int N = 3e3 + 10;
int n, m;
bool rem[N], g[N][N];
signed main() {
read(n), read(m);
for (int i = 1, u, v; i <= m; ++i)
read(u), read(v), g[u][v] = g[v][u] = 1;
int k = n / 3, num = 0;
for (int i = 1; i <= n; ++i) {
for (int j = i + 1; j <= n; ++j) {
if (rem[i] || rem[j])
continue;
if (!g[i][j]) {
rem[i] = rem[j] = 1;
if (++num == k)
break;
}
}
if (num == k)
break;
}
vector<int> ans;
for (int i = 1; i <= n; ++i)
if (!rem[i])
ans.push_back(i);
for (int i = 0; i < k; ++i)
write(ans[i]), putchar(" \n"[i == k - 1]);
return 0;
}
|
P3525 INS - Inspection
简要题意: 给定一棵 $n$ 个节点的树，对于每个节点 $i$，求出是否存在一个其余 $n-1$ 个点的排列，使得排列中相邻两个点到 $i$ 的路径没有重复部分。如果有，求出按照排列顺序从 $i$ 出发，依次前往 $n-1$ 个点，最后不需要回到 $i$，这样一条非简单路径长度的最小值。
数据规模: $1 \le n \le 10^6$。
题解: 判断 $i$ 是否有合法的路径，只需要判断以 $i$ 为根时是否有子树大小 $> \frac{n}{2}$。
路径长度的最小值，在大部分情况下的答案都是 $2dis_i - mxd_i$，其中 $dis_i$ 表示所有点到 $i$ 的距离总和，$mxd_i$ 表示所有点到 $i$ 距离的最大值，使用换根 dp 轻易求出。
考虑特殊情况下，即有某棵子树大小 $siz = \lfloor \frac{n}{2} \rfloor$。这时最后一个访问到的点所在的子树只有最多 $2$ 种，枚举 $i$ 周围的点，找到最后一个访问的点可能存在的子树 $subtree(v)$，利用换根 dp 两次 dfs 得到的数组，简单分讨一下 $v$ 是否为 $i$ 的父亲即可。
代码:
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
| using ll = long long;
const int N = 1e6 + 10;
int n, siz[N], mxd[N], len1[N], len2[N];
ll dis1[N], dis2[N];
vector<int> g[N];
void dfs1(int u, int f) {
siz[u] = 1;
for (auto v : g[u]) {
if (v == f)
continue;
dfs1(v, u), siz[u] += siz[v];
dis1[u] += dis1[v] + siz[v];
if (len1[v] + 1 > len1[u]) {
len2[u] = len1[u], len1[u] = len1[v] + 1;
} else if (len1[v] + 1 > len2[u]) {
len2[u] = len1[v] + 1;
}
}
}
void dfs2(int u, int f) {
if (!f)
dis2[u] = dis1[u];
for (auto v : g[u]) {
if (v == f)
continue;
int tmp = (len1[u] == len1[v] + 1 ? len2[u] : len1[u]);
mxd[v] = max(mxd[u], tmp) + 1;
dis2[v] = dis2[u] + (n - 2 * siz[v]);
dfs2(v, u);
}
}
signed main() {
read(n);
for (int i = 1, u, v; i < n; ++i)
read(u), read(v), g[u].push_back(v), g[v].push_back(u);
dfs1(1, 0), dfs2(1, 0);
for (int i = 1; i <= n; ++i) {
int mx = 0;
for (auto v : g[i]) {
int sz = siz[i] > siz[v] ? siz[v] : n - siz[i];
mx = max(mx, sz);
}
if (mx > (n >> 1)) {
puts("-1");
} else if (mx == (n >> 1)) {
int d = 0;
for (auto v : g[i]) {
int sz = siz[i] > siz[v] ? siz[v] : n - siz[i];
if (sz != mx)
continue;
if (siz[i] > siz[v]) {
d = max(d, len1[v] + 1);
} else {
d = max(d, mxd[i]);
}
}
write(2 * dis2[i] - d), putchar('\n');
} else {
int d = max(mxd[i], len1[i]);
write(2 * dis2[i] - d), putchar('\n');
}
}
return 0;
}
|
P3527 MET - Meteors
简要题意: 有 $n$ 个国家和一颗星球，星球的轨道为一个长 $m$ 的环，第 $i$ 个位置有第 $a_i$ 个国家的太空站。给定 $k$ 次陨石雨的情况，每次对于环上的一个区间，向区间中的每个太空站提供 $a_i$ 单位的陨石样本。第 $i$ 个成员国希望能够收集 $p_i$ 单位的陨石样本。判断对于每个国家，需要在第几次陨石雨之后，才能收集足够的陨石。
数据规模: $1 \le n,m,k \le 3 \times 10^5, \ 1 \le p_i,a_i \le 10^9$。
题解: 考虑只有 $1$ 个国家应该怎么做。显然直接二分 + 判断，用一棵树状数组维护当前时刻每个太空站的样本数量。
对于 $n$ 个国家，可以类似地进行整体二分。对于当前陨石雨的分治区间 $[L,R]$，将 $[1,mid]$ 之间的陨石雨使用树状数组维护出来，然后对当前区间中的国家依次判断进入左区间还是右区间。
需要注意的是，处理完分治区间 $[L,R]$ 后，需要将 $[L,R]$ 之间的陨石雨全都加入到树状数组中，这样在下一个分治区间求 $[1,mid]$ 的陨石雨时，只需要枚举 $[L,mid]$ 中的陨石雨并加入，复杂度可以得到保证。具体实现看代码。
分析一下复杂度，发现每个样本/国家会在 $O(\log )$ 个分治区间中被加入/查询。查询国家时暴力枚举该国家对应的太空站，实际上复杂度是均摊的 $O(m \log n)$。因此，假设 $n,m,k$ 同阶，则最终的时间复杂度为 $O(n \log^2 n)$。
代码细节上，还有一个需要注意的地方。虽然每个太空站的陨石数量是 $O(\sum a_i)$ 量级的，可以使用 long long 储存，但倘若将某个国家的所有太空站陨石数加起来，就是 $O(m \sum a_i)$ 量级的了，无法使用 long long 储存。关于这一点，固然可以使用 __int128_t，但也可以在这个值超过 $p_i$ 时直接 break 掉，就能避免掉这种 corner case 了。
代码:
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
| using ll = long long;
const int N = 3e5 + 10;
int n, m, q, id[N], ls[N], rs[N], val[N], ans[N], need[N], tmpl[N], tmpr[N];
vector<int> vec[N];
struct binary_indexed_tree {
ll bit[N];
void add(int x, ll v) {
for (int i = x; i <= m; i += i & -i)
bit[i] += v;
}
ll sum(int x) const {
ll ret = 0;
for (int i = x; i; i -= i & -i)
ret += bit[i];
return ret;
}
} bit;
void update(int l, int r, int v) {
if (l <= r) {
bit.add(l, v);
bit.add(r + 1, -v);
} else {
bit.add(l, v);
bit.add(m + 1, -v);
bit.add(1, v);
bit.add(r + 1, -v);
}
}
void solve(int l, int r, int ql, int qr) {
if (ql == qr) {
update(ls[ql], rs[ql], val[ql]);
for (int i = l; i <= r; ++i) {
ll sum = 0;
for (auto p : vec[id[i]])
if ((sum += bit.sum(p)) >= need[id[i]])
break;
if (sum >= need[id[i]])
ans[id[i]] = ql;
}
return;
}
int cntl = 0, cntr = 0;
int mid = (ql + qr) >> 1;
for (int i = ql; i <= mid; ++i)
update(ls[i], rs[i], val[i]);
for (int i = l; i <= r; ++i) {
ll sum = 0;
for (auto p : vec[id[i]])
if ((sum += bit.sum(p)) >= need[id[i]])
break;
if (sum >= need[id[i]]) {
tmpl[++cntl] = id[i];
} else {
tmpr[++cntr] = id[i];
}
}
for (int i = ql; i <= mid; ++i)
update(ls[i], rs[i], -val[i]);
copy(tmpl + 1, tmpl + cntl + 1, id + l);
copy(tmpr + 1, tmpr + cntr + 1, id + l + cntl);
solve(l, l + cntl - 1, ql, mid);
solve(l + cntl, r, mid + 1, qr);
}
signed main() {
read(n), read(m);
for (int i = 1, x; i <= m; ++i)
read(x), vec[x].push_back(i);
for (int i = 1; i <= n; ++i)
read(need[i]);
read(q);
for (int i = 1; i <= q; ++i)
read(ls[i]), read(rs[i]), read(val[i]);
iota(id + 1, id + n + 1, 1), solve(1, n, 1, q);
for (int i = 1; i <= n; ++i)
if (!ans[i]) {
puts("NIE");
} else {
write(ans[i]), putchar('\n');
}
return 0;
}
|
P3528 PAT - Sticks
简要题意: 给出若干木棍，每根木棍有特定的颜色和长度。找到三条颜色不同的木棍构成一个三角形。
数据规模: 木棍总数 $3 \le n \le 10^6$，颜色数 $3 \le k \le 50$。
题解: 假设 $3$ 根木棍的长度分别为 $a,b,c$，其中 $a \le b \le c$。
枚举 $b$。为了尽量满足 $a + b > c$，我们希望 $a$ 尽量大且 $c$ 尽量小。
将所有木棍按照长度排序得到数组 $len$。如果不考虑颜色不同的限制，那么当 $b = len_i$ 时，取 $a = len_{i-1}, c = len_{i+1}$ 最优。要求颜色不同时，一个套路是对于前缀 $[1,i-1]$ 和后缀 $[i+1,n]$，维护颜色不同的 $3$ 个最大次大/最小次小值，$3 \times 3$ 地枚举一下合并起来。显然，不在这 $3$ 个值中的 $a$ 和 $c$ 一定不会更优。
总复杂度关于 $n$ 线性，有个 $9$ 倍的常数。
代码:
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
| using ll = long long;
using pii = pair<int, int>;
#define fi first
#define se second
const int N = 1e6 + 10;
int n, k, pre[N], nxt[N];
pii a[N];
struct node {
pii val[3];
void upd_min(pii p) {
for (int i = 0; i < 3; ++i) {
if (p.fi < val[i].fi)
swap(p, val[i]);
if (p.se == val[i].se)
break;
}
}
void upd_max(pii p) {
for (int i = 0; i < 3; ++i) {
if (p.fi > val[i].fi)
swap(p, val[i]);
if (p.se == val[i].se)
break;
}
}
} prf[N], suf[N];
bool check(pii x, pii y, pii z) {
if (x.se == y.se || x.se == z.se || y.se == z.se)
return false;
return x.fi + y.fi > z.fi;
}
void print(pii x, pii y, pii z) {
printf("%d %d %d %d %d %d\n", x.se, x.fi, y.se, y.fi, z.se, z.fi);
}
signed main() {
read(k);
for (int i = 1; i <= k; ++i) {
int m, x;
read(m);
for (int j = 1; j <= m; ++j)
read(x), a[++n] = {x, i};
}
sort(a + 1, a + n + 1);
fill(prf[0].val, prf[0].val + 3, pii(-2e9, 0));
fill(suf[n + 1].val, suf[n + 1].val + 3, pii(2e9, 0));
for (int i = 1; i <= n; ++i)
prf[i] = prf[i - 1], prf[i].upd_max(a[i]);
for (int i = n; i >= 1; --i)
suf[i] = suf[i + 1], suf[i].upd_min(a[i]);
for (int i = 2; i < n; ++i)
for (int j = 0; j < 3; ++j)
for (int k = 0; k < 3; ++k) {
if (!prf[i - 1].val[j].se)
continue;
if (!suf[i + 1].val[k].se)
continue;
if (check(prf[i - 1].val[j], a[i], suf[i + 1].val[k]))
print(prf[i - 1].val[j], a[i], suf[i + 1].val[k]), exit(0);
}
return puts("NIE"), 0;
}
|
P3529 PRO - Programming Contest
简要题意: $n$ 个人 $m$ 个题目，每个题要 $r$ 分钟完成。比赛有 $t$ 分钟。给出每个人会做哪些题目，请你安排一个每个人在什么时候做什么题目，使得做出来的题目数最多。在做题数一样多的情况下，罚时尽量小。输出方案。
数据规模: $1 \le n,m \le 500, \ 1 \le r,t \le 10^6$。
题解: 这么小的数据范围，再加上奇怪的限制以及输出方案，这不一眼网络流？
看完题立马想到了[NOI2012] 美食节。实际上，由于每个人做每道题花费的时间相同，所以这道题简直就是那道题的超级弱化版（谁搬谁的还说不定呢）。
考虑将一个人做的题对罚时的贡献拆开。假设一个人做了 $k$ 道题，罚时则为 $(1 + \cdots + k) \times r$。因此，只需让一个人做的第 $i$ 道题罚时为 $i \times r$ 即可满足。
套路地，对于每个人 $i$ 和每道题 $j$ 分别新建点 $p_i$ 和 $q_j$。考虑费用流模型，建图方式如下：
- 若 $i$ 会做 $j$ 这道题，连 $p_i$ 到 $q_j$ 的边，流量为 $1$，费用为 $0$。
- $q_j$ 向汇点 $t$ 连边，流量为 $1$，费用为 $0$。
- 源点 $s$ 向 $p_i$ 连 $\lfloor\frac{t}{r}\rfloor$ 条边。对于第 $i$ 条边，流量为 $1$，费用为 $i \times r$。理由上面已经说过了。
这样建图，边的数量是 $O(n \times (m + \lfloor \frac{t}{r} \rfloor))$ 的，跑不过去。
注意到我们只会在流完 $i \times r$ 的边后，才会去流费用为 $(i + 1) \times r$ 的边。可以进行动态增流的网络流，即每次 dfs 增广完访问已经流满的 $i \times r$ 的边，并在对应的位置加入 $(i + 1) \times r$ 的边。注意到流量 $flow \le m$，所以总边数为 $O(n \times m)$ 级别。
由于该网络同时为二分图，所以使用 dinic 跑费用流，总时间复杂度为 $O((n \times m) \sqrt{n + m})$。
注意，用 EK 实现的网络流会被卡常，原因是第一次增广时多路增广效率优势会很明显。
代码:
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
| using ll = long long;
const int N = 505, INF = 0x3f3f3f3f;
int n, m, k, lim, tot, cnt[N];
namespace flow {
const int N = 1e3 + 10, M = 3e5 + 10;
struct edge {
int v, f, w, nxt;
} e[M * 2];
int n, s, t, etot, flow, cost, head[N], cur[N], dis[N];
bool vis[N];
void clear(int m) { n = m, s = ++n, t = ++n, etot = 1; }
void add_edge(int u, int v, int f, int w) {
e[++etot] = {v, f, w, head[u]}, head[u] = etot;
e[++etot] = {u, 0, -w, head[v]}, head[v] = etot;
}
bool spfa() {
static int que[N];
int hd = 0, tl = 0;
fill(dis + 1, dis + n + 1, INF);
que[tl++] = s, dis[s] = 0;
while (hd != tl) {
int u = que[hd++];
vis[u] = 0, hd == N && (hd = 0);
for (int i = cur[u] = head[u]; i; i = e[i].nxt)
if (e[i].f && dis[e[i].v] > dis[u] + e[i].w) {
dis[e[i].v] = dis[u] + e[i].w;
if (!vis[e[i].v])
que[tl++] = e[i].v, vis[e[i].v] = 1, tl == N && (tl = 0);
}
}
return dis[t] != INF;
}
int dfs(int u, int mx) {
if (vis[u])
return 0;
if (u == t || !mx)
return mx;
int ret = 0;
vis[u] = 1;
for (int &i = cur[u]; i; i = e[i].nxt) {
if (dis[e[i].v] != dis[u] + e[i].w)
continue;
int tmp = dfs(e[i].v, min(mx, e[i].f));
e[i].f -= tmp, e[i ^ 1].f += tmp, mx -= tmp, ret += tmp,
cost += e[i].w * tmp;
if (u == s && tmp && k * (cnt[e[i].v] + 1) <= lim)
add_edge(s, e[i].v, 1, k * ++cnt[e[i].v]);
if (!mx)
break;
}
return vis[u] = 0, ret;
}
void dinic() {
flow = cost = 0;
while (spfa())
flow += dfs(s, INF);
}
} // namespace flow
signed main() {
read(n), read(m), read(k), read(lim), read(tot);
flow::clear(n + m);
for (int i = 1, u, v; i <= tot; ++i)
read(u), read(v), flow::add_edge(u, v + n, 1, 0);
for (int i = 1; i <= n; ++i)
if (k * (cnt[i] + 1) <= lim)
flow::add_edge(flow::s, i, 1, k * ++cnt[i]);
for (int i = 1; i <= m; ++i)
flow::add_edge(i + n, flow::t, 1, 0);
flow::dinic();
printf("%d %d\n", flow::flow, flow::cost);
for (int i = 1; i <= n; ++i) {
vector<int> vec;
for (int j = flow::head[i]; j; j = flow::e[j].nxt)
if (flow::e[j].v != flow::s && flow::e[j ^ 1].f)
vec.push_back(flow::e[j].v - n);
for (int j = 0; j < (int)vec.size(); ++j)
printf("%d %d %d\n", i, vec[j], j * k);
}
return 0;
}
|
最后修改于 2025-07-05
Git 版本:
de2abab