N數(shù)碼問題

首先，先貫徹一個(gè)理念。奇偶性很神奇，對于一類問題，如果屬于同種性質(zhì)（奇偶性相同），那么它們就是完全相同（這個(gè)在某種意義上說）的，，一些問題如果奇偶性相同那么里面涉及的問題都是等價(jià)的。

數(shù)碼問題考慮的是逆序?qū)Φ钠媾夹浴⒍S數(shù)組排成一維，空格和左右的數(shù)交換不改變逆序?qū)€(gè)數(shù)（實(shí)際上在一維中，空格和左右的數(shù)交換，忽略空格的話，交換前后一維數(shù)組的排列順序是完全不變的）。

4*4空間5 6 7 8 \n 9 10 % 12 --> 5 6 % 8 \n 9 10 7 12 空格和上面的數(shù)7交換相當(dāng)于7依次和后面的8 9 10交換共N-1個(gè)數(shù)。將7 8 9 10作為一個(gè)整體，內(nèi)部交換不改變外部的逆序?qū)€(gè)數(shù)（也就是這個(gè)整個(gè)前后數(shù)的逆序?qū)€(gè)數(shù)）。在這個(gè)整體中，8 9 10之間的逆序?qū)€(gè)數(shù)也是不改變的，會改變的只有7和8 9 10之間的逆序?qū)€(gè)數(shù)（共形成N-1個(gè)逆序?qū)?#xff09;。這個(gè)整體中，原來是逆序的變成正序，原來正序變成逆序，因此原來逆序?qū)?shù)x+交換后的逆序?qū)?shù)y=N-1;當(dāng)N為奇數(shù)時(shí)，x+y=奇數(shù)，x,y一奇一偶，差值為奇數(shù) 當(dāng)N為偶數(shù)時(shí)，x+y=偶數(shù)，x,y同奇偶性，差值為偶數(shù)

• 兩個(gè)不同狀態(tài)相互可達(dá)的充要條件：“ 兩個(gè)狀態(tài)逆序?qū)?shù)之差 ” 和 “ 兩個(gè)狀態(tài)空格所在行數(shù)之差 ” 奇偶性相同。（這里考慮空格所在行數(shù)之差是因?yàn)?#xff0c;空格只有上下交換才會改變逆序?qū)?shù)）

2019年杭電多校聯(lián)賽-Just an Old Puzzle

• 15數(shù)碼是否有解問題

#include <bits/stdc++.h> using namespace std; #define fre freopen("C:\\Users\\22765\\Desktop\\in.txt","r",stdin); #define ms(a) memset((a),0,sizeof(a)) #define rep(i,a,b) for(register int (i)=(a);(i)<(b);++(i)) #define sf(x) scanf("%d",&(x)) #define reg register typedef long long LL; const int inf=(0x7f7f7f7f); const int maxn=3000; int a[20];int main(){int t;sf(t);int x,r;while(t--){int k=0;rep(i,0,4)rep(j,0,4){sf(x);if(x==0){r=i;continue;}a[k++]=x;}//計(jì)算逆序?qū)梢允褂脴錉顢?shù)組，這里規(guī)模小，直接爆力 int ni=0;rep(i,0,k){rep(j,0,i)if(a[j]>a[i])ni++;}if((ni+3-r)&1)puts("No");else puts("Yes");}return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/sstealer/p/11296391.html

總結(jié)

以上是生活随笔為你收集整理的# N数码问题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。