Processing math: 100%
SEERC 2018 I. Inversion

SEERC 2018 I. Inversion

题目链接

http://codeforces.com/gym/101964/problem/I

题目大意

用一个 1n 的一个数列的一个排列来构图。在数列中所有的逆序对的点对中建边。现在给你这个图的所有边,问你一共有多少种点的集合,使得这个集合中任意两个点都没有边相连,且其余所有点都最少与这个集合中的一个点相连。

题目分析

根据题目的提示,考虑可能需要将图还原成数列进行分析。我们考虑从这个数列中选出若干个点作为这个集合,那么这个集合应具备以下几个性质:

  1. 这若干个数应该是升序排列的,否则会出现逆序对出现连边。
  2. 对于这些数的右边的所有的点,应当都比选出来的最大的数(选出来的数的最后一个数)要小,这样才会出现逆序对,与点集有连边。
  3. 对于其他的不属于这个集合的点,应当不存在一个点,使得加入这个点后,这个选出来的数所组成的数列仍保持升序。因为如此的话应当是不存在逆序对的。

根据这性质 1, 3,可以进行 DP,计算出以每个点结尾的满足条件的升序数列有多少种情况,之后用性质 2 进行校验即可。

代码

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
using namespace std;
const int maxn = 100 + 5;
int n, m;
int cnt[maxn];
int a[maxn];
long long f[maxn];
int maxx[maxn];
int read(){
int x;
scanf("%d", &x);
return x;
}
int main(){
int i, j;
int x, y;
long long ans = 0;
n = read();
m = read();
for(i=1;i<=m;i++){
x = read();
y = read();
cnt[max(x, y)]++;
}
for(i=n;i>0;i--){
int t = 0;
for(j=n;j>0;j--){
if(!a[j]){
if(t == cnt[i]){
a[j] = i;
break;
}else{
t++;
}
}
}
}
for(i=n;i>=1;i--){
maxx[i] = max(maxx[i + 1], a[i]);
}
f[0] = 1;
for(i=1;i<=n;i++){
int t = 0;
for(j=i-1;j>=1;j--){
if(a[j] < a[i]){
t = max(t, a[j]);
if(a[j] >= t){
f[i] += f[j];
}
}
}
if(f[i] == 0){
f[i] = 1;
}
}
for(i=1;i<=n;i++){
if(a[i] > maxx[i + 1]){
ans += f[i];
}
}
printf("%lld\n", ans);
return 0;
}
#include <iostream> #include <cstdio> #include <cstdlib> #include <cmath> #include <cstring> #include <string> #include <algorithm> using namespace std; const int maxn = 100 + 5; int n, m; int cnt[maxn]; int a[maxn]; long long f[maxn]; int maxx[maxn]; int read(){ int x; scanf("%d", &x); return x; } int main(){ int i, j; int x, y; long long ans = 0; n = read(); m = read(); for(i=1;i<=m;i++){ x = read(); y = read(); cnt[max(x, y)]++; } for(i=n;i>0;i--){ int t = 0; for(j=n;j>0;j--){ if(!a[j]){ if(t == cnt[i]){ a[j] = i; break; }else{ t++; } } } } for(i=n;i>=1;i--){ maxx[i] = max(maxx[i + 1], a[i]); } f[0] = 1; for(i=1;i<=n;i++){ int t = 0; for(j=i-1;j>=1;j--){ if(a[j] < a[i]){ t = max(t, a[j]); if(a[j] >= t){ f[i] += f[j]; } } } if(f[i] == 0){ f[i] = 1; } } for(i=1;i<=n;i++){ if(a[i] > maxx[i + 1]){ ans += f[i]; } } printf("%lld\n", ans); return 0; }
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>

using namespace std;

const int maxn = 100 + 5;

int n, m;

int cnt[maxn];
int a[maxn];

long long f[maxn];

int maxx[maxn];

int read(){
	int x;
	scanf("%d", &x);
	return x;
}

int main(){
	int i, j;
	int x, y;
	long long ans = 0;
	
	n = read();
	m = read();
	
	for(i=1;i<=m;i++){
		x = read();
		y = read();
		cnt[max(x, y)]++;
	}
	
	for(i=n;i>0;i--){
		int t = 0;
		for(j=n;j>0;j--){
			if(!a[j]){
				if(t == cnt[i]){
					a[j] = i;
					break;
				}else{
					t++;
				}
			}
		}
	}
	
	for(i=n;i>=1;i--){
		maxx[i] = max(maxx[i + 1], a[i]);
	}
	
	f[0] = 1;
	
	for(i=1;i<=n;i++){
		int t = 0;
		for(j=i-1;j>=1;j--){
			if(a[j] < a[i]){
				t = max(t, a[j]);
				if(a[j] >= t){
					f[i] += f[j];
				}
			}
		}
		if(f[i] == 0){
			f[i] = 1;
		}
	}
	
	for(i=1;i<=n;i++){
		if(a[i] > maxx[i + 1]){
			ans += f[i];
		}
	}
	
	printf("%lld\n", ans);
	
	return 0;
}

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据