USACO 2.4

  • 两只塔姆沃斯牛 The Tamworth Two
  • 穿越栅栏 Overfencing
  • 牛的旅行 Cow Tours
  • 回家 Bessie Come Home
  • 分数化小数 Fractions to Decimals

    P1518 两只塔姆沃斯牛 The Tamworth Two

看楼下写得很复杂啊//ylx:其实你的更复杂
不过一堆if看起来有点233吧//ylx:你的也不一样
需仔细看题。然后照着模拟就行了。
不难看出,两头牛其实一直在一起。
上右下左分别用1,2,3,4代替,旋转90°相当于+1,4+1就是1了,所以可以直接先取模再+1。

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112

/*
ID: ylx14271
PROG: ttwo
LANG: C++
*/
#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<math.h>
#include<time.h>
#include<vector>
#include<bitset>
#include<memory>
#include<utility>
#include<stdio.h>
#include<sstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
#define LL unsigned long long
using namespace std;
int i,j,cx,cy,x,y;//(cy,cx):牛的坐标
int fc,ff,t;//fc牛的方向,ff人的方向,t:时间
char ch;
int a[15][15];//地图
int pd[11][11][11][11][5][5];//牛和人的坐标+方向
int f[5][3]=//1:上,2:右,3:下,4:左
{{0,0,0},
{0,-1,0},
{0,0,1},
{0,1,0},
{0,0,-1}};
int main()
{
freopen("ttwo.in","r",stdin);
freopen("ttwo.out","w",stdout);//文件
for (i=0;i<=11;i++)
{
a[i][0]=-1;//地图的边赋为障碍物
a[0][i]=-1;//四边
a[11][i]=-1;
a[i][11]=-1;
}
for (i=1;i<=10;i++)
{
for (j=1;j<=10;j++)//读入
{
scanf("%c",&ch);
switch (ch)
{
case '*':
{
a[i][j]=-1;//标记为障碍物
break;
}
case 'C':
{
cx=i;
cy=j;//牛的坐标
break;
}
case 'F':
{
x=i;
y=j;//坐标
break;
}
}//就是读入而已,被我写这么长
}
scanf("\n");
} //读入完毕
fc=1;ff=1;//开始都是向上走
while (true)//模拟
{
if (pd[cx][cy][x][y][fc][ff]==1)//走过了
{//这一步走过了且在此前没有相遇,那就抓不到了
printf("0\n");//输出
return 0;
}
pd[cx][cy][x][y][fc][ff]=1;//标记
t++;//记录时间
//牛走
if (a[cx+f[fc][1]][cy+f[fc][2]]==-1)//有障碍
{
fc=fc%4+1;//顺时针旋转
}else
{
cx+=f[fc][1];
cy+=f[fc][2];//走一步
}
//人走
if (a[x+f[ff][1]][y+f[ff][2]]==-1)//有障碍
{
ff=ff%4+1;//顺时针旋转
}else
{
x+=f[ff][1];
y+=f[ff][2];//走一步
}
if (cx==x&&cy==y)//相遇了
{
printf("%d\n",t);//输出
return 0;
}
}
return 0;
}

P1519 穿越栅栏 Overfencing

读入有点坑。我选择全部读进来,然后存,如图所示:

1
2
3
4
5
6
7
11111111111
10000000001
11101110101
10000010101
10111110101
10100000100
11101111111

我们把图以外的部分全都标记为墙,那么,门的周围则只有一个方向有路。

0代表格子?

不不不,如过0代表格子的话,格子就多很多。

不难发现,真正的格子横坐标与纵坐标都是偶数。这样就很好处理了,每次横坐标纵坐标移动2步。

把出口入队很不方便啊,于是我们就将离出口最近的格子入队。也就是图中&所示

1
2
3
4
5
6
7
11111111111
10000000001
11101110101
10000010101
10111110101
101& 00001& 0
11101111111

然后就开始灌水了。
其实还是很快的

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
/*
ID: ylx14271
PROG: maze1
LANG: C++
*/
#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<math.h>
#include<time.h>
#include<vector>
#include<bitset>
#include<memory>
#include<utility>
#include<stdio.h>
#include<sstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
#define LL unsigned long long
using namespace std;
int m,n,mm,i,j,k,ss,l,r;//mm:max
int a[310][310];//存地图,1代表墙,
int f[310][310]={0};//标记用
int dx[5]={0,-2,2,0,0};//上下左右
int dy[5]={0,0,0,-2,2};
int ddx[5]={0,-1,1,0,0};//上下左右
int ddy[5]={0,0,0,-1,1};
struct he
{
int x,y;
int t;//步数
}d[100000];
char x[500];
int main()
{
freopen("maze1.in","r",stdin);
freopen("maze1.out","w",stdout);
cin>>m>>n;
cin.getline(x,500);
ss=n*m;//格子数量
m=m*2+1;
n=n*2+1;
for (i=0;i<=n+3;i++)
{
for (j=0;j<=m+3;j++)
a[i][j]=1;//初始化
}
for (i=1;i<=n;i++)
{
char c[500];
cin.getline(c,500);//读入
for (j=1;j<=m;j++)
{
if (c[j-1]!='+'&&c[j-1]!='-'&&c[j-1]!='|')//判断
a[i][j]=0;//标记不是墙
}
}

for (i=1;i<=n;i++)
for (j=1;j<=m;j++)
f[i][j]=0;//初始化

for (i=1;i<=n;i++)
for (j=1;j<=m;j++)
if ((i==1)||(j==1)||(i==n)||(j==m))//在边框上
if (a[i][j]==0)//是出口
{//出口的外围赋初值的时候就变成墙了,所以保证只有一边为0
for (k=1;k<=4;k++)
{
if ((a[i+ddx[k]][j+ddy[k]]==0)&&//是格子
(i+ddx[k]>=1)&&(i+ddx[k]<=n)&&
(j+ddy[k]>=1)&&(j+ddy[k]<=m)&&
(f[i+ddx[k]][j+ddy[k]]==0))//没入队
{
r++; //入队
d[r].x=i+ddx[k];//坐标
d[r].y=j+ddy[k];
d[r].t=1;//步数
f[i+ddx[k]][j+ddy[k]]=1;//标记
break;
}
}
}
mm=1;
while (l<r)
{
l++;
for (i=1;i<=4;i++)//四个方向
{
if (a[d[l].x+ddx[i]][d[l].y+ddy[i]]==0&&//没墙挡着
d[l].x+dx[i]<=n&&d[l].y+dy[i]<=m&&//在范围内
d[l].x+dx[i]>=1&&d[l].y+dy[i]>=1&&//在范围内
f[d[l].x+dx[i]][d[l].y+dy[i]]==0)//没入队
{
r++; //入队
ss--;
d[r].x=d[l].x+dx[i];//坐标
d[r].y=d[l].y+dy[i];
d[r].t=d[l].t+1;//步数
f[d[r].x][d[r].y]=1;
if (d[r].t>mm) mm=d[r].t;//找最大步数
}
}
}
printf("%d\n",mm); //输出
return 0;
}

P1522 牛的旅行 Cow Tours

读题比较麻烦。处理起来不算太复杂吧。

  • 第一步:读入,存到邻接矩阵中,自己到自己有路,需要判断(读入的邻接矩阵自己到自己是0),没路的赋成很大的数。
  • 第二步:floyd求最短路。
  • 第三步:求现有的每个牧场的直径。
  • 第四步:枚举连路
    然后就可以输出了
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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
/*
ID: ylx14271
PROG: cowtour
LANG: C++
*/
#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<math.h>
#include<time.h>
#include<vector>
#include<bitset>
#include<memory>
#include<utility>
#include<stdio.h>
#include<sstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
#define LL unsigned long long
using namespace std;
int n,i,j,k;
char c;
double f[160][160];//邻接矩阵
int x[160],y[160];//坐标
double mm[160]; //牧场直径
double jl(int ii,int jj)//ii~jj直线距离
{
return sqrt((x[ii]-x[jj])*(x[ii]-x[jj])+(y[ii]-y[jj])*(y[ii]-y[jj]));
} //勾股定理
int main()
{//好题
freopen("cowtour.in","r",stdin);
freopen("cowtour.out","w",stdout);
scanf("%d",&n);
for (i=1;i<=n;i++)
{
scanf("%d %d",&x[i],&y[i]);//坐标
//printf("%d %d\n",x[i],y[i]);//坐标
}
for (i=1;i<=n;i++)
{
for (j=1;j<=n;j++)
{
cin>>c;//i→j是否右路
if (c=='1')//有路
{
f[i][j]=jl(i,j); //求直线距离
//printf("%4d %4d %20.6lf\n",i,j,f[i][j]);
} else//没路
{
if (i!=j)//i==j的话距离就为0
f[i][j]=23333333;//标记没直接的路
}
}
}
for (k=1;k<=n;k++)//floyd求最短路
for (i=1;i<=n;i++)
for (j=1;j<=n;j++)
{
if ((f[i][k]+f[k][j]<f[i][j])&&(i!=j)&&(i!=k)&&(j!=k))
f[i][j]=f[i][k]+f[k][j];//其实ijk相等也不影响结果
}
for (i=1;i<=n;i++)//求目前每个牧场直径
{
for (j=1;j<=n;j++)
{//是同一个牧场,且是该该牧场内部相距最远的
if ((f[i][j]>mm[i])&&(f[i][j]!=23333333))
mm[i]=f[i][j];//存起来
}
//printf("%.6lf ",mm[i]);
}
double Min=23333333;
for (i=1;i<=n;i++)//找最小直径
for (j=1;j<=n;j++)
{
if (f[i][j]==23333333)//无路
{
double x=jl(i,j);//如过ij连路,2牧场直线距离
if (x+mm[i]+mm[j]<Min)
{
Min=x+mm[i]+mm[j];
}
//printf("(%d , %d):%.6lf\n",i,j,x);
}
}
for (i=1;i<=n;i++)
//其实是要输出,将2个牧场连起来后,所有牧场中最大的直径
if (mm[i]>Min) Min=mm[i];
printf("%.6lf\n",Min);
return 0;
}

P1529 回家 Bessie Come Home

这道题Floyd就可以AC
还是很快的。

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
51
52
53
54
55

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<math.h>
#include<time.h>
#include<vector>
#include<bitset>
#include<memory>
#include<utility>
#include<stdio.h>
#include<sstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
int a[200][200]={0};
int p[200]={0};
int n,i,j,k;
char A,B;
int main()
{
scanf("%d\n",&n);
for (i='A';i<='z';i++)
for (j='A';j<='z';j++)
if(i!=j)a[i][j]=100000000;
for (i=1;i<=n;i++)
{
int haha;
scanf("%c %c %d\n",&A,&B,&haha);
if (A>='A'&&A<='Z') p[A]=1;//标记该地有牛
if (B>='A'&&B<='Z') p[B]=1;
a[A][B]= min(a[A][B],haha);
a[B][A]=min(a[A][B],a[B][A]);
}
for (k='A';k<='z';k++)//floyd
for (i='A';i<='z';i++)
for (j='A';j<='z';j++)
if(a[i][j]>a[i][k]+a[k][j])
a[i][j]= a[i][k]+a[k][j];
int m=100000000;
char he;
for (i='A';i<='Y';i++)//找最快到Z的母牛
if ((p[i]==1)&&(a[i]['Z']<m))
{
m=a[i]['Z'];
he=(char)i;
}
cout<<he<<" "<<m;
return 0;
}

P1530 分数化小数 Fractions to Decimals

模拟。

大概思路:

每次求出商和余数。余数为0即除尽了,可以输出。
如过商和余数都相同,也可以输出了。只有余数相同并不可以,某个点会错。
判断商和余数建议使用hash,否则TLE
关于76个字符一换行:
整数部分的位数要算上。
小数点也要算上。
括号也要算上。
0要特殊处理。
然后数组要稍微开大点。
于是就可以愉快的ac了。

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
/*
ID: ylx14271
PROG: fracdec
LANG: C++
*/
#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<math.h>
#include<time.h>
#include<vector>
#include<bitset>
#include<memory>
#include<utility>
#include<stdio.h>
#include<sstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
#define LL unsigned long long
using namespace std;
int n,m,f,i,j,l,r,he,x;//i:位数,第l~r位循环
int y[500000],z[500000];//y:余数部分,z:整数部分
int hash[100001];
int hs[100001];
int main()
{
freopen("fracdec.in","r",stdin);
freopen("fracdec.out","w",stdout);
scanf("%d%d",&n,&m);
if (n%m==0)//能整除
{

printf("%d.0\n",n/m); //输出
return 0;//退出
}
printf("%d.",n/m);//输出整数部分
x=1;
he=n/m;
while (he>0)//统计整数部分位数
{
he=he/10;
x++;
}
if (n/m==0) x++;//0的情况特殊处理
y[0]=n%m;//余数
while (true)
{
i++;
z[i]=y[i-1]*10/m;//小数第i位整数部分
y[i]=y[i-1]*10%m;//余数
if (y[i]==0)
{
f=1;//标记除尽了
break;//除尽了
}
if (hash[y[i]]>0&&hs[hash[y[i]]]==z[i])//商和余数都曾出现
{
l=hash[y[i]];//标记
r=i-1;
break;//退出
}
hash[y[i]]=i;//存余数为y[i]的位置
hs[hash[y[i]]]=z[i];//将商也存进去
if (i>499090) break;//不搜了
}
for (j=1;j<=i;j++)//输出
{
if (j==l)//输出括号
{
printf("(");
x++;//统计位数
}
printf("%d",z[j]);
x++;
if (r==j)
{
printf(")");
break;
}
if (x%76==0) printf("\n");//换行
}
printf("\n");
return 0;
}