USACO 2019 January Silver

A. Grass Planting

题目链接

https://www.luogu.org/problem/P5197

题解

考虑图中度最大的点，以它为根节点，它的所有子节点都应该染成不同颜色。

所以答案应该是最大的度+1（别忘了根节点还要染色）。

#include <cstdio>
#include <algorithm>
using namespace std;
int t[100005],ans;
int main()
{
 int n;
 scanf("%d",&n);
 for(int i=1;i<n;i++)
 {
  int x,y;
  scanf("%d%d",&x,&y);
  t[x]++,t[y]++;
  ans=max(ans,max(t[x],t[y]));
 }
 printf("%d\n",ans+1);
 return 0;
}

B. Icy Perimeter

题目链接

https://www.luogu.org/problem/P5198

题解

咕咕咕

C. Mountain View

题目链接

https://www.luogu.org/problem/P5199

题解

因为是等腰直角三角形，所以山的左右端点都能计算出来。

将所有山按照左端点第一关键字，山高度第二关键字排序。然后按顺序遍历每一座山，并维护最小左端点和最大右端点。

假如一座山左端点比最小左端点大，比最大右端点小的话，那么这座山就不能被看见。

#include <cstdio>
#include <algorithm>
using namespace std;
struct mountain
{
 int x,y,l,r;
}a[100005];
bool cmp(const mountain&a,const mountain&b)
{
 return a.l<b.l||(a.l==b.l&&a.y>b.y);
}
int main()
{
 int n,pl=0,pr=0;
 scanf("%d",&n);
 int ans=n;
 for(int i=1;i<=n;i++)
 {
  scanf("%d%d",&a[i].x,&a[i].y);
  a[i].l=a[i].x-a[i].y,a[i].r=a[i].x+a[i].y;
 }
 sort(a+1,a+n+1,cmp);
 for(int i=1;i<=n;i++)
 {
  if(a[i].l>=pl&&a[i].r<=pr)ans--;
  pl=min(pl,a[i].l),pr=max(pr,a[i].r);
 }
 printf("%d\n",ans);
 return 0;
}