题解：P11122 [ROIR 2024 Day 1] 表格游戏

ny_jerry2 · 2025-01-09 07:21:15 · 题解

update：发现写的有点简单，就多加了一点文字的描述。

思路

折半搜索模版题（之前确实没接触过）。
简单来说，就是分两段来搜索（当然有的时候并不是非要等分，一般两边均值是最佳的），然后用排序加二分或双指针来处理。这道题大致思路是这样的：

先去搜一下行的被选的状态，中途用一个数组来记录一下哪些行是被选了的。
然后记录一下列还剩多少价值（因为行列相交嘛）。
对于列就可以用折半搜索，这里取整个序列的中点为 \lfloor{\frac{n}{2}}\rfloor，然后分别进行搜索。
之后判断列有没有使用过可以状态压缩（搜索时就可以将列的被选的状态压缩成二进制）。
然后排序，排完序后发现两个序列都有单调性，就可以双指针或者二分了。
具体过程
折半搜索部分前， 先把每一列剩余的价值计算出来 。
然后分两次搜索，搜索时要记录剩下没选的行的总价值以及二进制状态。每一次结束递归前可以用 vector 来记录下当前的价值与状态，要分别用两个 vector 来记录，可以在搜索中多传一个参数。
然后排序。
排完序后。就可以双指针或者二分了（这里采用双指针）。
遍历第一个 vector，第二个用双指针来处理。具体就是在判断价值的和是否相等之前用双指针排除绝对不可能的数值。如果当前的指针对应的值与当前循环遍历到的值之和大于了要求的和，就向左移动指针。因为已经排序，所以有单调性，因此正确性可以保证。
判断和是否相等。相等的话就输出并结束程序。

输出稍加处理即可,其实就是先计算一下操作了多少次，然后看行列的删除情况。
行很简单，就是看有没有被标记为 1。列也不复杂，可以根据状态压缩的情况来判断有没有删掉（两次搜索的状态都要去判断）。

正解

搜索题还挺练习代码力的。

#include<iostream>
#include<vector>
#include<algorithm>
int n,m;
long long c;
using namespace std;
const int N=30;
long long col[N][N],p[N];
bool vis[N],ch=1;
struct node{
    long long val,S;
    bool operator<(const node &t){
        return val<t.val;
    }
};
vector<node> s[2];
void dfs(int u);
void work();
void dfs2(int u,int ed,long long val,long long S,int type);
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            scanf("%lld",&col[i][j]);
        }
    }
    cin>>c;
    dfs(1);
    if(ch){
        cout<<"NO";
    }
    return 0;
}
void dfs(int u){
    if(!ch){
        return;
    }
    if(u>n){
        work();
        return;
    }
    dfs(u+1);
    vis[u]=1;
    dfs(u+1);
    vis[u]=0;
}
void work(){
    for(int i=1;i<=m;i++){
        p[i]=0;
    }
    for(int i=1;i<=n;i++){
        if(vis[i]){
            continue;
        }
        for(int j=1;j<=m;j++){
            p[j]+=col[i][j];
        }
    }
    s[0].clear(),s[1].clear();
    int mid=(m>>1)+1;
    dfs2(1,mid,0,0,0);
    dfs2(mid+1,m,0,0,1);
    sort(s[0].begin(),s[0].end());
    sort(s[1].begin(),s[1].end());
    int x=s[0].size(),y=s[1].size();
    int j=y-1;
    for(int i=0;i<x;i++){
        while(j&&s[0][i].val+s[1][j].val>c){
            j--;
        }
        if(s[0][i].val+s[1][j].val!=c){
            continue;
        }
        int cnt=0;
        for(int k=1;k<=n;k++){
            if(vis[k]){
                cnt++;
            }
        }
        for(int k=1;k<=m;k++){
            if(!(s[0][i].S>>k&1)&&!(s[1][j].S>>k&1)){
                cnt++;
            }
        }
        printf("YES\n%d\n",cnt);
        for(int k=1;k<=n;k++){
            if(vis[k]){
                printf("1 %d\n",k);
            }
        }
        for(int k=1;k<=m;k++){
            if(!(s[0][i].S>>k&1)&&!(s[1][j].S>>k&1)){
                printf("2 %d\n",k);
            }
        }
        ch=0;
        return;
    }
}
void dfs2(int u,int ed,long long val,long long S,int type){
    if(u>ed){
        s[type].push_back({val,S});
        return;
    }
    dfs2(u+1,ed,val,S,type);
    dfs2(u+1,ed,val+p[u],S|(1<<u),type);
}

折半搜索是一个搜索的小优化，一般用于数据小但还没小到暴力做的程度，还是有套路。只不过考验代码力。感觉搜索都挺考代码力，练习多了还能提升 Debug 能力。

题解：P11122 [ROIR 2024 Day 1] 表格游戏

思路

具体过程

正解