挑战程序设计竞赛第二章练习题解

//poj1979

#include <iostream>
#include <sstream>
#include <fstream>
#include <string>
#include <map>
#include <vector>
#include <list>
#include <set>
#include <stack>
#include <queue>
#include <deque>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <limits>
#include <new>
#include <utility>
#include <iterator>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <ctime>
using namespace std;
const int INF = 0x3f3f3f3f;
const double PI = acos(-1.0);
int dx[] = {0, 1, 0, -1}, dy[] = {-1, 0, 1, 0};
const int maxn = 25;

int h, w;
char s[maxn][maxn];
int sx, sy;

bool range(int x, int y)
{
    return x >= 0 && x < h && y >= 0 && y < w;
}

int dfs(int x, int y)
{
    int ans = 1;
    s[x][y] = '#';
    for (int i = 0; i < 4; ++i)
        if (range(x+dx[i], y+dy[i]) && s[x+dx[i]][y+dy[i]] == '.')
            ans += dfs(x+dx[i], y+dy[i]);
    return ans;
}


int main()
{
    while (cin >> w >> h && (w || h))
    {
        for (int i = 0; i < h; ++i)
        {
            scanf("%s", s[i]);
            for (int j = 0; j < w; ++j)
                if (s[i][j] == '@')
                {
                    sx = i;
                    sy = j;
                }
        }
        cout << dfs(sx, sy) << endl;
    }
    return 0;
}


//poj3009

#include <iostream>
#include <sstream>
#include <fstream>
#include <string>
#include <map>
#include <vector>
#include <list>
#include <set>
#include <stack>
#include <queue>
#include <deque>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <limits>
#include <new>
#include <utility>
#include <iterator>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <ctime>
using namespace std;
const int INF = 0x3f3f3f3f;
const double PI = acos(-1.0);
int dx[] = {0, 1, 0, -1}, dy[] = {-1, 0, 1, 0};
const int maxn = 25;

int h, w;
int s[maxn][maxn];
int sx, sy;

bool range(int x, int y)
{
    return x >= 0 && x < h && y >= 0 && y < w;
}

int dfs(int x, int y, int cur)
{
    if (cur > 10)
        return INF;
    int ans = INF;
    for (int i = 0; i < 4; ++i)
    {
        int tmpx = x + dx[i], tmpy = y + dy[i];
        if (!range(tmpx, tmpy) || s[tmpx][tmpy] == 1)
            continue;
        while (range(tmpx, tmpy) && (!s[tmpx][tmpy] || s[tmpx][tmpy] == 3))
        {
            if (s[tmpx][tmpy] == 3)
                return cur;
            tmpx += dx[i];
            tmpy += dy[i];
        }
        if (!range(tmpx, tmpy))
            continue;
        s[tmpx][tmpy] = 0;
        ans = min(ans, dfs(tmpx-dx[i], tmpy-dy[i], cur+1));
        s[tmpx][tmpy] = 1;
    }
    return ans;
}

int main()
{
    while (cin >> w >> h && (w || h))
    {
        for (int i = 0; i < h; ++i)
            for (int j = 0; j < w; ++j)
            {
                scanf("%d", &s[i][j]);
                if (s[i][j] == 2)
                {
                    s[i][j] = 0;
                    sx = i;
                    sy = j;
                }
            }
        int ans = dfs(sx, sy, 1);
        if (ans == INF)
            ans = -1;
        cout << ans << endl;
    }
    return 0;
}

 


//poj3669

#include <iostream>
#include <sstream>
#include <fstream>
#include <string>
#include <map>
#include <vector>
#include <list>
#include <set>
#include <stack>
#include <queue>
#include <deque>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <limits>
#include <new>
#include <utility>
#include <iterator>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <ctime>
using namespace std;
const int INF = 0x3f3f3f3f;
const double PI = acos(-1.0);
int dx[] = {0, 1, 0, -1, 0}, dy[] = {-1, 0, 1, 0, 0};
const int maxn = 400;

struct Point
{
    int x, y, len;
};

int s[maxn][maxn], vis[maxn][maxn];

bool range(int x, int y)
{
    return x >= 0 && y >= 0;
}

int bfs()
{
    queue<Point> q;
    q.push({0, 0, 0});
    vis[0][0] = 1;
    while (!q.empty())
    {
        Point p = q.front();
        q.pop();
        int x = p.x, y = p.y;
        if (s[x][y] == INF)
            return p.len;
        if (s[x][y] <= p.len)
            continue;
        for (int i = 0; i < 5; ++i)
        {
            int tx = x + dx[i], ty = y + dy[i];
            if (range(tx, ty) && !vis[tx][ty])
            {
                vis[tx][ty] = 1;
                q.push({tx, ty, p.len+1});
            }
        }
    }
    return -1;
}

int main()
{
    for (int i = 0; i < 400; ++i)
        for (int j = 0; j < 400; ++j)
        {
            s[i][j] = INF;
            vis[i][j] = 0;
        }
    int m;
    cin >> m;
    while (m--)
    {
        int x, y, t;
        scanf("%d%d%d", &x, &y, &t);
        for (int i = 0; i < 5; ++i)
            if (range(x+dx[i], y+dy[i]) && s[x+dx[i]][y+dy[i]] > t)
                s[x+dx[i]][y+dy[i]] = t;
    }
    cout << bfs() << endl;
    return 0;
}

 


//poj2718

#include <iostream>
#include <sstream>
#include <fstream>
#include <string>
#include <map>
#include <vector>
#include <list>
#include <set>
#include <stack>
#include <queue>
#include <deque>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <limits>
#include <new>
#include <utility>
#include <iterator>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <ctime>
using namespace std;
const int INF = 0x3f3f3f3f;
const double PI = acos(-1.0);
int dx[] = {0, 1, 0, -1, 0}, dy[] = {-1, 0, 1, 0, 0};
const int maxn = 400;

int ans, n;
int num[10], vis[10];

void solve(int a)
{
    int tmp[10], cnt = 0;
    for (int i = 0; i < n; ++i)
        if (!vis[i])
            tmp[cnt++] = num[i];
    do
    {
        if (!tmp[0] && cnt > 1)
            continue;
        int b = tmp[0];
        for (int i = 1; i < cnt; ++i)
            b = b * 10 + tmp[i];
        ans = min(ans, abs(a-b));
    } while (next_permutation(tmp, tmp+cnt));
}

void dfs(int cur, int res)
{
    if (cur == n/2)
    {
        solve(res);
        return;
    }
    for (int i = 0; i < n; ++i)
        if (!vis[i])
        {
            if (!cur && !i && n > 2)
                continue;
            vis[i] = 1;
            dfs(cur+1, res*10+num[i]);
            vis[i] = 0;
        }
}

int main()
{
    int kase;
    cin >> kase;
    getchar();
    while (kase--)
    {
        ans = INF;
        memset(vis, 0, sizeof(vis));
        char ch;
        n = 0;
        while (scanf("%c", &ch) == 1 && ch != '\n')
            if (ch != ' ')
                num[n++] = ch - '0';
        dfs(0, 0);
        cout << ans << endl;
    }
    return 0;
}

 


//poj3187

#include <iostream>
#include <sstream>
#include <fstream>
#include <string>
#include <map>
#include <vector>
#include <list>
#include <set>
#include <stack>
#include <queue>
#include <deque>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <limits>
#include <new>
#include <utility>
#include <iterator>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <ctime>
using namespace std;
const int INF = 0x3f3f3f3f;
const double PI = acos(-1.0);
int dx[] = {0, 1, 0, -1}, dy[] = {-1, 0, 1, 0};
const int maxn = 10000010;

int main()
{
    int n, sum;
    cin >> n >> sum;
    int s[15];
    for (int i = 0; i < n; ++i)
        s[i] = i + 1;
    do
    {
        int t[15];
        for (int i = 0; i < n; ++i)
            t[i] = s[i];
        int tmp = n;
        while (tmp-- > 1)
            for (int i = 0; i < tmp; ++i)
                t[i] += t[i+1];
        if (t[0] == sum)
        {
            for (int i = 0; i < n-1; ++i)
                printf("%d ", s[i]);
            printf("%d\n", s[n-1]);
            break;
        }
    } while (next_permutation(s, s+n));
    return 0;
}

 


//poj3050

#include <iostream>
#include <sstream>
#include <fstream>
#include <string>
#include <map>
#include <vector>
#include <list>
#include <set>
#include <stack>
#include <queue>
#include <deque>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <limits>
#include <new>
#include <utility>
#include <iterator>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <ctime>
using namespace std;
const int INF = 0x3f3f3f3f;
const double PI = acos(-1.0);
int dx[] = {0, 1, 0, -1}, dy[] = {-1, 0, 1, 0};
const int maxn = 10000010;

int s[5][5];
set<int> m;

bool range(int x, int y)
{
    return x >= 0 && x < 5 && y >= 0 && y < 5;
}

void dfs(int x, int y, int res, int cur)
{
    if (cur == 5)
    {
        m.insert(res);
        return;
    }
    for (int i = 0; i < 4; ++i)
    {
        int tx = x + dx[i], ty = y + dy[i];
        if (range(tx, ty))
        {
            int tmp = res * 10 + s[tx][ty];
            dfs(tx, ty, tmp, cur+1);
        }
    }
}

int main()
{
    for (int i = 0; i < 5; ++i)
        for (int j = 0; j < 5; ++j)
            scanf("%d", &s[i][j]);
    for (int i = 0; i < 5; ++i)
        for (int j = 0; j < 5; ++j)
            dfs(i, j, s[i][j], 0);
    int ans = 0;
    for (set<int>::iterator it = m.begin(); it != m.end(); ++it)
        ans++;
    cout << ans << endl;
    return 0;
}

 


//poj2376

#include <iostream>
#include <sstream>
#include <fstream>
#include <string>
#include <map>
#include <vector>
#include <list>
#include <set>
#include <stack>
#include <queue>
#include <deque>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <limits>
#include <new>
#include <utility>
#include <iterator>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <ctime>
using namespace std;
const int INF = 0x3f3f3f3f;
const double PI = acos(-1.0);
int dx[] = {0, 1, 0, -1}, dy[] = {-1, 0, 1, 0};
const int maxn = 25010;

struct cow
{
    int start, over;
    bool operator < (const cow& b) const
    {
        if (start != b.start)
            return start < b.start;
        return over > b.over;
    }
};

cow s[maxn];

int main()
{
    int n, t;
    scanf("%d%d", &n, &t);
    for (int i = 0; i < n; ++i)
        scanf("%d%d", &s[i].start, &s[i].over);
    sort(s, s+n);
    int ans = 0, last = 1, tmp = 0;
    while (last <= t)
    {
        if (tmp == n || s[tmp].start > last)
            break;
        int tmplast = 0;
        for (int i = tmp; i < n; ++i)
        {
            if (s[i].start > last)
            {
                tmp = i;
                break;
            }
            if (tmplast < s[i].over)
                tmplast = s[i].over;
            tmp = i + 1;
        }
        ans++;
        last = tmplast + 1;
    }
    if (last <= t)
        ans = -1;
    cout << ans << endl;
    return 0;
}

 

 

 

//poj1328

 

#include <iostream>
#include <sstream>
#include <fstream>
#include <string>
#include <map>
#include <vector>
#include <list>
#include <set>
#include <stack>
#include <queue>
#include <deque>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <limits>
#include <new>
#include <utility>
#include <iterator>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <ctime>
using namespace std;
const int inf = 0x3f3f3f3f;
const double pi = acos(-1.0);
const double eps = 1e-8;
int dx[] = {0, 1, 0, -1}, dy[] = {-1, 0, 1, 0};
const int maxn = 25010;

struct island
{
    double left, right;
    bool operator < (const island& b) const
    {
        if (right != b.right)
            return right < b.right;
        return left > b.left;
    }
};

int main()
{
    int n, d, kase = 1;
    while (scanf("%d%d", &n, &d) == 2 && (n || d))
    {
        island s[1010];
        int can = 1;
        for (int i = 0; i < n; ++i)
        {
            int x, y;
            scanf("%d%d", &x, &y);
            if (abs(y) > d)
            {
                can = 0;
                continue;
            }
            s[i].left = x - sqrt(1.0*d*d-y*y);
            s[i].right = x + sqrt(1.0*d*d-y*y);
        }
        if (!can)
        {
            printf("Case %d: -1\n", kase++);
            continue;
        }
        sort(s, s+n);
        int ans = 1;
        island tmp = s[0];
        for (int i = 1; i < n; ++i)
            if (s[i].left > tmp.right)
            {
                ++ans;
                tmp = s[i];
            }
        printf("Case %d: %d\n", kase++, ans);
    }
    return 0;
}

 

算法码上来 文章被收录于专栏

公众号「算法码上来」。godweiyang带你学习算法，不管是编程算法，还是深度学习、自然语言处理算法都一网打尽，更有各种计算机新鲜知识和你分享。别急，算法码上来。

全部评论

相关推荐

昨天 23:28
河南理工大学 平台产品
点赞 评论 收藏
分享
头像
11-07 12:13
东北大学 Java
点赞 评论 收藏
分享
10-10 21:40
门头沟学院 前端工程师
你们出生产事故了？
哪个程序员要背绩效了？
Java抽象带篮子：难蚌，点进图片上面就是我的大头😆
点赞 评论 收藏
分享
10-16 07:59
ノートルダム清心女子大学 Java
逆天了，都已经转行了，小米捞了个面试
牛客969571862号：昨天捞我今天面这个，岗位一模一样，感觉就是面着玩
点赞 评论 收藏
分享
11-03 14:10
厦门大学 数据分析师
字节一周实习体验：想死，但没时间死
每天都有一堆需求、无数会议，感觉一天的工作量能顶我在京东干三天。早上到晚上，根本停不下来，想死的时候就去楼下喝杯咖啡继续拼命。不过我的导师特别用心，入职以来经常关心我的感受，带我开会，还每天叫我一起吃饭，顺便帮我拿下午茶，还让我参与自己的项目。小组氛围超级好，字节的扁平化管理做得很到位，大家沟通没有等级差距，直呼名字就行。一起团建、下午茶，聊八卦，虽然大家都很卷，但气氛轻松。公司福利也不错，下午茶、礼包、免费办公用具、三餐应有尽有。工区的视野超赞，每天都能看夕阳，虽然三餐的味道比京东差点，但也能接受。
字节跳动成长空间 493人发布
点赞 评论 收藏
分享
点赞 收藏 评论
分享

全站热榜

正在热议
# 25届秋招公司红黑榜 #
112526次浏览 586人参与
# 通信硬件人笔面经互助 #
1015639次浏览 14710人参与
# 机械制造笔面经 #
1852174次浏览 28880人参与
# 非技术投递记录 #
425636次浏览 5496人参与
# 不考虑薪资和职业，你最想做什么工作呢？ #
20636次浏览 175人参与
# 央国企投递记录 #
37362次浏览 948人参与
# 我的实习日记 #
1278049次浏览 15892人参与
# 25届秋招总结 #
33699次浏览 462人参与
# 今年秋招哪家公司给的薪资最良心？ #
19553次浏览 178人参与
# 硬件应届生薪资是否普遍偏低？ #
42431次浏览 404人参与
# 如果公司降薪，你会跳槽吗？ #
18743次浏览 197人参与
# 想给25届机械人的秋招建议 #
15706次浏览 161人参与
# 简历被挂麻了，求建议 #
2357701次浏览 32269人参与
# 一觉醒来，秋招难度下降一万倍…… #
15618次浏览 182人参与
# 如何写一份好简历 #
580864次浏览 8271人参与
# 实习好累，可以辞职全力准备秋招吗 #
30040次浏览 506人参与
# 投递实习岗位前的准备 #
1136790次浏览 17781人参与
# 米哈游求职进展汇总 #
163484次浏览 1406人参与
# 你会选择考研还是直接就业 #
165767次浏览 1782人参与
# 实习中的菜狗时刻 #
266876次浏览 2672人参与
牛客网
牛客企业服务