HDU6048Puzzle

题目连接

题意

​ 有一个 n×m 大的拼图盒，共有 n×m−1 个拼图块，拼图原本为拼好的状态。将所有拼图块取出来并按升序排好，每一轮取出剩余拼图序列中的第 1 块，第 P+1 块，第 2×P+1 块,….，第 n×P+1 块。按顺序放会拼图盒中。在所有拼图块均放回后，问是否能将拼图拼回原来的样子。

分析

​ 官方题解 中证明的很详细了，证明方面不再复述。任意大小的拼图均能够转换到仅剩余右下角 2×2 的拼图未确定，而其他拼图块回到原位的状态。枚举 2×2 大小拼图的所有情况，容易发现仅在逆序对为偶数时能够拼回原图。而右下角 2×2 的拼图的逆序对奇偶性和拼图初始的逆序对奇偶性相同，所以只要求出拼图初始时的逆序对奇偶性即可。求解逆序对数可以考虑所选取的每个拼图产生的贡献，不难发现贡献呈现一个等差数列的结果，其公差为 P−1 。于是快速计算总的逆序对数了。详细过程可以参考代码。

代码

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> using namespace std; int main(){ int T,n,m,p; cin>>T; while(T--){ scanf("%d %d %d",&n,&m,&p); int now=n*m-1,cnt=0; while(now>p){ int tmp=(now-1)/p+1; cnt+=tmp*(tmp-1)/2*(p-1); now-=tmp; } if(cnt&1) printf("NO\n"); else printf("YES\n"); } }