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
１１１１１１１１１１１
１０００００００００１
１１１０１１１０１０１
１０００００１０１０１
１０１１１１１０１０１
１０１０００００１００
１１１０１１１１１１１

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

0代表格子？

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

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

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

1
2
3
4
5
6
7
１１１１１１１１１１１
１０００００００００１
１１１０１１１０１０１
１０００００１０１０１
１０１１１１１０１０１
１０１& ００００１& ０
１１１０１１１１１１１

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

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;
}
置顶

扫一扫，分享到微信

微信分享二维码