洛谷基础题-P1047 [NOIP2005 普及组] 校门外的树

洛谷基础题-P1047 [NOIP2005 普及组] 校门外的树 P1047 [NOIP2005 普及组] 校门外的树 1.第一次使用暴力匹配的方法解决，只能过前两个测试点

#include
#include 
#include 
using namespace std;
#define MAX 1000

int main()
{
	int roadLength,zoneNumber;
	int u_v[MAX][2];
	int u,v;
	cin>>roadLength>>zoneNumber;
	int count = 0,countRepeat = 0;
	int result;
	for (int i=0; i>u>>v;
		u_v[i][0] = u;
		u_v[i][1] = v;
		for (int j=0; j u_v[j][0]))
				{
					countRepeat  +=  u_v[i][1] - u_v[j][0] + 1;
				}
				else if(u_v[i][1]  > u_v[j][1])
				{
					countRepeat  +=  u_v[j][1] - u_v[j][0] + 1;
				}
			}
			else if((u_v[i][0]  > u_v[j][0])&&(u_v[i][0]  < u_v[j][1]))
			{
				if((u_v[i][1] < u_v[j][1])&&(u_v[i][1]  > u_v[j][0]))
				{
					countRepeat  +=  u_v[i][1] - u_v[i][0] + 1;
				}
				else if(u_v[i][1] > u_v[j][1])
				{
					countRepeat  +=  u_v[j][1] - u_v[i][0] + 1;
				}
			}else{
				countRepeat  +=  0;
			}
		}
		//计算所有的树木
		count +=  u_v[i][1] - u_v[i][0] + 1;
	}
	//所有的树木减去重复的树木
	result =roadLength + 1 - (count - countRepeat);
	cout< 
2.第二次使用珂朵莉树数据结构，计算通过 
不用单独考虑重复区域，应该做标记！！！ 
#include
#include
#include
#include
#include
#define re register
#define FOR(i,l,r) for(re int i=l;i<=r;++i)
#define IT set::iterator
using namespace std;

//全局变量
int n,m,x,y;

//内联函数
inline void in(re int &x){
	x=0;char c=getchar();
	while(c<'0'||c>'9'){
		c=getchar();
	}
	while(c<='9'&&c>='0'){
		x=(x<<1)+(x<<3)+(c^'0');
		c=getchar();
	}
}

inline void out(re int a){
	if(a>=10)out(a/10);
	putchar(a%10+'0');
}

//珂朵莉树
//珂朵莉树的关键在于推平一段区间，即把一段区间的数变的一样
struct node{
	//l 左节点 r 右节点
	int l,r;
	//v 值
	/


inline IT split(re int pos){
	IT it=s.lower_bound(node(pos));
	if(it!=s.end()&&it->l==pos)
		return it;
	--it;
	int L=it->l;
	int R=it->r;
	int V=it->v;
	s.erase(it);
	s.insert(node(L,pos-1,V));
	return s.insert(node(pos,R,V)).first;
}



inline void assign_val(re int l,re int r,re int val=0){
	IT itr=split(r+1),itl=split(l);
	s.erase(itl,itr);
	s.insert(node(l,r,val));
}

//区间和查询
//求和计算v=1的点数
inline int query(re int l,re int r){
	int res=0;
	IT itr=split(r+1),itl=split(l);
	for(;itl!=itr;++itl)
		res+=(itl->r - itl->l+1)*(itl->v);
	return res;
}

int main(){
	//n总的树木
	//m分段
	in(n),in(m);
	//0-n 全部置为1
	s.insert(node(0,n,1));

	//将每一段都置为0
	//关键在于不用特别考虑重复区域
	FOR(i,1,m){
		in(x),in(y);
		assign_val(x,y,0);
	}
	out(query(0,n));
	puts("");
}
 
3.第三次使用标记法，计算通过 
#include
#include 
#include 
using namespace std;
#define MAX 100000

//将数组arr中l到r位置的值置为value
bool assignValue(int l,int r,int value,int arr[])
{
	int j;
	if (l > r)
	{
		return false;
	}
	for (j = l;j<=r;j++)
	{
		arr[j] = value;
	}
	return true;
}

//计算value =1的个数
int countValue(int l,int r,int arr[])
{
	int count, j;
	count = 0;
	for (j = l;j<=r;j++)
	{
		if (arr[j] == 1)
		{
			count += 1;
		}
	}
	return count;
}
int main()
{
	int n,m;
	cin>>n>>m;
	int valueVec[MAX];
	int u,v,count;

	assignValue(0,n,1,valueVec);
	for (int i = 0 ;i < m;i++)
	{
		cin>>u>>v;
		assignValue(u,v,0,valueVec);
	}
	count = countValue(0,n,valueVec);
	cout<					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5713817.html