XCPC Notes

Appearance

发布时间：2023-10-12

前置知识(曼哈顿距离和切比雪夫距离) ​

曼哈顿距离： ∣x1−x2∣+∣y1−y2∣|x_1-x_2|+|y_1-y_2|
切比雪夫距离： max(∣x1−x2∣,∣y1−y2∣)max(|x_1-x_2|,|y_1-y_2|)
转换坐标：
曼哈顿距离 →\to 切比雪夫距离：
(x,y)→(x+y,x−y)(x,y) \to (x+y,x-y)
切比雪夫距离 →\to 曼哈顿距离： (x,y)→(x+y2,x−y2)(x,y) \to (\frac{x+y}{2},\frac{x-y}{2})
原坐标的曼哈顿(切尔雪夫)距离=新坐标的切尔雪夫(曼哈顿)距离

例题 ​

洛谷P3964松鼠聚会 ​

题意：
给出多个坐标，选择一个坐标，使所有点到该坐标的切尔雪夫距离之和最小
思路： 切尔雪夫距离转换为曼哈顿距离求最小，转换坐标时先不除以2以免出现小数，最后答案再除以2
对于选定的一个点 (xj,yj)(x_j,y_j) ,求 ∑i=1n(∣xi−xj∣+∣yi−yj∣)\sum_{i=1}^n(|x_i-x_j|+|y_i-y_j|),可以用前缀和解决，以x为例，对于x坐标从小到大排序：
∑i=1n∣xi−xj∣=∑i=1j(xj−xi)+∑i=j+1n(xi−xj)=j⋅xj−∑i=1jxi+∑j+1n−(n−j)⋅xj=(2j−n)⋅xj+∑i=1nxi−2⋅∑i=1jxi\sum_{i=1}^n|x_i-x_j|=\sum_{i=1}^j(x_j-x_i)+\sum_{i=j+1}^n(x_i-x_j)=j \cdot x_j-\sum_{i=1}^jx_i+\sum_{j+1}^n-(n-j) \cdot x_j=(2j-n) \cdot x_j+\sum_{i=1}^nx_i-2 \cdot \sum_{i=1}^jx_i
y同理，然后把算好的值映射回原来的坐标，全部遍历求min即可

cpp
struct node{
    ll pos,val;
    bool operator<(const node&tmp)const{
        return val<tmp.val;
    }
};
struct Z{
    ll posx,posy;
};
void solve() {
    ll n;
    cin>>n;
    vector<node> X(n+1),Y(n+1);
    vector<ll> sumx(n+1),sumy(n+1);
    vector<Z> A(n+1);
    for(int i=1;i<=n;i++){
        ll x,y;
        cin>>x>>y;
        X[i].val=(x+y);
        Y[i].val=(x-y);
        X[i].pos=Y[i].pos=i;
    }
    sort(X.begin()+1,X.end());
    sort(Y.begin()+1,Y.end());
    for(int i=1;i<=n;i++)sumx[i]=sumx[i-1]+X[i].val;
    for(int i=1;i<=n;i++)sumy[i]=sumy[i-1]+Y[i].val;
    for(int i=1;i<=n;i++)A[X[i].pos].posx=i;
    for(int i=1;i<=n;i++)A[Y[i].pos].posy=i;
    ll ans=1e18;
    for(int i=1;i<=n;i++){
        ll x=A[i].posx,y=A[i].posy;
        ll tmp=(2*x-n)*X[x].val+sumx[n]-2*sumx[x];
        tmp+=(2*y-n)*Y[y].val+sumy[n]-2*sumy[y];
        ans=min(ans,tmp);
    }
    cout<<ans/2<<'\n';
}

Heidi and the Turing Test (Medium)(扫描线+曼哈顿切尔雪夫转换) ​

查看题解

leetcode3102最小化曼哈顿距离 ​

题意:
给多个点，删除某个点使得全部点之间的最大曼哈顿距离最小
思路：
曼哈顿转切比雪夫，用multiset维护x和y集合，枚举每个点删点恢复，算切比雪夫距离即可

AT_code_festival_2017_quala_d ​

题意：
给定一个网格n*m，和d，给每个网格涂上RYGB四种颜色，求曼哈顿距离为d的不能为相同颜色的一种方案
思路：

  • 曼哈顿转切比雪夫，然后给x的距离为d的网格交错涂上RY两种颜色
  • 接下来处理y坐标，分别处理颜色R和Y的网格，如果有差异，则涂另外两种颜色 更简单的一种思路：
  • 涂色想到奇偶性
  • 转化成切比雪夫距离后
  • 对于一个d*d的网格里，所有的点都不可能互斥，因此可以涂相同的颜色，而对于相邻的d*d的网格涂不同的颜色，刚好可以用四种颜色做到
cpp
char col[4]={'R','Y','G','B'};
void solve(){
    int n,m,d;
    cin>>n>>m>>d;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            int x=i+j+m,y=i-j+m;
            cout<<col[((x/d)%2)*2+(y/d)%2];
        }
        cout<<"\n";
    }
}

P3439 [POI2006] MAG-Warehouse ​

题意：
在坐标系上选一个点，到所有点的切比雪夫距离总和最小 前置知识：
类似CF1648A，在坐标系上选一个点，到所有点的曼哈顿距离总和最小，可以横纵坐标分开做，转化为一维的中位数定理问题
思路：
转化成曼哈顿距离，直接做
特殊情况：
曼哈顿转回切比雪夫需要除2，因此xy需要奇偶性相同，如果奇偶性已经固定了，那么需要判断四个方向

cpp
__int128 check(vector<array<int,3>>&a,int x,int y){
    int i=(x+y)/2,j=(x-y)/2;
    __int128 ans=0;
    for(auto &[xx,yy,t]:a)ans+=max(llabs(i-xx),llabs(j-yy))*t;
    return ans;
};
void solve(){
    int n;
    cin>>n;
    vector<array<int,3>> a(n);
    vector<PII> X,Y;
    int lx=-1e18,rx=-1e18,ly=-1e18,ry=-1e18;
    int nn=0;
    for(auto &[x,y,t]:a)cin>>x>>y>>t,X.push_back({x+y,t}),Y.push_back({x-y,t}),nn+=t;
    sort(X.begin(),X.end());
    sort(Y.begin(),Y.end());
    int m=0;
    for(auto [val,t]:X){
        m+=t;
        if(nn%2){
            if(m>=nn/2+1&&lx==-1e18)lx=rx=val;
        }
        else{
            if(m>=nn/2&&lx==-1e18)lx=val;
            if(m>=nn/2+1&&rx==-1e18)rx=val;
        }
    }
    m=0;
    for(auto [val,t]:Y){
        m+=t;
        if(nn%2){
            if(m>=nn/2+1&&ly==-1e18)ly=ry=val;
        }
        else{
            if(m>=nn/2&&ly==-1e18)ly=val;
            if(m>=nn/2+1&&ry==-1e18)ry=val;
        }
    }
    int x=lx,y=ly;
    if(lx%2!=ly%2){
        if(lx+1<=rx)lx++;
        else if(ly+1<=ry)ly++;
        else{
            int x,y;
            __int128 val=1e25,tmp;
            if((tmp=check(a,lx,ly))<val){
                val=tmp;
                x=lx,y=ly;
            }
            if((tmp=check(a,lx+1,ly))<val){
                val=tmp;
                x=lx+1,y=ly;
            }
            if((tmp=check(a,lx-1,ly))<val){
                val=tmp;
                x=lx-1,y=ly;
            }
            if((tmp=check(a,lx,ly+1))<val){
                val=tmp;
                x=lx,y=ly+1;
            }
            if((tmp=check(a,lx,ly-1))<val){
                val=tmp;
                x=lx,y=ly-1;
            }
            cout<<(x+y)/2<<" "<<(x-y)/2<<"\n";
            return;
        }
    }
    cout<<(lx+ly)/2<<" "<<(lx-ly)/2<<"\n";
}

P2906 [USACO08OPEN] Cow Neighborhoods G ​

题意：
曼哈顿距离小于等于c的在一个集合，求集合个数以及最大集合的大小
思路：

  • 转化为切比雪夫距离，x坐标排序，双指针维护一个大小为c的窗口，则x坐标都满足条件
  • 用set维护y坐标，二分查找当前y左右两边的点，只需要与左右两边的点连边，并查集维护集合大小
  • set左右两边加哨兵，即可不用判断边界
cpp
struct Node{
    int x,y;
};
bool cmp(Node &x,Node &y){
    return x.x<y.x;
}
struct DSU{
    vector<int> par;
    int n;
    DSU(int n):n(n){
        par.resize(n,0);
        iota(par.begin(),par.end(),0);
    }
    int find(int x){
        return par[x]==x?x:par[x]=find(par[x]);
    }
    bool merge(int x,int y){
        x=find(x),y=find(y);
        if(x==y)return false;
        par[y]=x;
        return true;
    }
};
void solve(){
    int n,c;
    cin>>n>>c;
    vector<Node> a(n+1);
    for(int i=1;i<=n;i++){
        int x,y;
        cin>>x>>y;
        a[i].x=x+y,a[i].y=x-y;
    }
    DSU dsu(n+1);
    sort(a.begin()+1,a.end(),cmp);
    set<PII> s;
    s.insert(make_pair(a[1].y,1));
    s.insert(make_pair(-1ll<<60,0));
    s.insert(make_pair(1ll<<60,0));
    for(int i=2,j=1;i<=n;i++){
        while(a[i].x-a[j].x>c)s.erase({a[j].y,j}),j++;
        auto it=s.lower_bound(make_pair(a[i].y,0));
        if(it->first-a[i].y<=c)dsu.merge(it->second,i);
        it--;
        if(a[i].y-it->first<=c)dsu.merge(it->second,i);
        s.insert({a[i].y,i});
    }
    map<int,int> cnt;
    int mx=0;
    for(int i=1;i<=n;i++){
        mx=max(mx,++cnt[dsu.find(i)]);
    }
    cout<<cnt.size()<<" "<<mx<<"\n";
}

P4648 [IOI2007] pairs 动物对数 ​

题意：
两个点可达，当且仅当两点的曼哈顿距离小于等于d，问可达的点对有多少个
需要计算一维二维三维的情况 思路：

  • 一维
    • 直接双指针维护窗口，计数
    • 时间复杂度:O(N)O(N)
  • 二维
    • 曼哈顿转切比雪夫
    • 暴力做法即查询(x-d,y-d),(x+d,y+d)这个平面的点对
    • 双指针维护x坐标窗口，权值树状数组维护y
    • 然后差分计数即可
    • 时间复杂度: O(NlogN)O(NlogN)
  • 三维
    • x,y坐标曼哈顿转切比雪夫
    • 规模只有75，参考二维的暴力做法，给z坐标每一维都维护一个前缀和
    • 枚举点数，然后枚举z的维度，前缀和查找即可
    • 时间复杂度: O(753+75⋅N)O(75^3+75 \cdot N)
cpp
int n,d,m;
void solve1(){
    cin>>n>>d>>m;
    int ans=0;
    vector<int> a(n+1);
    for(int i=1;i<=n;i++)cin>>a[i];
    sort(a.begin()+1,a.end());
    for(int i=1,j=1;i<=n;i++){
        while(j<i&&a[i]-a[j]>d)j++;
        ans+=i-j;
    }
    cout<<ans<<"\n";
}
void solve2(){
    cin>>n>>d>>m;
    vector<array<int,2>> a(n+1);
    vector<int> nums={0};
    for(int i=1;i<=n;i++){
        int x,y;
        cin>>x>>y;
        a[i][0]=x+y,a[i][1]=x-y,nums.push_back(a[i][1]+d),nums.push_back(a[i][1]-d-1),nums.push_back(a[i][1]);
    }    
    sort(a.begin()+1,a.end());
    int ans=0;
    sort(nums.begin()+1,nums.end());
    nums.erase(unique(nums.begin()+1,nums.end()),nums.end());
    auto id=[&](int x){
        return lower_bound(nums.begin()+1,nums.end(),x)-nums.begin();
    };
    vector<int> c(nums.size()+10);
    auto add=[&](int x,int y){
        for(int i=x;i<nums.size();i+=i&-i)c[i]+=y;
    };
    auto query=[&](int x){
        int ans=0;
        for(int i=x;i;i&=i-1)ans+=c[i];
        return ans;
    };
    for(int i=1,j=1;i<=n;i++){
        while(j<i&&a[i][0]-a[j][0]>d)add(id(a[j][1]),-1),j++;
        ans+=query(id(a[i][1]+d))-query(id(a[i][1]-d-1));
        add(id(a[i][1]),1);
    }
    cout<<ans<<"\n";
}
void solve3(){
    vector<vector<vector<int>>> sum(100,vector<vector<int>>(400,vector<int>(400)));
    cin>>n>>d>>m;
    vector<array<int,3>> a(n+1);
    for(int i=1;i<=n;i++){
        int x,y,z;
        cin>>x>>y>>z;
        int xx=x+y+m,yy=x-y+m;
        a[i][0]=xx,a[i][1]=yy,a[i][2]=z;
        sum[z][xx][yy]++;
    } 
    for(int z=1;z<=m;z++){
        for(int i=1;i<=399;i++){
            for(int j=1;j<=399;j++)sum[z][i][j]+=sum[z][i-1][j]+sum[z][i][j-1]-sum[z][i-1][j-1];
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        int z=a[i][2];
        for(int j=1;j<=m;j++){
            int dd=d-abs(z-j);
            if(dd<0)continue;
            int xx=min(399ll,a[i][0]+dd),x=max(1ll,a[i][0]-dd),yy=min(399ll,a[i][1]+dd),y=max(1ll,a[i][1]-dd);
            ans+=sum[j][xx][yy]-sum[j][x-1][yy]-sum[j][xx][y-1]+sum[j][x-1][y-1];
        }
    }
    ans-=n;
    cout<<ans/2<<"\n";
}
signed main(){
    cin.tie(0)->sync_with_stdio(0);
    int T=1;
    // cin>>T; 
    // while(T--)solve();
    int B;
    cin>>B;
    if(B==1)solve1();
    if(B==2)solve2();
    if(B==3)solve3();
    return 0;
}

Wenwei Lin · 2022 — 2025