[USACO07JAN] Tallest Cow S

题目

原题地址

解说

题目挺长，说白了就是差分模板题。
因为两个奶牛互相望得见说明之间的奶牛比它们都矮，那么我们每有一个限制条件就说明之间的奶牛的最大高度\(-1\)，最后每个奶牛的高度就是最大高度减去累计减少的高度。考虑时间效率我们可以用差分数组实现。

代码

#include
#include
#include
#include
#include
using namespace std;
int n,p,h,r;
const int maxn=10000+3;
int b[maxn];
map,bool> cun;//记得判断重复出现的
int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
} 
int main(){
	n=read(); p=read(); h=read(); r=read();
	for(int i=1;i<=r;i++){
		int l=read(),r=read();
		if(l>r) swap(l,r);
		if(cun[make_pair(l,r)]) continue;
		cun[make_pair(l,r)]=1;
		b[l+1]-=1; b[r]+=1;//注意“两个奶牛之间”不包括这两只奶牛
	}
	int add=0;
	for(int i=1;i<=n;i++){
		add+=b[i];
		printf("%d\n",h+add);
	}
	return 0;
}

幸甚至哉，歌以咏志。

差分

相关

[学习笔记] 树上差分

【数论】【差分】Row GCD

3.10前缀和与差分

AcWing 4195. 线段覆盖（离散化+差分）

差分

【YBT2022寒假Day4 B】连通的图（结论）（树上差分）（线性基）

题解报告（差分模板）

[差分][后缀数组][线段树]luogu P1117 [NOI2016] 优秀的拆分

差分约束自学笔记

差分格式

Java差分数组

AcWing 1987.粉刷栅栏（离散化，差分）

标签