当前位置：首页 > news >正文

2025.11 做题记录

news 2026/6/22 2:43:19

P3412 仓鼠找sugar II

solution

先把题意转化成，求对于所有 \(a,b\) 的情况，从 \(a\) 走到 \(b\) 的期望步数和。

对于这个东西，把每条边的贡献拆出来。答案即 \(\sum 每条边的经过次数 \times 走过每条边的期望步数\)。

下文 \(siz_u\) 为 \(u\) 的子树大小，\(deg_u\) 为 \(u\) 的度数，\(v\in u\) 表示 \(v\) 是 \(u\) 的儿子，\(fa\) 默认 \(u\) 的父亲。

设 \(f_u\) 为从 \(u\) 走到 \(fa\) 的期望步数，\(g_u\) 为从 \(fa\) 走到 \(u\) 的期望步数。

我们有：

\[\begin{align} f_u&=\frac{1}{deg_u}(1+\sum_{v\in u}(1+f_v+f_u))\\ &=deg_u+\sum_{v\in u} f_v\\ g_u&=\frac{1}{deg_{fa}}(1+\sum_{\substack{v\in fa\\v\neq u}}(1+f_v+f_u))\\ &=deg_{fa}+\sum_{\substack{v\in fa\\v\neq u}} f_v \end{align} \]

求这个东西没什么难度吧！

然后计算每条边的经过次数。其实比较简单，\(u\) 走到 \(fa\) 的话可选择的起点个数为 \(siz_u\)，终点个数为 \(n-siz_u\)。\(fa\) 走到 \(u\) 同理。

直接统计答案即可。

P3527 [POI 2011] MET-Meteors

在这题 mark 一下整体二分。

solution

考虑只有一个国家怎么做。~~扫过去当然是可以的。~~

使用二分。判断一个 \(i\) 合不合法时，将 \([1,i]\) 的修改全部做完，如果修改后的陨石数量 \(\ge\) 需求量说明答案 \(\le i\)。复杂度 \(O(n\log n)\)。

那么 \(n\) 个国家呢？直接做显然就爆了。但是我们发现做了很多冗余的操作。比如说，第一轮 \(\operatorname{check}(\frac{n}{2})\) 时，所有的国家都会把 \([1,\frac{n}{2}]\) 的操作全部做一次。

所以可以把一些答案确定的区间相同的询问合并在一起做。这样说有点抽象，具体来说：

\(\operatorname{dvd}(L,R,l,r)\) 表示需要处理国家（编号）在 \([L,R]\) 范围内，它们目前的答案范围均为 \([l,r]\)。

我们将 \([1,mid]\) 的操作全部做完（不止一个国家，所以需要上数据结构。BIT 即可。）。此时扫一遍，判断哪些国家已经收集到足够陨石了，将它们扔进 \([l,mid]\) 中，否则扔进 \([mid+1,r]\) 中。实现时可以将合法的部分重新放在 \([L,L+cnt-1]\) 中，剩下的往后排。就不需要用什么动态数组了！

复杂度 \(O(n\log^2 n)\)。

code

当然不能真的“将 \([1,mid]\) 的操作全部做完”。有两种处理方式：

做完当前区间先递归进入右区间，不删除贡献（类似莫队写法？）。这个比较好写，但是在有默认时间维时显然会出问题。
把要递归进右区间的询问 \(k\) 减去 \([1,mid]\) 部分的贡献。

其实感觉说得还是一坨。代码比较好理解。

扔一个分治部分的实现方式。

void dvd(int L,int R,int l,int r){if(L>R||l>r) return;if(l==r){for(int i=L;i<=R;i++) ans[p[i]]=l;return;}const int mid=(l+r>>1);while(liz<mid) upda(++liz,1);while(liz>mid) upda(liz--,0);int lx=0,ly=0;for(int i=L;i<=R;i++){chk(p[i])?(x[++lx]=p[i]):(y[++ly]=p[i]);}for(int i=1;i<=lx;i++) p[L+i-1]=x[i];for(int i=1;i<=ly;i++) p[R-i+1]=y[i];dvd(R-ly+1,R,mid+1,r);dvd(L,L+lx-1,l,mid);
}

Submission。

P3332 [ZJOI2013] K大数查询

solution

二分答案，线段树（因为我不会树状数组维护区间加区间查）维护一段区间内的集合 \(\ge mid\) 的数总共有多少个。

注意这题就属于上文提到的“有默认时间维”一类。

code

因为要保证相对顺序（时间维）稳定，所以略繁琐一点？

void dvd(int L,int R,int l,int r){if(L>R||l>r) return;if(l==r){for(int i=L;i<=R;i++) ans[p[i]]=l;return;}const int md=(l+r>>1);int lx=0,ly=0;for(int z=L,i;z<=R;z++){i=p[z];if(!o[i].op){if(o[i].x>md){y[++ly]=i;upda(i,1);}else{x[++lx]=i;}}else{chk(i)?(y[++ly]=i):(x[++lx]=i);}}for(int i=1;i<=ly;i++){if(!o[y[i]].op) upda(y[i],-1);}for(int i=1;i<=lx;i++) p[L+i-1]=x[i];for(int i=1;i<=ly;i++) p[L+lx+i-1]=y[i];dvd(L,L+lx-1,l,md);dvd(R-ly+1,R,md+1,r);
}

Submission。