题解归档 - cf2187B

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf2187B
• 本地来源：problems/cf2187B/idea.md
• 题目链接：https://codeforces.com/contest/2187/problem/B
• 原始标题：B. Shortest Statement Ever

思路

B. Shortest Statement Ever

pattern

math_reasoning_search: DP modeling was the relevant hint. The condition p&q=0 is bitwise, but the absolute values depend on the final comparison with x,y, so split by comparison signs.

claim

Partition the optimum into four regions:

• p<=x, q<=y: minimize (x-p)+(y-q), equivalent to maximize p+q.
• p<=x, q>=y: minimize (x-p)+(q-y), equivalent to minimize q-p.
• p>=x, q<=y: minimize (p-x)+(y-q), equivalent to minimize p-q.
• p>=x, q>=y: minimize (p-x)+(q-y), equivalent to minimize p+q.

Inside each region the objective is linear in the bits of p,q.

necessary

For every bit, at most one of p_bit,q_bit may be 1. The DP enumerates only (0,0),(1,0),(0,1), so every produced pair satisfies p&q=0.

The DP keeps prefix comparison states of p versus x and q versus y: less/equal/greater. Final states are filtered by the current region.

sufficient

Every feasible pair with max(p,q)<2^31 has a unique 31-bit path in exactly one or more of the four regions. For a fixed region, the DP minimizes the corresponding linear objective over all such paths, so taking the best actual |x-p|+|y-q| among four regions is globally optimal.

brute/check

Compared the DP cost with full enumeration for all 0<=x,y<64; all matched. Also checked sample-shaped large edge x=2^30-1, y=2^30-2, where the DP outputs a valid cost-1 pair.

edge

Bits 0..30 are enough because the statement guarantees an optimal answer with max(p,q)<2^31.

代码

来源：problems/cf2187B/solution.cpp

#include<bits/stdc++.h>
#define ll long long
using namespace std;
struct node{
    ll ok,cost,p,q;
};
node dp[5][5],ndp[5][5];
ll wp[5]={0,-1,-1,1,1},wq[5]={0,-1,1,-1,1},rp[5]={0,-1,-1,1,1},rq[5]={0,-1,1,-1,1};
ll x,y,ansp,ansq;
int main(){
    ll t,n,i,j,k,zc,pd,cur,dq,cnt,ans,inf,best,cs,bit,val,ch,xb,yb,pb,qb,cp,cq,ncp,ncq,ncost,np,nq;
    scanf("%lld",&t);
    while(t--){
        scanf("%lld%lld",&x,&y);
        inf=(1ll<<62);
        best=inf;
        for(cs=1;cs<=4;cs++){
            for(i=0;i<3;i++){
                for(j=0;j<3;j++){
                    dp[i][j].ok=0;
                }
            }
            dp[1][1].ok=1;
            dp[1][1].cost=0;
            dp[1][1].p=0;
            dp[1][1].q=0;
            for(bit=30;bit>=0;bit--){
                for(i=0;i<3;i++){
                    for(j=0;j<3;j++){
                        ndp[i][j].ok=0;
                    }
                }
                val=1ll<<bit;
                xb=(x>>bit)&1;
                yb=(y>>bit)&1;
                for(i=0;i<3;i++){
                    for(j=0;j<3;j++){
                        if(!dp[i][j].ok) continue;
                        cp=i-1;
                        cq=j-1;
                        for(ch=0;ch<3;ch++){
                            pb=(ch==1);
                            qb=(ch==2);
                            ncp=cp;
                            ncq=cq;
                            if(ncp==0){
                                if(pb<xb) ncp=-1;
                                if(pb>xb) ncp=1;
                            }
                            if(ncq==0){
                                if(qb<yb) ncq=-1;
                                if(qb>yb) ncq=1;
                            }
                            ncost=dp[i][j].cost+(wp[cs]*pb+wq[cs]*qb)*val;
                            np=dp[i][j].p+pb*val;
                            nq=dp[i][j].q+qb*val;
                            if(!ndp[ncp+1][ncq+1].ok or ncost<ndp[ncp+1][ncq+1].cost){
                                ndp[ncp+1][ncq+1].ok=1;
                                ndp[ncp+1][ncq+1].cost=ncost;
                                ndp[ncp+1][ncq+1].p=np;
                                ndp[ncp+1][ncq+1].q=nq;
                            }
                        }
                    }
                }
                for(i=0;i<3;i++){
                    for(j=0;j<3;j++){
                        dp[i][j]=ndp[i][j];
                    }
                }
            }
            for(i=0;i<3;i++){
                for(j=0;j<3;j++){
                    if(!dp[i][j].ok) continue;
                    cp=i-1;
                    cq=j-1;
                    if(rp[cs]<0 and cp>0) continue;
                    if(rp[cs]>0 and cp<0) continue;
                    if(rq[cs]<0 and cq>0) continue;
                    if(rq[cs]>0 and cq<0) continue;
                    cur=llabs(dp[i][j].p-x)+llabs(dp[i][j].q-y);
                    if(cur<best){
                        best=cur;
                        ansp=dp[i][j].p;
                        ansq=dp[i][j].q;
                    }
                }
            }
        }
        printf("%lld %lld\n",ansp,ansq);
    }
    return 0;
}