Reverse the Rivers 题解

原题链接https://codeforces.com/problemset/problem/2036/E
（暂时不会弄翻译，所以不上原题了）

说一下我对题意的理解吧

有n个国家，每个国家有k个区域，用a_ij表示第i个国家的第j个地区。
这n个国家所处地势呈斜坡状，也就是编号为1的国家所处地势比编号为2的国家要高，编号为2的国家所处地势比编号为3的国家要高，于是水就会往下流，这n个国家的水会满足或规则，例如：（由a数组变成b数组）

(https://img2024.cnblogs.com/blog/3466055/202412/3466055-20241215111342004-545958007.png)
现给出m条规则，比如：2<3。也就是说要找到满足b_i2<3的最小i。先要找到有一个i使b_i满这m条规则，若没有则输出-1。

题意大致是这样。

上思路
变成b数组后，b数组每一列(从第1行到第n行)都是单调不递减。（这句话其实重点，但刚刚打题意打了太久，有点写不动了，可以看看|这个运算的规则）；
看到这，这个题的重点也就出来了，就是二分查找。然后上两个二分数组。
上代码

#include <bits/stdc++.h>
#define int long long

using namespace std;
const int xmmm=1e5+1000;
vector<int>s[xmmm];
struct p{
    int x, y;
    char c;
}k[xmmm];

bool cmp(p t1, p t2){
    if(t1.c!=t2.c)return t1.c<t2.c;
    else if(t1.x!=t2.x)return t1.x<t2.x;
    else return t1.y<t2.y;
}
int n, k1, q;

int check1(int l, int r, int i, int pos){//">"
    if(s[r][i]<=pos)return -1;
    while(l<r){
        int mid=(l+r)/2;
        if(s[mid][i]>pos)r=mid;
        else l=mid+1;
    }
    return l;
}

int check2(int l, int r, int i, int pos){//"<"
    if(s[l][i]>=pos)return -1;
    while(l<r){
        int mid=(l+r+1)/2;
        if(s[mid][i]<pos)l=mid;
        else r=mid-1;
    }
    return l;
}

signed main()
{
    int T;T=1;
    while(T--){
        cin>>n>>k1>>q;
        for(int i=0;i<n;i++){
            for(int j=0;j<k1;j++){
                int t;cin>>t;
                s[i].push_back(t);
            }
        }
        for(int i=0;i<k1;i++){
            for(int j=1;j<n;j++)s[j][i]=s[j-1][i]|s[j][i];
        }
        while(q--){
            int m;cin>>m;
            for(int i=0;i<m;i++){
                cin>>k[i].x>>k[i].c>>k[i].y;
                k[i].x--;
            }
            int l=0, r=n-1;
            for(int j=0;j<m;j++){
                if(k[j].c=='>'){
                    l=check1(l, r, k[j].x,  k[j].y);
                }
                else {
                    r=check2(l, r, k[j].x, k[j].y);
                }
                if(l>r||l==-1||r==-1)break;
            }
            if(l==-1||r==-1||l>r)cout<<-1<<'\n';
            else cout<<l+1<<'\n';
        }
    }
    return 0;
}

已经放好代码了，我觉得最重要的就是那两个二分查找吧，不过也可以用现成的函数实现。

题解写到这已经告一段落了，后面就是我的碎碎念了。

*** 自我总结**
为什么我上这道题的题解，因为最近写了这个题，还因为这题写了很久。

开始的时候读了个假题，以为要输出多少个国家满足这些要求，意识到读错题以后，结合每一列具有单调性的性质用了两个指针试图锁定满足条件国家的范围，然后超时了，之后发现其实二分就够了。
调试的时候还扯到了一个很扯的错误。哈哈哈哈哈哈哈哈哈

放一张好看的图片。

秒客网

Reverse the Rivers 题解

相关文章