Painting Fence Posts (USACO Silver 2024 Open)

Painting Fence Posts (USACO Silver 2024 Open)

这个题就是需要生成一个所有柱子的顺序，使得柱子能够围成一个合法的篱笆。有了这个顺序之后，就计算出每个牛的起点和终点在哪段篱笆上，并计算出起点和终点从初始柱子的距离值，就可以计算顺时针走和逆时针走的距离，取其中较小那个，就是牛实际会走的路线。然后就得到牛的出发柱子和到达柱子，然后用差分的方法循环一遍，就可以算出每个柱子被碰了多少次。

下面我们看怎样生成所有柱子的顺序，在每行，行列用一个set存储所有柱子坐标。这时，因为同一个柱子上的两块篱笆一定要成90度，我们可以发现关键的规律是：

对于同一行/列上的柱子，我们需要间隔地加篱笆，就是在所有2i−12i-1和2i2i之间加篱笆。

这样就找到了一个简单的生成所以篱笆的办法（程序中connect()）。通过这个办法，我们可以得到每个柱子的两个邻居，然后DFS，就可以得到所有柱子的顺序，以及离初始柱子的距离。

以下程序中的一些细节：

  1. find(x,y)将牛的坐标转化成(pole,offset)对，就是从某柱子出发，按.nxt顺序遍历情况下的位置。
  2. dist(c1,c2,pass1)计算两头牛之前的距离，按以上遍历顺序，以及是否在过程中走过了1号pole。
  3. non_pole1_nxt()是关于1号柱子的特判，计算差分时，如果下一个柱子是1号柱，都不应该计算差分。例子：从1号柱之前篱笆段中间开始，在1号柱之后篱笆段中间结束，这时起始柱本来应该是1，但是因为pole1初始值（res）已经计入这个1，所以我们把st设为0。

程序实际的调试过程比较困难（我花了一天时间），主要是特殊情况比较多，而且好像没有简单的办法不需要特判。感觉这不是一道好题。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
#define f first
#define s second
 
// #define debug(x...) printf(x)
#define debug(x...) do { } while (0)
 
int n, p;
struct pole {
    int x, y;
    int nxt;       // next pole in the order
    int adj[2];    // 0: horizontal neighbor, 1: vertical neighbor
    ll dist;
};
 
pole ps[200005];
map<int, set<pi>> row, col;   // y -> {x, idx}
int delta[200005];
int ans[200005];
 
// connect all poles in the same row/column
void connect(map<int, set<pi>> &rc, int a) {
    for (auto &[x, ys]: rc) {
        for (auto i = ys.begin(); i != ys.end(); ) {
            auto j = next(i);
            ps[i->s].adj[a] = j->s;
            ps[j->s].adj[a] = i->s;
            i = next(j);
        }
    }
}
 
void dfs(int x, int e) {
    // printf("dist[%d] = %lld\n", x, ps[x].dist);
    for (int i = 0; i < 2; i++) {
        int y = ps[x].adj[i];
        if (y == e || e == -1 && i == 1) continue;  // traverse in one direction
        ps[x].nxt = y;
        ps[y].dist = ps[x].dist + abs(ps[x].x-ps[y].x) + abs(ps[x].y-ps[y].y);
        if (y == 1) {
            debug("perimeter = %lld\n", ps[y].dist);
            break;   // stop when back to pole 1
        }
        dfs(y, x);
    }
}
 
pi find(int x, int y) {
    auto &r = row[y];
    auto it = r.lower_bound({x, 0});
    if (it != r.end() && it->f == x) return {it->s, 0};  // exactly on a post
    if (it != r.end() && it != r.begin()) {
        int p1 = it->s, p2 = prev(it)->s;
        if (ps[p1].nxt == p2) return {p1, abs(x-ps[p1].x)};
        if (ps[p2].nxt == p1) return {p2, abs(x-ps[p2].x)};
    }
    auto &c = col[x];
    it = c.lower_bound({y, 0});
    if (it != c.end() && it->f == y) return {it->s, 0};
    if (it != c.end() && it != c.begin()) {
        int p1 = it->s, p2 = prev(it)->s;
        if (ps[p1].nxt == p2) return {p1, abs(y-ps[p1].y)};
        if (ps[p2].nxt == p1) return {p2, abs(y-ps[p2].y)};
    }
    return {0,0};
}
 
// return distance from c1 to c2, and whether pass pole 1
// c1: (pole, off)
ll dist(pi c1, pi c2, bool &pass1) {
    ll dist1 = c1.f == 1 ? c1.s : ps[c1.f].dist + c1.s;
    ll dist2 = c2.f == 1 ? c2.s : ps[c2.f].dist + c2.s;
    if (dist1 <= dist2) {
        pass1 = false;
        return dist2 - dist1;
    } else {
        pass1 = true;
        return dist2 + ps[1].dist - dist1;
    }
}
 
int main() {
    scanf("%d %d", &n, &p);
    for (int i = 1; i <= p; i++) {
        scanf("%d %d", &ps[i].x, &ps[i].y);
        row[ps[i].y].insert({ps[i].x, i});
        col[ps[i].x].insert({ps[i].y, i});
    }
    connect(row, 0);  // connect all poles in the same row
    connect(col, 1);  // connect all poles in the same column
    dfs(1, -1);       // calculate distance from pole 1
    long long perimeter = ps[1].dist;
 
    int res = 0;
    for (int i = 0; i < n; i++) {
        int x1, y1, x2, y2;
        scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
        pi c1 = find(x1, y1);   // convert (x,y) to (pole, off)
        pi c2 = find(x2, y2);
        debug("(%d, %d) -> (%d, %d), (%d, %d) = (%d, %d)\n", x1, y1, c1.f, c1.s, x2, y2, c2.f, c2.s);
        bool pass1 = false;
        long long d = dist(c1, c2, pass1);
        debug("d = %lld, pass1 = %d\n", d, pass1);
        int st, ed;
        auto non_pole1_nxt = [](int p) {  // special case for pole 1
            return ps[p].nxt == 1 ? 0 : ps[p].nxt;
        };
        if (d * 2 <= perimeter) {
            st = c1.s ? non_pole1_nxt(c1.f) : c1.f;
            ed = non_pole1_nxt(c2.f);
            res += pass1;           // initial sum
        } else {
            st = c2.s ? non_pole1_nxt(c2.f) : c2.f;
            ed = non_pole1_nxt(c1.f);
            res += !pass1;
        }
        debug("st = %d, ed = %d, pole1 = %d\n", st, ed, res);
        delta[st]++;
        delta[ed]--;
    }
    int i = 1;
    do {
        res += delta[i];
        debug("delta[%d] = %d\n", i, delta[i]);
        ans[i] = res;
        i = ps[i].nxt;
    } while (i != 1);
    for (int i = 1; i <= p; i++) {
        printf("%d\n", ans[i]);
    }
    return 0;
}