第八次训练课总结

· · 个人记录

P1696 [USACO18JAN] Blocked Billboard II B

这是一个二维平面上的矩形覆盖问题，我们可以使用网格标记法来计算需要覆盖的最小矩形面积。

我们先看数据范围，坐标是从-1000到+1000，那么便于存储我们可以把每一个坐标都+1000，这样就可以很好的存储和计算了，但是要注意，我们的数据范围就要扩大到2000了。

我们可以首先将割草机广告牌覆盖的网格标记为 1（表示需要被覆盖）。 然后将牛饲料广告牌覆盖的网格重新标记为 0（表示这些部分已被遮挡，不需要覆盖）。

标记以后我们就找到剩下的割草机广告牌的最大/最小的y坐标，以及最大/最小的x坐标，然后

(mx - nx + 1) * (my - ny + 1)

就求出了这块防水布的面积了。

别急，我知道你还不理解为什么是这样，那我们看个图就知道了 我们的长就是最大的x坐标-最小的x坐标，宽就是最大的y坐标-最小的y坐标，而题目里是按格点来算的长度，而我们算的是坐标之间的长度，将一个点转化成一个格点我们发现坐标x从1到3中间只有2个格子，因此我们要+1才能算出正确长度。

那么代码

#include<bits/stdc++.h>
using namespace std;
bool vis[2010][2010]; 
int main(){
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    a += 1000, b += 1000, c += 1000, d += 1000;//方便计算
    for(int i = a; i < c; i++){
        for(int j = b; j < d; j++){
            vis[i][j] = 1;
        }
    }
    int e, f, g, h;
    cin >> e >> f >> g >> h;
    e += 1000, f += 1000, g += 1000, h += 1000;
    for(int i = e; i < g; i++){
        for(int j = f; j < h; j++){
            vis[i][j] = 0;
        }
    }
    int mx = -1e9, my = -1e9, nx = 1e9, ny = 1e9;
    for(int i = 0; i <= 2000; i++){
        for(int j = 0; j <= 2000; j++){
            if(vis[i][j]){
                mx = max(mx, i);
                my = max(my, j);
                nx = min(nx, i);
                ny = min(ny, j);
            }
        }
    }
    if(mx != -1e9)
        cout << abs(mx - nx + 1) * abs(my - ny + 1);//计算面积
    else//如果我全都被覆盖了
        cout << 0;
}

P6207 [USACO06OCT] Cows on Skates G

这道题其实就是一个简单的四联通bfs，唯一的难点在于如何储存路径，但仔细一想，如果我走出这一步，并且这一步可以走，那我的上一步不就确定是这个一整个路径的一份子了吗？然后我把上一步的x和y坐标记录一下就可以了。

#include<bits/stdc++.h>
using namespace std;
char a[120][120];
int r, c;
struct node{
    int x, y;
};
int idx = 0;
int vis[120][120];
int d[4][2] = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};
node pre[120][120];
node ans[120 * 120];
void bfs(){
    queue<node>q;
    q.push({1, 1});
    for(int i = 1; i <= r; i++){
        for(int j = 1; j <= c; j++){
            vis[i][j] = -1;//初始化
        }
    }
    vis[1][1] = false;
    while(q.size()){
        node t = q.front();
        q.pop();
        if(t.x == r && t.y == c){
            return;
        }
        for(int i = 0; i < 4; i++){
            int dx = t.x + d[i][0], dy = t.y + d[i][1];
            if(dx < 1 || dx > r || dy < 1 || dy > c){//判断越界
                continue;
            } 
            if(vis[dx][dy] != -1){//判断走没走过
                continue;
            }
            if(a[dx][dy] == '*'){//判断是否是障碍
                continue;
            }
            q.push({dx, dy});
            vis[dx][dy] = vis[t.x][t.y] + 1;
            pre[dx][dy] = t;//记录上一步
        } 
    }
}
int main(){
    cin >> r >> c;
    for(int i = 1; i <= r; i++){
        for(int j = 1; j <= c;j++){
            cin >> a[i][j];
        }
    }
    bfs();
    int x = r, y = c;
    //反推路径
    while(x != 0 && y != 0){
        ans[++idx] = {x, y};
        int nx = pre[x][y].x, ny = pre[x][y].y;
        x = nx, y = ny;
    }
    //反着输出
    for(int i = idx; i >= 1; i--){
        cout << ans[i].x << " " << ans[i].y << endl;
    }
    return 0;
}

P8160 [JOI 2022 Final] 星际蛋糕 / Intercastellar

我们首先读取蛋糕初始分段信息，对于每个长度，不断除以 2 直到变为奇数，记录最终奇数长度和该长度对应的段数（初始段数为 1，每次除以 2 时段数翻倍）。为什么可以这么做呢？因为我们知道，一个数一直/2，最终的出的偶数个奇数一定都一样，所以我们直接放在一起即可，然后要记录这个奇数总共有多少个，方便后面我们查找第Xj段的长度为多少。

然后计算前缀和数组，用于快速定位查询位置所在的段。对于每个查询，使用二分查找在前缀和数组中找到第一个大于等于查询位置的索引，该索引对应的奇数长度即为所求答案。

如果你不理解，那么看了代码肯定就理解了

#include<bits/stdc++.h>
using namespace std;
struct node{
    long long x, cnt;
};
node a[201000];
long long sum[2000010];
int main(){
    long long n, k;
    cin >> n;
    for(int i = 1; i <= n; i++){
        int x;
        cin >> x;
        int cnt = 1;
        while(x % 2 == 0){//一直/2知道分成了cnt个这样的奇数
            x /= 2;
            cnt *= 2;//cnt计数
        }
        a[i].x = x, a[i].cnt = cnt;
    }
    //计算前缀和
    sum[1] = a[1].cnt;
    for(int i = 2; i <= n; i++){
        sum[i] = sum[i - 1] + a[i].cnt;
    }
    //多组访问
    int q;
    cin >> q;
    while(q--){
        cin >> k;
        /*前缀和数组 sum 的含义
假设初始蛋糕被分成 n 段，每段长度经过处理后变为奇数 a[i].x，且该段会被切分为 a[i].cnt 个最终段。sum 数组记录这些段数的前缀和：
sum[i] 表示前 i 个初始段处理后的总段数。
例如，sum[3] = a[1].cnt + a[2].cnt + a[3].cnt。
查询位置 k 的定位
当查询第 k 段的长度时，需要找到 k 落在哪个初始段处理后的区间内。然后输出这个区间的奇数*/
        int pos = lower_bound(sum + 1, sum + n + 1, k) - sum;
        cout << a[pos].x << endl;
    }
    return 0;
}