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