【CodeForces】[673B]Problems for Round

问题描述

问题分析

求把题目划分为两个部分的可行方案种类数

因为要满足div1的都要比div2的大
同时给出一对要在两个div
并且这个关系不传递

所以对于给出的每一对
大的必须要在div1
小的必须在div2

同时更新div1中的最小值和div2的最大值

最后若div1的最小值没有超过div2的最大值
则一定无法划分

否则min-max的题目都有两种划分方法
其余的有一种划分方法
所以方案数为min-max

若没给任何对关系
则方案数为n-1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include<stdio.h>
#include<string.h>
//int a[100200];
int main() {
	int n,m;
	while(scanf("%d %d",&n,&m)!=EOF) {
//		memset(a,0,sizeof(a));
		int min=n,max=0;
		while(m--) {
			int x,y;
			scanf("%d %d",&x,&y);
	//		a[x]=a[y]=1;
			int t=x>y?x:y;
			min=min>t?t:min;
			t=x<y?x:y;
			max=max<t?t:max;
		}
		if(min<=max) {
			printf("0\n");
			continue;
		}
		printf("%d\n",min-max==n?n-1:min-max);
	}
	return 0;
}

题目地址:【CodeForces】[673B]Problems for Round