【Acwing】第55场周赛 题解

这道题直接采用简单的哈希表或者是用一个数组进行记录：记录a数组中的数字是否在b数组中出现即可。

#include 
using namespace std;

const int N = 100;

int b[N];
int a[N];

int main()
{
    int n, m;
    cin >> n >> m;
    for(int i = 0; i < n; i ++ ) cin >> a[i];
    for(int i = 0; i < m; i ++ ) 
    {
        int num; cin >> num;
        b[num] ++ ;
    }
    for(int i = 0; i < n; i ++ )
    {
        if(b[a[i]] != 0) cout << a[i] << ' ';
    }
    cout << endl;
    return 0;
}

首先看到这一题，有两种解法：

1.双指针（因为坐标是单调上升的，数组中存在单调性）

2.二分（同意具有单调性）

但是有几个注意事项：

1.存在边界情况（A中所有的坐标均>B中所有的坐标 或 与之相反），这种情况下需要我们在最开始和最后的位置增加两个哨兵结点

2.数据范围：1e9的数据相加减可能会爆int，需要使用long long 

3.刚开始存储点的坐标的数组的范围应该开到 2e5（两倍的范围）

#include 
#include 
using namespace std;

typedef long long LL;

const int N = 2e5 + 10, INF = 2e9;

int n, m;
LL p[N];
LL Garbage[N];
LL sum[N];
LL Residents[N];
LL cnt1, cnt2;

int main()
{
    cin >> n >> m;
    for(int i = 0; i < n + m; i ++ ) scanf("%lld", &p[i]);
    for(int i = 0; i < n + m; i ++ )
    {
        int op; scanf("%d", &op);
        if(op == 0) Residents[ ++ cnt2] = p[i];
        else Garbage[ ++ cnt1] = p[i];
    }
    
    // 设置哨兵结点
    Garbage[0] = -INF, Garbage[m + 1] = INF;
    
    for(int i = 1; i <= n; i ++ )
    {
        int l = 0, r = m + 1;
        while(l < r)
        {
            int mid = l + r >> 1;
            if(Garbage[mid] >= Residents[i]) r = mid;
            else l = mid + 1;
        }
        
        if((LL)Residents[i] - Garbage[r - 1] <= (LL)Garbage[r] - Residents[i]) sum[r - 1] ++ ;
        else sum[r] ++ ;
    }
    for(int i = 1; i <= m; i ++ ) cout << sum[i] << ' ';
    return 0;
}

二分核心代码的那一句采用库函数里面的二分进行调用

Garbage[0] = -INF, Garbage[m + 1] = INF;
    
    for(int i = 1; i <= n; i ++ )
    {
        int r = lower_bound(Garbage, Garbage + m + 2, Residents[i]) - Garbage;
        if((LL)Residents[i] - Garbage[r - 1] <= (LL)Garbage[r] - Residents[i]) sum[r - 1] ++ ;
        else sum[r] ++ ;
    }

#include 
#include 
using namespace std;

const int N = 2e5 + 10;

int n, m;
int p[N];
int Garbage[N];
int sum[N];
int Residents[N];
int cnt1, cnt2;

int dis(int x1, int x2)
{
    return abs(x1 - x2);
}

int main()
{
    cin >> n >> m;
    for(int i = 0; i < n + m; i ++ ) scanf("%d", &p[i]);
    for(int i = 0; i < n + m; i ++ )
    {
        int op; scanf("%d", &op);
        if(op == 0) Residents[cnt2 ++ ] = p[i];
        if(op == 1) Garbage[cnt1 ++ ] = p[i];
    }
    
    int t = 0;
    for(int i = 0; i < cnt2; i ++ )
    {
        if(t < cnt1 - 1)
        {
            while(dis(Garbage[t], Residents[i]) > dis(Garbage[t + 1], Residents[i]) && t < cnt1 - 1) t ++ ;
        }
        sum[t] ++ ;
    }
    for(int i = 0; i < cnt1; i ++ ) cout << sum[i] << ' ';
    return 0;
}

给定一个 nn 行 mm 列的方格矩阵。行坐标从上到下为 1∼n1∼n，列坐标从左到右为 1∼m1∼m。

其中的每个方格，要么是空格（用 . 表示），要么包含障碍物（用 * 表示）。

初始时，一个人位于第 rr 行第 cc 列的空格之中。

他可以沿上下左右四个方向进行移动，每次移动一格距离。

对于他的移动，有如下限制：

• 他不能进入到包含障碍物的方格中，也不能走出矩阵的边界。
• 在整个移动过程中，他向左移动的总次数不能超过 xx 次。
• 在整个移动过程中，他向右移动的总次数不能超过 yy 次。

请问，一共有多少个空格是此人可以抵达的？

注意，初始空格视为此人可达。

输入格式

第一行包含两个整数 n,mn,m。

第二行包含两个整数 r,cr,c。

第三行包含两个整数 x,yx,y。

接下来 nn 行，每行包含一个长度为 mm 的由 . 和 * 组成的字符串，用来描述方格矩阵。

输入保证第 rr 行第 cc 列的方格一定是空格。

输出格式

一个整数，表示可达空格数量。

数据范围

前三个测试点满足 1≤n,m≤51≤n,m≤5。
所有测试点满足 1≤n,m≤20001≤n,m≤2000，1≤r≤n1≤r≤n，1≤c≤m1≤c≤m，0≤x,y≤1090≤x,y≤109。

输入样例1：

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

输出样例1：

10

输入样例2：

4 4
2 2
0 1
....
..*.
....
....

输出样例2：

7

对于这道题，我们可以刚开始使用DP的思维来进行分析。

时间复杂度是O(N^4)

 需要进行如下优化：

将b放到f(..)里面的值里面去,这样可以将状态优化到三维

f(i, j, a) 表示往右走最少几步能到达，且满足 a <= x, f(i, j, a) <= y

但是这样还是会超时，我们还需要进一步挖掘题目里面隐含的关系，再优化一维：

从起点(r, c) 到达终点(i, j)，满足以下条件：

所以，此时f(i, j)表示往右最少的步数，存在以下关系：

所以此题是一个经典的 01最短路问题 - 双端队列BFS 

【搜索】—— 双端队列广搜_玄澈_的博客-CSDN博客

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

#define x first
#define y second

typedef pair PII;

const int N = 2010;

int n, m, sx, sy, X, Y;
int dist[N][N];
char g[N][N];
bool st[N][N]; // 判重

void bfs()
{
    memset(dist, 0x3f, sizeof dist);
    dist[sx][sy] = 0;
    deque q;
    q.push_back({sx, sy});
    
    int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
    while(q.size())
    {
        auto t = q.front();
        q.pop_front();
        if(st[t.x][t.y]) continue;
        st[t.x][t.y] = true;
        
        for(int i = 0; i < 4; i ++ )
        {
            int x = t.x + dx[i], y = t.y + dy[i];
            if(x < 0 || x >= n || y < 0 || y >= m || g[x][y] == '*') continue;
            int w = 0;
            if(i == 1) w = 1;
            if(dist[x][y] > dist[t.x][t.y] + w)
            {
                dist[x][y] = dist[t.x][t.y] + w;
                if(w) q.push_back({x, y});
                else q.push_front({x, y});
            }
        }
    }
}

int main()
{
    cin >> n >> m >> sx >> sy >> X >> Y;
    sx -- , sy -- ;
    for(int i = 0; i < n; i ++ ) scanf("%s", g[i]);
    
    bfs();
    
    int res = 0;
    for(int i = 0; i < n; i ++ )
        for(int j = 0; j < m; j ++ )
        {
            int b = dist[i][j];
            if(b <= Y &&  b - (j - sy) <= X) res ++ ;
        }
    
    cout << res << endl;
    return 0;
}