题面Bessie 有一个N×NN\times NN×N1≤N≤10001\le N\le 10001≤N≤1000的加法表其中对于所有1≤r,c≤N1\le r,c\le N1≤r,c≤N第rrr行第ccc列的方格中的整数为rcrcrc。例如对于N3N3N3表格如下所示2 3 4 3 4 5 4 5 6不幸的是Elsie 得到了这张表格并通过执行若干次以下三种类型的操作对表格进行了变换。交换两行交换两列选择两个同时存在于表格中的值aaa和bbb然后同时将每一个aaa更改为bbb每一个bbb更改为aaa。Elsie 总是按类型顺序执行操作也就是说她首先执行任意数量可能为零的类型111操作然后是类型222操作最后是类型333操作。请帮助 Bessie 恢复 Elsie 在执行完所有类型111和222操作后但在执行任意类型333操作之前表格的一种可能状态。可能存在多种可能的答案在这种情况下你应当输出字典序最小的答案。按字典序比较两个表格时比较它们在自然顺序行间从上到下行内从左到右下读取时第一个不同的项。输入样例3 3 4 2 5 2 3 6 3 5输出样例4 2 3 5 3 4 6 4 5解释2 3 4 3 4 5 4 5 6 - 操作 2交换列 2 和 3 2 4 3 3 5 4 4 6 5 - 操作 2交换列 1 和 2 4 2 3 5 3 4 6 4 5 - 操作 3交换值 2 和 3 4 3 2 5 2 4 6 4 5 - 操作 3交换值 3 和 4 3 4 2 5 2 3 6 3 5注意以下也是经过类型 1 和 2 操作后表格的一种可能状态但它不是字典序最小的因为第一行的第二项比正确答案中的要大。4 6 5 3 5 4 2 4 3分析在交换两行的时候每个数所在的列数不变同一行的数仍旧在同一行在交换两列的时候每个数所在的行数不变同一列的数也仍旧在同一列可以发现前两种操作完成后原本在一行的数还是在同一行只是换了顺序每列也一样。操作333的性质我考试的时候没看出来交换数值aaa和bbb之后数值相同的位置仍然数值相同只是换了一个数值。bbb的个数变成了原本数值aaa的个数aaa的个数变成了原本数值bbb的个数我们发现只要数每个数出现的次数就能确定这个位置上原本的数。参照题目中3×33 \times 33×3的表格出现一次的是222和666两次的是333和555三次的是444。再画出一个5×55 \times 55×5的表格2 3 4 5 6 3 4 5 6 7 4 5 6 7 8 5 6 7 8 9 6 7 8 9 10得出规律出现cntxcnt_xcntx​次的数原本应该是cntx1cnt_x1cntx​1或2 ⋅n−cntx12\,·n-cnt_x12⋅n−cntx​1如何确定具体是哪个呢先从222和2 ⋅n2\,·n2⋅n入手和222同行或同列的是222到n1n1n1和2 ⋅n2\,·n2⋅n同行或同列的是n1n1n1到2 ⋅n2\,·n2⋅n也就是说我们只要确定222所在的行和2 ⋅n2\,·n2⋅n所在的行的数值对应关系怎么确定对应关系在实现里就可以覆盖表格中的所有数值。由于222和2 ⋅n2\,·n2⋅n的位置可以对换所以我们分成两个表格讨论最后取字典序最小的答案。实现先枚举222所在的行这里的数值都小于等于n1n1n1cntxcnt_xcntx​最大是nnn所以可以确定每个位置上的值是cnt[a[i][j]]1将a[i][j]与cnt[a[i][j]]1建立对应关系再枚举2 ⋅n2\,·n2⋅n所在的行这里的数值都大于等于n1n1n1将a[i][j]与2*n-cnt[a[i][j]]1建立对应关系再通过对应关系处理出答案表格即可。#includebits/stdc.husingnamespacestd;intn,a[1005][1005],cnt[1000005],px1,px2;intaa[2][1005][1005],go[1000005];//aa:answer go:correspondence//px1,px2:record the rows that have 2 or 2nintmain(){cinn;for(inti1;in;i)for(intj1;jn;j)cina[i][j],cnt[a[i][j]];if(n1){couta[1][1]endl;return0;}//edge case,we cant find px2 if n equals to 1for(inti1;in;i)for(intj1;jn;j)if(cnt[a[i][j]]1)if(px1)px2i;elsepx1i;for(intj1;jn;j){go[a[px1][j]]cnt[a[px1][j]]1;go[a[px2][j]]2*n-cnt[a[px2][j]]1;}for(inti1;in;i)for(intj1;jn;j)aa[0][i][j]go[a[i][j]];for(intj1;jn;j){go[a[px2][j]]cnt[a[px2][j]]1;go[a[px1][j]]2*n-cnt[a[px1][j]]1;}for(inti1;in;i)for(intj1;jn;j)aa[1][i][j]go[a[i][j]];intrec-1;for(inti1;in;i){for(intj1;jn;j){if(aa[0][i][j]aa[1][i][j]){rec0;break;}elseif(aa[0][i][j]aa[1][i][j]){rec1;break;}}if(rec!-1)break;}for(inti1;in;i){if(i1)coutendl;for(intj1;jn;j){if(j1)cout ;coutaa[rec][i][j];}}return0;}