题解：CF1974F Cutting Game

lgx57 · 2025-01-03 18:42:22 · 题解

纯纯搞笑题。

把每一次操作后剩下的矩阵存下来（x 左右端点，y 左右端点），然后对每一个棋子计算它的贡献，显然可以二分出它最后出现在哪里，那么这个棋子就算当时删矩阵的那个人，即后面一个

const int N=2e5+5;
int x[N],y[N];
struct node{
    int lx,rx,ly,ry;
}p[N];
bool check(int id,int num){
    return x[id]<=p[num].rx&&x[id]>=p[num].lx&&y[id]<=p[num].ry&&y[id]>=p[num].ly;
}//是否在剩下的矩阵中
void sol(){
    int a,b,n,m;
    cin>>a>>b>>n>>m;
    for (int i=1;i<=n;i++) cin>>x[i]>>y[i];
    int lx=1,ly=1,rx=a,ry=b;
    for (int i=1;i<=m;i++){
        char c;
        int k;
        cin>>c>>k;
        if (c=='U') lx+=k;
        if (c=='D') rx-=k;
        if (c=='L') ly+=k;
        if (c=='R') ry-=k;
        p[i]={lx,rx,ly,ry};//存下剩下的矩阵
    }
    int ans1=0,ans2=0;
    for (int i=1;i<=n;i++){
        int L=1,R=m,Ans=-1;
        while (L<=R){
            int mid=(L+R)>>1;
            if (check(i,mid)) Ans=mid+1,/*一定要在这里 +1!!!*/L=mid+1;
            else R=mid-1;
        }
        if (Ans!=m+1){
            if (Ans&1) ans1++;
            else ans2++;
        }
    }
    cout<<ans1<<' '<<ans2<<endl;
}

二分时注意 Ans 要 +1，原因上面已经解释了。