题解：CF1991G Grid Reset

山田リョウ · 2024-08-22 16:38:09 · 题解

通过思考 k|n 的情况发现，我们需要单独留出一个空间用于消方块。

于是考虑将矩阵划分为四个部分，分别是左上角的 k\times k 的消消区和左下 (n-k)\times k、右上 k\times(m-k) 的行/列正常摆放区域与右下 (n-k)\times(m-k) 的废弃区。

不难发现如果我们在能在对应正常摆放区摆放的前提下往里填，否则填到消消区尽可能去消另一种摆放，则一定合法。

于是我们就有了一个构造方式，而大部分人似乎都是写的朴素枚举可选位置的做法，但是其实更优。

考虑对行和列各记一个下一次填的位置的指针，与一个记录在消消区的残留的指针，你可以每次 O(1) 跳指针并进行判断更新了！具体细节见代码。

注意特判 n=k 或 m=k。

#include<stdio.h>
char s[1001];
int main(){
    int T,N,M,K,Q;
    for(scanf("%d",&T);T--;){
        scanf("%d%d%d%d %s",&N,&M,&K,&Q,s);
        if(N==K&&M==K){
            for(int i=0;i<Q;++i)puts("1 1");
        }else if(N==K){
            for(int i=0,p=0;i<Q;++i)
                if(s[i]=='H'){
                    printf("%d 1\n",++p);
                    if(p==N)p=0;
                }else printf("1 %d\n",M);
        }else if(M==K){
            for(int i=0,p=0;i<Q;++i)
                if(s[i]=='V'){
                    printf("1 %d\n",++p);
                    if(p==M)p=0;
                }else printf("%d 1\n",N);
        }else{
            int x=N,y=M,p=K,q=K;
            for(int i=0;i<Q;++i)
                if(s[i]=='H'){
                    printf("%d 1\n",x--);
                    if(!x){
                        if(y<=K)q=y,y=M,x=K;
                        else x=N;
                    }else if(x==K)x=p,p=K;
                }else{
                    printf("1 %d\n",y--);
                    if(!y){
                        if(x<=K)p=x,x=N,y=K;
                        else y=M;
                    }else if(y==K)y=q,q=K;
                }
        }
    }
    return 0;
}