目录
显示
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; }