AcWing第55场周赛

这次周赛还是有一定难度的。第二道需要我们合理的处理边界或者设置哨兵。第三道则需要我们对动态规划和搜索的思想有一定的理解才能够分析出来。

给定一个长度为 n 的序列 a1,a2,…,an 和一个长度为 m 的序列 b1,b2,…,bm。

现在，我们希望找到一个序列 a 的子序列，使得该子序列满足：

子序列中的每一个元素都在序列 b 中出现过。
子序列的长度应尽可能长。
请你输出满足条件的最长子序列。

输入格式
第一行包含两个整数 n,m。

第二行包含 n 个整数 a1,a2,…,an。

第三行包含 m 个整数 b1,b2,…,bm。

输出格式
在一行中输出满足条件的最长子序列。

如果满足条件的最长子序列为空，则不输出任何内容或输出单个换行符均可。

数据范围
所有测试点满足 1≤n,m≤10，0≤ai,bi≤9。

输入样例1：
7 3
3 5 7 1 6 2 8
1 2 7
输出样例1：
7 1 2
输入样例2：
4 4
3 4 1 0
0 1 7 9
输出样例2：
1 0

本题求最长子序列，第一反应应该是子序列可以是不连续的。也很容易让人想到最长公共子序列问题，最长公共子序列问题需要两个序列中元素出现的先后顺序保持一致，而本题没有这个要求，只需要a中的元素在b中出现过就可以加入子序列了，也就是考察哈希。先遍历下b数组统计下出现的元素，然后遍历下a将b中出现过的元素输出即可。

#include 
#include 
#include 
using namespace std;
const int N = 15;
bool st[10];
int a[N];
int main(){
    int n,m,x;
    scanf("%d%d",&n,&m);
    for(int i = 0;i < n;i++) {
        scanf("%d",&a[i]);
    }
    for(int i = 0;i < m;i++) {
        scanf("%d",&x);
        st[x] = true;
    }
    for(int i = 0;i < n;i++){
        if(st[a[i]]) cout<

一条街道可以看作一个数轴。

街道上住着 n 个居民并设有 m 个垃圾桶，每个居民的住所或垃圾桶占据一个位置。

已知，这 n+m 个位置两两不同。

每个居民每天都会前往距离自己家最近的垃圾桶处倒垃圾。

如果这样的垃圾桶不唯一，则居民会优先选择前往位置坐标更小的垃圾桶处倒垃圾。

请你计算，对于每个垃圾桶，每天有多少居民在该垃圾桶处倒垃圾。

输入格式
第一行包含两个整数 n,m。

第二行包含 n+m 个整数 x1,x2,…,xn+m，表示所有居民住所以及垃圾桶的位置坐标。

第三行包含 n+m 个整数 t1,t2,…,tn+m，如果 ti=1，则表示第 i 个位置坐标处是垃圾桶，如果 ti=0，则表示第 i 个位置坐标处是居民住所。

输入保证，满足 ti=1 的 i 的数量为 m。

输出格式
不妨按照位置坐标从小到大的顺序，将 m 个垃圾桶编号 1∼m。

请你在一行中输出 m 个整数 a1,a2,…,am，其中 ai 表示每天在第 i 个垃圾桶处倒垃圾的居民数量。

数据范围
前三个测试点满足 1≤n,m≤5。
所有测试点满足 1≤n,m≤10⁵，1≤x19，0≤ti≤1。

输入样例1：
3 1
1 2 3 10
0 0 1 0
输出样例1：
3
输入样例2：
3 2
2 3 4 5 6
1 0 0 0 1
输出样例2：
2 1
输入样例3：
1 4
2 4 6 10 15
1 1 1 1 0
输出样例3：
0 0 0 1

本题抽象下就是一个数轴上有n + m个点，其中n个是居民，m个是垃圾桶，每个居民选择最近的垃圾桶扔垃圾，如果左右垃圾桶一样近就选择坐标小的垃圾桶扔垃圾，最后输出每个垃圾桶里面有多少个居民扔了垃圾。
一般情况下，只需要每个居民向左向右查找下最近的垃圾桶的坐标，然后选择最近的那个扔垃圾就行了。这题编码还花了我不少时间，主要是输入把居民和垃圾桶放一起了，周赛时犹豫要不要把他们的坐标分开存放，如果题目数据范围不是10w而是1w，那可以果断暴力秒掉这题，遍历居民和垃圾桶混合的数组，如果是居民，向左遍历找到最近的垃圾桶，向右遍历找到最近的垃圾桶，然后取两个中最近的垃圾桶扔垃圾，时间复杂度是平方级别的。
这题输入的居民和垃圾桶的坐标是有序的，题目将这个条件放在数据范围里，周赛时我就没看见这个条件，于是只能拆成两个数组，分别存储居民和垃圾桶的坐标，然后对垃圾桶坐标进行排序，当时以为是无序的，想着再对居民坐标排序然后用线性的算法求解就没有意义了，因为排序已经是nlogn的时间了，于是只对垃圾桶坐标排了序，然后对每个居民坐标在垃圾桶数组里二分答案，当然最后也ac了。
既然题目已经给定了输入的坐标是有序的，一个解法就是不拆成两个数组，直接优化下暴力算法，遍历下居民和垃圾桶的混合数组，然后用两个数组统计下离每个居民最近的左边和右边的垃圾桶坐标，再遍历下数组就可以统计每个垃圾桶里面的垃圾数量了。这种解法也是线性的，但是既然为了节省时间都使用了两个辅助数组，而且同样需要考虑边界情况，还不如一开始就拆成两个数组。拆成两个数组的话可以分别处理居民和垃圾桶，更加的方便。拆成两个数组的第一个解法就是上面说的二分答案，混合数组有序，我们拆成的两个数组也是有序的，就不需要排序了。
现在拆成的a数组存储着居民坐标，b数组存储着垃圾桶坐标，要做的就是对a中每个元素在b中找到离它最近的坐标。对于a中的某个元素x，可以对b数组二分查找不小于x的第一个位置，最后离x最近的垃圾桶坐标要么就是二分查找到的位置l，要么就是l - 1.如果l是0，没有前一个位置，特判下即可，如果l是最后一个位置，说明也可能所有垃圾桶都在x的左边，此时l依旧是离x最近的，无需处理边界。本题的二分查找，查找不小于或者不大于x的位置均可，但是需要提前设定好要查找的目标是什么，如果先写好二分，再根据代码判断查找到的元素是什么，就很容易乱，比如上面说的查找不小于x的第一个位置也可能后面找不到就结束二分了，找到的只是数组的最后一个元素，是不满足查找的目标的。
当然更高效的就是双指针解法。对于a中第k个居民，如果在b中离它最近的垃圾桶的下标是j，那么k以后的居民离他们最近的垃圾桶的坐标一定不会在j的左边，这点很容易理解。因此我们可以使用两个指针i，j分别指向a和b的首元素，当j指向的元素小于等于i指向的元素时，离a[i]最近的垃圾桶就在b[j]和b[j-1]之间，当然需要特判下j = 0的情况，求出离第i个居民最近的垃圾桶位置后i就可以右移，继续求下一个；如果i指向的元素大于j指向的元素，j右移至下一个垃圾桶位置即可。特殊情况是b中没有大于等于a中某个元素的值了，此时要么在循环结束后，将剩下的a中的元素倒垃圾的地点都设置在最后一个垃圾桶处，要么设置在b数组末尾设置一个坐标很大的哨兵节点，使其大于所有居民的坐标，这样一来所有居民在遍历时最远都会停在b的哨兵节点处，同时离b的最后一个元素更近，实现了给a中所有元素选择最近的垃圾桶的目的。

二分解法

#include 
#include 
#include 
using namespace std;
const int N = 100005;
int a[2*N];
int p[N],q[N],res[N];
int main(){
    int n,m,x;
    scanf("%d%d",&n,&m);
    for(int i = 0;i < n + m;i++) {
        scanf("%d",&a[i]);
    }
    int x1 = 0,x2 = 0;
    for(int i = 0;i < n + m;i++) {
        scanf("%d",&x);
        if(x)   q[x2++] = a[i];
        else    p[x1++] = a[i];
    }
    for(int i = 0;i < n;i++){
        int t = p[i];
        int l = 0,r = m - 1;
        while(l < r){
            int mid = l + r >> 1;
            if(t > q[mid])  l = mid + 1;
            else    r = mid;
        }
        if(l >= 1 && abs(t - q[l]) >= abs(t - q[l-1]))    res[l-1]++;
        else    res[l]++;
    }
    for(int i = 0;i < m;i++)    printf("%d ",res[i]);
    return 0;
}

双指针解法

#include 
#include 
#include 
using namespace std;
const int N = 100005;
int a[2*N];
int p[N],q[N],res[N];
int main(){
    int n,m,x;
    scanf("%d%d",&n,&m);
    for(int i = 0;i < n + m;i++) {
        scanf("%d",&a[i]);
    }
    int x1 = 0,x2 = 0;
    for(int i = 0;i < n + m;i++) {
        scanf("%d",&x);
        if(x)   q[x2++] = a[i];
        else    p[x1++] = a[i];
    }
    int i = 0,j = 0;
    q[m] = 2e9;
    while(i < n && j <= m){
        if(q[j] >= p[i]){
            if(!j || q[j] - p[i] < p[i] - q[j-1])   res[j]++;
            else    res[j-1]++;
            i++;
        }
        else    j++;
    }
    for(int i = 0;i < m;i++)    printf("%d ",res[i]);
    return 0;
}

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

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

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

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

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

他不能进入到包含障碍物的方格中，也不能走出矩阵的边界。
在整个移动过程中，他向左移动的总次数不能超过 x 次。
在整个移动过程中，他向右移动的总次数不能超过 y 次。
请问，一共有多少个空格是此人可以抵达的？

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

输入格式
第一行包含两个整数 n,m。

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

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

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

输入保证第 r 行第 c 列的方格一定是空格。

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

数据范围
前三个测试点满足 1≤n,m≤5。
所有测试点满足 1≤n,m≤2000，1≤r≤n，1≤c≤m，0≤x,y≤10⁹。

输入样例1：
4 5
3 2
1 2
…
.*.
…
…
输出样例1：
10
输入样例2：
4 4
2 2
0 1
…
….
…
…
输出样例2：
7

借助本题总结下BFS的应用。
BFS有两个经典应用，Flood fill问题和最短步数模型。本题相当于把这两个应用结合到一起了，一般flood fill问题需要我们求连通块的数量，或者求从起点出发能够到达的方格数量。最短步数模型一般需要我们求从初始状态到最终状态需要的最少转移步数，相当于在平面上用动态规划的思想进行状态转移。
flood fill问题比较简单，只要求对地形图进行遍历，宽搜和深搜都可以解决，但是最短步数模型因为涉及到动态规划的思想，往往可以出较难的应用。一类应用就是求边权为1的最短路问题，经典应用是走迷宫，求从起点走到终点需要的最短步数，我们只需要先遍历离起点步数是1的点，再遍历离起点步数是2的点，依次类推，直到遍历到终点，就找到了起点到终点的最短步数。另一类应用是对步数进行限制，求能到达的位置，比如从起点出发，最多走k步能够到达的坐标。这两种应用的限制条件都是步数最少，状态表示一般是三维的，比如(x,y,d)表示从起点走到（x,y）消耗的步数是d的状态，步数不同代表的状态也不同。比如（1,1，1）和（1,1,2）尽管都是到了（1,1）的状态，但是步数不同代表的状态也不同。由于BFS求解的问题一般一个坐标只会入队一次，所以我们不太关注第三维步数，将第三维也加入队列也只是为了出队时方便统计相邻格子的步数。也可以将步数独立处理，用一个d数组存储离起点最小的距离，这样入队的坐标都是最短路径下的坐标，就不需要考虑其它状态了。
本题要求从起点出发，向左走不超过x步，向右走不超过y步能够到达的空格数。一般最短步数模型我们只需要求最短的总的移动步数，不顾及方向，BFS队列中队头元素永远是队列里离起点步数最小的坐标。而本题的限制条件有x和y，这就很难用常规的BFS解决了，如果本题只给向右的步数施加限制了，要求向右走不能超过y步，那么向左走，向上和向下走消耗的步数都是0，只有向右走消耗的步数是1，求边权只有0和1的最短路问题就可以使用双端队列BFS解决了，遇见边权为0的状态放到队头，遇见状态为1的状态放到队尾。此时队头元素向右走的步数一定是队列里最少的，不论是最短步数还是最短向右步数，需要的最优化的变量只有一个，而本题有两个需要最小化的变量。
有左右步数限制，上下方向边权是0，自然可以加入到队头，而向左消耗了向左移动的步数，向右消耗了向右移动的步数，这两个方向消耗的代价就没法进行比较了，如果将其视为一致，那么到达一个坐标时消耗的左右移动步数分别是(1,2)和(2,1)时的优先级同样无法比较，因为二者各有一维的代价比较小，能够转移到的位置也不一样。
对于有两个限制条件的最短路模型，需要考虑这两个限制条件有没有线性关系，比如对于本题而言，初始坐标是(r,c)，某一时刻走到（a，b），能够到达（a，b）的路径有很多条，上下移动的步数和左右移动的步数都不是固定的，由于障碍物的存在，可能从起点先向左走了很多步，然后向上走，再向右走了很多步，最后才到的（a，b），但是有一点是不变的，向左走时y坐标减少了1，向右走时y坐标增加了1，而起点到终点的y坐标之差一定等于左右走的次数之差，即b - c = r - l，l和r表示向左和向右走的步数。起点和终点固定，如果向右走的步数最少，则向左走的步数也是最少的，这意味着走到某个坐标上，只要我们保证向右移动的次数最少，那么向左移动的次数一定也是最少的，这样一来需要最小化的变量就只有一个了。原问题就转化为了前面说的双端队列BFS问题，只在向右走的时候增加步长。
对于BFS而言，我们设置标志数组表示某个状态是否已经入队，如果已经入队，就不再重复入队，这是因为我们能够保证最先入队的元素的状态步数一定是最小的。而双端队列BFS某种意义上属于Dijkstra的范畴了，也就是基于优先级的搜索PFS的一种，此时某种状态入队时是不能保证当时的步数是最小的，需要后续入队的状态不断的松弛来更新最短步数，所以标志数组不能表示是否已经入队了，同一个坐标的状态有多个，BFS能够保证最先入队的状态步数是最小的才可以不让其它相同坐标的状态入队，但是PFS只有元素出队了才能保证此时该坐标的状态步数是最小的，也就是说一个坐标加上一个步数的状态入队之后，还可能有相同坐标加上更小步数的状态再次入队，在双端队列BFS里就表现在后入队但是放在了队头位置。概括下就是BFS的标志数组在入队时置为true是入队时最短步数已经确定了，而其他的PFS需要出队时最短步数才能确定，所以出队时才能将标志数组置为true。
基于上面的分析，我们在双端队列BFS时还是将坐标加入队列，用d数组存储向右移动的次数，用st[a][b]表示该坐标的状态是否已经出队，如果已经出队，就不再入队该坐标了。这样相同坐标可能会入队多次，也自然会出队多次，我们统计方格数时候只能在st数组还是false的时候进行统计，否则会重复统计。另一种方案是让每个坐标只入队一次，但是遇见可以松弛周围步数的时机继续松弛，这样一来即使某个坐标入队时步数不是最短的，但是出队时已经被没有入队的状态松弛了步数，取得的依旧是最短的步数。

坐标入队多次

#include 
#include 
#include 
#include 
#include 
using namespace std;
const int N = 2005;
char g[N][N];
int d[N][N];
bool st[N][N];
deque > q;
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
int main(){
    int n,m,r,c,x,y;
    scanf("%d%d%d%d%d%d",&n,&m,&r,&c,&x,&y);
    scanf("%d%d",&r,&c);
    for(int i = 0;i < n;i++) cin>>g[i];
    r--,c--;
    int res = 0;
    if(g[r][c] == '.'){
        q.push_back({r,c});
        memset(d,0x3f,sizeof d);//0x3f恰好比1e9大点
        d[r][c] = 0;
        while(q.size()){
            auto u = q.front();
            q.pop_front();
            if(!st[u.first][u.second])  res++;//可能重复出队
            st[u.first][u.second] = true;
            for(int i = 0;i < 4;i++){
                int a = u.first + dx[i],b = u.second + dy[i];
                if(a>=0&&a=0&&b y || dis - b + c > x || dis >= d[a][b]) continue;
                    if(i)   q.push_front({a,b});
                    else    q.push_back({a,b});
                    d[a][b] = dis;
                }
            }
        }
    }
    cout< 
坐标只入队一次
 
#include 
#include 
#include 
#include 
#include 
using namespace std;
const int N = 2005;
char g[N][N];
int d[N][N];
bool st[N][N];
deque > q;
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
int main(){
    int n,m,r,c,x,y;
    scanf("%d%d%d%d%d%d",&n,&m,&r,&c,&x,&y);
    scanf("%d%d",&r,&c);
    for(int i = 0;i < n;i++) cin>>g[i];
    r--,c--;
    int res = 0;
    if(g[r][c] == '.'){
        q.push_back({r,c});
        st[r][c] = true;
        memset(d,0x3f,sizeof d);
        d[r][c] = 0;
        while(q.size()){
            auto u = q.front();
            q.pop_front();
            res++;
            for(int i = 0;i < 4;i++){
                int a = u.first + dx[i],b = u.second + dy[i];
                if(a>=0&&a=0&&b y || dis - b + c > x || st[a][b]) continue;
                    if(i)   q.push_front({a,b});
                    else    q.push_back({a,b});
                    st[a][b] = true;
                }
            }
        }
    }
    cout<