扯两句闲话

咕了这么长时间，其实是想看看有没有人能想出正解。

很遗憾，目前为止，只有@__VAN♂游戏__ 写出了正确的解法。

不过由于一些奇奇怪怪的错误，他写的正解只得了 $20$ 分......后来只好去写只能拿 $40$ 分的解法。

我也没看出来哪错了。

另外这题数据生成器其实也有一段故事，到最后给大家说。

Subtask#1

依照题意，对于每一个 $A$ 数列中的数，暴力在 $B$ 数列中查找即可。

不过有一点需要注意：在 $B$ 数列中查找时，我们需要额外开一个数组来记录这个数是否已经被查找过了。

不然的话，就像那个例子一样：

$\begin{matrix}A:&2&3&3&3\\B:&3&2&2&2 \end{matrix}$

我们在 $B$ 数列中查找 $2$，找到了。

接着在 $B$ 数列中查找 $3$，找到了。

此时，虽然对于 $A$ 数列中的每一个元素， $B$ 数列中都有相同的元素与其对应，但是对于 $A$ 数列中的第二到第四个数，都只能与 $B$ 数列中的第一个数对应，所以 $A$ 数列与 $B$ 数列并不是「本质相同」的。

代码如下：

#include<bits/stdc++.h>
using namespace std;
inline int read(){
    int w=0;
    char c=getchar();
    while(c>'9'||c<'0') c=getchar();
    while(c>='0'&&c<='9'){
        w=(w<<3)+(w<<1)+(c^48);
        c=getchar();
    } 
    return w;
}   //给的快读，直接复制粘贴。
int n,q,a[20005],b[20005];  //如题意。
bool vis[20005];            //vis[20005]用来记录 B 数组中的元素是否已经被查找过了。
int main(){
    cin>>q; //询问次数
    for(int i=1;i<=q;i++){  //q 次询问。
        memset(a,0,sizeof(a));
        memset(b,0,sizeof(b));
        memset(vis,0,sizeof(vis));
        //每次询问前都要把 a,b,vis 清零
        cin>>n;
        for(int i=1;i<=n;i++){
            cin>>a[i];      //输入 A 数列。
        }
        for(int i=1;i<=n;i++){
            cin>>b[i];      //输入 B 数列。
        }
        bool k=1;           //k 用于记录两数列是否「本质相同」
        for(int i=1;i<=n;i++){      //对于 A 数列中的每一个元素
            bool f=0;               //用 f 记录是否找到了
            for(int j=1;j<=n;j++){  //在 B 数列中查找
                if(a[i]==b[j]&&vis[j]!=1){  //如果对于 A 数列中的第 i 个元素，在 B 数列中找到了对应的元素，并且这个元素还是第一次被找到
                    vis[j]=1;       //标记一下，这个元素已经被查找过了。
                    f=1;            //找到了
                    break;          //就不用继续找了。
                }
            }
            if(f==0){               //如果一直没找到
                cout<<"NO"<<endl;   //输出 NO
                k=0;                //两数列并不是「本质相同」的。
                break;              //跳出循环。
            }
        }
        if(k==1){
            cout<<"YES"<<endl;      //两数列「本质相同」，输出 YES
        }
    }
    return 0;
}

其实这代码能得 $\sout{40}$ 分

Subtask#2

上一个代码中，有一个二重循环，再加上 $q$ 次询问，总时间复杂度达到了恐怖的 $O(qn^2)$。

显然 $O(q)$ 这部分没法再优化了，我们考虑优化判断两个数列是否相同的部分。

仔细想一想：如果两个数列相同，那么他们本质上是什么？

$\color{red}\large\texttt{其实，第二个数列就是第一个数列打乱顺序之后的结果！}$

打乱顺序......顺序......排序？！

对呀，两个顺序不同但元素相同的数列，排序之后，肯定每一位上的元素都对应上了。

这也是大多数同学的解法：排序之后一位一位判断是否相同。

由于排序的时间复杂度是 $O(n\log n)$，有 $q$ 次询问，所以总时间复杂度为 $O(qn\log n)$。

代码如下：

#include<bits/stdc++.h>
using namespace std;
int q;
int n;
int a[20001],b[20001];
int t;
int read(){
    int k=0;
    char i=getchar();
    while(i<'0'||i>'9'){
        i=getchar();
    }
    while(i>='0'&&i<='9'){
        k*=10;
        k+=i-'0';
        i=getchar();
    }
    return k;
}
int main(){
    q=read();
    for(int i=1;i<=q;i++){
        n=read();
        for(int j=1;j<=n;j++){
            a[j]=read();
        }
        for(int j=1;j<=n;j++){
            b[j]=read();
        }
        sort(a+1,a+n+1);
        sort(b+1,b+n+1);
        t=1;
        for(int j=1;j<=n;j++){
            if(a[j]!=b[j]){
                t=0;
                break;
            }
        }
        if(t==1){
            cout<<"YES\n";
        }else{
            cout<<"NO\n";
        }
    }
    return 0;
}

由于这个方法很好想，做法显然，就懒得写注释了（

Subtask#3

好，接下来我们看看不太好想的 $\text{Subtask\#3}$。

还是那个问题：如果两个数列相同，那么他们本质上是什么？

$\large\color{red}\texttt{两个数列相同，等价于他们中的每一个元素出现的次数都相同！}$

我们可以用一个数组 $p$ 来表示两数列中每一个元素出现的次数。$p[i]=k$ 的意思是：元素 $i$ 出现了 $k$ 次。

例如：

$\begin{matrix}A:&2&3&3&3\\B:&3&2&2&2 \end{matrix}$

对于 $A$ 数列：

$p[2]=1$（元素 $2$ 出现了 $1$ 次）。

$p[3]=3$（元素 $3$ 出现了 $3$ 次）。

对于 $B$ 数列：

$p[2]=3$（元素 $2$ 出现了 $3$ 次）。

$p[3]=1$（元素 $3$ 出现了 $1$ 次）。

而显然这两个不相同，所以两数列不是「本质相同」的。

那么，我们可以像消消乐一样，用 $B$ 数列中的元素去一个一个「消掉」$A$ 数列中的元素。

具体做法是：我们在输入 $A$ 数列时，就让 $\texttt{p[a[i]]++}$，意思是 $\texttt{a[i]}$ 这个元素出现的次数多了一次。

然后在输入 $B$ 数列时，让 $\texttt{p[b[i]]-\,\!-}$，意思是这两个元素「消掉了」。

最后，如果两数列「本质相同」，那么 $p$ 数组中的所有元素应该都刚好被消掉了，即都是 $0$。

所以，最后判断一下 $p$ 数组中是否都是 $0$ 即可。

可能有点不好理解，建议照着下面的代码手动模拟一下程序运行过程。

代码如下：

#include<bits/stdc++.h>
using namespace std;
inline int read(){
    int w=0;
    char c=getchar();
    while(c>'9'||c<'0') c=getchar();
    while(c>='0'&&c<='9'){
        w=(w<<3)+(w<<1)+(c^48);
        c=getchar();
    } 
    return w;
}
int a[20005],b[20005],p[200005];
//注意这里 p 数组要开到 200005 而不是 20005，因为 a,b 数组中的元素最大是 200005，而 p 数组存储的是两数组中元素的出现次数。
int n,q;
int main(){
    q=read();
    for(int i=1;i<=q;i++){
        memset(p,0,sizeof(p));
        memset(a,0,sizeof(a));
        memset(b,0,sizeof(b));
        //清空
        n=read();
        for(int i=1;i<=n;i++){
            a[i]=read();
            p[a[i]]++;  //出现次数加一。
        }
        for(int i=1;i<=n;i++){
            b[i]=read();
            p[b[i]]--;  //用 A 数组中的元素「消掉」它。
        }
        bool f=1;       //判断是否「本质相同」
        for(int i=1;i<=n;i++){
            if(p[a[i]]!=0||p[b[i]]!=0){ //如果没「消完」
                cout<<"NO"<<endl;       //输出 NO
                f=0;        //两数列并不「本质相同」
                break;      //不用再比了。
            }
        }
        if(f==1)cout<<"YES"<<endl;  //如果「本质相同」，输出 YES。
    }
    return 0;
}

关于数据生成器的小故事：鸽掉了（