GitBook

这里写图片描述

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

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

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

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

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

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

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

#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