专栏文章

题解：CF985G Team Players

HHPXXZYY
CF985G题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mipm6wx5
此快照首次捕获于
2025/12/03 14:17
3 个月前
此快照最后确认于
2025/12/03 14:17
3 个月前
查看原文
我敢赌，就算你知道怎么做，也必然得调试半天才能 AC。
[Analysis]\color{blue}{\texttt{[Analysis]}}
显然不可能正面计算。所以被迫正难则反。
把所有三元组分成四类：不考虑有没有边相连；有且只有一条边连接；有且只有两条边连接；三个点形成三元环。
每种情况分别考虑。
  1. 不考虑有没有边相连。
    等价于对所有 (i,j,k)s.t.0≤i<j<k<n(i,j,k) \quad \text{s.t.} \quad 0 \leq i <j<k<n 求出 ∑legal (i,j,k)Ai+Bj+Ck\sum\limits_{\text{legal (i,j,k)}} Ai+Bj+Ck。
    枚举 kk，则 (i,j)(i,j) 只能在 [0,k−1][0,k-1] 中取值，共 k(k−1)2\dfrac{k(k-1)}{2} 种情况。
    对于固定的 kk，∑0≤i<j<kAi+Bj=∑0≤i<k−1(∑i<j<kAi+Bj)=∑0≤i<k−1(Ai(k−i−1)+∑i<j<kBj)\sum\limits_{0 \leq i < j <k}Ai+Bj=\sum\limits_{0 \leq i < k-1}\left ( \sum\limits_{i<j<k}Ai+Bj \right )=\sum\limits_{0\leq i <k-1} \left ( Ai(k-i-1)+\sum\limits_{i<j<k}Bj\right )
    然后把括号内的项展开，可以得到关于 ∑i2\sum i^2，∑i\sum i 的式子，这些式子都是有公式可以 O(1)O(1) 计算的。
  2. 有且只有一条边连接的三元组。
    枚举每条边 (u,v)s.t.u<v(u,v) \quad \text{s.t.} \quad u<v，则第三个点 ww 只有三种情况：w<u<vw<u<v，u<w<vu<w<v，u<v<wu<v<w。每种情况下 u,vu,v 的贡献都是确定的，而 ww 的和是连续正整数的和，可以用公式求出。
    注意： 用这种方法求出的三元组包含了第三步和第四步的情况。因此，准确地说，第二种情况是有边相连的三元组。
  3. 有且只有两条边连接的三元组。
    这是最不好想的一种情况。不仅容易漏掉，也不好想解决方法。
    正解还是很惊艳的。三个点有且只有两条边连接，必然两条边有一个公共点。枚举这个公共点 uu，那么 v,wv,w 就只能在和 uu 有边相连的点集中取值。
    问题是，这个点集可能很大，怎么办？
    那我们就不要同时考虑 v,wv,w，仅考虑单个点对答案的贡献。
    如果 v<uv<u，那么 vv 前面的系数可能是 AA 或者 BB（绝对不会是 CC）。如果系数是 AA，那么 ww 比 vv 大。在一个有限的点集中，我们很容易知道这样的 ww 有多少个，因此 AvAv 的系数我们就可以求出来（请注意，我们只算 vv 的贡献，至于 ww 的和我们先不考虑）。其它情况同理。
    枚举点集里的所有点，即可求出第三种情况的贡献。
    注意： 第三步里也重复计算了第四步的情况。
  4. 有三条边连接的三元组。
    这部分最简单了。直接用三元组计数的模板即可。
    （当然，不会这个模板就是送命。）
现在来考虑容斥系数。分别记四个步骤算出来的结果为 S1,S2,S3,S4S_1,S_2,S_3,S_4。
  • 所有的三元组都会在第一步中计算且仅计算一次。
  • 第二步中，有且仅有一条边连接的三元组仅计算了一次，两条边相连的三元组计算了两次，三条边相连的三元组计算了三次。
  • 第三步中，有两条边相连的二元组计算了一次；三条边相连的三元组计算了三次。
  • 第四步中，三条边连接的三元组都仅计算了一次。
因此，通过你聪明的大脑，你一定可以发现，答案就是 S1−S2+S3−S4S_1-S_2+S_3-S_4。
就这么开心的写代码吧。小心细节不要 WA 哦。
Code\color{blue}{\text{Code}}
CPP
typedef unsigned long long ll; 

const int N=2e5+100; 

int n,m,A,B,C,u[N],v[N];
ll ans;
vector<int> edge[N],e[N];

ll pre_sqr(int n){
	return 1ull*n*(n+1)/2*(2*n+1)/3;
}
ll pre_sum(int n){
	return 1ull*n*(n+1)/2;
}
ll get_sum(int a,int b){
	int t=(b-a+1);
	return 1ull*(a+b)*t/2;
}

ll get_all(){
	ll cnt,tmp1,tmp2,res=0;
	
	for(int j=2;j<n;j++){
//		从 0 到 j-1 中选出两个数
		int i=j-1;//写着简单 
		
		cnt=pre_sum(i);
		tmp1=1ull*i*pre_sum(i-1)-pre_sqr(i-1);
		tmp2=pre_sqr(i);
		
		res+=1ull*tmp1*A;
		res+=1ull*tmp2*B;
		res+=1ull*cnt*C*j;
	}
	
	return res;
}//第一步

ll get_minus(){
	ll res=0;
	
	for(int i=1;i<=m;i++){
		if (u[i]>v[i]) swap(u[i],v[i]);
		
		//(x, u[i], v[i])
		if (u[i]>0)
			res+=1ull*A*pre_sum(u[i]-1)+1ull*u[i]*(1ull*B*u[i]+1ull*C*v[i]);
		
		//(u[i], x, v[i])
		if (v[i]-u[i]>1)
			res+=1ull*B*get_sum(u[i]+1,v[i]-1)+(1ull*A*u[i]+1ull*C*v[i])*(v[i]-u[i]-1);
		//(u[i], v[i], x)
		if (v[i]<n-1)
			res+=1ull*C*get_sum(v[i]+1,n-1)+(1ull*A*u[i]+1ull*B*v[i])*(n-1-v[i]);
	} 
	
	return res;
}//第三步

int ind[N],vistime[N];

ll get_triple(){
	ll res=0;
	
	for(int i=1;i<=m;i++){
		++ind[u[i]];
		++ind[v[i]];
	}
	
	for(int i=1;i<=m;i++){
		if (ind[u[i]]>ind[v[i]]) swap(u[i],v[i]);
		else if ((ind[u[i]]==ind[v[i]])&&(u[i]>v[i])) swap(u[i],v[i]);
		
		edge[u[i]].push_back(v[i]);
	}
	
	memset(vistime,-1,sizeof(vistime));//注意这里，不然可能会多算出一些三元组
	for(int i=0;i<n;i++){
		for(int j:edge[i]) vistime[j]=i;
		
		for(int j:edge[i])
			for(int k:edge[j])
				if (vistime[k]==i){//因为这里
					int t[]={i,j,k};
					sort(t,t+3);
					
					res+=1ull*A*t[0]+1ull*B*t[1]+1ull*C*t[2];
				}
	}
	
	return res;
}//第四步，三元环计数的板子

ll get_add(){
	for(int i=1;i<=m;i++){
		e[u[i]].push_back(v[i]);
		e[v[i]].push_back(u[i]);
	}
	
	ll res=0;
	
	for(int u=0;u<n;u++){
		e[u].push_back(u);
		sort(e[u].begin(),e[u].end());
		
		int x=e[u].size()-1;
		if (x==0) continue;
		
		for(int i=0;i<=x;i++){
			int v=e[u][i];
			
			if (v<u)
				res+=1ull*A*v*(x-i-1)+1ull*B*v*i;
			else if (v>u)
				res+=1ull*B*v*(x-i)+1ull*C*v*(i-1);
			else
				res+=1ull*v*(1ull*(x-i)*(x-i-1)/2*A+1ull*B*(x-i)*i+1ull*i*(i-1)/2*C); 
		}
	}//第二步
	
	return res;
}

int main(){
	n=read();m=read();
	A=read();B=read();C=read();
	for(int i=1;i<=m;i++){
		u[i]=read();
		v[i]=read();
	}
	
	ans=get_all()-get_minus()+get_add()-get_triple();
	
	cout<<ans<<endl;
	
	return 0;
}
最后，Good luck to you。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...