#C241104B. 金银变换
标签（Label）
- 数学
- 数学推理
网址（Website）
题目（Problem）
样例
输入数据 1
3
5 1 2 3 4 5
5 3 2 5 4 1
2
5 1 2 3 4 5
5 3 2 1 4 5
2
5 1 2 3 4 5
5 5 4 3 2 1
2输出数据 1
YES
NO
YES
题解（Solution）
出题者题解
算法分析
细心观察的套路题。
2.1 算法 0
当 $n \neq m$ 时，显然无解。
期望得分 $0$ 分，但是如果没判的话，期望得分也是 $0$ 分。
2.2 算法 1
我会读题！
对于 $k = 1$， 容易发现操作即为交换相邻的两个数，排序后判断对应位置是否相等即可。
对于 $2k \geqslant n$:
若 $2k > n$，则无法进行操作，直接判断 $A$ 和 $B$ 是否相等即可。
若 $2k = n$，容易发现操作即为交换序列的前后两半，判断交换和不交换两种情况即可。
可以通过测试点 $9$ 和 $12$，期望得分 $8$ 分。
2.3 算法 2
我会爆搜！
对于 $T \leqslant 100$ 且 $n, m \leqslant 10$，直接记忆化搜索即可。
状态数上界为 $5! \times 5! = 14400$，但不会分析应该也能猜到爆搜可过吧。
可以通过测试点 $1 \sim 3$，结合算法 1，期望得分 $20$ 分。
2.4 算法 3
我会贪心和模拟！
可以证明，当 $A$ 中元素互不相同时，下列贪心是正确的。（该结论的证明见2.5节）
按 $i = 1, 2, \cdots, n - 2k + 1$ 的顺序依次执行下列操作：
若 $A_i, A_{i+k}, A_{i+2k}, \cdots$ 中没有和 $B_i$ 相等的数，无解。
否则，设 $A_{i+tk} = B_i$，考虑在不改变 $A_1, A_2, \cdots, A_{i-1}$ 的前提下，通过 $t$ 次操作将 $A_{i+tk}$ 移至 $A_i$。
设当前下标为 $j (j > i)$，若 $j + k - 1 \leqslant n$ 则执行操作 $i = j - k$（此处是题目描述中的变量，下同），否则执行操作 $i = n - 2k + 1$。 每次执行后 $j \rightarrow j - k$， 因此 $t$ 次操作后可以达成目标。
最终，若 $A = B$ 则答案为 $YES$，否则答案为 $NO$。
直接模拟上述过程，时间复杂度 $O(Tn^2)$。
可以通过测试点 $4 \sim 8$，期望得分 $20$ 分。
注： 放这档分主要是想提醒选手，如果不会正解的话有些贪心该写还是要写的。（即使你不会证）
2.5 算法 4
首先，容易发现一个元素的下标 $\text{mod}\ k$ 是不会变的，所以按下标 $\text{mod}\ k$ 把 $A$ 和 $B$ 的元素分别分成 $k$ 组，对应组的可重集必须相等，否则无解。下面假设该条件满足。
考虑 $A$ 中元素互不相同的情况。
考虑将 $A$ 中的元素替换为其目标位置的下标。换句话说，若 $A_i = B_j$，则将 $A_i$ 替换为 $j$。那么目标转化为使 $A$ 单调递增，即 $A_i = i$。
考查每次操作前后的不变量：对于每一组元素所组成的子序列（按下标 $\text{mod}\ k$ 分组，下同)，逆序对数量恰好变化 $1$。这意味着对于任意两组，它们逆序对数量的奇偶性要么保持相同，要么保持不同。
由于 $A_i = i$ 时每一组逆序对数量均为 $0$，因此初始时各组逆序对数量的奇偶性必须相同。
事实上，该条件是充分的。
证明： 按照 2.4 中的贪心方法，我们总可以使 $\forall i \in [1,n-2k+1] \cup {n-k+1}$，$A_i = i$。 此时下标 $n-k+1$ 所在组的逆序对数量为 $0$，故其余组的逆序对数量为偶数。又它们的逆序对个数 $\leqslant 1$ (每组只有末尾两个元素可能产生逆序对)，进而逆序对数量均等于 $0$，得证。
进而证明了 2.4 中贪心做法的正确性。
时间复杂度 $O(\sum n \log n)$，可以通过测试点 $4 \sim 8$ 及 $15 \sim 20$，期望得分 $44$ 分。
2.6 算法 5
算法4 和正解仅有一步之遥：$A$ 中同一组有相同元素怎么办？
首先仍然判掉对应组可重集不相等的情况。
然后我们仍然可以检查逆序对奇偶性，如果全部相同则答案为 $YES$ 。
唯一的不同是，不全部相同也可能是 $YES$ ：
设 $a \equiv b\ (\text{mod}\ k)(a \neq b)$ ， 且 $A_a = A_b$，则存在 $c \equiv d \equiv a\ (\text{mod}\ k)(c \neq d)$ 使得 $B_c = B_d = A_a$。 由于 $A_a$ 和 $A_b$ 的目标位置可交换，因此将 $A_a, A_b$ 依次替换为 $c, d$， 或者将 $A_a, A_b$ 依次替换为 $d, c$ 均可。
这意味着，对于有相同元素的一组，其逆序对数量的奇偶性可以人为更改，因此只需要对不存在相同元素的组，判断它们的逆序对数量的奇偶性是否全部相同即可。 时间复杂度仍为 $O(\sum n \log n)$。
可以通过全部测试点，期望得分 $100$ 分。
代码（Code）
#include<bits/stdc++.h>
#include<vector>
#include<set>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define P pair<int,int>
#define int long long
#define x first
#define y second
inline int rd(){
char c;bool f=false;while(!isdigit(c=getchar()))f=c=='-';int x=c^48;
while(isdigit(c=getchar())){x=(((x<<2)+x)<<1)+(c^48);}return f?-x:x;
}const int inf = 0x3f3f3f3f3f3f3f3f;
const int N = 201234;
bool ST;
int a[N],b[N];
int n,m,k;
struct BIT{
int n,c[N];inline void init(int siz){n=siz;fill(c,c+n+1,0);}
inline int lbt(int x){return x&(-x);}
void update(int x,int v){for(int i=x;i<=n;i+=lbt(i))c[i]+=v;}
int ask(int x){int res=0;for(int i=x;i;i-=lbt(i))res+=c[i];return res;}
}B;
vector<int> vec[N];
int c[N],d[N],vn;
bool flag;
void Solve(){
n=rd();For(i,1,n) a[i]=rd();
m=rd();For(i,1,m) b[i]=rd();
k=rd();if(n^m) return printf("NO\n"),void();
int bas=-1;
For(i,1,k){
vn=0;for(int j=i;j<=n;j+=k) vn++,c[vn] = a[j];
vn=0;for(int j=i;j<=n;j+=k) vn++,d[vn] = b[j];
sort(c+1,c+vn+1);sort(d+1,d+vn+1);
For(j,1,vn) if(c[j]^d[j]) return printf("NO\n"),void();
int lst = unique(c+1,c+vn+1)-c-1;
if(lst^vn) continue;
B.init(vn);int res=0;
for(int j=i;j<=n;j+=k){
int p=lower_bound(c+1,c+vn+1,a[j])-c;
res ^= B.ask(p), B.update(p,1);
}
B.init(vn);
for(int j=i;j<=n;j+=k){
int p=lower_bound(d+1,d+vn+1,b[j])-d;
res ^= B.ask(p), B.update(p,1);
}res%=2;
if(res!=bas&&bas!=-1) return printf("NO\n"),void();
bas = res;
}printf("YES\n");
}
bool ED;
signed main(){
cerr<<abs(&ST-&ED)/1024./1024.<<"MB\n";
freopen("yinrier.in","r",stdin);
freopen("yinrier.out","w",stdout);
int T = rd();double Tim = clock();
while(T--) Solve();
return cerr<<"TIME:"<<(clock()-Tim)/CLOCKS_PER_SEC,0;
}
