差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2020-2021:teams:legal_string:jxm2001:contest:ccpc_wannafly_winter_camp_day1 [2020/09/13 22:37]
jxm2001 创建
+++ 2020-2021:teams:legal_string:jxm2001:contest:ccpc_wannafly_winter_camp_day1 [2020/09/20 21:11] (当前版本)
jxm2001 [题解]
@@ 行 2: / 行 2: @@
 [[https://ac.nowcoder.com/acm/contest/3979|比赛链接]]
+===== A. 期望逆序对 =====
+==== 题意 ====
+给定 $n$ 个随机变量，第 $i$ 个变量的取值为 $[l_i,r_i]$ 中的随机一个数。
+要求将 $n$ 个随机变量重新排列，使得最终的逆序对的期望值最小。询问该方案下逆序对的期望值。
+==== 题解 ====
+假设最终排序为 $p_1p_2\cdots p_n$，考虑相邻两个随机变量 $p_i$ 和 $p_{i+1}$，显然 $p_i$ 大于 $p_{i+1}$ 的概率不超过 $\frac 12$ 时最优。
+事实上，这等价于 $l_i+r_i\le l_{i+1}r_{i+1}$，发现不等号两边的式子只与自身有关。
+于是该性质具有传递性，于是对不相邻的随机变量也应该满足该约束，对序列按上述关键字排序即可得到最终序列。
+考虑暴力计算最终答案，枚举数对 $i\lt j$，该数对的贡献为 $\sum_{k=l_i}^{r_i}\max(0,\min(k-l_j,r_j-l_j+1))$，可以 $O(1)$ 计算。
+时间复杂度 $O(n^2)$。
+<hidden 查看代码>
+<code cpp>
+const int MAXN=5e3+5,Mod=998244353;
+int Inv[MAXN];
+int inv(int x){
+	int k=Mod-2,ans=1;
+	while(k){
+		if(k&1)ans=1LL*ans*x%Mod;
+		x=1LL*x*x%Mod;
+		k>>=1;
+	}
+	return ans;
+}
+struct Seg{
+	int lef,rig;
+	bool operator < (const Seg &b)const{
+		return lef+rig<b.lef+b.rig;
+	}
+}seg[MAXN];
+int cal(int l1,int r1,int l2,int r2){
+	if(r1<=l2)return 0;
+	int s=0,L=max(l1,l2+1),R=min(r1,r2);
+	if(r1>r2)
+	s=1LL*(r1-r2)*(r2-l2+1)%Mod;
+	s=(s+1LL*(R-l2+L-l2)*(R-L+1)/2)%Mod;
+	return s;
+}
+int main()
+{
+	int n=read_int();
+	_for(i,0,n)
+	seg[i].lef=read_int(),seg[i].rig=read_int();
+	sort(seg,seg+n);
+	int ans=0;
+	_for(i,0,n)
+	Inv[i]=inv(seg[i].rig-seg[i].lef+1);
+	_for(i,0,n)
+	_for(j,i+1,n)
+	ans=(ans+1LL*Inv[i]*Inv[j]%Mod*cal(seg[i].lef,seg[i].rig,seg[j].lef,seg[j].rig))%Mod;
+	enter(ans);
+	return 0;
+}
+</code>
+</hidden>
+===== E. 树与路径 =====
+==== 题意 ====
+给定一个有根树，定义任意两点 $u,v$ 的路径为 $\text{dis}(u,p)\text{dis}(v,p)(p=\text{LCP}(u,v))$。
+给定 $m$ 条路径，询问以每个结点为跟时所有路径的权值和。
+==== 题解 ====
+先考虑每条路径对以路径上每个结点为根节点时答案的贡献，记 $\text{dis}(u,v)=L$。
+对 $u\to p$ 上路径的每个结点，不难得出该路径对某个结点 $i$ 的贡献为 $(d_u-d_i)(L-d_u+d_i)$。
+而对路径上的其他结点，该路径对该点的贡献等于该路径对路径上距离该点最近的结点的贡献。
+于是可以树上差分维护该路径对所有点的贡献，其中路径 $u\to p(\text{不含} p)$ 的点的差分值为 $2(d_u-d_i)+1-L$，同理 $v\to p(\text{不含} p)$ 也类似。
+而其他点差分值为 $0$。发现差分值为等差数列，于是考虑利用子树和维护路径 $u\to p(\text{不含} p)$ 的差分值。
+注意子树和维护最后结点 $p$ 的差分值为 $2(d_u-d_p)+1-L+2(d_v-d_p)+1-L=2$，而 $p$ 的实际差分值应该为 $0$，需要修正。
+总时间复杂度 $O(n+m\log n)$。
+<hidden 查看代码>
+<code cpp>
+const int MAXN=3e5+5;
+struct Edge{
+	int to,next;
+}edge[MAXN<<1];
+int head[MAXN],edge_cnt;
+void Insert(int u,int v){
+	edge[++edge_cnt]=Edge{v,head[u]};
+	head[u]=edge_cnt;
+}
+namespace LCA{
+	int d[MAXN],sz[MAXN],f[MAXN];
+	int h_son[MAXN],mson[MAXN],p[MAXN];
+	void dfs_1(int u,int fa,int depth){
+		sz[u]=1;f[u]=fa;d[u]=depth;mson[u]=0;
+		for(int i=head[u];i;i=edge[i].next){
+			int v=edge[i].to;
+			if(v==fa)
+			continue;
+			dfs_1(v,u,depth+1);
+			sz[u]+=sz[v];
+			if(sz[v]>mson[u])
+			h_son[u]=v,mson[u]=sz[v];
+		}
+	}
+	void dfs_2(int u,int top){
+		p[u]=top;
+		if(mson[u])dfs_2(h_son[u],top);
+		for(int i=head[u];i;i=edge[i].next){
+			int v=edge[i].to;
+			if(v==f[u]||v==h_son[u])
+			continue;
+			dfs_2(v,v);
+		}
+	}
+	void Init(int root){dfs_1(root,0,0);dfs_2(root,root);}
+	int query_lca(int u,int v){
+		while(p[u]!=p[v]){
+			if(d[p[u]]<d[p[v]])swap(u,v);
+			u=f[p[u]];
+		}
+		return d[u]<d[v]?u:v;
+	}
+};
+LL dp1[MAXN],dp2[MAXN];
+void dfs1(int u,int fa){
+	for(int i=head[u];i;i=edge[i].next){
+		int v=edge[i].to;
+		if(v==fa)continue;
+		dfs1(v,u);
+		dp1[u]+=dp1[v];
+		dp2[u]+=dp2[v]+dp1[v];
+	}
+}
+void dfs2(int u,int fa){
+	for(int i=head[u];i;i=edge[i].next){
+		int v=edge[i].to;
+		if(v==fa)continue;
+		dp2[v]+=dp2[u];
+		dfs2(v,u);
+	}
+}
+int main()
+{
+	int n=read_int(),m=read_int();
+	_for(i,1,n){
+		int u=read_int(),v=read_int();
+		Insert(u,v);
+		Insert(v,u);
+	}
+	LCA::Init(1);
+	LL s=0;
+	while(m--){
+		int u=read_int(),v=read_int(),p=LCA::query_lca(u,v),len=LCA::d[u]+LCA::d[v]-2*LCA::d[p];
+		dp1[u]+=2,dp1[v]+=2,dp1[p]-=4;
+		dp2[u]+=1-len,dp2[v]+=1-len,dp2[p]-=2;
+		s+=1LL*(LCA::d[u]-LCA::d[p])*(LCA::d[v]-LCA::d[p]);
+	}
+	dfs1(1,0);
+	dp2[1]+=s;
+	dfs2(1,0);
+	_rep(i,1,n)enter(dp2[i]);
+	return 0;
+}
+</code>
+</hidden>
 ===== I. K 小数查询 =====
@@ 行 20: / 行 197: @@
 修改完成后同样打上懒标记，必要时下放标记。
-显然每次修改复杂度为 $O(k\log n)$，其中 $k$ 为该次修改删除的权值线段树的叶子数。
+显然每次修改复杂度为 $O(k\log^2 n)$，其中 $k$ 为该次修改删除的权值线段树的叶子数。
-由于初始时仅有 $O(n\log n)$ 个权值线段树的叶子结点，于是修改操作的总时间复杂度为 $O(n\log^2 n)$。
+由于初始时仅有 $O(n\log n)$ 个权值线段树的叶子结点，于是修改操作的总时间复杂度为 $O(n\log^3 n)$。
 于是总时间复杂度 $O(n\log^3 n)$，总空间复杂度 $O(n\log^2 n)$。

CVBB ACM Team

用户工具

站点工具

差别

页面工具