Old-NOIP 泛做三

以下的题是我做了之后不禁感慨“啊,真是个好题”的题们……

然后首先打出难度标签:

然后以下题目按照得较高的部分分的难度排序

$~1~2013F$ 华容道

$Link$

可能这道题很难…但是它有70分的暴力分!70分!在loj你甚至可以获得80分!tm这样的话暴力和正解有什么区别吗…从得分的时间分布上来讲,想正解就是大写的不值……

首先我们思考什么信息是有用的,嗯,空白格子的位子和当前棋子的位置,所以只要我们用BFS(而不是DFS,DFS的状态开销极大,但更可能的是我DFS的打开方式不对吧/sigh)的话,状态数就是$O(n^2m^2)$的,然后总复杂度就是$O(qn^2m^2)$,大概是四亿零500万的运算量上限…然而一开始我算成了四千五百万还纳闷为什么开了-O2在1s以内还跑不出来……

先贴个暴力吧:

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 bfs(){
memset(vis, 0, sizeof(vis)) ;
ans = Inf, vis[ex][ey][sx][sy] = 1 ;
q.push((state){ex, ey, sx, sy, 0, 1}) ;
while (!q.empty()){
state n = q.front() ; q.pop() ;
if (n.sx == tx && n.sy == ty) ans = min(ans, n.s) ;
for (int k = 0 ; k < 4 ; ++ k){
int kx = n.bx + dx[k], ky = n.by + dy[k], px, py ;
if (kx == n.sx && ky == n.sy)
px = n.bx, py = n.by ; else px = n.sx, py = n.sy ;
if (!base[kx][ky] || kx > N || ky > M || kx < 1 || ky < 1 || vis[kx][ky][px][py]) continue ;
vis[kx][ky][px][py] = 1 ;
q.push((state){kx, ky, px, py, n.s + 1, n.num + 1}) ;
}
}
if (ans >= Inf) puts("-1") ; else printf("%d\n", ans) ;
}
int main(){
cin >> N >> M >> Q ;
for (i = 1 ; i <= N ; ++ i)
for (j = 1 ; j <= M ; ++ j)
scanf("%d", &base[i][j]) ;
while (Q --) cin >> ex >> ey >> sx >> sy >> tx >> ty, bfs() ;
return 0 ;
}

喜闻乐见…不过自己打暴力的能力还是不行啊,还得练啊qaq

之后就是更加喜闻乐见的状态压缩。我们思考,这$n^2m^2$个状态都他娘的有鸟用吗(李云龙疾呼态),如果空白格子不在目标格子周围,那么无论空白格子怎么移动都不可能用爱发电。所以我们考虑吧直接预处理出来每个空白格子与目标格子(即起始格子)相邻的状态之间的代价,之后直接对此跑个$SPFA$就好了,毕竟最坏情况下SPFA的复杂度也只是$O(nM)$的,大概就是$O(n\cdot 4nm)<\frac{O(n^2m^2)}{7.5}$,也算是很稳的复杂度了。

然后我们思考这样的复杂度是多少。考虑目标格子有$nm$种情况,空白格子在有效情况下只能在其四周,故状态数是$O(4nm)=nm$的。

然后关于代码实现这块需要比较深入的理解。首先我们先预处理出来当当前格子在随便一个格子上,空白格子想要转到另一个方向的步数。这样就可以抽象成一张空白图上先有的一个一个树(也就是一坨森林)。然后为了让这些森林之间能连上边,再将“空白格子和目标格子换了个位置”这种转移连上边(不连的话就不存在从一个格子到另一个格子的转移了)。同时不要忘了对状态的编号。即:

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
inline int _get(int x, int y, int d){ return x * 120 + y * 4 + d ; }
void bfs(int fx, int fy, int ox, int oy, int d){
int Id = _get(ox, oy, d) ;
memset(dis, 0, sizeof(dis)),
dis[fx][fy] = 1, q.push((state){fx, fy}) ;
// cout << fx << " " << fy << endl ;
while (!q.empty()){
state n = q.front() ;
int nx = n.x, ny = n.y ; q.pop() ;
for (int k = 0 ; k < 4 ; ++ k){
int kx = nx + dx[k], ky = ny + dy[k] ;
if (kx > N || ky > M || kx < 1 || ky < 1) continue ;
if (base[kx][ky] && !dis[kx][ky] && (kx != ox || ky != oy))
dis[kx][ky] = dis[nx][ny] + 1, q.push((state){kx, ky}) ;
}
}
if (d > 3) return ;
for (int k = 0 ; k < 4 ; ++ k){
int kx = ox + dx[k], ky = oy + dy[k] ;
if (kx > N || ky > M || kx < 1 || ky < 1) continue ;
if (dis[kx][ky] && (kx != fx || ky != fy) && base[kx][ky])
Add(Id, _get(ox, oy, k), dis[kx][ky] - 1) ;
}
Add(Id, _get(fx, fy, d) ^ 1, 1) ;
}

以及

1
2
3
4
5
6
7
8
9
10
11
for (i = 1 ; i <= N ; ++ i)
for (j = 1 ; j <= M ; ++ j)
cin >> base[i][j] ;
for (i = 1 ; i <= N ; ++ i)
for (j = 1 ; j <= M ; ++ j){
if (!base[i][j]) continue ;
if (base[i - 1][j]) bfs(i - 1, j, i, j, 0) ;
if (base[i + 1][j]) bfs(i + 1, j, i, j, 1) ;
if (base[i][j - 1]) bfs(i, j - 1, i, j, 2) ;
if (base[i][j + 1]) bfs(i, j + 1, i, j, 3) ;
}

然后我们考虑在SPFA之前,我们需要求出空白格子从(ex,ey)到(sx, sy)周围需要的步数作为起始点,然后SPFA就好了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void Spfa(){
for (int k = 0 ; k < MAXS ; ++ k) f[k] = Inf, vis[k] = 0 ;
for (int k = 0 ; k < 4 ; ++ k){
int Id = _get(sx, sy, k), kx = sx + dx[k], ky = sy + dy[k] ;
if (dis[kx][ky]) f[Id] = dis[kx][ky] - 1, Q.push(Id), vis[Id] = 1 ;
}
while (!Q.empty()){
int n = Q.front() ; Q.pop() ; vis[n] = 0 ;
for (int k = head[n] ; k ; k = E[k].next){
if (f[to(k)] > f[n] + E[k].val){
f[to(k)] = f[n] + E[k].val ;
if (!vis[to(k)]) vis[to(k)] = 1, Q.push(to(k)) ;
}
}
}
}

$2~2012C$ 开车旅行

$Link$

不得不说2012的题目质量是真心好啊……

首先这题为了看上去不是那么毒瘤,于是加了一个70分的暴力分。然而…细节贼多——或者说只是我不细心,比如说把A和B怎么走看反了、算比值的时候用了个假double之类的……

于是70分好像有个头就会写吧= = 不知道当年什么区分度= =

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
struct Path{
int v1, v2 ;
int Id1, Id2 ;
}P[MAXN] ; int i, j ; double o, q ;
int res, ans, N, M, T, base[MAXN], s[MAXN], x[MAXN], p ;

inline int mabs(int x){ return x < 0 ? -x : x ; }
inline void GO(int S, int H){
int u = 0 ; res = ans = 0 ;
for (j = S ; j <= N && j ; u ^= 1){
if (u) if (res + ans + P[j].v1 > H) return ;
else res += P[j].v1, j = P[j].Id1 ;
else /*pkspks*/ if (res + ans + P[j].v2 > H) return ;
else ans += P[j].v2, j = P[j].Id2 ;
// cout << j << endl ;
}
}
signed main(){
cin >> N ; q = Inf ;
for (i = 1 ; i <= N ; ++ i) scanf("%lld", &base[i]) ;
cin >> T >> M ; for (i = 1 ; i <= M ; ++ i) scanf("%lld%lld", &s[i], &x[i]) ;
for (i = 1 ; i <= N ; ++ i){
int tp = Inf, w = 0 ;
for (j = i + 1 ; j <= N ; ++ j){
int qwq = abs(base[i] - base[j]) ;
if (qwq < tp || (qwq == tp && base[w] > base[j]))
tp = qwq, w = j ;
}
P[i].Id1 = w, P[i].v1 = tp ; tp = Inf, w = 0 ;
for (j = i + 1 ; j <= N ; ++ j){
int qwq = abs(base[i] - base[j]) ;
if (qwq < tp && (qwq > P[i].v1 || (qwq == P[i].v1 && base[P[i].Id1] < base[j])))
tp = qwq, w = j ;
}
P[i].Id2 = w, P[i].v2 = tp ;
}
// GO(2, T), cout << ans << " " << res << endl ;
// GO(4, T), cout << ans << " " << res << endl ;
// for (i = 1 ; i <= N ; ++ i) cout << i << " " << P[i].v1 << " " << P[i].Id1 << " " << P[i].v2 << " " << P[i].Id2 << endl ;
for (i = 1 ; i <= N ; ++ i){
GO(i, T) ; o = 1.0 * res ? (1.0 * ans) / (1.0 * res) : Inf ;
if (o < q ||(o == q && base[p] < base[i])) q = o, p = i ;
}
cout << p << endl ;
for (i = 1 ; i <= M ; ++ i)
GO(s[i], x[i]), printf("%lld %lld\n", ans, res) ; return 0 ;
}

然后感觉从暴力到正解完全不是一个难度的。首先考虑到底是什么地方阻碍了社会的发展——初始化似乎是$n^2$的,走似乎是$<n^2$的,那么从初始化入手:

$\rm{Part~1}$ 初始化的优化

我们思考如果当前轮到第$i$高的城市了,并且此时所有现存城市中不存在编号在$i$之前的城市,即$i$是最左边的城市,那么对其有用的信息只会在第$i-1,i-2,i+1$或者第$i+2$的城市中选取。这就提示我们似乎如果从值域上考虑就是$O(4n)$的了——只要我们保证不存在在$i$左边的城市、即对应城市不可走的情况。

然后这个时候有个很神仙的想法就是双向链表优化,我们考虑按高度排完序之后,对相邻元素建立双向链表。然后按照从左到右的顺序枚举城市、get信息然后删除掉这个城市

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
inline bool cmp(BASE A, BASE B){ return A.h < B.h ; }
inline bool cmp2(BASE A, BASE B){ return A.id < B.id ; }
inline int inlaw(int pos){ return (pos > N || !pos) ? Inf : 0 ; }
signed main(){
cin >> N ; q = Inf ;
for (i = 1 ; i <= N ; ++ i) pre[i] = i - 1, nxt[i] = i + 1 ;
for (i = 1 ; i <= N ; ++ i) scanf("%lld", &base[i].h), base[i].id = i ;
cin >> T >> M ; for (i = 1 ; i <= M ; ++ i) scanf("%lld%lld", &s[i], &x[i]) ;
sort(base + 1, base + N + 1, cmp) ;
for (i = 1 ; i <= N ; ++ i) Tid[base[i].id] = i ;
for (i = 1 ; i <= N ; ++ i){
int t = Tid[i] ;
d[1].h = inlaw(pre[t]) + abs(base[pre[t]].h - base[t].h),
d[2].h = inlaw(pre[pre[t]]) + abs(base[pre[pre[t]]].h - base[t].h) ;
d[3].h = inlaw(nxt[t]) + abs(base[nxt[t]].h - base[t].h),
d[4].h = inlaw(nxt[nxt[t]]) + abs(base[nxt[nxt[t]]].h - base[t].h) ;
d[1].id = base[pre[t]].id, d[2].id = base[pre[pre[t]]].id,
d[3].id = base[nxt[t]].id, d[4].id = base[nxt[nxt[t]]].id,
sort(d + 1, d + 5, cmp) ;
P[i].Id1 = d[1].id, P[i].v1 = d[1].h,
P[i].Id2 = d[2].id, P[i].v2 = d[2].h ;
pre[nxt[t]] = pre[t], nxt[pre[t]] = nxt[t] ;
}

然后初始化的工作就优化完了。至此可以在Luogu获得75pts的好成绩。

$\rm{Part~2}$ 走的优化

…然而只有第一个优化情况并不会好转多少。查看数据之后发现原来最后几个点的$s$和$x$都完全是随的那种……所以就复杂度爆炸。然后我们考虑这么一个喜闻乐见的事情——限制似乎只有“小于x”和“可以继续走”诶,于是似乎相邻的几步如果都不超过限制是不是就可以一起走?于是想到倍增预处理

我们用$A_{i,j}$表示从i号点开始,走$2^j$之后$A$走过的路程;同理$B_{i,j}$表示从i号点开始,走$2^j$之后$B$走过的路程。并且选择用$f_{i,j}$表示从i开始走$2^j$轮之后到达的点。然后值得注意的是最后可能走的不满一整轮,于是特判一下A能不能再走一次就好。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
sort(base + 1, base + N + 1, cmp2) ;//重排回来= =
for (i = 1 ; i <= N ; ++ i){
f[i][0] = P[P[i].Id2].Id1 ;
if (P[i].Id2)
A[i][0] = abs(base[P[i].Id2].h - base[i].h) ;
if (P[P[i].Id2].Id1)
B[i][0] = abs(base[P[i].Id2].h - base[P[P[i].Id2].Id1].h) ;
}
for (i = 1 ; i <= 20 ; ++ i)
for (j = 1 ; j <= N ; ++ j)
f[j][i] = f[f[j][i - 1]][i - 1],
A[j][i] = A[f[j][i - 1]][i - 1] + A[j][i - 1],
B[j][i] = B[f[j][i - 1]][i - 1] + B[j][i - 1] ;
...
inline void GO(int S, ll H){
ans = res = 0 ;
for (j = 20 ; j >= 0 ; -- j)
if (f[S][j] && A[S][j] + B[S][j] <= H)
ans += A[S][j], res += B[S][j], H -= (A[S][j] + B[S][j]), S = f[S][j] ;
if (A[S][0] <= H) ans += A[S][0] ;
}

$3~2016B$ 天天爱跑步

$Link$

……当年的毒瘤题,还记得那还是我第一次参加NOIP(普及组),不出所料地考挂,然后rqy不出所料地考好……

咳,偏题了,然后对于这道题,我索性把每个部分分都写了一遍:

$\rm{Part~1}$ 25pts

$n,m\leq 1000$

其实就是LCA一下然后$nm$的统计答案就完了。

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
void build(int now, int f){
fa[now][0] = f, dep[now] = dep[f] + 1 ;
for (int k = head[now] ; k ; k = E[k].next)
if (to(k) == f) continue ; else build(to(k), now) ;
}
void Setup(){
h = log(N) / log(2) + 1 ;
for (j = 1 ; j <= h ; ++ j)
for (i = 1 ; i <= N ; ++ i)
fa[i][j] = fa[fa[i][j - 1]][j - 1] ;
}
int lca(int u, int v){
if (dep[u] < dep[v]) u ^= v ^= u ^= v ; l = dep[u] - dep[v] ;
for (int k = h ; k >= 0 ; -- k) if (dep[fa[u][k]] >= dep[v]) u = fa[u][k] ;
if (u == v) return u ; for (int k = h ; k >= 0 ; -- k) if (fa[u][k] != fa[v][k]) u = fa[u][k], v = fa[v][k] ; return fa[u][0] ;
}
int main(){
cin >> N >> M ;
for (i = 1 ; i < N ; ++ i) scanf("%d%d", &x, &y), Add(x, y) ;
build(1, 0), Setup() ; for (i = 1 ; i <= N ; ++ i) scanf("%d", &base[i]) ;
for (i = 1 ; i <= M ; ++ i)
scanf("%d%d", &s[i], &e[i]),
lca1[i] = t = lca(s[i], e[i]),
_up[i] = -(dep[t] << 1) + (dep[s[i]] + dep[e[i]]) ;
for (i = 1 ; i <= N ; ++ i, printf("%d ", ans), ans = 0)
for (j = 1 ; j <= M ; ++ j) t = lca(e[j], i), p = lca(s[j], i),
w1 = -(dep[p] << 1) + (dep[i] + dep[s[j]]),
w2 = dep[i] + dep[e[j]] - (dep[t] << 1),
ans += (w1 == base[i]) * (_up[j] == w1 + w2) ;
return 0 ;
}

$\rm{Part~2}$ 15pts

这部分是链,保证$i$到$i+1$有一条边。

那么其实这个问题就转化成了在一个序列上,与点$i$相隔恰好为$t[i]$的点的个数,顺便注意判断一下走没走完就好。但是这个地方我用了一个肥肠zz的写法,就是每次加完之后删除到这个点停止的那些点,而“那些点”的求法则是我手写了一个很诡异的二分……

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
namespace Tink{
struct Nodes{
int s, e, n ;
}u[MAXN], v[MAXN] ; int t1, t2 ;
int be[MAXN], bs[MAXN], res[MAXN], k1 = 0, k2 = 0 ;
bool cmp1(Nodes a, Nodes b) { return a.e < b.e ; }
bool cmp2(Nodes a, Nodes b) { return a.e > b.e ; }
void del(int p, bool m){
int l = 1, r = (m ? k2 : k1) + 1 , mid, l0, l1 ;
if (!m){
while (l < r){
mid = (l + r) >> 1 ;
if (u[mid].e < p) l = mid + 1 ; else r = mid ;
} l0 = l, l = 1, r = k1 + 1 ;
while (l < r){
mid = (l + r) >> 1 ;
if (u[mid].e < p + 1) l = mid + 1 ; else r = mid ;
} l1 = l ;
for (int i = l0 ; i < l1 ; ++ i) bs[u[i].s] -- ;
}
else{
while (l < r){
mid = (l + r) >> 1 ;
if (v[mid].e < p) l = mid + 1 ; else r = mid ;
} l0 = l, l = 0, r = k2 + 1 ;
while (l < r){
mid = (l + r) >> 1 ;
if (v[mid].e < p + 1) l = mid + 1 ; else r = mid ;
} l1 = l ;
for (int i = l0 ; i < l1 ; ++ i) be[v[i].s] -- ;
}
}
void Solve2(){
for (int i = 1 ; i <= M ; ++ i) {
t1 = qr(), t2 = qr() ;
if (t1 < t2) bs[t1] ++, u[++ k1] = (Nodes){t1, t2, k1} ;
else /**/be[t1] ++, v[++ k2] = (Nodes){t1, t2, k2} ;
}
sort(u + 1, u + k1 + 1, cmp1) ;
for (int i = 1 ; i <= N ; ++ i) res[i] += bs[i - base[i]], del(i, 0) ;
sort(v + 1, v + k2 + 1, cmp1) ;
for (int i = N ; i >= 1 ; -- i) res[i] += be[i + base[i]], del(i, 1) ;
for (int p = 1 ; p <= N ; ++ p) cout << res[p] << " " ;
}
}

$\rm{Part~3}$ 20pts

保证所有起点都在根(1号点)。

其实这个部分也是挺水的。就是考虑一个树形DP即可。然后判断也很好判断,如果这个点的开眼时间正好是根到它的距离(深度差),那么就会一定会满足到它的点和到它的子树内的所有的点。否则就肯定不行,也就是一个都不满足。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
namespace DP{
int dp[MAXN], dis[MAXN] ;
int dfs(int now, int fa){
int sum = 0 ;
for (int k = head[now] ; k ; k = E[k].next){
if (to(k) == fa) continue ;
dis[to(k)] = dis[now] + 1, sum += dfs(to(k), now) ;
}
dp[now] += sum ; return dp[now] ;
}
inline void Solve3(){
memset(dis, 63, sizeof(dis)), dis[1] = 0 ;
for (int i = 1 ; i <= M ; ++ i) dp[e[i]] ++ ; dp[1] = dfs(1, 0) ;
for (int i = 1 ; i <= N ; ++ i)
if (base[i] == dis[i]) printf("%d ", dp[i]) ; else cout << 0 << " " ;
}
}

于是现在就有了60pts的优秀分数。似乎这样的话就可以直接把剩下的部分弃了去写T3的期望DP辽233

$\rm{Part~4~and~5}$ 40pts

剩下的部分没有选择分开写所以就不算谢了每个部分分是不是,因为剩下的两个部分实在是太像了,都要用到一种思想——. 其实80pts还有一种不是很想写的写法在这里就留个图吧:

然后我们思考桶的解法。我们把每一段路程拆成向上和向下两段。下文中设$x$为当前节点。

  • 对于向上的路径

    • 首先可以产生贡献的点就是子树内的$buc[dep[x]+ base[x]]$,这个我们用作差来求解(原因是我们可能会遍历许多棵子树所以会产生数值相同但不合法的贡献)。
    • 其次我们需要知道,如果一个人的起点和终点的LCA在子树内但不是$x$,那么也不会产生贡献。解决方案是每次dfs完一个点向上回溯的时候删除掉子树内所有以该点为LCA的点。
    • 同时也需要我们更新以该节点为起点的路径的桶。
  • 对于向下的路径

    • 首先对于一条路径$(u,v)$,当对点i产生贡献时可以推出来式子:

    $$
    dep_v-dis_{u,v}=dep_i-base_i
    $$

    那么也就是说我们可以通过把每条路径的$dep_v-dis_{u,v}$压到桶里面,然后每次计算贡献。
    
    • 同时我们还是需要消除贡献,即消除那些对于儿子而言在父亲那里停止的路径,方法就是在向下迭代之前先把所有以当前点为终点的贡献加上,到儿子时通过作差就可以减去这部分。注意向上回溯时还是需要删除那些蜷缩在子树内的路径。

之后还有需要注意的,就是如果在一条路径的LCA处正好可以观察到这条路径,那么就需要-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
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
namespace Prepare{ //25
inline int max(const int &a, const int &b) { return a > b ? a : b ; }
inline void Add(int u, int v){
E[++ cnt].to = v, E[cnt].next = head[u], head[u] = cnt ;
E[++ cnt].to = u, E[cnt].next = head[v], head[v] = cnt ;
}
void build(int now, int f){
fa[now][0] = f, dep[now] = dep[f] + 1, H = max(H, dep[now]) ;
for (int k = head[now] ; k ; k = E[k].next)
if (to(k) == f) continue ; else build(to(k), now) ;
}
void Setup(){
h = log(N) / log(2) + 1 ;
for (j = 1 ; j <= h ; ++ j)
for (i = 1 ; i <= N ; ++ i)
fa[i][j] = fa[fa[i][j - 1]][j - 1] ;
}
int lca(int u, int v){
if (dep[u] < dep[v]) u ^= v ^= u ^= v ; l = dep[u] - dep[v] ;
for (int k = h ; k >= 0 ; -- k) if (dep[fa[u][k]] >= dep[v]) u = fa[u][k] ;
if (u == v) return u ; for (int k = h ; k >= 0 ; -- k) if (fa[u][k] != fa[v][k]) u = fa[u][k], v = fa[v][k] ; return fa[u][0] ;
}
inline int qr(){
register int k = 0 ; char c = getchar() ; while(!isdigit(c)) c = getchar() ;
while(isdigit(c)) k = (k << 1) + (k << 3) + c - 48, c = getchar() ; return k ;
}
inline int wo(int a, int b, int c){ return -(dep[c] << 1) + (dep[a] + dep[b]) ; }
}
namespace pks{
using namespace Prepare ;
vector <int> v1[MAXN], v2[MAXN], v3[MAXN] ;
int buc_d[MAXN << 2], buc_u[MAXN << 2], ans[MAXN] ;
void dfs1(int now, int fa){
int co = base[now] + dep[now], ks ; if (co <= H) ks = buc_d[co] ;
for (int k = head[now] ; k ; k = E[k].next) if (fa ^ to(k)) dfs1(to(k), now) ;
buc_d[dep[now]] += cnbt[now] ; if (co <= H) ans[now] = buc_d[co] - ks ;
for (int k = 0 ; k < v1[now].size() ; ++ k) -- buc_d[dep[v1[now][k]]] ;
}
void dfs2(int now, int fa){
int co = dep[now] - base[now] + N, ks = buc_u[co] ;
for (int k = 0 ; k < v2[now].size() ; ++ k) ++ buc_u[v2[now][k] + N] ;
for (int k = head[now] ; k ; k = E[k].next) if (fa ^ to(k)) dfs2(to(k), now) ;
ans[now] += buc_u[co] - ks ;
for (int k = 0 ; k < v3[now].size() ; ++ k) -- buc_u[v3[now][k] + N] ;
}
void Solve5(){
for (int i = 1 ; i <= M ; ++ i)
cnbt[s[i]] ++, v1[LCA[i]].push_back(s[i]) ; dfs1(1, 0) ;
for (int i = 1 ; i <= M ; ++ i)
v2[e[i]].push_back(dep[e[i]] - _up[i]),
v3[LCA[i]].push_back(dep[e[i]] - _up[i]) ; dfs2(1, 0) ;
for (int i = 1 ; i <= M ; ++ i)
if (dep[s[i]] - dep[LCA[i]] == base[LCA[i]]) -- ans[LCA[i]] ;
for (int i = 1 ; i <= N ; ++ i) printf("%d ", ans[i]) ;
}
}
int main(){
using namespace Prepare ; cin >> N >> M ;
for (i = 1 ; i < N ; ++ i) x = qr(), y = qr(), Add(x, y) ;
for (i = 1 ; i <= N ; ++ i) scanf("%d", &base[i]) ;
for (i = 1 ; i <= M ; ++ i) scanf("%d%d", &s[i], &e[i]) ;
build(1, 0), Setup() ;
for (i = 1 ; i <= M ; ++ i)
LCA[i] = lca(s[i], e[i]), _up[i] = wo(s[i], e[i], LCA[i]) ;
pks :: Solve5() ; return 0 ;
}

嗯,然后这道题就完了。不得不说虽然当时用心做了,但是过上几周再反过头来看还是觉得有些细节理解的并不到位、或者说是满分做法中的有些流程当时根本没有仔细推导。

不过不得不说这个题还是非常妙的。或许有时候题面复杂、需求复杂会让人忘记这道题到底有多巧妙…反正就是感觉这道题用“桶+即时修改”这个组合思想还是很nice的。

$4~2012F$ 疫情控制

$Link$

…这个题之所以放在最后一个是因为我真的不知道部分分该怎么写啊。

嗯,首先是二分,这倒是可以想到。之后一开始想的是似乎不断把城市向上移动就好了,毕竟越靠上越优;但是样例就把我这种写法卡掉了,原因很浅显,我忽略了绕过根继续走的那些点可以继续产生贡献……于是就很GG。

…于是我选择统计了那些可以跨越根的节点。对于最终每个被覆盖的节点,我用的是直接更新vector预处理出来挂在每个点底下的叶子节点,check的时候直接判一下每个节点的mark。然而这样写的很繁琐,并且复杂度也是个迷…最后只能不了了之了

所以大概这个题我想出了50%~60%?…然而还是没有分数。

$\rm{Part~1}$ 倍增!倍增!倍增!

首先喜闻乐见的是,我们向上跳的时候van♂全可以用倍增来搞,只要预处理出$2^k$级祖先就好了。

然后注意顺便判断一下可不可以拐弯,即跳到根之后是否在二分的时间内可以继续向下跳。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#define fr first
#define sc second
#define mp(a, b) make_pair(a, b)
pair<int ,int> Army[MAXN], Pest[MAXN] ;
memset(res, 0, sizeof(res)) ;
memset(Army, 0, sizeof(Army)) ;
memset(Pest, 0, sizeof(Pest)) ;
for (i = 1 ; i <= M ; ++ i){
t = base[i] ;
for (j = 20 ; j >= 0 ; -- j)
if (!fa[t][j] || Sum[base[i]] - Sum[fa[t][j]] > x) continue ;
else t = fa[t][j] ;
if (t > 1) res[t] = 1 ;
else {
t = base[i] ;
for (j = 20 ; j >= 0 ; -- j)
if (fa[t][j] > 1) t = fa[t][j] ;
Army[++ n] = mp(x - Sum[base[i]], t) ;
}
}

$\rm{Part~2}$ 转化!转化!转化!

这个地方有个肥肠有意思的点,就是我们思考假设一个叶子节点没有被覆盖,那么就说明一定存在它的某一级祖先的整棵子树没有被覆盖。那么这就提示我们可以考虑直接判断根的每个儿子是否都被覆盖了(树形结构的优越性)

嗯,于是对于我们上一部分打完mark之后的那些点(暂时是只有不会拐弯的被打了mark),我们直接考虑不进行一次$O(n)$的dfs就可以完成push_up的操作。

然后我们考虑如何操作那些可以拐弯的点。思考最优的方案一定是越高越好,所以不妨就让他拐过来之后落在根的儿子上。于是我们需要统计这个的代价,并对收集来的两个信息分别排序。之后就直接双指针扫一遍根的全部儿子,看看是否全部都被覆盖了即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void push_down(int rt){
bool x = 1, y = 0 ;
for (int k = head[rt] ; k ; k = E[k].next){
if (to(k) == fa[rt][0]) continue ;
push_down(to(k)) ; x &= res[to(k)] ; y = 1 ;
}
if (rt > 1 && x && y) res[rt] = 1 ;
}
....
push_down(1) ;
for (int k = head[1] ; k ; k = E[k].next)
if (res[to(k)]) continue ; else Pest[++ m] = mp(E[k].v, to(k)) ;
j = 1 ; sort(Army + 1, Army + n + 1, cmp), sort(Pest + 1, Pest + m + 1, cmp) ;
for (i = 1 ; i <= n ; ++ i){
if (!res[Army[i].sc]) res[Army[i].sc] = 1 ;
else if (Army[i].fr >= Pest[j].fr) res[Pest[j].sc] = 1 ;
while (res[Pest[j].sc] && j <= m) ++ j ;
}
return j > 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
struct Edge{
int to, next, v ;
}E[MAXN << 1] ; int cnt, head[MAXN], n, m ; bool res[MAXN] ;
int N, M, P, Sum[MAXN], ans, base[MAXN], fa[MAXN][25], i, j, l, r, mid ;
inline void Add(int u, int v, int w){
P += w ;
E[++ cnt].to = v, E[cnt].v = w, E[cnt].next = head[u], head[u] = cnt ;
E[++ cnt].to = u, E[cnt].v = w, E[cnt].next = head[v], head[v] = cnt ;
}

#define fr first
#define sc second
#define mp(a, b) make_pair(a, b)
pair<int ,int> Army[MAXN], Pest[MAXN] ;
inline bool cmp(pair<int, int> a, pair<int, int> b){ return a.fr < b.fr ; }

void Init(){
for (i = 1 ; i <= 20 ; ++ i)
for (j = 1 ; j <= N ; ++ j)
fa[j][i] = fa[fa[j][i - 1]][i - 1] ;
}
void dfs(int now, int f){
fa[now][0] = f ;
for (int k = head[now] ; k ; k = E[k].next){
if (to(k) == f) continue ;
Sum[to(k)] = Sum[now] + E[k].v ; dfs(to(k), now) ;
}
}
void push_down(int rt){
bool x = 1, y = 0 ;
for (int k = head[rt] ; k ; k = E[k].next){
if (to(k) == fa[rt][0]) continue ;
push_down(to(k)) ; x &= res[to(k)] ; y = 1 ;
}
if (rt > 1 && x && y) res[rt] = 1 ;
}
bool check(int x){
int t ; n = m = 0 ;
memset(res, 0, sizeof(res)) ;
memset(Army, 0, sizeof(Army)) ;
memset(Pest, 0, sizeof(Pest)) ;
for (i = 1 ; i <= M ; ++ i){
t = base[i] ;
for (j = 20 ; j >= 0 ; -- j)
if (!fa[t][j] || Sum[base[i]] - Sum[fa[t][j]] > x) continue ; else t = fa[t][j] ;
if (t > 1) res[t] = 1 ; else { t = base[i] ; for (j = 20 ; j >= 0 ; -- j) if (fa[t][j] > 1) t = fa[t][j] ; Army[++ n] = mp(x - Sum[base[i]], t) ; }
}
push_down(1) ; for (int k = head[1] ; k ; k = E[k].next) if (res[to(k)]) continue ; else Pest[++ m] = mp(E[k].v, to(k)) ;
j = 1 ; sort(Army + 1, Army + n + 1, cmp), sort(Pest + 1, Pest + m + 1, cmp) ;
for (i = 1 ; i <= n ; ++ i){
if (!res[Army[i].sc]) res[Army[i].sc] = 1 ;
else if (Army[i].fr >= Pest[j].fr) res[Pest[j].sc] = 1 ;
while (res[Pest[j].sc] && j <= m) ++ j ;
}
return j > m ;
}
int main(){
cin >> N ; int a, b, c ;
for (i = 1 ; i < N ; ++ i) scanf("%d%d%d", &a, &b, &c), Add(a, b, c) ;
cin >> M ; for (i = 1 ; i <= M ; ++ i) scanf("%d", &base[i]) ; dfs(1, 0) ; Init() ;
l = 0, r = P ;
while (l <= r){
mid = (l + r) >> 1 ;
if (check(mid)) r = mid - 1, ans = mid ; else l = mid + 1 ;
}
cout << ans << endl ; return 0 ;
}

$\rm{Afterword}$

其实总感觉自己做这些题还是有些力不从心233

不得不说类似于“二分答案”这种东西是很有OI风味的,毕竟是一种特殊的思想…不知道自己什么时候能把类似的所有思想真正地打包学会啊qaq