题解：P11244 吻秋

_sin_ · 2024-11-02 19:23:04 · 题解

感觉这道题有点抽象了。

注意到 m\le 20，大胆猜想需要暴力做的操作数不是很多。感性理解一下就是暴力操作总次数的上界应该是关于 m 的多项式。

于是我们想到一下两种优化：\ 对于序列 a_x,a_y 的一次操作，如果 a_x 和 a_y 是有序的，且 a_x 的最大值小于等于 a_y 的最大值，这样显然是不用操作。\ 如果 a_x 和 a_y 是有序的，且 a_x 的最小值大于等于 a_y 的最大值，直接将 a_x,a_y 交换即可。

然后我们可以写出暴力代码，在暴力代码上加上上述优化，即可就可以通过本题。注意存 a 数组的时候要用 vector 存，这样交换操作就是 O(1) 的。

代码如下：

#include<bits/stdc++.h>
using namespace std;

namespace FastIO {
    char buf[1 << 21], *p1 = buf, *p2 = buf;
#define getchar() (p1 == p2 && (p1 = buf, p2 = (p1 + fread(buf, 1, 1 << 21, stdin))) == p1 ? EOF : *p1++)
    template <typename T> inline T Read() { T x = 0, w = 0; char ch = getchar(); while (ch < '0' || ch > '9') w |= (ch == '-'), ch = getchar(); while ('0' <= ch && ch <= '9') x = x * 10 + (ch ^ '0'), ch = getchar(); return w ? -x : x; }
    template <typename T> inline void write(T x) { if (!x) return; write<T>(x / 10), putchar((x % 10) ^ '0'); }
    template <typename T> inline void Print(T x) { if (x > 0) write<T>(x); else if (x < 0) putchar('-'), write<T>(-x); else putchar('0'); }
    template <typename T> inline void Print(T x, char en) { Print<T>(x), putchar(en); }
}; using namespace FastIO;
#undef getchar()

#define read(x) Read<int>(x)
#define print(x,y) Print<int>(x,y)

const int N = 2e6+5,M=25;
int n, m, q;
vector<int>a[M],vec;
bool sorted[M];

int main(){
    n=read(),m=read(),q=read();
    for(int i=1;i<=m;i++){
        int x;for(int j=1;j<=n;j++){
            x=read();a[i].push_back(x);
        }
    }while(q--){
        int opt=read(),x=read(),y=read();
        if(opt==2)print(a[x][y-1],'\n');
        else{
            if(sorted[x]&&sorted[y]){
                if(a[x][a[x].size()-1]<=a[y][0])continue;
                if(a[y][a[y].size()-1]<=a[x][0]){swap(a[x],a[y]);continue;}
            }
            vec.clear();vec.insert(vec.end(),a[x].begin(),a[x].end());
            vec.insert(vec.end(),a[y].begin(),a[y].end());sort(vec.begin(),vec.end());
            for(int i=0;i<n;i++)a[x][i]=vec[i];sorted[x]=sorted[y]=1;
            for(int i=n;i<vec.size();i++)a[y][i-n]=vec[i];
        }
    }
    return 0;
}

评价：题目有点抽象，一个玄学复杂度的做法过了。