酷暑一夏1

不忘初心，方得始终

• 于  USACO, 比赛  阅读 

USACO 2017 February Contest, Silver

Result

The name and year was hidden.

1
2
3
4
5
* = Correct
x = Wrong Answer (including possibly empty or missing output file)
Country|Year|Name      |Score  |helpcross          |maxcross             |countcross
CHN    |····|··········|833    |* x * * x x * x x *|* * * * * * * * * * *|* * * * * * * * * *

Solution

Important Information

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

Why Did the Cow Cross the Road(helpcross)

Important Information

这是一个233分(10个测试点通过了5个)的题解。

Translate

Description

有C头牛，第i(1≤i≤C)牛要在Ti时刻过马路，现在有N只鸡帮助他们，第j(1≤j≤N)在[Aj,Bj]可以提供帮助，请求出最大的牛-鸡配对数，每只鸡只能配对一头牛，每头牛也只能配对一只鸡。

Input Format(helpcross.in)

第一行两个数C和N，接下来C行每行一个Ti，再接下来N行每行两个数Aj和Bj。

Output Format(helpcross.in)

输出最大鸡-牛匹配数。

Solution

50%题解：将所有Ti和(Aj,Bj)升序排序，然后对于每头牛枚举在(Aj,Bj)内的鸡，若找到合适的匹配则匹配这只牛和这只鸡，也就是答案自增1，输出答案即可。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<cstdio>
#include<algorithm>
const int MAXN=20000+5;
struct data{int a,b;};
int c,n,t[MAXN];data d[MAXN];
bool comp(data a,data b){return a.a==b.a?a.b<b.b:a.a<b.a;}
int main()
{
	freopen("helpcross.in","r",stdin);
	freopen("helpcross.out","w",stdout);
	scanf("%d %d",&c,&n);
	for(int i=1;i<=c;i++)
		scanf("%d",&t[i]);
	for(int i=1;i<=n;i++)
		scanf("%d %d",&d[i].a,&d[i].b);
	std::sort(t+1,t+c+1);
	std::sort(d+1,d+n+1,comp);
	int now=1,ans=0;
	for(int i=1;i<=n;i++)
	{
		while(t[now]<d[i].a) 
		{
			now++;
			if(now>c) goto out;
		}
		if(t[now]>d[i].b) continue;
		ans++;
		now++;
	}
	out:
	printf("%d\n",ans);
}

Something want to say

这题这种奇怪的解法都能得50%……

Why Did the Cow Cross the Road II(maxcross)

Translate

Description

总共有N个灯，坏了B个，求最小的修复个数使得至少有K个连续的工作的灯。

Input Format(file maxcross.in)

第一行N,K,B三个数，接下来B行每行一个坏的灯号。

Output Format(file maxcross.out)

输出最小修复个数

Solution

枚举连续的K个灯，求这K个灯中有多少个坏的，取最小值输出。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include<cstdio>
#include<algorithm>
const int MAXN=100000+5;
int n,m,k,ans;bool flag[MAXN];
int main()
{
	freopen("maxcross.in","r",stdin);
	freopen("maxcross.out","w",stdout);
	scanf("%d %d %d",&n,&m,&k);
	int x;
	for(int i=1;i<=k;i++)
	{
		scanf("%d",&x);
		flag[x]=1;
	}
	int tot=0;
	for(int i=1;i<=m;i++)
	{
		tot+=flag[i];
	}
	ans=tot;
	int start=2,end=m+1;
	while(end<=n)
	{
		tot-=flag[start-1];
		tot+=flag[end];
		ans=std::min(tot,ans);
		start++;
		end++;
	}
	printf("%d\n",ans);
	return 0;
}

Why Did the Cow Cross the Road III(countcross)

Translate

Description

为什么牛过马路？ 那么，一个原因是农夫约翰的农场只有很多道路，使他的母牛不可能在不穿过许多道路的情况下旅行。
农夫约翰的农场被布置成N×N的正方形网格，某些相邻的网格（例如南-北，西-南）被道路隔开，并且高围栏围着农场周边，防止离开。牛可以从任意网格移动到相邻网格，除非绝对必要他们不喜欢穿过道路。
有K头奶牛，位于不同领域。如果一头奶牛要去访问另一头奶牛必须穿过至少一条路则这对奶牛被认为是“遥远的”。请计算“遥远的”奶牛对数。

Input Format

第一行三个数N,K,R，接下来R行每行描述一条马路，以r c r′ c′形式呈现，表示(r,c)和(r′,c′)间有一条马路。接下来K行每行描述一头奶牛坐标。

Output Format

输出“遥远的”奶牛对数。

Solution

对于每个马路，标记两格子间不能互通。然后求连通块，接着进行比较每对奶牛的块的编号，若不同表示至少要走一个马路。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include<cstdio>
#include<queue>
const int MAXN=100+5;
struct point{int x,y;};
bool limit[MAXN][MAXN][MAXN][MAXN];
int vis[MAXN][MAXN],xd[4]={-1,1,0,0},yd[4]={0,0,-1,1};
int x1,y1,x2,y2,n,k,r;point cow[MAXN];
std::queue<point>que;
void BFS(int bx,int by,int vid)
{
	point temp,tmp;
	temp.x=bx;temp.y=by;
	vis[bx][by]=vid;
	que.push(temp);
	while(!que.empty())
	{
		temp=que.front();que.pop();
		for(int i=0;i<4;i++)
		{
			tmp=temp;
			tmp.x+=xd[i];tmp.y+=yd[i];
			if(tmp.x<1 || tmp.y<1 || tmp.x>r || tmp.y>r ||limit[temp.x][temp.y][tmp.x][tmp.y] || vis[tmp.x][tmp.y]) continue;
			que.push(tmp);
			vis[tmp.x][tmp.y]=vid;
		}
	}
}
int main()
{
	freopen("countcross.in","r",stdin);
	freopen("countcross.out","w",stdout);
	scanf("%d %d %d",&r,&k,&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
		limit[x1][y1][x2][y2]=limit[x2][y2][x1][y1]=1;
	}
	for(int i=1;i<=k;i++)
		scanf("%d %d",&cow[i].x,&cow[i].y);
	int par3=0;
	for(int i=1;i<=r;i++)
		for(int j=1;j<=r;j++)
			if(!vis[i][j]) BFS(i,j,++par3);
	int ans=0;
	for(int i=1;i<=k;i++)
		for(int j=i+1;j<=k;j++)
			if(vis[cow[i].x][cow[i].y]!=vis[cow[j].x][cow[j].y]) ans++;
	printf("%d\n",ans);
	return 0;
}
Like Issue Page
Error: Not Found
Styling with Markdown is supported
Powered by Gitment
最近的文章

CodeVS1365 欲火银河星际跳跃 题解

题目小 K 又在玩浴火银河了。。。不过这次他的目的不是跑运输赚钱，而是做任务赚钱。他想知道关于一个任务的两个星系是否可以连通。 题解并查集。若两节点联通就把他们放在同一集合中，对于每个询问判断是否在同一集合中即可。 代码1234567891011121314151617181920212223#in …

• 于  CodeVS, 欲火银河 继续阅读
更早的文章

USACO Chapter3 Section3 Prob 2 Solution

一、翻译（来源）在商店中，每一种商品都有一个价格（用整数表示）。例如,一朵花的价格是 2 zorkmids （z），而一个花瓶的价格是 5z 。为了吸引更多的顾客，商店举行了促销活动。促销活动把一个或多个商品组合起来降价销售，例如：三朵花的价格是 5z 而不是 6z， 两个花瓶和一朵花的价格是 10z 而不是 12z。 编写一个程序，计算顾客购买一定商品的花费，尽量利用优惠使花费最少。尽管有时候添加其他商品可以获得更少的花费，但是你不能这么做。对于上面的商品信息，购买三朵花和两个花瓶的最少花费的方案是：以优惠价购买两个花瓶和一朵花（10z），以原价购买两朵花（4z）。INPUT FORMAT：（file shopping.in)输入文件包括一些商店提供的优惠信息，接着是购物清单。（最多有5种商品）第一行 优惠方案的种类数（0 &lt;= s &lt;= 99）。第二行..第s+1 行 每一行都用几个整数来表示一种优惠方式。第一个整数 n （1 &lt;= n &lt;= 5），表示这种优惠方式由 n 种商品组成。后面 n 对整数 c 和 k 表示 k （1 &lt;= k &lt;= 5）个编号为 c （1 &lt;= c &lt;= 999）的商品共同构成这种优惠，最后的整数 p 表示这种优惠的优惠价（1 &lt;= p &lt;= 9999）。优惠价总是比原价低。第 s+2 行 这一行有一个整数 b （0 &lt;= b &lt;= 5），表示需要购买 b 种不同的商品。第 s+3 行..第 s+b+2 行 这 b 行中的每一行包括三个整数：c，k，p。 c 表示唯一的商品编号（1 &lt;= c &lt;= 999），k 表示需要购买的 c 商品的数量（1 &lt;= k &lt;= 5）。p 表示 c 商品的原价（1 &lt;= p &lt;= 999）。最多购买 5*5=25 个商品。OUTPUT FORMAT：(file shopping.out)只有一行，输出一个整数：购买这些物品的最低价格。 二、题解多重背包问题，对于编号问题要好好处理。 …

• 于  USACO, USACO Training 继续阅读