竹子建站模板怎么下载织梦网站怎么做模板

竹子建站模板怎么下载,织梦网站怎么做模板,苏州工业园区属于哪个区,重庆建网站推广公司P10454 奇数码问题 题目描述 你一定玩过八数码游戏#xff0c;它实际上是在一个 333 \times 333 的网格中进行的#xff0c;111 个空格和 1∼81 \sim 81∼8 这 888 个数字恰好不重不漏地分布在这 333 \times 333 的网格中。 例如#xff1a; 5 2 8 1 3 _ 4 6 7在游戏过程中它实际上是在一个3×33 \times 33×3的网格中进行的111个空格和1∼81 \sim 81∼8这888个数字恰好不重不漏地分布在这3×33 \times 33×3的网格中。例如5 2 8 1 3 _ 4 6 7在游戏过程中可以把空格与其上、下、左、右四个方向之一的数字交换如果存在。例如在上例中空格可与左、上、下面的数字交换分别变成5 2 8 5 2 _ 5 2 8 1 _ 3 1 3 8 1 3 7 4 6 7 4 6 7 4 6 _奇数码游戏是它的一个扩展在一个n×nn \times nn×n的网格中进行其中nnn为奇数111个空格和1∼n2−11 \sim n^2-11∼n2−1这n2−1n^2-1n2−1个数恰好不重不漏地分布在n×nn \times nn×n的网格中。空格移动的规则与八数码游戏相同实际上八数码就是一个n3n3n3的奇数码游戏。现在给定两个奇数码游戏的局面请判断是否存在一种移动空格的方式使得其中一个局面可以变化到另一个局面。输入格式多组数据对于每组数据第111行输入一个整数nnnnnn为奇数。接下来nnn行每行nnn个整数表示第一个局面。再接下来nnn行每行nnn个整数表示第二个局面。局面中每个整数都是0∼n2−10 \sim n^2-10∼n2−1之一其中用000代表空格其余数值与奇数码游戏中的意义相同保证这些整数的分布不重不漏。输出格式对于每组数据若两个局面可达输出TAK否则输出NIE。输入输出样例 #1输入 #13 1 2 3 0 4 6 7 5 8 1 2 3 4 5 6 7 8 0 1 0 0输出 #1TAK TAK说明/提示1≤n5001 \le n 5001≤n500奇数码问题题解这是我针对奇数码问题的解题题解核心依托归并排序求逆序对来完成可达性判断下面结合我的代码详细拆解解题思路。一、题目分析本题要求我们判断两个n×nn \times nn×nnnn为奇数的奇数码局面是否可达其中000代表空格其余数字为1∼n2−11 \sim n^2-11∼n2−1空格仅能与上下左右相邻数字交换。这是一道经典的数码问题核心在于掌握奇数码局面可达性的判定定理同时需要高效求解逆序对。二、核心解题思路1. 奇数码可达性判定定理对于nnn为奇数的奇数码问题两个局面可达的充要条件是忽略空格数字000后两个局面的数字序列的逆序对数量奇偶性相同。逆序对定义对于一个数字序列若存在两个数aia_iai​和aja_jaj​iji jij满足aiaja_i a_jai​aj​则称这对数字为一个逆序对。为什么该定理成立因为空格的移动与相邻数字交换不会改变整个序列逆序对数量的奇偶性因此只有当两个局面的逆序对奇偶性一致时才可以通过移动空格实现相互转化。2. 逆序对的高效求解由于nnn最大接近500500500n2n^2n2最大为250000250000250000普通的暴力枚举O(n4)O(n^4)O(n4)会超时因此我采用归并排序求解逆序对时间复杂度为O(mlog⁡m)O(m \log m)O(mlogm)mn2m n^2mn2能够高效处理最大数据量。三、代码逐部分解析intn;inta[250005];intt[250005];longlongans,ans1,ans2;voidms(intl,intr){if(lr)return;// 递归终止条件区间仅含一个元素无需排序intm(lr)/2;ms(l,m);// 递归处理左区间 [l, m]ms(m1,r);// 递归处理右区间 [m1, r]intlpl;// 左区间指针intrpm1;// 右区间指针inttpl;// 临时数组t的指针while(lpmrpr){if(a[rp]a[lp]){t[tp]a[rp];if(a[rp]!0){// 忽略空格0不统计0参与的逆序对ansm-lp1;// 核心统计逆序对数量}tp;rp;}else{t[tp]a[lp];tp;lp;}}// 处理左区间剩余元素while(lpm){t[tp]a[lp];tp;lp;}// 处理右区间剩余元素while(rpr){t[tp]a[rp];tp;rp;}// 将临时数组的有序元素复制回原数组afor(intil;ir;i){a[i]t[i];}return;}longlongcalc(intx){for(inti1;ix*x;i){cina[i];// 读取x*x个元素将二维矩阵展平为一维数组}ans0;// 初始化逆序对数量为0ms(1,x*x);// 调用归并排序统计逆序对returnans;// 返回当前局面的逆序对数量}intmain(){while(cinn){// 多组输入直到输入结束ans1calc(n);// 计算第一个局面的逆序对数量ans2calc(n);// 计算第二个局面的逆序对数量if(ans1%2ans2%2){coutTAK\n;// 奇偶性相同可达}else{coutNIE\n;// 奇偶性不同不可达}}return0;}1. 全局变量说明nnn存储奇数码矩阵的边长因多组输入在循环中读取。a[]a[]a[]用于存储展平后的n×nn \times nn×n数码矩阵二维转一维方便归并排序处理数组大小250005250005250005是为了容纳500×500250000500 \times 500 250000500×500250000个元素预留充足余量。t[]t[]t[]归并排序的临时辅助数组用于合并两个有序子数组避免直接修改原数组导致数据混乱。ansansans临时存储单个局面的逆序对数量ans1ans1ans1、ans2ans2ans2分别存储两个输入局面的逆序对数量。2. 归并排序求逆序对ms 函数函数功能对aaa数组的[l,r][l, r][l,r]区间进行归并排序同时统计该区间内忽略000后的逆序对数量累加到全局变量ansansans中。核心逻辑合并阶段统计逆序对当a[rp]a[lp]a[rp] a[lp]a[rp]a[lp]时说明a[rp]a[rp]a[rp]与左区间中从lplplp到mmm的所有元素都构成逆序对因此逆序对数量增加m−lp1m - lp 1m−lp1同时通过a[rp]!0判断跳过空格000不统计其参与的逆序对符合可达性判定定理的要求。归并排序的稳定性保证了在统计逆序对时不会重复或遗漏是高效求解逆序对的经典方法。3. 读取局面并计算逆序对calc 函数函数功能读取一个x×xx \times xx×x的数码局面将其展平为一维数组后调用归并排序函数计算逆序对数量并返回该值。二维转一维无需额外存储二维数组直接按行读取所有元素存入aaa数组简化了数据处理逻辑同时不影响逆序对的统计结果因为矩阵的行优先展平不改变数字之间的相对位置关系。4. 主函数多组输入处理与可达性判断多组输入处理使用while(cinn)循环读取每组数据的边长nnn适配题目多组输入的要求。可达性判断通过比较两个局面逆序对数量的奇偶性若相同则输出TAK可达否则输出NIE不可达完全符合奇数码可达性判定定理。四、总结本题的核心是掌握奇数码问题的可达性判定定理以及使用归并排序高效求解逆序对。我的代码通过“二维矩阵展平 归并排序统计逆序对 奇偶性判断”的流程高效且准确地解决了该问题能够适配n500n 500n500的最大数据规模。