2017-01-28 • 于 USACO, 比赛阅读

USACO 2017 January Contest, Bronze

Result

The name was hidden.

* = Correct
x = Wrong Answer (including possibly empty or missing output file)
Country    Name    Score    notlast	      hps        cowtip
CHN     ··········  800    *********** ********** ****xxxxxx

Solution

Important Information

翻译不保证全部正确，请以原题为准。

Don’t Be Last!(notlast)

Translation

Problem Description

农夫John有七头奶牛：Bessie，Elsie，Daisy，Gertie，Annabelle，Maggie和Henrietta。
他每天给他们喝牛奶，并在每次挤奶期间详细记录每只奶牛提供的奶量。毫不奇怪，农夫约翰高度奖励提供大量牛奶的奶牛。
奶牛，作为懒惰的生物，不一定要负责生产太多的牛奶。如果它们取决于他们，他们将完全满足于成为整个牛群中产量最低的牛。然而，他们仍然听说农夫约翰提到与他的人的朋友“farm to table”这个短语，虽然他们不太明白这是什么意思，他们怀疑，成为生产牛奶量最小的奶牛不是最好的想法。相反，他们认为在牛群中生产量第二小牛奶的牛奶量的地位更安全。请帮助奶牛找出他们目前占据这个理想的位置。

Input Format(file notlast.in)

此任务的输入文件以包含整数（）的行开始，给出Farmer John的挤奶日志中的条目数。
以下行中的每一行包含牛的名称（上述七个中的一个），后跟正整数（至多），指示牛在其挤奶期间产生的牛奶的量。
Output Format(file notlast.out)
输出生产第二小牛奶量的牛的名称。如果有多头奶牛为这个值或者没有第二小的牛奶量则输出Tie。

Solution

维护每头奶牛总生产量，升序排序，判断是否存在Tie的情况，若存在则输出Tie，否则输出产奶量第二小的奶牛名。注意对于输入文件中没有出现的奶牛的处理。

Code

#include<cstdio>
#include<map>
#include<string>
#include<iostream>
#include<algorithm>
const int MAXN=100+5;
std::map<std::string,int>map;
std::map<std::string,int>::iterator it;
struct term{int value;std::string name;};
int n,x,c,now,nowc;std::string tmp;term t[MAXN];
bool comp(term a,term b){return a.value<b.value;}
void init()
{
	map["Bessie"]=map["Elsie"]=map["Daisy"]=map["Gertie"]=map["Annabelle"]=map["Maggie"]=map["Henrietta"]=-1;
}
int main()
{
	std::ios::sync_with_stdio(false);
	freopen("notlast.in","r",stdin);
	freopen("notlast.out","w",stdout);
	init();
	std::cin>>n;
	for(int i=1;i<=n;i++)
	{
		std::cin>>tmp>>x;
		map[tmp]+=x;
	}
	for(it=map.begin();it!=map.end();it++)
	{
		t[++c].name=it->first;
		t[c].value=it->second+1;
	}
	std::sort(t+1,t+c+1,comp);
	x=t[1].value;now=-1;
	for(int i=2;i<=c;i++)
	{
		if(t[i].value>x && now==-1)
		{
			now=t[i].value;
			nowc=i;
			continue;
		}
		if(t[i].value==now)
		{
			printf("Tie\n");
			return 0;
		}
		if(t[i].value>now && now!=-1) break;
	}
	if(now==-1) printf("Tie\n"); else std::cout<<t[nowc].name<<std::endl;
	return 0;
}

Hoof, Paper, Scissors(hps)

Translation

Description

你可能听说过游戏“剪刀石头布”。奶牛喜欢玩一个类似的游戏，他们称之为“蹄，纸，剪刀”。
“蹄，纸，剪刀”的规则很简单。两头母牛互相玩耍。他们都数三、二、一，然后每个同时做一个姿势，代表一个蹄子，一张纸或一把剪刀。蹄胜剪刀（因为蹄子可以粉碎一把剪刀），剪刀胜纸（因为剪刀可以切纸），纸胜蹄（因为蹄可以得到一个剪纸）。如果动作相同则打平。
农夫约翰在迷人中看着他的两头牛玩“蹄，纸，剪刀”的一系列次游戏（）。不幸的是，虽然他可以看到奶牛正在做三种不同类型的手势，但他不能知道哪一个代表“蹄”，哪一个代表“纸”，哪一个代表“剪刀”（对农夫约翰未经训练的眼睛，他们所有似乎都是“蹄”的变化…）
不知道三种手势的含义，农夫John给他们分配数字1,2和3.也许手势1代表“蹄”，或者它代表“纸”。他的意思不清楚。考虑到两个牛在所有次游戏上做出的手势，请帮助农民约翰确定第一头牛可能赢得的最大可能数量的游戏，给定数字和他们各自的手势之间的适当映射。

Input Format(file hps.in)

第一行一个数表示游戏次数，接下来行每行两个数描述一场John视角的游戏。

Output Format(file hps.out)

输出最大的第一头牛胜利的次数。

Solution

枚举表示蹄，纸，剪刀的值，代入游戏求第一头牛胜利次数。求最大值。

Code

#include<cstdio>
#include<algorithm>
const int MAXN=100+5;
int n,game[MAXN][2];//game: 0 CowA 1 CowB
bool beatlist[4][4]={{},{0,0,0,1},{0,1,0,0},{0,0,1,0}};
int tmp,ans,x1,x2;
int main()
{
	freopen("hps.in","r",stdin);
	freopen("hps.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d %d",&game[i][0],&game[i][1]);
	int is[4];
	for(int a=1;a<=3;a++)//Hoof
		for(int b=1;b<=3;b++)//Paper
			for(int c=1;c<=3;c++)//Scissor
			{
				if(a==b || a==c || b==c) continue;
				tmp=0;
				if(a==1) is[1]=1;if(a==2) is[2]=1;if(a==3) is[3]=1;
				if(b==1) is[1]=2;if(b==2) is[2]=2;if(b==3) is[3]=2;
				if(c==1) is[1]=3;if(b==2) is[2]=3;if(c==3) is[3]=3;
				for(int i=1;i<=n;i++)
				{
					tmp+=beatlist[is[game[i][0]]][is[game[i][1]]];
				}
				ans=std::max(ans,tmp);
			}
	printf("%d\n",ans);
	return 0;
}

Cow Tipping(cowtip)

Important Information

这是一个200分(10个测试点通过了4个)的题解

Translation

Description

农夫John偶尔遇到麻烦的青少年造访他的农场，并翻转他的奶牛。它的头牛被整齐地排成了的网格。并且一部分牛反过来了。
幸运的是，John可以用拖拉机和叉车组成一个光荣的机器牛翻转器3000(Cow-Untipperator 3000)，可以翻转大量牛群。他可以把机器放在子矩形的左上角，将会翻转其中的所有牛。（会转换区域中所有牛的状态，反的变正，正的变反）
农民约翰认为，通过将他的机器充分地应用到适当的矩形集合，他可以最终将所有的牛恢复到他们正确的的状态。请帮助他确定他的机器所需的最少应用次数。
注意，将机器应用于相同的矩形两次将是无意义的，因为这将不会对矩形中的奶牛产生净影响。因此，您应该只考虑将机器应用于每个左上方的矩形，可能只有一次。

Input Format(cowtip.in)

输入的第一行是整数。
后行中的每一行包含个字符的字符串，每个字符为0（代表反的牛）或1（代表正的牛）。
Output Format(cowtip.out)
输出John的牛翻转器3000所需的最少应用次数。

Solution

先用输入数据所提供的牛的状态进行灌水法得出
然后翻转所有牛的状态（）再次灌水得出
答案

Code

#include<cstdio>
#include<queue>
#include<algorithm>
#include<cstring>
const int MAXN=10+5;
struct point{int x,y;};
bool vis[MAXN][MAXN];int n,map[MAXN][MAXN];char inp[MAXN];
std::queue<point>que;
int xd[3]={1,1,0},yd[3]={1,0,1};
void BFS(int beginx,int beginy)
{
	point temp,tmp;
	vis[beginx][beginy]=1;
	temp.x=beginx;temp.y=beginy;
	que.push(temp);
	while(!que.empty())
	{
		temp=que.front();que.pop();
//		printf("%d,%d\n",temp.x,temp.y);
		for(int i=0;i<3;i++)
		{
			tmp=temp;
			tmp.x+=xd[i];tmp.y+=yd[i];
			if(i==0)
			{
				if(vis[tmp.x][tmp.y] || vis[tmp.x-1][tmp.y] || vis[tmp.x][tmp.y-1] || !map[tmp.x][tmp.y] || !map[tmp.x-1][tmp.y] || !map[tmp.x][tmp.y-1] || tmp.x-1<1 || tmp.y-1<1 || tmp.x<1 || tmp.x>n || tmp.y<1 || tmp.y>n) continue;
			}
			if(vis[tmp.x][tmp.y] || !map[tmp.x][tmp.y] || tmp.x>n || tmp.x<1 || tmp.y>n || tmp.x<1) continue; else {que.push(tmp);vis[tmp.x][tmp.y]=1;if(i==0){vis[tmp.x-1][tmp.y]=vis[tmp.x][tmp.y-1]=1;}}
		}
	}
//	printf("----\n");
	return;
}
int main()
{
	freopen("cowtip.in","r",stdin);
	freopen("cowtip.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%s",inp);
		for(int j=0;j<n;j++)
			map[i][j+1]=inp[j]-'0';
	}
	int ans=0,ans2=1;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			if(map[i][j] && !vis[i][j])
			{
				BFS(i,j);
				ans++;
			}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			map[i][j]=!map[i][j];
	memset(vis,0,sizeof(vis));
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			if(map[i][j] && !vis[i][j])
			{
				BFS(i,j);
				ans2++;
			}
	printf("%d\n",std::min(ans,ans2));
	return 0;
}

酷暑一夏1

USACO 2017 January Contest, Bronze

Result

Solution

Important Information

Don’t Be Last!(notlast)

Hoof, Paper, Scissors(hps)

Cow Tipping(cowtip)

USACO Chapter3 Section3 Prob 1 Solution