2021 年百度之星·程序设计大赛 - 初赛三

本文主要是介绍2021 年百度之星·程序设计大赛 - 初赛三，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

网址：Contest Problem List (hdu.edu.cn)

1001	签到题	判断取得的平均数是否在最大值和最小值之间，但是题目并未保证输入最大值一定比最小值大，并且未发现该问题，导致不断的WA，需要加以判断。
1002	DFS深搜模板提	就是简单的表格路径深度搜索，只需要将走过的路径设置为不可通过，调用两次深度搜索的方法即可，并且行进的路径只能是向右以及向下。问题中居然未保证起始点和终止点一定是可以行走的。
1003
1004	DFS深搜+ 打表	将问题转换成搜索的问题，由于数据量比较小只有80，将在线计算的结果保存到数组中变成离线的问题即可，然后根据输入判断取出值即可。

由于第一道签到题存在的坑点迟迟未发现，导致三个小时的比赛变成了一个半小时，其中很大部分时间都在考虑为什么这么简单的签到题却不能A掉呢。共计AC两道，罚时5次。

1001

该题为一个签到题，判断最后的均值是否在最大值和最小值之间即可。一道极为自闭的题目。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

int main()
{
    int T;
    scanf("%d", &T);
    while(T--)
    {
        ll n, max_, min_, ave_;
        scanf("%lld%lld%lld%lld", &n, &max_, &min_, &ave_);
        max_ = max_ + 100;
        min_ = min_ + 100;
        ave_ = ave_ + 100;
        if(n == 1)
        {
            if(max_ == min_ && max_ == ave_)
            {
                cout << "yes" << endl;
            }
            else
            {
                cout << "no" << endl;
            }

        }
        else if(n == 2)
        {
            if(max_ + min_ == ave_ * 2 && max_ >= min_)
            {
                cout << "yes" << endl;
            }
            else
            {
                cout << "no" << endl;
            }
        }
        else if(n >= 3)
        {

            ll sum = n * ave_;
            sum = sum - max_;
            sum = sum - min_;

            //if(ans >= min_ * 1.0 && ans <= max_)
            if(sum >= min_ * (n - 2) && sum <= max_ * (n - 2))
            {
                cout << "yes" << endl;
            }
            else
            {
                cout << "no" << endl;
            }
        }
    }
    return 0;
}

1002

该题就是简单的DFS深搜，由于路径的数目最多只能为2，所以只有0，1，2的情况，将写好的DFS代码执行两次，其中将走过的路径转换为不可行进，即可获得答案。其中起点和终点未保证一定是可以行进的。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 15;
int vis[maxn][maxn];
char str[maxn][maxn];
int ans;

void DFS(int x, int y, int n, int &k)
{
    //printf("%d   %d\n", x, y);
    if(x == n-1 && y == n-1)
    {
        vis[x][y] = 0;
        k = 1;
        ans ++;
        //cout << ans << endl;
        return;
    }
    int x1 = x + 1;
    int y1 = y;
    int x2 = x;
    int y2 = y + 1;
    if(x1 < n && y1 < n && vis[x1][y1] == 0)
    {
        vis[x1][y1] = 1;
        DFS(x1, y1, n, k);
        if(k == 1)
            return;
    }
    if(x2 < n && y2 < n && vis[x2][y2] == 0)
    {
        vis[x2][y2] = 1;
        DFS(x2, y2, n, k);
        if(k == 1)
            return;
    }
    return;
}

int main()
{
    int T;
    scanf("%d", &T);
    while(T--)
    {
        int n;
        scanf("%d", &n);
        for(int i=0; i<n; i++)
        {
            scanf("%s", str[i]);
        }
        memset(vis, 0, sizeof(vis));

        for(int i=0; i<n; i++)
        {
            for(int j=0; j<n; j++)
            {
                if(str[i][j] == '.')
                {
                    vis[i][j] = 0;
                }
                else if(str[i][j] == '#')
                {
                    vis[i][j] = 1;
                }
            }
        }
        if(vis[0][0] == 1 || vis[n-1][n-1] == 1)
        {
            cout << 0 << endl;
        }
        else
        {
            /*
            for(int i = 0; i<n ; i++)
            {
                for(int j=0; j<n; j++)
                {
                    printf("%d ", vis[i][j]);
                }
                printf("\n");
            }
            */
            int k = 0;
            ans = 0;
            DFS(0, 0, n, k);
            /*
            for(int i = 0; i<n ; i++)
            {
                for(int j=0; j<n; j++)
                {
                    printf("%d ", vis[i][j]);
                }
                printf("\n");
            }
            */
            k = 0;
            DFS(0, 0, n, k);
            /*
            for(int i = 0; i<n ; i++)
            {
                for(int j=0; j<n; j++)
                {
                    printf("%d ", vis[i][j]);
                }
                printf("\n");
            }
            */
            cout << ans << endl;
        }

    }
    return 0;
}

1003

1004

该题目分为两部分进行，因为使用在线计算的情况会超时，并且查询量较小只有80个，故所以我们离线在本地计算好结果好保存到数组中，然后提交在线查询，根据查询在数组中取出对应值即可。

代码段一为在线的方法，计算出每个值对应的结构。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 100;
int vis[maxn];
int ans;
int sum[maxn];

void DFS(int s, int k, int n)
{
    if(k == n)
    {
        ans++;
        return;
    }
    int r = (s + k + n) % n;
    if(r == 0)
        r = n;
    int l = (s - k + n) % n;
    if(l == 0)
        l = n;

    if(vis[r] == 0)
    {
        vis[r] = 1;
        DFS(r, k+1, n);
        vis[r] = 0;
    }
    if(vis[l] == 0)
    {
        vis[l] = 1;
        DFS(l, k+1, n);
        vis[l] = 0;
    }
    return;
}

int main()
{
    int t, n;
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d", &n);
        memset(vis, 0, sizeof(vis));
        ans = 0;

        vis[1] = 1;
        DFS(1, 1, n);
        cout << ans << endl;
    }
    return 0;
}

代码段二，将结构保存至数组中，直接取出对应的值即可。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 105;

int main()
{
    int sum[80] = {1, 2, 2, 4, 2, 4, 4, 8, 2, 4, 6, 8, 2, 8, 6, 16, 2, 4, 6, 8, 4, 12, 6, 16, 4, 4, 4, 16, 2, 12, 10, 32, 4, 4, 8, 8, 2, 12, 6, 16, 2, 8, 6, 24, 6, 12, 8, 32, 6, 8, 6, 8, 2, 8, 10, 32, 4, 4, 6, 24, 2, 20, 6, 64, 6, 8, 8, 8, 4, 16, 6, 16, 2, 4, 8, 24, 14, 12, 6, 32};
    int t, n;
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d", &n);
        cout << sum[n-1] << endl;
    }
    return 0;
}

这篇关于2021 年百度之星·程序设计大赛 - 初赛三的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！

Java教程