Acwing - game 55 of the week

AcWing—— The first 55 Weekly match

competition - AcWing

4479. The longest subsequence - AcWing Question bank

Given a length of n Sequence a1,a2,…,an And a length of m Sequence b1,b2,…,bm.

Now? , We want to find a sequence a The subsequence , Make the subsequence satisfy ：

Every element in the subsequence is in the sequence b There has been .
The length of the subsequence should be as long as possible .
Please output the longest subsequence that meets the conditions .

Input format

The first line contains two integers n,m.

The second line contains n It's an integer a1,a2,…,an.

The third line contains m It's an integer b1,b2,…,bm.

Output format

Output the longest subsequence satisfying the condition in one line .

If the longest subsequence satisfying the condition is null , You can output nothing or a single line break .

Data range

All test points meet 1≤n,m≤10,0≤ai,bi≤9.

sample input 1：

7 3
3 5 7 1 6 2 8
1 2 7

sample output 1：

7 1 2

Problem analysis

The title requires the output of “ Sequence ”, Go straight through a Array , If a[i] stay b[i] Once it appears, just output this element .

AC Code

#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'
#define int ll
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll>PII;
const int N = 2e5 + 50;

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<int>a(n), b(m);
    unordered_map<int, int>mymap;
    for (int i = 0; i < n; i++)cin >> a[i];
    for (int i = 0; i < m; i++)
    {
        cin >> b[i];
        mymap[b[i]] = 1;
    }
    for (int i = 0; i < n; i++)
    {
        if (mymap[a[i]])cout << a[i] << " ";
    }
    return 0;
}

4480. take out the trash - AcWing Question bank

A street can be regarded as a number axis .

On the street lived n Residents with m A trash can , Each resident's residence or trash can occupies a location .

It is known that , this n+m The two positions are different .

Every resident will go to the nearest garbage can to his home every day to take out the garbage .

If such a trash can is not unique , Then the residents will give priority to go to the garbage can with smaller location coordinates to dump garbage .

Please calculate , For each trash can , How many residents take out garbage at the garbage can every day .

Input format

The first line contains two integers n,m.

The second line contains n+m It's an integer x1,x2,…,xn+m, Indicates the location coordinates of all residents' residences and garbage cans .

The third line contains n+m It's an integer t1,t2,…,tn+m, If ti=1, It means No i At the coordinates of the first position is the garbage can , If ti=0, It means No i At the coordinates of three positions is the residence of the residents .

Input guarantee , Satisfy ti=1 Of i The quantity of is m.

Output format

You might as well follow the order of position coordinates from small to large , take m Bin number 1∼m.

Please output in one line m It's an integer a1,a2,…,am, among ai Means every day on the i The number of residents taking out garbage at the garbage cans .

Data range

The first three test points meet 1≤n,m≤5.
All test points meet 1≤n,m≤10^{5,1≤x1<x2<…<xn+m≤10}9,0≤ti≤1.

sample input 1：

3 1
1 2 3 10
0 0 1 0

sample output 1：

3

sample input 2：

1 4
2 4 6 10 15
1 1 1 1 0

sample output 2：

0 0 0 1

Problem analysis

Sliding window method .

First put all the garbage cans into an array ans in , If there's only one trash can , Direct output n The value of the can , Because all the garbage can only be thrown there .

We use double pointers l、r To point to the location of the trash can , Traverse all households , If the current resident's position is between the positions pointed by our double pointer , Then we can judge by calculation that this resident is going to l Throw it well or r good （ If equal , Also go to l throw ）, And write it down , When the location of residents is larger than ours r The pointer , Then move the window to the right （l Point to the original r,r Go down one , If r It's the last trash can , Just move the left pointer ）, Because if the household location is greater than r 了 , So relative to l Distance of , The resident must have arrived r The distance between them is smaller . Finally, output the quantity of all records .

AC Code

#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'
#define int ll
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll>PII;
const int N = 2e5 + 50;

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<int>a(n + m), b(m + n), ans;
    unordered_map<int, int>mymap,cnt;
    if (m == 1)
    {
        cout << n << endl;
        return 0;
    }
    for (int i = 0; i < n+m; i++)cin >> a[i];
    for (int i = 0; i < n+m; i++)
    {
        cin >> b[i];
        if (b[i] == 1)ans.push_back(a[i]), mymap[a[i]] = 1;
    }
    int l = 0, r = 1;
    for (int i = 0; i < n+m; i++)
    {
        if (a[i] > ans[r])
        {
            l = r;
            if (r + 1 < m)r++;
        }
        if (mymap[a[i]] == 0)
        {
            if (abs(a[i] - ans[l]) <= abs(a[i] - ans[r]))
            {
                cnt[ans[l]]++;
            }
            else
            {
                cnt[ans[r]]++;
            }
        }
    }
    for (int i = 0; i < m; i++)cout << cnt[ans[i]] << " ";
    
    return 0;
}

4481. Grid exploration - AcWing Question bank

Given a n That's ok m The grid matrix of columns . The row coordinates from top to bottom are 1∼n, The column coordinates from left to right are 1∼m.

Each of these squares , Or a space （ use . Express ）, Or it contains obstacles （ use * Express ）.

At the beginning , One person is in the r Xing di c In the space of the column .

He can move up, down, left and right , Move one space at a time .

For his movement , There are the following restrictions ：

He cannot enter a square containing obstacles , Nor can it go beyond the bounds of the matrix .
Throughout the movement , The total number of times he moves to the left cannot exceed x Time .
Throughout the movement , The total number of times he moves to the right cannot exceed y Time .
Excuse me, , How many spaces can this person reach ？

Be careful , The initial space is considered as the person can reach .

Input format

The first line contains two integers n,m.

The second line contains two integers r,c.

The third line contains two integers x,y.

Next n That's ok , Each line contains a length of m By . and * Composed string , Used to describe a square matrix .

Input guarantee No r Xing di c The box of the column must be a space .

Output format

An integer , Indicates the number of reachable spaces .

Data range

The first three test points meet 1≤n,m≤5.
All test points meet 1≤n,m≤2000,1≤r≤n,1≤c≤m,0≤x,y≤10^9.

sample input :

4 5
3 2
1 2
.....
.***.
...**
*....

sample output ：

10

Problem analysis

The maze problem , But here you need to record how many steps you have taken to the left or right .

The queue should make its own custom data type , To be able to store four variables ：{ Abscissa , Ordinate , The number of times you have left , The number of times you have walked to the right }, Then there is the standard maze , It's just that the corresponding variables are +1, If the number is greater than the limit , Then you can't get to this level .

When we get to the first space, we have to make two marks , One is to judge whether this grid has passed before , If not, mark it , And counter ++; The other is to record that you have walked left or right several times when you came to this grid , If you want to go further , Then you must walk left and right less often , If you reach this grid again , If you walk left and right more than we recorded before, skip , If less than, replace the mark , And join the team at this point .

AC Code

#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'
#define int ll
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll>PII;
const int N = 2e5 + 50;
PII cnt[2050][2050];
int mymap[2050][2050];
int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 };

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n, m, x, y, a, b, res = 1;
    cin >> n >> m >> x >> y >> a >> b;
    vector<string>v(n);
    for (int i = 0; i < n; i++)
        cin >> v[i];
    queue<pair<pair<int, int>, pair<int, int>>>que;

    que.push({ {x - 1,y - 1} ,{0,0} });
    mymap[x - 1][y - 1] = 1;
    while (!que.empty())
    {
        int len = que.size();
        for (int i = 0; i < len; i++)
        {
            pair<pair<int, int>, pair<int, int>> t = que.front();
            que.pop();
            int l = t.second.first, r = t.second.second;
            for (int j = 0; j < 4; j++)
            {
                int c = l + (j == 3), d = r + (j == 1);
                if (c > a || d > b)continue;
                int x1 = t.first.first + dx[j], y1 = t.first.second + dy[j];
                if (x1 >= 0 && x1 < n && y1 >= 0 && y1 < m && v[x1][y1] == '.')
                {
                    if (mymap[x1][y1] && cnt[x1][y1].first <= c && cnt[x1][y1].second <= d)continue;
                    if (mymap[x1][y1] == 0)
                    {
                        mymap[x1][y1] = 1;
                        res++;
                    }
                    cnt[x1][y1] = { c,d };
                    que.push({ {x1,y1},{c,d} });
                }

            }
        }
    }


    cout << res << endl;

    return 0;
}