“战疫杯”在线邀请赛——第三场题解_C

“战疫杯”在线邀请赛——第三场题解题目详情 - 1 疫情防控网格化 (pintia.cn)

由于防控形势严峻，现在z市已经开始了全区域的网格化封控管理。该市的区域可以看成一个矩形，其中所有主干道都是水平或垂直的，并且贯穿整个区域。如图所示，黑色表示城区的边界，红色表示城区的主干道，其中边界和主干道宽度都为1，且不存在边界与主干道、主干道与主干道相邻的情况。

为了方便网格化管理，我们定义网格单元是由城区边界或主干道围成的区域，且任意网格单元内不能包含主干道。上图中，该城区共被分割成了16个网格单元。

现在给出该区域的地图，需要你统计出该城区划分出了多少个网格单元，以方便安排医务人员和应急物资。

在计算机中，图像的本质就是二维的矩阵。为了方便处理，我们将上述图像中城区边界及里面的内容转化为了二维字符矩阵，详细见输入格式描述。

输入格式:

第一行输入两个整数n,m(3≤n,m≤100)
其后n行，每行m个字符，字符有’‘和’#‘两种。’‘代表城区边界或主干道，’#'代表网格单元内区域。

输出格式:

输出一行一个整数，代表地图中的网格单元个数。

输入样例:

3 7
*******
*##*##*
*******

输出样例:

问题解析

简单的模拟，我们可以一行行的去遍历，当出现当前位置是‘#’，上一个位置是‘ *'，且当前位置的上方也是’ *‘时就说明我们已经找到一个网格单元的左上角了，计数器++。遍历完矩阵后输出计数器即可。

#include
using namespace std;
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include

#define endl '\n';
typedef long long ll;
typedef pairPII;
const int N = 2e5 + 50;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vectorv(n);
    for (int i = 0; i < n; i++)cin >> v[i];
    bool flag = true;
    int res = 0;
    for (int i = 0; i < n; i++)
    {
        for (int j = 1; j < m; j++)
        {
            if (flag && v[i][j] == '#' && v[i][j - 1] == '*' && (i == 0 || v[i - 1][j] == '*'))
            {
                res++;
            }
        }
    }
    cout << res;
    return 0;
}

题目详情 - 2 子区域计数 (pintia.cn)

由于防控形势严峻，现在z市已经开始了全区域的网格化封控管理。该市的区域可以看成一个矩形，其中所有主干道都是水平或垂直的，并且贯穿整个区域。如图所示，黑色表示城区的边界，红色表示城区的主干道。其中边界和主干道宽度都为1，且不存在边界与主干道、主干道与主干道相邻的情况。

同时，网格化管理的本质思想是“分治”，不同的划分粒度对于管理效率会产生深远的影响。所以，这次W同学思考的不仅仅是网格单元，而是子网格。

子网格的定义为：子网格也是一个矩形，且子网格矩形4个角的对应点都位于边界与边界、边界与主干道、主干道与主干道的交点上。我们认为两个子网格是相同的，当且仅当两个子网格的4个角对应点全部重合。根据这个定义，我们可以知道，任意的网格单元也是一种子网格，整个城区的矩形也是一种特殊的子网格。

同样给出上述的图像，你能否帮小W计算下，有多少种可能的子网格？

输入格式:

第一行输入两个整数n,m(3≤n,m≤100)
其后n行，每行m个字符，字符有’‘和’#‘两种。’‘代表城区边界或主干道，’#'代表网格单元内区域。

输出格式:

输出一行一个整数，代表符合条件不同子网格的个数。

输入样例:

3 7
*******
*##*##*
*******

输出样例:

问题解析

这题是上一题的延申，从找单个单元格到找所有的矩阵单元格。先分析一下样例：答案是3，一共有以下这些矩阵单元格

****        *******
*##* X 2    *##*##*  X 1
****        *******

然后因为题目已经固定了同一题里每个单元格的长款是相等的（比如样例的单元格是长2宽1，就不会出现长2宽2这样的单元格），我们可以先求出每行的单元格个数h，和每列的单元格个数s，通过枚举每个子矩阵的长和宽算出有多少个子矩阵。

举例：

7 10
**********
*##*##*##*
**********
*##*##*##*
**********
*##*##*##*
**********

此时长是3，宽是3，那我们就可以枚举出下列样子的单元格：

答案就是36。

#include
using namespace std;
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include

#define endl '\n';
typedef long long ll;
typedef pairPII;
const int N = 2e5 + 50;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vectorv(n);
    for (int i = 0; i < n; i++)cin >> v[i];
    bool flag = true;
    ll res = 0;
    //h是一行有多少单元格，s是一列有多少单元格
    int h = 0, s = 0;
    for (int i = 0; i < n; i++)
    {
        int ans=res;
        for (int j = 1; j < m; j++)
        {
            if (flag && v[i][j] == '#' && v[i][j - 1] == '*' && (i == 0 || v[i - 1][j] == '*'))
            {
                res++;
            }
        }
        //如果res数量在此层发生变化，说明这一层是有单元格的，横数++
        if(ans!=res)s++;
    }
    //总数除去列数就得到行数
    h = res / s;
    res = 0;
    
    for (int i = 0; i < s; i++)
    {
        for (int j = 0; j < h; j++)
        {
            res += (h - j) * (s - i);
        }
    }

    cout << res;
    return 0;
}

题目详情 - 3 怀旧的思考挑战 (pintia.cn)

疫情来了，柴刘青山在寝室关着非常无聊，和室友一起玩跑跑卡丁车这款老游戏。

这款游戏有一个模式叫做组队竞速，每局8个人，分为两队，最终比拼哪队总分更高。

第一名冲线得到8分，第二名得到7分，以此类推，第八名得到1分。

柴刘青山好奇自己队伍在某一局游戏中是否能得到某个总分，如果可以，有多少种排名情况可以达成该总分？

后记：柴刘青山和室友们寻求过短暂的放松后，决定还是在学业上开启“竞速模式”，约定共同努力学习，参加“战疫杯”！输入格式:

第一行一个正整数n，表示猜想的n总分。 0≤n≤10000

输出格式:

如果可以达成，输出一个正整数x，代表有多少种排名情况。
如果不能达成，输出NO。

输入样例:

输出样例:

样例解释1

柴刘青山的队伍需要取得1、2、3、5名，对应8+7+6+4=25。有且仅有这一种情况。

问题解析

8人分成两队就是一队四人，我们四重for循环枚举每个位置可能的排名数，只要四个排名得分加一起等于n，计数器就++，如果计数器为0，说明不可能得到，输出NO。

#include
using namespace std;
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include

#define endl '\n';
typedef long long ll;
typedef pairPII;
const int N = 2e5 + 50;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n;
    cin >> n;
    int res = 0;
    for (int i = 1; i <= 8; i++)
    {
        for (int j = i + 1; j <= 8; j++)
        {
            for (int k = j + 1; k <= 8; k++)
            {
                for (int l = k + 1; l <= 8; l++)
                {
                    if (l + k + i + j == n)res++;
                }
            }
        }
    }
    if (res == 0)cout << "NO";
    else cout << res;
    return 0;
}

欢迎分享，转载请注明来源：内存溢出

原文地址: http://outofmemory.cn/langs/914584.html

“战疫杯”在线邀请赛——第三场题解

发表评论

评论列表（0条）