专栏文章

题解：P5871 [SEERC 2018] Inversion

TTzh20111118
P5871题解参与者 1已保存评论 0

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@minkj50r
此快照首次捕获于
2025/12/02 03:54
3 个月前
此快照最后确认于
2025/12/02 03:54
3 个月前
查看原文

题目大意

定义一个长为 nn 的排列为一个序列 p1,p2,…,pnp_1, p_2, \dots, p_n，其中 [1,n][1, n] 范围内的整数都恰好在这个序列中出现一次。定义排列中的一个逆序对为一对整数 (i,j)(i, j)，其中 i,j∈[1,n]i, j \in [1,n]，且满足 i<j,pi>pji<j, p_i>p_j。
定义一个逆序对图为一个有 nn 个点的图，图中存在一条 (i,j)(i, j) 的边当且仅当 (i,j)(i,j) 是一个逆序对。
定义一个图中的独立集为一个图中点的集合，满足集合中的点两两之间没有边相连。定义一个图中的支配集为一个图中点的集合，满足不在这个集合中的点都与集合中的某个点有边相连。定义一个图中的独立支配集为一个图中点的集合，这个集合既是独立集又是支配集。
给定某一个长为 nn 的排列的逆序对图，请计算出这个图中独立支配集的数量。
几乎就是复述一遍罢了

解题思路

先求出 cnticnt_i 的值后进行下一步。
然后考虑 dp，可得转移方程式 if(cnt[j]>maxn&&cnt[j]<cnt[i]) maxn=cnt[j],dp[i]+=dp[j];，接下去就是枚举每个求得的值然后比较并累加求和即可。

代码实现

CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=110;
int a[N],cd[N],rd[N],cnt[N],dp[N];
vector<int>G[N<<1];
signed main()
{
	ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
	int n,m;cin>>n>>m;
	for(int i=1;i<=m;i++){
		int u,v;cin>>u>>v;
		if(u>v) swap(u,v);
		G[u].push_back(v);
		cd[u]++,rd[v]++;
	}
	for(int i=1;i<=n;i++) rd[i]=i-rd[i],cnt[i]=rd[i]+cd[i];
	for(int i=1;i<=n;i++){
		int maxn=0;
		for(int j=i-1;j>=1;j--){
			if(cnt[j]>maxn&&cnt[j]<cnt[i]) maxn=cnt[j],dp[i]+=dp[j];
		}
		if(dp[i]==0) dp[i]++;
	}
	int maxn=0,ans=0;
	for(int i=n;i>=1;i--) if(cnt[i]>maxn) maxn=cnt[i],ans+=dp[i];
	cout<<ans;
	return 0;
}

评论

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

正在加载评论...