Bzoj2066 Gra
简要题意: 长度为 $m$ 的整数数轴上有 $n$ 个坐标不同的棋子，保证棋子初始时不在 $m$，两人轮流移动，每次将一个棋子移动到右边第一个空位置上，将棋子移动到 $m$ 的人胜利，问先手必胜时第一步有多少种移动方法。
数据规模: $n \le 10^6,\ m \le 10^9$。
题解: 先考虑从结束状态往前推。显然当 $m-1$ 处有棋子时先手必胜，所以两人都不希望自己将棋子移动到 $m-1$。如果 $[m-n-1,m-2]$ 内均有棋子，则下一步对方不得不将棋子移动到 $m-1$，故此时先手必胜。于是胜利条件转化为将所有棋子移动到 $[m-n-1,m-2]$。
下面考虑对每轮的操作进行转化。注意到每次操作相当于选出一些连续棋子的后缀，将其整体右移一格。考虑设 $num_x$ 表示右边有 $x$ 个空格子的棋子数量，即选择 $k \in [1,num_x]$，并对其进行 $num_x \leftarrow num_x - k$ 和 $num_{x-1} \leftarrow num_{x-1}+k$ 的操作。这是个非常经典的阶梯 Nim 博弈，其 SG 函数为所有奇数 $x$ 的 $num_x$ 的异或和。
预处理当前状态的 SG 函数，枚举第一步的移动并简单维护下新的 SG 函数即可。
代码:
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;
int n, m, tot, cur, ans, a[N], num[N];
unordered_map<int, int> mp;
signed main() {
read(m), read(n);
for (int i = 1; i <= n; ++i)
read(a[i]);
while (tot < n && a[n - tot] == m - tot - 1)
++tot;
if (tot)
return write(tot), putchar('\n'), 0;
for (int i = 1; i <= n; ++i)
++mp[num[i] = m - a[i] - 2 - n + i];
for (auto p : mp)
if (p.first & 1)
cur ^= p.second;
for (auto p : mp) {
int id = p.first, cx = p.second;
int cy = mp.count(id - 1) ? mp[id - 1] : 0;
if (id == 0)
continue;
cur ^= (id & 1) ? cx : cy;
for (int i = 1; i <= cx; ++i)
if (!(cur ^ ((id & 1) ? (cx - i) : (cy + i))))
++ans;
cur ^= (id & 1) ? cx : cy;
}
write(ans), putchar('\n');
return 0;
}
|
Bzoj2067 Szn
简要题意: 给定一棵树，边的长度为 $1$，求使用最少的链的数量使得所有边被且仅被覆盖一次，并同时要求最长链最短。
数据规模: $n \le 10^4$。
题解: 第一问的答案为 $1+\sum\frac{deg_u-1}{2}$，可以看作是将每个节点的儿子两两配对，剩下的链延伸到父亲。
第二问可以二分答案 + 判断，也是经典的老套路了。对整棵树进行 dfs，将子树向上延伸的链的长度两两匹配。在失配的链中找到最短的那个向父亲延伸，剩下的链直接断开，代码也非常好写，总复杂度 $O(n\log^2n)$，因为要排序。
注意在匹配儿子延伸上来的链的时候要从大往小匹配，否则是错的，但是数据没有卡。这里提供一组 hack 数据。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| 15
1 2
2 3
3 4
4 5
5 6
1 7
7 8
7 9
9 10
7 11
11 12
12 13
13 14
14 15
|
代码:
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
| using ll = long long;
const int N = 1e4 + 10;
int n, ans1, ans2, fa[N], cnt[N], len[N];
vector<int> g[N];
void dfs(int u, int f, int mid) {
vector<int> vec;
cnt[u] = 0, len[u] = 1;
for (auto v : g[u]) {
if (v == f)
continue;
dfs(v, u, mid), cnt[u] += cnt[v];
vec.push_back(len[v]);
}
sort(vec.begin(), vec.end());
int sz = vec.size(), mat = 0, up = 0;
set<pair<int, int>> st;
for (int i = 0; i < sz; ++i)
st.insert({vec[i], i});
for (int i = sz - 1; ~i; --i) {
if (!vec[i])
continue;
st.erase({vec[i], i});
auto it = st.upper_bound({mid - vec[i], (int)1e9});
if (it == st.begin()) {
st.insert({vec[i], i});
continue;
}
int p = (--it)->second;
vec[i] = vec[p] = 0, st.erase(it), ++mat;
}
for (int i = 0; i < sz; ++i)
if (vec[i] && (!up || vec[i] < up))
up = vec[i];
cnt[u] += sz - mat;
if (f && up && up + 1 <= mid)
--cnt[u], len[u] = up + 1;
}
signed main() {
read(n);
for (int i = 1; i < n; ++i) {
int u, v;
read(u), read(v);
g[u].push_back(v), g[v].push_back(u);
}
for (int i = ans1 = 1; i <= n; ++i)
ans1 += (g[i].size() - 1) >> 1;
int l = 1, r = n;
ans2 = n;
while (l <= r) {
int mid = (l + r) >> 1;
if (dfs(1, 0, mid), cnt[1] == ans1) {
r = mid - 1, ans2 = mid;
} else {
l = mid + 1;
}
}
printf("%d %d\n", ans1, ans2);
return 0;
}
|
Bzoj2069 Zaw
简要题意: 给定一张无向图，每条边正着走和反着走的边权不同，求从点 $1$ 开始不重复经过边并回到 $1$ 的最短路。
数据规模: $n \le 5000,\ m \le 10^4$。
题解: 暴力枚举第一条边后跑可以过，但有更好的做法。假设已经确定走第一条边 $(1,s)$ 和最后一条边 $(t,1)$，可以直接将与 $1$ 有关的边删去后跑最短路，因为最短路一定不会重复经过一条边。由于不能经过同一条边多次，所以要确保 $s \neq t$。
既然有 $s \neq t$，就意味着 $s$ 和 $t$ 的二进制表示中至少有一位不同。于是可以枚举二进制位 $k$，将第 $k$ 位为 $0$ 的作为源点，为 $1$ 的作为汇点，跑最短路，反过来同理，这样就保证了源点 $s$ 和汇点 $t$ 一定不相同。因此，可以使用二进制分组，在 $O(m\log^2m)$ 的时间复杂度内完成。
代码:
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>;
const int N = 5e3 + 10;
int n, m, ds[N], dt[N], dis[N];
struct Edge {
int v, w;
};
vector<Edge> g[N];
priority_queue<pii, vector<pii>, greater<pii>> pq;
int dijkstra(int s, int t) {
fill(dis + 1, dis + n + 3, 1e9);
dis[s] = 0, pq.push({0, s});
while (!pq.empty()) {
int u, d;
tie(d, u) = pq.top(), pq.pop();
if (d > dis[u])
continue;
for (auto e : g[u])
if (dis[e.v] > dis[u] + e.w)
dis[e.v] = dis[u] + e.w, pq.push({dis[e.v], e.v});
}
return dis[t];
}
signed main() {
read(n), read(m);
fill(ds + 1, ds + n + 1, 1e9);
fill(dt + 1, dt + n + 1, 1e9);
for (int i = 1; i <= m; ++i) {
int u, v, x, y;
read(u), read(v), read(x), read(y);
if (u == 1)
ds[v] = min(ds[v], x), dt[v] = min(dt[v], y);
if (v == 1)
ds[u] = min(ds[u], y), dt[u] = min(dt[u], x);
if (u != 1 && v != 1)
g[u].push_back({v, x}), g[v].push_back({u, y});
}
int ans = 1e9, s = n + 1, t = n + 2;
for (int k = 12; ~k; --k) {
for (int u = 2; u <= n; ++u)
if (u >> k & 1) {
g[s].push_back({u, ds[u]});
} else {
g[u].push_back({t, dt[u]});
}
ans = min(ans, dijkstra(s, t));
for (int u = 2; u <= n; ++u)
g[(u >> k & 1) ? s : u].pop_back();
for (int u = 2; u <= n; ++u)
if (u >> k & 1) {
g[u].push_back({t, dt[u]});
} else {
g[s].push_back({u, ds[u]});
}
ans = min(ans, dijkstra(s, t));
for (int u = 2; u <= n; ++u)
g[(u >> k & 1) ? u : s].pop_back();
}
write(ans), putchar('\n');
return 0;
}
|
Bzoj2070 Bra
简要题意: 给定有向图，节点 $0$ 和 $1$ 的入度为 $0$。每个点有 $0,1,\frac{1}{2}$ 三种取值，初始 $0$ 的取值为 $0$，$1$ 的取值为 $1$。对于节点 $u > 1$ 的值，若指向它的节点中 $0$ 的数量严格大于 $1$ 的数量则为 $0$，$1$ 的数量严格大于 $0$ 则为 $1$，否则为 $\frac{1}{2}$。问对于每个点求出其取值，或输出 ? 表示不确定。
数据规模: $n \le 10^4,\ m \le 2\times 10^5$。
题解: 由于环的存在，这道题一眼看上去根本无从下手。看完题解后，发现可以求出每个点取值的上界和下界从而确定这个点的取值。
下面只说如何求出上界，因为下界是类似的。先将所有点的点权赋成 $1$，将点 $0$ 的点权赋为 $0$，从 $0$ 开始用 bfs 更新其他点的点权。容易发现每个点的点权最多只会从 $1\to \frac{1}{2} \to 0$ 这样更改 $2$ 次，即每个点最多入队 $2$ 次，所以复杂度是 $O(n+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
55
56
57
58
59
60
61
62
| using ll = long long;
const int N = 1e4 + 10;
int n, ind[N], mnc[N], mxc[N], cnt[N][3];
vector<int> g[N];
queue<int> que;
inline int calc(int u) {
return cnt[u][0] == cnt[u][1] ? 2 : cnt[u][0] < cnt[u][1];
}
signed main() {
read(n);
for (int i = 2; i < n; ++i) {
int k, x;
read(k);
while (k--)
read(x), g[x].push_back(i), ++ind[i];
}
for (int i = 0; i < n; ++i)
cnt[i][0] = ind[i], cnt[i][1] = cnt[i][2] = 0, mnc[i] = 0;
mnc[1] = 1, que.push(1);
for (auto v : g[1])
--cnt[v][0], ++cnt[v][1];
while (!que.empty()) {
int u = que.front();
que.pop();
for (auto v : g[u]) {
int t = calc(v);
if (mnc[v] != t) {
for (auto w : g[v])
--cnt[w][mnc[v]], ++cnt[w][t];
mnc[v] = t, que.push(v);
}
}
}
for (int i = 0; i < n; ++i)
cnt[i][1] = ind[i], cnt[i][0] = cnt[i][2] = 0, mxc[i] = 1;
mxc[0] = 0, que.push(0);
for (auto v : g[0])
--cnt[v][1], ++cnt[v][0];
while (!que.empty()) {
int u = que.front();
que.pop();
for (auto v : g[u]) {
int t = calc(v);
if (mxc[v] != t) {
for (auto w : g[v])
--cnt[w][mxc[v]], ++cnt[w][t];
mxc[v] = t, que.push(v);
}
}
}
for (int i = 0; i < n; ++i)
if (mnc[i] == mxc[i]) {
if (mxc[i] != 2) {
write(mxc[i]), putchar('\n');
} else {
puts("1/2");
}
} else {
puts("?");
}
return 0;
}
|
Bzoj2071 Jas
简要题意: 求给定树的最小点分树深度。
数据规模: $n \le 5\times 10^4$。
题解: 为了方便，我们设 $d_u$ 表示 $u$ 点分树上的子树深度大小。根据点分树的性质，“点分树上的 LCA 在原树的路径上”，便要求对于每一组 $d_u = d_v$，有 $x \in {\rm path}(u,v)$ 使得 $d_x > d_u$。
根据点分树的深度上界，$d$ 数组的取值范围是 $O(\log n)$ 的，这就允许我们对每个节点储存每个 $d$ 是否合法。令 $S_u$ 表示节点 $u$ 的不合法的 $d$ 的集合，并考虑将子树的 $S$ 合并得到父亲的取值以及 $S$。
考察集合 $S$ 的含义，不合法的 $d$ 当且仅当 $u$ 的子树内存在一个 $d$ 并且这个 $d$ 到 $u$ 的路径上没有其他 $> d$ 的值。因此，对于子树 $v$ 和 $w$，$d_u$ 一定大于 $S_v \cap S_w$ 的值。同时，对任意子树 $v$，都要求 $d_u \notin S_v$。在所有满足条件的 $d_u$ 中，我们贪心地取最小的，并用 $d_u$ 去更新 $S_u$ 的值即可。具体地，
$$
d_u = \min \{c \mid c > \max \{ x \mid x \in S_v \cap S_w \} \ \and\ c \notin S_v \} \\
S_u = \{d_u\} \cup \left\{ x \mid x \ge d_u \ \and\ x \in \bigcup S_v \right\}
$$
使用二进制压位进行 $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
| using ll = long long;
const int N = 5e4 + 10, K = 1 << 17;
int n, mx[N], dp[N], lg2[K];
vector<int> g[N];
void dfs(int u, int f) {
int msk = 0, ban = 0;
for (auto v : g[u]) {
if (v == f)
continue;
dfs(v, u), mx[u] = max(mx[u], mx[v]);
msk |= ban & dp[v], ban |= dp[v];
}
msk = ((K - 1) ^ ban) & (K - (1 << lg2[msk]));
int t = lg2[msk & -msk];
mx[u] = max(mx[u], t);
dp[u] = ((ban >> t) << t) | (1 << t);
}
signed main() {
read(n);
for (int i = 2; i < K; ++i)
lg2[i] = lg2[i >> 1] + 1;
for (int i = 1; i < n; ++i) {
int u, v;
read(u), read(v);
g[u].push_back(v), g[v].push_back(u);
}
dfs(1, 0), write(mx[1]), putchar('\n');
return 0;
}
|
Bzoj2072 Mos
简要题意: 小学奥数题，一队人带着一个火把要从一边走到另一边，一个火把能带最多 $2$ 人，问最少时间。
数据规模: $n \le 10^6$。
题解: 根据小学奥数经验，第 $i$ 个人走到对面有 $2$ 种决策：
- $1$ 和 $i$ 过去，$1$ 回来。
- $1$ 和 $2$ 过去，$1$ 回来，$i$ 和 $i+1$ 过去，$2$ 回来。
从大往小 dp，设 $dp_i$ 表示 $i\sim n$ 都到达对岸所需的时间，分情况转移一下即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| using ll = long long;
const int N = 1e5 + 10;
int n, a[N];
ll dp[N];
signed main() {
read(n);
for (int i = 1; i <= n; ++i)
read(a[i]);
if (n == 1)
return write(a[1]), putchar('\n'), 0;
fill(dp + 1, dp + n + 3, 1e18), dp[n + 1] = 0;
for (int i = n; i >= 3; --i)
dp[i] =
min(dp[i + 2] + a[1] + 2 * a[2] + a[i + 1], dp[i + 1] + a[i] + a[1]);
write(dp[3] + a[2]), putchar('\n');
return 0;
}
|
Bzoj2074 Tur
简要题意: 有 $n$ 个人进行淘汰赛，已知 $m$ 组 $(u,v)$ 使得 $u$ 一定能打败 $v$，问在比赛顺序任意的情况下，哪些人可能胜利。
数据规模: $n \le 10^5,\ m \le 10^6$。
题解: 考虑某个人 $u$ 是否能获胜。如果 $u$ 一定无法获胜，考虑最后谁会打败 $u$，设这个人为 $w$。对于 $u$ 能打败的人 $v_1 \cdots v_k$，$v_i$ 一定无法打败 $w$，否则可以构造出 $v_i \to w,\ u \to v_i$ 使得 $u$ 胜利，故一定有限制 $(w, v_i)$ 存在。同时，由于 $u$ 一定无法打败 $w$，所以一定存在限制 $(w, u)$，此时必有 $deg_w > deg_u$。因此，度数最大的点一定有概率获胜。
考虑当 $u$ 能获胜时，还有其他哪些人能够获胜。可以证明任意不会被 $u$ 打败的 $v$ 都能获胜，只需先构造出除去 $v$ 以外让 $u$ 获胜的方法，再让 $v \to u$ 即可让 $v$ 获胜。
这就有了一个较为暴力的写法，其中 $rt$ 表示度数最大的节点，$st$ 集合维护还没确定能否获胜的人。交上去发现能过：
1
2
3
4
5
6
7
8
9
10
11
12
| que.push(rt), st.erase(rt);
while (!que.empty()) {
int u = que.front();
que.pop();
for (auto v : g[u])
tag[v] = 1;
for (auto it = st.begin(); it != st.end(); ++it)
if (!tag[*it])
que.push(*it), st.erase(it--);
for (auto v : g[u])
tag[v] = 0;
}
|
下证该算法的复杂度正确。首先对于最后获胜的节点，显然遍历的复杂度为 $O(n+m)$。对于无法获胜的节点，复杂度应该是 $O(ans(n-ans))$ 的。当 $ans = \frac{n}{2}$ 时，复杂度会达到 $O(n^2)$ 级别。
但是 $ans$ 真的能达到 $\frac{n}{2}$ 吗？不妨考察胜利节点的含义，即原图的补图中 $rt$ 所在的连通块。该连通块在补图中与非胜利节点没有边，也就是说在原图中该连通块与非胜利节点都有边，即至少 $ans(n-ans)$ 条边。因此，有 $ans(n-ans) \le m$，故该算法的复杂度仍可做到 $O(n+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
| using ll = long long;
const int N = 1e5 + 10;
int n, rt, oud[N];
bool tag[N];
vector<int> g[N];
signed main() {
read(n);
for (int i = 1; i <= n; ++i) {
int k, x;
read(k);
while (k--)
read(x), g[i].push_back(x), ++oud[i];
}
rt = max_element(oud + 1, oud + n + 1) - oud;
queue<int> que;
set<int> st;
vector<int> ans;
for (int i = 1; i <= n; ++i)
st.insert(i);
que.push(rt), st.erase(rt);
while (!que.empty()) {
int u = que.front();
que.pop();
ans.push_back(u);
for (auto v : g[u])
tag[v] = 1;
for (auto it = st.begin(); it != st.end(); ++it)
if (!tag[*it])
que.push(*it), st.erase(it--);
for (auto v : g[u])
tag[v] = 0;
}
sort(ans.begin(), ans.end());
write(ans.size()), putchar(' ');
for (int i = 0; i < (int)ans.size(); ++i)
write(ans[i]), putchar(" \n"[i == (int)ans.size() - 1]);
return 0;
}
|
Bzoj2075 Kag
简要题意: 原题的题面描述已经够清楚了。
数据规模: $n \le 10^4,\ m \le 10^5$。
题解: 为了表述方便，我们称原图的边为黑边，原图的补图的边为白边。
注意到，如果对于一张导出子图，如果其是通过图 $(1)$ 的方式合并，则黑边一定形成 $> 1$ 个连通块；如果是通过图 $(2)$ 的方式合并，则白边一定形成 $> 1$ 个连通块。而由于补图的性质，黑边和白边不可能同时形成 $> 1$ 个连通块。
所以考虑分治。对于一张导出子图，计算其黑色和白色的连通块个数。如果二者都 $= 1$，直接返回 NIE。否则，根据对应的合并方式分成几个新的导出子图进行递归。
我们希望，可以快速计算出黑色和白色的连通块。黑色是容易计算的，直接 bfs 就可以 $O(n+m)$ 地求出。问题在于白色连通块，要判断两个白色连通块 $S_1$ 和 $S_2$ 之间是否有白边，不妨暴力枚举 $u \in S_1$ 和 $v \in S_2$，判断 $(u,v)$ 是否为白色。这样的复杂度是正确的，因为如果 $(u,v)$ 为黑色，那么相当于枚举了所有的黑边，是 $O(m)$ 的；否则 $(u,v)$ 为白色，那么直接将 $S_1$ 与 $S_2$ 合并，最多合并 $O(n)$ 次，复杂度也是 $O(n+m)$ 的。
最后便是递归次数的计算。注意到，按照黑色连通块分裂，则最多递归 $O(n)$ 层；按照白色连通块分裂，则每次分裂都会使得 $O(n)$ 条黑边被去掉；且黑色分裂与白色分裂一定是交替进行。所以总的递归次数是 $O(\min(n,m/n))$，即 $O(\sqrt m)$ 的。
综上所述，此题可以在 $O((n+m)\sqrt 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
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
| using ll = long long;
const int N = 1e4 + 10;
int n, m;
vector<int> g[N];
unordered_set<int> stg[N];
vector<vector<int>> black_connect(const vector<int> &nds) {
static bool vis[N];
vector<vector<int>> res;
for (auto p : nds)
vis[p] = 0;
for (auto s : nds) {
if (vis[s])
continue;
res.push_back({});
queue<int> que;
vis[s] = 1, que.push(s);
while (!que.empty()) {
int u = que.front();
que.pop();
res.back().push_back(u);
for (auto v : g[u])
if (!vis[v])
vis[v] = 1, que.push(v);
}
}
return res;
}
vector<vector<int>> white_connect(const vector<int> &nds) {
static int dns[N], nxt[N];
int szn = nds.size();
for (auto p : nds)
dns[p] = 0;
for (int i = 1; i < szn; ++i)
nxt[nds[i - 1]] = nds[i];
nxt[nds[szn - 1]] = 0;
vector<vector<int>> res;
for (int hd = nds[0]; hd; hd = nxt[hd]) {
for (int u = hd; u; u = dns[u]) {
for (int v = nxt[hd], p = hd; v; p = v, v = nxt[v]) {
if (stg[u].count(v))
continue;
nxt[p] = nxt[v], nxt[v] = 0, dns[v] = dns[u], dns[u] = v, v = p;
}
}
res.push_back({});
for (int u = hd; u; u = dns[u])
res.back().push_back(u);
}
return res;
}
bool check(const vector<int> &nds) {
static int col[N];
if (nds.size() == 1)
return true;
auto ndb = black_connect(nds), ndw = white_connect(nds);
if (ndb.size() == 1 && ndw.size() == 1)
return false;
auto &nnds = (ndb.size() == 1 ? ndw : ndb);
for (int i = 0; i < (int)nnds.size(); ++i)
for (auto p : nnds[i])
col[p] = i;
for (auto u : nds) {
vector<int> ng;
ng.reserve(g[u].size());
for (auto v : g[u])
if (col[u] == col[v])
ng.push_back(v);
swap(g[u], ng);
}
bool ret = true;
for (auto &nxt : nnds)
if (!(ret &= check(nxt)))
break;
return ret;
}
signed main() {
int cas;
read(cas);
while (cas--) {
read(n), read(m);
for (int i = 1; i <= n; ++i)
g[i].clear(), stg[i].clear();
for (int i = 1; i <= m; ++i) {
int u, v;
read(u), read(v);
g[u].push_back(v), g[v].push_back(u);
stg[u].insert(v), stg[v].insert(u);
}
vector<int> all(n);
iota(all.begin(), all.end(), 1);
puts(check(all) ? "TAK" : "NIE");
}
return 0;
}
|
Bzoj2076 Mak
简要题意: 原题的题面描述已经够清楚了。
数据规模: $n \le 10^4$，数据组数 $T \le 10$。
题解: 相当于将 $n$ 拆分为若干项 $a_1 \cdots a_k$ 之和，使得 ${\rm lcm}(a_1 \cdots a_k)$ 最大。
发现 $a_i$ 必须两两互质，否则一定不优。于是对于每个质数 $p_i$，要么根本不取，要么就使得有 $a_j = p_i^k$。不妨设计一个背包 dp，$dp_{i,j}$ 表示前 $i$ 个质数，$a$ 数组的和为 $j$ 的最大乘积。由于乘积可能很大，所以不妨取一个 $\log$ 进行储存和比较。同时在 dp 过程中记录转移以便于最后得出 $a$ 数组。得出 $a$ 数组以后，字典序最小的方案容易构造。
在 dp 的过程中，我们发现太大的质数都不会被取到，因为大质数太劣了。具体地，只需要保留前 $75$ 个质数就可以通过此题。于是经过计算后，发现复杂度约为 $O(130n)$，稳稳地通过。
代码:
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
| using ll = long long;
const int N = 1e4 + 10, K = 100;
int n, cntp, pri[N], ans[N], num[K][N], pwp[K][K];
bool mark[N];
long double dp[K][N], ln[K];
void sieve(int n) {
for (int i = 2; i <= n; ++i) {
if (!mark[i])
pri[++cntp] = i;
for (int j = 1; j <= cntp; ++j) {
if (i * pri[j] > n)
break;
mark[i * pri[j]] = 1;
if (i % pri[j] == 0)
break;
}
}
}
signed main() {
sieve(N - 1);
cntp = min(cntp, 75);
for (int i = 1; i <= cntp; ++i) {
ln[i] = log(pri[i]);
for (int j = pwp[i][0] = 1; pwp[i][j - 1] < N; ++j)
pwp[i][j] = pwp[i][j - 1] * pri[i];
}
int cas;
read(cas);
while (cas--) {
read(n);
fill(dp[0], dp[0] + n + 1, 0);
for (int i = 1; i <= cntp; ++i) {
fill(num[i], num[i] + n + 1, 0);
copy(dp[i - 1], dp[i - 1] + n + 1, dp[i]);
for (int j = 0; j <= n; ++j) {
for (int k = 0; pwp[i][k] <= j; ++k)
if (dp[i][j] < dp[i - 1][j - pwp[i][k]] + ln[i] * k) {
dp[i][j] = dp[i - 1][j - pwp[i][k]] + ln[i] * k;
num[i][j] = pwp[i][k];
}
}
}
vector<int> circ;
int sum = n;
for (int i = cntp; i >= 1; --i)
if (num[i][sum])
circ.push_back(num[i][sum]), sum -= num[i][sum];
while (sum > 0)
circ.push_back(1), --sum;
sort(circ.begin(), circ.end());
iota(ans + 1, ans + n + 1, 1);
for (auto p : circ)
rotate(ans + sum + 1, ans + sum + 2, ans + sum + p + 1), sum += p;
for (int i = 1; i <= n; ++i)
write(ans[i]), putchar(" \n"[i == n]);
}
return 0;
}
|
Bzoj2077 Wsc
简要题意: 给定 $n$ 个节点的树，边权为 $1$，其中必然存在一条边 $(u,v)$ 使得点 $[1,z]$ 在边的 $u$ 侧，点 $[n-w+1, n]$ 在边的 $v$ 侧。现在有 $k$ 列火车从 $[1,z]$ 中给定的 $k$ 个不同的点出发，需要到达 $[n-w+1, n]$ 中的任意 $p$ 个不同节点。火车可以停留，但不能有 $2$ 列火车同时走一条边。求火车到达目标城市的最早时间。
数据规模: $n \le 10^6, \ 1 < k < \min(z,w), \ n \ge w + z + 2$。
题解: 考虑先求出 $(u,v)$ 这条边，并任选 $u$ 或 $v$ 中的一点作为树根 $rt$。从 $rt$ 开始，一遍 dfs 求出 $dep_i$ 表示 $i$ 到根的距离。
从 $v$ 出发走向 $[n-w+1,n]$ 是容易考虑的，因为只要火车到达 $v$ 点的时间互不相同，那么从 $v$ 出发后一定也不会同时走到一条边上。将 $\{dep_{n-w+1}, \cdots, dep_{n}\}$ 排序后得到 $\{dv_1,\cdots,dv_w\}$，取 $\{dv_1,\cdots,dv_k\}$ 即可。
从 $[1,z]$ 出发走向 $u$，不妨先算出 $\{dep_{p_1},\cdots dep_{p_k}\}$ 排序后的数组 $\{du_1,\cdots,du_k\}$。若存在 $du_i = du_{i+1}$，说明会有 $2$ 列火车同时到达 $u$，这时我们令 $du_{i+1} \leftarrow du_{i+1} + 1$，即让火车 $i+1$ 等待 $1$ 时刻再出发。重复此操作使得 $du$ 中的数互不相同，这时答案便是 $\displaystyle{\max_{i=1}^{k} du_i + dv_{k-i+1}}$。
现在的问题在于如何求出 $(u,v)$ 这条边以及树根 $rt$。可以任取一点进行 dfs，求出 $sz_i$ 和 $sw_i$，分别表示 $i$ 的子树中 $[1,z]$ 的数量以及 $[n-w+1,n]$ 的数量。当且仅当 $(sz_i = z \ \land \ sw_i = 0) \lor (sz_i = 0 \ \land \ sw_i = w)$ 时，$i$ 可以成为 $rt$。容易证明无论从哪个点开始 dfs，$u$ 和 $v$ 中都必有至少一个可以选中。
于是本题被解决，时间复杂度 $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
50
| using ll = long long;
const int N = 1e6 + 10;
int n, z, w, p, rt, sz[N], sw[N], dep[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 dfs1(int u, int f) {
sz[u] = (u <= z), sw[u] = (u > n - w);
for (int i = g.hd[u]; i; i = g.nxt[i]) {
int v = g.to[i];
if (v == f)
continue;
dfs1(v, u), sz[u] += sz[v], sw[u] += sw[v];
}
}
void dfs2(int u, int f) {
if (f)
dep[u] = dep[f] + 1;
for (int i = g.hd[u]; i; i = g.nxt[i])
if (g.to[i] != f)
dfs2(g.to[i], u);
}
signed main() {
read(n), read(z), read(w);
for (int i = 1, u, v; i < n; ++i)
read(u), read(v), g.add_edge(u, v);
dfs1(1, 0);
for (int i = 1; i <= n; ++i)
if ((sz[i] == z && !sw[i]) || (sw[i] == w && !sz[i]))
rt = i;
dfs2(rt, 0);
read(p);
vector<int> v1, v2;
for (int i = 1, u; i <= p; ++i)
read(u), v1.push_back(dep[u]);
for (int i = 1; i <= w; ++i)
v2.push_back(dep[n - w + i]);
sort(v1.begin(), v1.end()), sort(v2.begin(), v2.end());
for (int i = 1; i < p; ++i)
v1[i] = max(v1[i - 1] + 1, v1[i]);
int ans = 0;
for (int i = 1; i <= p; ++i)
ans = max(ans, v1[i - 1] + v2[p - i]);
write(ans), putchar('\n');
return 0;
}
|
Bzoj2078 Wys
简要题意: 给定 $n$ 个边不相交的多边形，每条边平行或垂直于 $x$ 轴，顶点坐标按照逆时针给出，其包含关系形成树形结构。求树形结构的最大深度。
数据规模: $n \le 4\times 10^4$，点数 $|V| \le 2\times 10^5$。
题解: 类似于这道题，对于此类将多边形的嵌套关系转成树形结构的问题，比较套路的做法是在当前多边形的任意边缘处添加一条向外的射线，并找到其经过的第一个多边形。我们设当前多边形为 $u$，射线所经过的第一个多边形为 $p$，则 $u$ 和 $p$ 有以下两种关系：
- $p$ 是 $u$ 的父亲。其充要条件是 $u$ 被 $p$ 所包含。
- $p$ 是 $u$ 的兄弟。其充要条件是 $u$ 不被 $p$ 所包含。
下面问题转化为判断 $u$ 和 $p$ 是否产生包含关系。对于每个多边形，我们按照逆时针的顺序加入若干条有向边，这样可以根据射线扫到的 $p$ 的边的方向来判断射线是否在多边形 $p$ 内，进而得到 $u$ 和 $p$ 的包含关系。
具体到这道题目，由于题目条件中每条边都平行于坐标轴，所以不难想到直接提取出所有跟 $y$ 轴平行的边进行扫描线，维护每一时刻每个点左边的第一条边对应的多边形以及其方向即可，最后直接在树上求出最大深度即为答案。时间复杂度 $O(|V|\log |V|)$，代码很好写。
代码:
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 = 4e4 + 10, M = 2e5 + 10;
int n, sz, fa[N], dep[N], mp[M];
struct Line {
int x, l, r, id;
bool operator<(const Line &o) const { return x < o.x; }
};
vector<Line> lin;
struct Quer {
int x, y, id;
bool operator<(const Quer &o) const { return x < o.x; }
};
vector<Quer> qrs;
struct SegmentTree {
#define li (i << 1)
#define ri (i << 1 | 1)
#define lson li, l, mid
#define rson ri, mid + 1, r
int tag[M * 4];
void getdown(int i, int v) { tag[i] = v; }
void pushdown(int i) {
tag[i] && (getdown(li, tag[i]), getdown(ri, tag[i]), tag[i] = 0);
}
void update(int i, int l, int r, int ql, int qr, int v) {
if (ql <= l && r <= qr)
return getdown(i, v);
int mid = (l + r) >> 1;
pushdown(i);
if (ql <= mid)
update(lson, ql, qr, v);
if (qr > mid)
update(rson, ql, qr, v);
}
int query(int i, int l, int r, int p) {
if (l == r)
return tag[i];
int mid = (l + r) >> 1;
pushdown(i);
return p <= mid ? query(lson, p) : query(rson, p);
}
} sgt;
signed main() {
read(n);
for (int i = 1; i <= n; ++i) {
int k;
read(k);
vector<int> xs;
int sx = 1e9, sy = 1e9;
for (int j = 0, x; j < k; ++j)
read(x), xs.push_back(x), mp[++sz] = x;
for (int j = 0; j < k; j += 2) {
int pl = (j + k - 1) % k, pr = (j + 1) % k;
tie(sx, sy) = min<pair<int, int>>({sx, sy}, {xs[j], xs[pl]});
tie(sx, sy) = min<pair<int, int>>({sx, sy}, {xs[j], xs[pr]});
if (xs[pl] <= xs[pr]) {
lin.push_back({xs[j], xs[pl], xs[pr], i});
} else {
lin.push_back({xs[j], xs[pr], xs[pl], -i});
}
}
qrs.push_back({sx, sy, i});
}
sort(mp + 1, mp + sz + 1), sz = unique(mp + 1, mp + sz + 1) - mp - 1;
for (auto &p : lin)
p.l = lower_bound(mp + 1, mp + sz + 1, p.l) - mp;
for (auto &p : lin)
p.r = lower_bound(mp + 1, mp + sz + 1, p.r) - mp;
for (auto &p : qrs)
p.y = lower_bound(mp + 1, mp + sz + 1, p.y) - mp;
sort(lin.begin(), lin.end()), sort(qrs.begin(), qrs.end());
for (int i = 0, j = 0; i < (int)qrs.size(); ++i) {
while (j < (int)lin.size() && lin[j].x < qrs[i].x)
sgt.update(1, 1, sz, lin[j].l, lin[j].r, lin[j].id), ++j;
int idx = sgt.query(1, 1, sz, qrs[i].y);
fa[qrs[i].id] = (idx <= 0) ? -idx : fa[idx];
dep[qrs[i].id] = dep[fa[qrs[i].id]] + 1;
}
write(*max_element(dep + 1, dep + n + 1)), putchar('\n');
return 0;
}
|
最后修改于 2025-07-05
Git 版本:
de2abab
