"War epidemic Cup" online invitational tournament -- solution to the third game

"War epidemic Cup" online invitational tournament -- solution to the third game

Topic details - 1 grid of epidemic prevention and control (pintia.cn)

Due to the severe situation of prevention and control, z City has started the grid sealing and control management of the whole region. The area of the city can be regarded as a rectangle, in which all main roads are horizontal or vertical and run through the whole area. As shown in the figure, black indicates the boundary of the urban area, and red indicates the main road of the urban area. The width of the boundary and the main road is 1, and there is no situation that the boundary is adjacent to the main road, and the main road is adjacent to the main road.

In order to facilitate grid management, we define grid cells as areas surrounded by urban boundaries or trunk roads, and any grid cell cannot contain trunk roads. In the figure above, the urban area is divided into 16 grid units.

Now give the map of the area. You need to count how many grid units are divided in the urban area to facilitate the arrangement of medical personnel and emergency supplies.

In computer, the essence of image is two-dimensional matrix. In order to facilitate processing, we convert the urban boundary and contents in the above image into a two-dimensional character matrix. See the input format description for details.

Input format:

Enter two integers n,m(3 ≤ n,m ≤ 100) in the first line
The next n lines are m characters in each line, and the characters are '#' and '#'‘ Represents the urban boundary or main road, and '#' represents the area within the grid unit.

Output format:

Output an integer per line, representing the number of grid cells in the map.

Input sample:

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

Output example:

2

Problem analysis

In simple simulation, we can traverse line by line. When the current position is' # ', the previous position is' *', and the upper part of the current position is also '*', it means that we have found the upper left corner of a grid cell, counter + +. After traversing the matrix, output the counter.

#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<math.h>
#include<set>
#include<numeric>
#include<string>
#include<string.h>
#include<iterator>
#include<map>
#include<unordered_map>
#include<stack>
#include<list>
#include<queue>
#include<iomanip>

#define endl '\n';
typedef long long ll;
typedef pair<ll, ll>PII;
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;
    vector<string>v(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;
}

Topic details - 2 sub area count (pintia.cn)

Due to the severe situation of prevention and control, z City has started the grid sealing and control management of the whole region. The area of the city can be regarded as a rectangle, in which all main roads are horizontal or vertical and run through the whole area. As shown in the figure, black represents the boundary of the urban area and red represents the main road of the urban area. The width of the boundary and the main road is 1, and there is no case that the boundary is adjacent to the main road, and the main road is adjacent to the main road.

In order to facilitate grid management, we define grid cells as areas surrounded by urban boundaries or trunk roads, and any grid cell cannot contain trunk roads. In the figure above, the urban area is divided into 16 grid units.

At the same time, the essential idea of grid management is "divide and conquer", and different division granularity will have a far-reaching impact on management efficiency. Therefore, this time, classmate W is thinking about not only grid cells, but sub grids.

The definition of sub grid is that the sub grid is also a rectangle, and the corresponding points of the four corners of the sub grid rectangle are located at the intersection of boundary and boundary, boundary and main road, main road and main road. We believe that the two sub grids are the same if and only if the corresponding points of the four corners of the two sub grids coincide. According to this definition, we can know that any grid cell is also a sub grid, and the rectangle of the whole urban area is also a special sub grid.

Also given the above image, can you help Xiao W calculate how many possible sub grids there are?

Input format:

Enter two integers n,m(3 ≤ n,m ≤ 100) in the first line
The next n lines are m characters in each line, and the characters are '#' and '#'‘ Represents the urban boundary or main road, and '#' represents the area within the grid unit.

Output format:

Output one integer per line, representing the number of different sub grids that meet the conditions.

Input sample:

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

Output example:

3

Problem analysis

This question is an extension of the previous one, from finding a single cell to finding all matrix cells. First analyze the example: the answer is 3. There are the following matrix cells

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

Then, because the topic has been fixed, the length of each cell in the same topic is equal (for example, if the sample cell is 2 long and 1 wide, there will be no such cell as 2 long and 2 wide). We can first calculate the number of cells in each row h and the number of cells in each column s, and calculate how many sub matrices there are by enumerating the length and width of each sub matrix.

give an example:

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

When the length is 3 and the width is 3, we can list the following cells:

The answer is 36.

#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<math.h>
#include<set>
#include<numeric>
#include<string>
#include<string.h>
#include<iterator>
#include<map>
#include<unordered_map>
#include<stack>
#include<list>
#include<queue>
#include<iomanip>

#define endl '\n';
typedef long long ll;
typedef pair<ll, ll>PII;
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;
    vector<string>v(n);
    for (int i = 0; i < n; i++)cin >> v[i];
    bool flag = true;
    ll res = 0;
    //h is the number of cells in a row and s is the number of cells in a column
    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++;
            }
        }
        //If the number of res changes in this layer, it indicates that there are cells in this layer, horizontal number++
        if(ans!=res)s++;
    }
    //The total number of rows is obtained by removing the number of columns
    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;
}

Topic details - 3 nostalgic thinking challenge (pintia.cn)

When the epidemic came, Chai Liu Qingshan was very bored in his bedroom and played the old game of running kart with his roommate.

This game has a mode called team racing. There are 8 people in each game, divided into two teams, and finally compete which team has a higher total score.

The first place gets 8 points, the second place gets 7 points, and so on, and the eighth place gets 1 point.

Chai Liu Qingshan wonders whether his team can get a total score in a game. If so, how many ranking situations can achieve the total score?

Postscript: after seeking a brief relaxation, Chai, Liu Qingshan and his roommates decided to start the "racing mode" in their studies and agreed to work hard together to participate in the "war epidemic Cup"!

Input format:

The first line is a positive integer n, which represents the total score of conjecture n. 0≤n≤10000

Output format:

If it can be achieved, output a positive integer x, representing how many ranking situations there are.
If not, output NO.

Input sample:

25

Output example:

1

Example explanation 1

Chai Liu Qingshan's team needs to get 1, 2, 3 and 5, corresponding to 8 + 7 + 6 + 4 = 25. There is and only one case.

Problem analysis

Eight people are divided into two teams, that is, a team of four people. We enumerate the possible rankings of each position in a quadruple for loop. As long as the sum of the four ranking scores is equal to n, the counter is + +. If the counter is 0, it means it is impossible to get and output NO.

#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<math.h>
#include<set>
#include<numeric>
#include<string>
#include<string.h>
#include<iterator>
#include<map>
#include<unordered_map>
#include<stack>
#include<list>
#include<queue>
#include<iomanip>

#define endl '\n';
typedef long long ll;
typedef pair<ll, ll>PII;
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;
}

Tags: C++ Algorithm Graph Theory

Posted by smarlowe on Thu, 12 May 2022 23:32:49 +0300