T1 懒羊羊找朋友

题目

题目描述

最近电视上热播“喜羊羊与灰太狼”，大家都说“做人要做懒羊羊”，为什么呢？因为他 不愿意多做一个动作、不愿意多动一个脑筋，甚至懒得张嘴吃饭，简直是懒的无与伦比！ 话说羊村的羊还真多啊！每周一早晨，羊村老村长慢羊羊同志学着人类的学校，把所有 羊列队在广场上进行思想教育，主要是保持警惕防止狼类的攻击，当然也包括对懒羊羊之类 的“异类”进行批评教育。 羊群列队成一个 m*n 的方阵，每只羊站在一个格子里，而且是长期固定的，便于点名啊：） 晕倒！当然，这样一来的好处是，大家都知道自己的朋友站在哪个位置，虽然它们可能互相 看不见，但心里都知道，并且在老村长进行无聊的训教时，大家都还想赶快结束赶快找离自 己最近的朋友交流周末的开心事呢？ 懒羊羊也想尽快找到自己的好朋友聊天，但是他既不愿意多走路、又不愿意动脑筋去想 怎么走，所以就请智羊羊同学帮它编个程序，以便快速定位找到离它最近的一位好朋友。 如果你是智羊羊，你怎么完成这个任务呢？

输入格式

问题输入： 第 1 行为两个整数 m 和 n， 2<=m,n<=100。 第 2 行为懒羊羊的位置 x,y，表示在第 x 行 y 列。 以下 m 行为一个 m*n 的数字方阵， 所有 a[i,j]的值相等的表示是好朋友， 1<=a[i,j]<=100。 每行的两个数之间都有一个空格分隔。

输出格式

问题输出： 输出一行两个数 x1,y1，表示懒羊羊最近的一个朋友的位置在第 x1 行 y1 列，之间用一 个空格隔开。 如果最近的的朋友不只一个，则输出 x1 最小的，如果还不唯一则输出 y1 最小的。 数据保证懒羊羊一定有朋友。

输入输出样例

输入 #1

1
2
3
4
5
6
4 4
1 2
2 1 2 1
1 3 1 3
2 1 2 2
2 2 1 3

输出 #1

1
1 4

分析

这道题很明显是一个极其裸的广搜题。

可是我竟然因为太长时间没做广搜的题导致忘记了广搜怎么写……

不过我还是根据自己对于广搜的理解写出了正确的广搜代码。

但是还是不对……对广搜的极度不自信导致我一直在检查我的广搜……

考试的时候调试了将近两个小时，后来又调试了很长时间也没有调试出来。

最后发现竟然是变量名称写错了……

应该是temp1结果写成temp了……

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
113
#include<bits/stdc++.h>

using namespace std;

inline long long read()
{
    long long x = 0;
    int f = 1;
    char ch = getchar();
    while (ch < '0' || ch>'9')
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar();
    }
    return x * f;
}

int totN;
int totM;
int X,Y;
int mapp[109][109];
queue<pair<int,int> > Q;
int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
int step[109][109];
struct student
{
    int x,y;
}friends[109];
int fricnt=1;
bool vis[109][109];
int mindis=99999999;

bool operator<(student aa,student bb)
{
    if(aa.x<bb.x)
    {
        return 1;
    }
    if(aa.x>bb.x)
    {
        return 0;
    }
    if(aa.y<bb.y)
    {
        return 1;
    }
    return 0;
}

void BFS()
{
    pair<int,int> temppair;
    temppair.first=X;
    temppair.second=Y;
    Q.push(temppair);
    vis[X][Y]=true;
    while(!Q.empty())
    {
        int nowx=Q.front().first;
        int nowy=Q.front().second;
        int nowstep=step[Q.front().first][Q.front().second];
        if(mapp[nowx][nowy]==mapp[X][Y]&&nowstep<=mindis&&(nowx!=X||nowy!=Y))
        {
            mindis=nowstep;
            friends[fricnt].x=nowx;
            friends[fricnt].y=nowy;
            fricnt++;
        }
        if(nowstep>mindis+3)
        {
            break;
        }
        for(auto & i : dir)
        {
            int x=Q.front().first+i[0];
            int y=Q.front().second+i[1];
            int astep=step[Q.front().first][Q.front().second];
            step[x][y]=astep+1;
            if(x<=totM&&y<=totN&&!vis[x][y]&&x>0&&y>0)
            {
                vis[x][y]=true;
                pair<int,int> temppair1;
                temppair1.first=x;
                temppair1.second=y;
                Q.push(temppair1);
            }
        }
        Q.pop();
    }
}

int main()
{
    cin>>totM>>totN;
    cin>>X>>Y;
    for(int i=1;i<=totM;i++)
    {
        for(int j=1;j<=totN;j++)
        {
            mapp[i][j]=read();
        }
    }
    BFS();
    sort(friends+1,friends+fricnt);
    printf("%d %d",friends[1].x,friends[1].y);
    return 0;
}

就是在第91行……应该pushtemppair1结果当时push成temppair了……

就导致我后面的题几乎没多少时间了……

T2 圆的国度

题目

题目描述

平面上有 n 个没有公共点 ． ． ． ． ． 的圆。你要从点(x1,y1)走到(x2,y2)。问你最少要经过多少圆 的边界。保证这两个点都不在圆的边界上。

输入格式

问题输入： 第一行一个整数 n， 1<=n<=50。 接下来三行每行 n 个整数，分别表示 n 个圆的圆心和半径，格式如下： x1,x2,„,xi,„,xn y1,y2,„,yi,„,yn r1,r2,„,ri,„,rn -1000<=xi,yi<=1000,1<=ri<=1000 最后一行四个整数 X1,Y1,X2,Y2， -1000<=x1,y1,x2,y2<=1000。

输出格式

问题输出： 一个整数，意义如上。

输入输出样例

输入 #1

1
2
3
4
5
1
0 
0 
2 
-5 1 5 1

输出 #1

1
0

输入 #2

1
2
3
4
5
3
0 -6 6
0 1 6
2 2 2
-5 1 5 1

输出 #2

1
1

分析

这道题其实是很简单的……

但是我当时把圆都当作了实心圆，“没有公共点”理解成了圆内部也不会有其他圆

就导致我认为这个题答案只会有0,1,2。

而样例恰恰没有违背我的理解，我的代码还过了样例……

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
#include <bits/stdc++.h>

using namespace std;

inline long long read()
{
    long long x = 0;
    int f = 1;
    char ch = getchar();
    while (ch < '0' || ch>'9')
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar();
    }
    return x * f;
}
void write(const int& x)
{
    if (!x)
    {
        putchar('0');
        return;
    }
    char f[100];
    int tmp = x;
    if (tmp < 0)
    {
        tmp = -tmp;
        putchar('-');
    }
    int s = 0;
    while (tmp > 0)
    {
        f[s++] = tmp % 10 + '0';
        tmp /= 10;
    }
    while (s > 0)
    {
        putchar(f[--s]);
    }
}

int totN;
double ax,ay,bx,by;
struct circle
{
    double x,y;
    double r;
    bool in[3];
}circles[1009];
int result;

int main()
{
    totN=read();
    for (int i = 1; i <= totN; ++i)
    {
        circles[i].x=read();
    }
    for (int i = 1; i <= totN; ++i)
    {
        circles[i].y=read();
    }
    for (int i = 1; i <= totN; ++i)
    {
        circles[i].r=read();
    }
    ax=read();
    ay=read();
    bx=read();
    by=read();
    for (int i = 1; i <= totN; ++i)
    {
        if (fabs(circles[i].x-ax+0.0)*fabs(circles[i].x-ax+0.0)+fabs(circles[i].y-ay+0.0)*fabs(circles[i].y-ay+0.0)<=circles[i].r*circles[i].r+0.0)
        {
            circles[i].in[1]=true;
        }
        if (fabs(circles[i].x-bx+0.0)*fabs(circles[i].x-bx+0.0)+fabs(circles[i].y-by+0.0)*fabs(circles[i].y-by+0.0)<=circles[i].r*circles[i].r+0.0)
        {
            circles[i].in[2]=true;
        }
    }
    for (int i = 1; i <= totN; ++i)
    {
        result+=circles[i].in[1]^circles[i].in[2];
    }
    write(result);
    return 0;
}//LikiBlaze Code

如果圆之间可以包含的话，其实总体思路是一样的……只要有圆是一个点在但是另一个点不在，result++即可。

T3 阶乘之和

题目

题目描述

给定一个非负整数 n，请你判断 n 是否可以由一些非负整数的阶乘相加得到。

输入格式

有若干组数据。每行一个整数 n，保证 n<1000000。 以负数结束输入。

输出格式

对于每组数据输出一行，若可以则输出‘YES’，否则输出‘NO’。

输入输出样例

输入 #1

1
2
9 
-1

输出 #1

1
YES

分析

这道题可以选择深搜，也可以选择01背包预处理。

我考试的时候写的是深搜，然后后来写的是预处理。

主要的错误其实和别人也是一样的，以为0!=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
#include <bits/stdc++.h>

using namespace std;

inline long long read()
{
    long long x = 0;
    int f = 1;
    char ch = getchar();
    while (ch < '0' || ch>'9')
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar();
    }
    return x * f;
}
void write(const int& x)
{
    if (!x)
    {
        putchar('0');
        return;
    }
    char f[100];
    int tmp = x;
    if (tmp < 0)
    {
        tmp = -tmp;
        putchar('-');
    }
    int s = 0;
    while (tmp > 0)
    {
        f[s++] = tmp % 10 + '0';
        tmp /= 10;
    }
    while (s > 0)
    {
        putchar(f[--s]);
    }
}

bool flag;

const int maxc=10;
long long jie[19]={1,1};
bool used[19];
bool able[1000090]={1};

void cheng()
{
    for (int i = 2; i <= maxc; ++i)
    {
        jie[i] = jie[i - 1] * i;
    }
}
void work()
{
    for (int j = 9; j >= 0; --j)
    {
        for (int i = 1000009-jie[j]; i >= 0; --i)
        {
            if (able[i])
            {
                able[i+jie[j]]=true;
            }
        }
    }
}

int main()
{
    cheng();
    work();
    int temp;
    temp=read();
    while (temp>=0)
    {
        if (temp==0)
        {
            putchar('N');
            putchar('O');
            putchar('\n');
        }
        else if (able[temp])
        {
            putchar('Y');
            putchar('E');
            putchar('S');
            putchar('\n');
        }
        else
        {
                putchar('N');
                putchar('O');
                putchar('\n');
        }
        temp=read();
    }
    return 0;
}//LikiBlaze Code