大意

给定一个 $n \times m$ 的方格, 每格中有一个数字, 设两个方格是 联通的 , 仅当两个方格相邻且数字相同 .

$q$ 个询问, 每次给定 $l$, $r$, 求从第 $l$ 列至第 $r$ 列中联通块的个数 .

数据范围

题解

这道题要分成 3 个部分, 对应上表中的三个数据范围.

#1

$n \le 2, m \le 10^6, q \le 1.3 \times 10^6$

可以发现, $n \le 2$, 同时 $m, q$ 很大, 考虑用前缀和解决.

设 $s_i$ 为前 i 列的联通块个数.

$n = 1$ 时:

$$s_i = s_{i-1} + [a_i \not= a_{i - 1}]$$

$n = 2$ 时:

$$s_i = s_{i-1} + [a_{1, i} \not= a_{1, i-1}] + [a_{2, i} \not= a_{2, i-1}] - [a_{1, i} = a_{2, i} \wedge a_{1, i} \not= a_{1, i-1} \wedge a_{2, i} \not= a_{2, i-1}]$$

查询时, 同样解决.

$n = 1$ 时:

$$s_r - s_{l-1} + [a_l \not= a_{l - 1}]$$

$n = 2$ 时:

$$s_r - s_{l-1} + [a_{1, l} = a_{1, l-1}] + [a_{2, l} = a_{2, l-1}] - [a_{1, l} = a_{1, l-1} \wedge a_{2, l} = a_{2, l-1} \wedge a_{1, l} = a_{2, l}]$$

#2

线段树.

设 $id(i, j) = (i - 1) \cdot m + j$

每个节点存储 $l, r, cnt$, 分别代表该区间左端和右端的编号 (编号相同就代表数字相同, 反之不一定) , 和联通块个数.

先考虑每一列:

$$l_{i, j} = l_{i - 1, j}, i \ge 2 \wedge a_{i, j} = a{i - 1, j} \newline \newline l_{i, j} = id(i, j), otherwise$$

然后考虑合并

首先 $cnt \leftarrow cnt(ls) + cnt(rs)$.

对于中间的两列, 即 ls.r 和 rs.l, 若相同, 则用 dsu 加入同一个集合, 并 $cnt \leftarrow cnt-1$.

然后对于左右两列, $l \leftarrow l(ls)$, $r \leftarrow r(rs)$, 并要在 dsu 中查询.

合并完将 dsu 恢复.

#3

仿照 #2 的情况, 独立处理每一列, 然后合并时, 若两侧相同且不在同一个集合内, 就合并, $cnt \leftarrow cnt - 1$.

大意

在树上新增 $k, k \le 2$ 条边, 新增的边能且只能经过 $1$ 次, 求遍历这棵树最小步数.

题解

k = 1

显然, 添加直径最优.

k = 2

所以, 先求一遍直径, 将直径上的边权设为 $-1$ , 再求一次直径, 即可.

大意

给定一棵树，对于任意的三个点 $a, b, c$ , 求 $\bar d, d = dis(a, b) + dis(b, c) + dis(c, a)$ .

解法

对于每条边，计算对于答案的贡献.

设 $left(x), right(x)$ 为该边左右的点数.

$$\frac {left(x) \cdot right(x) \cdot (left(x) - 1) + left(x) \cdot right(x) \cdot (right(x) - 1)} {\frac {n(n - 1)(n - 2)} 6} = \frac {6(left(x)right(x))} {n(n-1)}$$

题意

给定一棵 $n$ 个节点的树, 可以从中选出一些节点, 这些节点是连通的, 构成一棵
子树. 求所有子树方案的节点数目的总和.

题解

设 $g(u)$ 以 $u$ 为根的方案总数.

设 $h(u)$ 以 $u$ 为根的方案总和.

$$g(u) = \prod_{v \in son(u)} g(v) \newline h(u) = \sum_{v \in sum(u)} \frac{g(u)}{g(v)} h(v) \newline res = sum(h(u))$$

证明

$$h(v) = c_{1, 1} + c_{1, 2} + c_{1, 3} + ... \newline h(u) = (c_{1, 1} + c_{2, 1}) + (c_{1, 2} + c_{2, 2}) + ...$$

$c_{1, 1}, c_{1, 2} ...$ 出现了 $\frac {g_u} {g_v}$ 次,
其他同理.

大意

最初 $x = s$, 然后进行 $k$ 个操作, 每次 $x \leftarrow x + a_i$ 或者 $x \leftarrow x - a_i$ ,
同时要求 $0 \le x \le n$, 最后, 求 $max(x)$ .

题解

分成两部分, 先求出 $k = \frac m 2$ 时的所有情况, 记为 $x$.

然后, $s := 0$ , 再求出剩下情况, 对于每种情况 $y$ , 最大 $h$ , 最小 $l$ , 找到最大的 $x$ 使得 $0 \le x + l \le maxdepth, 0 \le x + h \le maxdepth$ , 即 $-l \le x \le maxdepth - h$ .

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

void dfs1(ll x, ll i)
{
    if (x > max_dep || x < 0) return;
    if (i > half) {
        pos[++cnt] = x;
        return;
    }
}

pair<ll, ll> find(ll l, ll h)
{
    ll l_pos = lower_bound(pos + 1, pos + 1 + cnt, l) - pos;
    ll h_pos = upper_bound(pos + 1, pos + 1 + cnt, h + 1) - pos;
    return { pos[l_pos], pos[h_pos - 1] };
}

void dfs2(ll x, ll l, ll h, ll i)
{
    if (i > n) {
        pair<ll, ll> y = find(-l, max_dep - h);
        if (x + y.first >= 0) res_min = min(res_min, x + y.first);
        if (x + y.second <= max_dep) res_max = max(res_max, x + y.second);
        return;
    }
    ...
}

链接

problem: https://codeforces.com/problemset/problem/311/B

status: https://codeforces.com/problemset/submission/311/163441918

题解

$$dis_i = \sum_{j = 1}^i D_j \newline time = \{sort(T_i - dis_{H_i})\} \newline pretime = \sum{j = 1}^i time_i \newline$$

$$f_i = f_j + (i - j) * time_i - (pretime_i - pretime_j) \newline \newline g_i = g_j + (i - j) * time_i \newline res = g_i - \sum time_i \newline$$

$f$ $g$ 两种不同的解法, 有时候只有 $g$ 能够使用 (如以时间为 $i$) .