2017-10-12校训练题题解

T1

傻逼题。 ans=n−出现最多的数的出现次数 。然而我在考试的时候去写dp去了还写了个单调队列优化，怕不是中了bzoj1044的毒。

T2

离散化。田地太大，面积太大，直接搜是不可能的，但是 N 最大只有 1000 ，那么可以考虑把 x 坐标 y 坐标离散化，点最多也就上千，这里有一个技巧，就是离散化后的点扩大两倍，为了后面方便 bfs ，所以我把最外围扩了一圈，那么离散的坐标就是 1,3,5.....2∗k+1 。 0 和 2∗k+2 是外围。我把整个图压缩成了一维，比如（x,y）对应的下标就是 x∗列宽+y ,接下来就是 bfs ，先把走过的地方全部标记为 1 ，其他地方标记为 −1 ，此时我只需要把 (0,0) 加入队列搜即可（你可以仔细想一下为什么），把能够走的地方全部标记为 0 。但是要注意一点，因为我是扩大了两倍，如果当前搜的方向是上或下，且这个点的 y 坐标是偶数（不是边界），需要判断一下离散化的左右两个数的差值是否为 1 ，是的话是不能走的（被堵死了），因为这个点本就是虚拟的点。如果当前搜的方向是左或右， x 坐标是偶数（不是边界）同理。最后就是计算总面积，如果这个点不是标记为 0 （不能被害虫入侵），则判断它的 x , y 坐标的奇偶性， x , y 同时为奇数则加 1 ， x 为偶数，则加 x 轴方向的距离 −1 ， y 为偶数，则加y轴方向的距离 −1 ，都是偶数则加两个方向的距离 −1 的乘积。（注意会爆 int ）

T3

首先 bfs ，把每个店到它最近的敌人的距离跑出来，然后二分 + bfs check 。
附上T3代码。

#include<bits/stdc++.h>
using namespace std;

#define rep(i, a, b) for (int i = a; i <= b; i++)
#define N 1001
#define INF 2100000000
const int dr[] = { 0, 1, 0, -1 };
const int dc[] = { 1, 0, -1, 0 };

inline int read() {
    int x = 0, flag = 1; char ch = getchar();
    while (ch > '9' || ch < '0') { if (ch == '-') flag = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * flag;
}
inline void write(int x) { if (x >= 10) write(x / 10); putchar(x % 10 + '0'); }

int n, x, y;
int xs, ys, xt, yt;
struct enemy { int r, c, dis; };
queue<enemy> q;
bool vis[N][N];
int dis[N][N], d[N][N];

void bfs() {
    while (q.size()) {
        enemy u = q.front(); q.pop();
        if (vis[u.r][u.c]) continue;
        vis[u.r][u.c] = 1;
        dis[u.r][u.c] = u.dis;
        rep(i, 0, 3) {
            int nr = u.r + dr[i], nc = u.c + dc[i];
            if (nr >= 0 && nr < x && nc >= 0 && nc < y)
                q.push(enemy{ nr, nc, u.dis + 1 });
        }
    }
}

bool check(int k) {
    q.push(enemy{ xs, ys, 0 });
    while (q.size()) {
        enemy u = q.front(); q.pop();
        if (vis[u.r][u.c]) continue;
        vis[u.r][u.c] = 1;
        d[u.r][u.c] = u.dis;
        rep(i, 0, 3) {
            int nr = u.r + dr[i], nc = u.c + dc[i];
            if (nr >= 0 && nr < x && nc >= 0 && nc < y && dis[nr][nc] >= k)
                q.push(enemy{ nr, nc, u.dis + 1 });
        }
    }
    return d[xt][yt] != INF;
}

int main() {
    scanf("%d%d%d%d%d%d%d", &n, &x, &y, &xs, &ys, &xt, &yt);
    rep(i, 1, n) q.push(enemy{ read(), read(), 0 });
    bfs();
    int l = 0, r = min(dis[xs][ys], dis[xt][yt]);
    int ans1, ans2;
    while (l <= r) {
        memset(vis, 0, sizeof vis);
        rep(i, 0, x) rep(j, 0, y) d[i][j] = INF;
        int mid = l + r >> 1;
        if (check(mid)) ans1 = mid, l = mid + 1, ans2 = d[xt][yt];
        else r = mid - 1;
    }
    printf("%d %d", ans1, ans2);
    return 0;
}