Codeforces Round 875 (Div. 2) C-D题解

C

Problem - C - Codeforces

我们发现题述所形成的父亲节点一定比子节点先画出，并且如果子节点顺序在父节点后面，则父，子节点为同一个周期加入。反之，则子节点的周期为父节点+1。所以做法考虑树上dp，维护第i个节点加入树的周期。转移方程如下：

其中u为父节点，x为子节点，e[u]为父节点的加入顺序，i为子节点加入顺序。

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;

void solve(){
	int n;
	cin>>n;
	vector<pair<int,int>> edge[n+1];
	for(int i=1;i<n;i++){
		int u,v;
		cin>>u>>v;
		edge[u].push_back({v,i});  //双向存图，因为可能从两边连边
		edge[v].push_back({u,i});	
	}
	edge[0].push_back({1,n});

	vector<int> e(n+1),f(n+1);  //e[x]为加入x点的顺序，可以在dfs的过程中维护
	e[0]=n;
	function<void(int,int)> dfs=[&](int u,int p){
		for(auto [x,i]:edge[u]){
			if(x!=p){
				e[x]=i;
				f[x]=f[u]+(e[u]>e[x]);
				dfs(x,u);
			}
		}
	};
	dfs(0,-1);
	int ans=0;
	for(int i=1;i<=n;i++){
		ans=max(ans,f[i]);
	}
	cout<<ans<<'\n';
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);

	int t;
	cin>>t;
	while(t--){
		solve();
	}
	return 0;
}

D

Problem - D - Codeforces

这种题考虑研究数的性质，考虑如何更好地暴力枚举。

我们发现a,b均小于n，然后我们发现\(s=a_i*a_j=b_i+b_j\)必然小于\(2n\),则发现\(a_i和a_j\)较小的(其实就是\(a_i\))一定小于\(sqrt(2n)\),考虑我们第一维枚举较小的\(a_i\) ，第二位枚举所有的\(a,b数对\),然后可以算出对应的\(b[i]\)，这时我们需要知道了\(b[i]\)的个数，我们可以在第二维遍历时就更新\(b[i]\)个数,因为更新时\(s=a[i]\)所以一定是在满足条件前枚举。考虑到我们只枚举了\(a[i]<a[j]\)的情况，其实这已经是所以的情况，因为考虑位置的关系，所以情况要除2。注意时间复杂度\(O(nsqrt(2n))\)

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;

void solve(){
	int n;
	cin>>n;
	vector<pair<i64,i64>> c(n+1);
	for(int i=1;i<=n;i++){
		cin>>c[i].first;
	}
	for(int i=1;i<=n;i++){
		cin>>c[i].second;
	}
	sort(c.begin(),c.end());
	i64 ans=0;
	vector<i64> cnt(n+1);
	for(int s=1;s*s<=2*n;s++){
		cnt.assign(n+1,0);
		for(auto [a,b]:c){
			int v=1LL*s*a-b;
			if(v>=1&&v<=n){
				ans+=cnt[v];
			}
			if(1LL*s==a) cnt[b]++;
		}
	}
	cout<<ans<<'\n';
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);

	int t;
	cin>>t;
	while(t--){
		solve();
	}
	return 0;
}