USACO 2019 February S 题解

2019 February S

P5541 [USACO19FEB]Sleepy Cow Herding S

对于求最小值，我们只要找到一段区间所包含的奶牛数量最多即可（还要特判一下移动后还是端点的情况）

对于求最大值，我们考虑 \(a_0 \to a_1\) 和 \(a_{n-1} \to a_{n-1}\) 的两个端点间隙。

我们的第一步先“牺牲”其中的一个端点间隙，所以我们不能把任何一头牛移到这个缺口中。除了这一个缺口之外，我们要确保一头奶牛移动后在队列中 \(a_0\) 和 \(a_{n-1}\) 之间的每一个空地。

#include 
#include  
#define min(a,b) ((a)<(b)?(a):(b))
using namespace std;
const int inf=0x3f3f3f3f;
const int N=1e5+7;

int a[N];

int n,ans=inf,cnt;

signed main() {
	scanf("%d",&n);
	for(int i=1;i<=n;++i)
		scanf("%d",a+i);
	sort(a+1,a+1+n);
	for(int i=2;i<=n;++i)
		if(a[i]-a[i-1]==1)
			++cnt;
	if(cnt==n-2 && (a[n]-a[n-1]>2 || a[2]-a[1]>2))
		puts("2");
	else {
		for(int i=1;a[i]+n-1<=a[n];++i)
			ans=min(ans,n-((upper_bound(a+1,a+1+n,a[i]+n-1)-a-1)-(i-1)));
		printf("%d\n",ans);
	}
	printf("%d",max(a[n-1]-a[1],a[n]-a[2])-n+2);
    return 0;
}

P5542 [USACO19FEB]Painting The Barn S

通过观察题目可以发现，本题的实质为二维区间修改，最后在查询有几个点值与 \(k\) 相同

因为是最后查询，所以我们可以用二维差分解决本题

#include 
using namespace std;
const int MAX=1e3+7;

int c[MAX][MAX];

int n,k;
int cnt,ans;

inline void update(int x,int y,int xx,int yy) {
	++c[x][y],++c[xx+1][yy+1],--c[x][yy+1],--c[xx+1][y]; // 差分数组修改
}

signed main() {
	scanf("%d%d",&n,&k);
	for(int x,y,xx,yy;n;--n) {
		scanf("%d%d%d%d",&x,&y,&xx,&yy);
		update(x+2,y+2,xx+1,yy+1);
	}
	for(int i=1;i<=1e3+1;++i)
		for(int j=1;j<=1e3+1;++j) {
			c[i][j]+=c[i-1][j]+c[i][j-1]-c[i-1][j-1]; // 差分数组查询
			if(c[i][j]==k)
				++ans;
		}
	printf("%d",ans);
    return 0;
}

P5543 [USACO19FEB]The Great Revegetation S

通过观察题目可以发现，每组奶牛喜爱的牧场草的种类都是被捆绑在一起的（即确定了一个牧场中的草就可以确定另一个牧场种什么草）。

不难想到，我们可以将这一些具有捆绑关系的牧场并到一个集合中进行维护。那么这个集合中的牧场种的草就有两种方案。

我们可以用并查集维护这些集合，通过计算可以得到最终的答案为 \(2^{集合数量}\) 。

另外，还要暴力模拟一遍牧场种的草判断是否有无解情况，若在标记过程中发现矛盾，即为无解。

#include 
#include 
#include 
#include 
using namespace std;
const int N=1e5+7;

int fa[N];

struct node {
	char op;
	int x,y;
};

queue q;

int vis[N];

int n,m,ans;

inline int find(int x) {
    while(x!=fa[x]) 
    	fa[x]=fa[fa[x]],x=fa[x];
    return x;
}

inline void merge(int x,int y) {
	fa[find(x)]=find(y);
}

signed main() {
	memset(vis,-1,sizeof(vis));
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i)
		fa[i]=i;
	for(int i=1,x,y;i<=m;++i) {
		char c;
		cin>>c;
		scanf("%d%d",&x,&y);
		merge(x,y); // 将具有捆绑关系的牧场并到一个集合中
		q.push({c,x,y});
	}
	for(int i=1;i<=n;++i)
		if(find(i)==i) {
			++ans; // 计算集合数量
			vis[i]=0; // 为每个集合先种一种草
		}
	while(!q.empty()) {
		char op=q.front().op;
		int x=q.front().x,y=q.front().y;
		q.pop();
		if(vis[x]==-1 && vis[y]==-1)
			q.push({op,x,y}); // 若还无法确定种什么草，先放着
		else if(vis[y]==-1)
			vis[y]=((op=='S') ? vis[x] : !vis[x]); // 标记牧场种的草
		else if(vis[x]==-1)
			vis[x]=((op=='S') ? vis[y] : !vis[y]); // 标记牧场种的草
		else if(vis[y]!=((op=='S') ? vis[x] : !vis[x]))
			return putchar('0'),0; // 产生矛盾，无解
		else if(vis[x]!=((op=='S') ? vis[y] : !vis[y]))
			return putchar('0'),0; // 产生矛盾，无解
	}
	putchar('1');
	for(int i=1;i<=ans;++i)
		putchar('0'); // 二进制输出
    return 0;
}