[TIOJ 1405] 神秘的鏡子盒

這題真的蠻好玩的XD 想了好久才想出來。但是作法好難寫清楚阿......而且又寫了好長，我自己也快看不懂在寫甚麼了，整個解也有點破破碎碎的。希望徵求更好的作法或是更簡潔的理解方法QQ

作法：

首先要觀察到，每加一面鏡子其實是把兩條入射光交換。以範測的圖為例，如果在 2 右邊 3 上面的那個格子放一面鏡子，其實就等價於把從 2 號射入的光和從 3 號射入的光交換。所以每一種鏡子的放法都會對應到一個 1 ~ m+n 的排列，例如範測對應到的就是 2 , 5 , 3 , 1 , 4 ，其中 a[ i ] 代表最後落在 i 號入射光方向的是從 a[ i ] 射入的光。

但這些「交換」的動作不能按任意順序作，一樣以範測的圖為例，總不能 5射出的光線和 2 射出的光線交換之後，再和 3 射出的光線交換。所以交換的順序必須按照： ( n+1,n ) , ( n+1 , n-1 ) , ... , (n+1 , 1) , (n+2 , n) , ... , (n+2 , 1) , ... , ( n+m.n ) , ... , (n+m,1) 的順序進行，也就是按照這個順序依次決定這兩個數是否要交換。而我們的目的就是要把 1 2 3 4 5 交換成 2 5 3 1 4。以後就記 a 這個陣列代表目標的陣列 ( 像這裡就是 2 5 3 1 4 )。

(對了，上面的交換 ( x , y ) 指的是把位置在 x 的數和位置在 y 的數交換，而不是把 x 和 y 對調位置。)

總之現在問題變成，我們要想辦法把 1 2 3 ... m+n ，經過一些特定順序的交換兩數的操作之後，變成給定的 a_1 , a_2 , ... , a_(m+n) 。首先看按照那種順序作兩數交換可以造成怎樣的效果。我們會在 ( x , n ) , ( x , n-1 ) , ... , ( x , 1 ) 這些操作裡面選他的子序列出來操作，假設選的是 ( x , y_1 ) , ... , ( x , y_k ) 好了( y_1 > y_2 > ... > y_k )，那麼會發現經過這些操作之後，會把在 x 的數移到 y_1 位置，在 y_1 的數移到 y_2 位置，...，在 y_(k-1) 的數移到 y_k 位置，在 y_k 的數移到 x 位置。所以可以把整個交換的過程看成，對每個 x 屬於 [ n+1 , n+m ] ，都選幾個位在 1 ~ n 的東西，然後讓他們一起往左轉一格(?)。

有了這件事之後，就可以得到兩個很重要的性質：
(1) 如果 i <= n 且 b[ i ] <= n ，則 b[ i ] <= i 。
(2) 如果 i > n 且 b[ i ] > n ，則 b[ i ] >= i 。
其中 b[ i ] 是 a[ i ] 的反函數( 也就是滿足 b[ a[ i ] ] = i 的陣列，因為很類似反函數，所以我都叫他反函數，可以把他看成「 i 這個數在 a 陣列出現的位置是 b[ i ]  」 )。
這兩件事都可以由剛才得到的「交換的過程」推出來。並且由之後的作法可以得到這個條件是充要的。

再來回到目標的陣列，我們的目的是把 a_(n+1) , a_(n+2) , ... , a_(m+n) 依序歸位( 把需要的值拉過來這個位子放好 )，因為在作完和第 n+1 個位子有關的操作之後就不會再動到他了。而如果 a_(n+1) 歸位了，並且讓新的目標陣列也滿足上面兩個性質，就可以把 ( n , m ) 的問題化為 ( n , m-1 ) 的問題了。

但因為我們是把 1 , 2 , ... , n+m 交換成 a_1 , ... , a_(m+n) ，而當作完 a_(n+1) 並且化歸為 ( n , m-1 ) 的問題的時候，他已經不再是按照 1 , 2 , ... 的順序排好了。所以我們需要把上面的性質重述一次，因為新問題的 a 與 b 已經不再是舊問題的 a 與 b 了，這樣會造成混淆。

假設交換到目前為止的數列是 a0 ( 所以在一開始他就是 1 ~ n+m )，還有他的反函數 b0 ，那麼這時候我們想要將 a0 經過那些交換過程變成 a ，那麼那兩個性質就會變成：
(1) 如果 i <= n 且 b[ a0[ i ] ] <= n ，則 b[ a0[ i ] ] <= i 。
(2) 如果 i > n 且b[ a0[ i ] ] > n ，則 b[ a0[ i ] ] >= i 。
其實就是原封不動的把 b[ ] 換成 b[ a0 [ ] ]。這個式子看起來很恐怖，但仔細想想，剛才那個性質告訴我們的是「當位置在 i 的數即將被移到位置 j 的時候，它滿足的性質」，而在這裡，位置在 i 的數就是 a0[ i ] ，而他即將要到的位置就是滿足 a[ j ] = a0[ i ] 的 j ，也就是 b[ a0[ i ] ] ，所以就必須要求 b[ a0 [ ] ] 這個陣列滿足上述性質。

回到我們要如何把 a[ x ] 歸位的問題( x = n+1 ~ n+m )，如果 a0[ x ] = a [ x ]，那就甚麼都不用作，繼續作 x+1 。如果不一樣的話，我們要把值等於 a[ x ] 的數換到 x 的位子，而這個數就位於 b0 [ a [ x ] ] 。接下來我覺得要建立圖像會比較好理解，我們考慮對每個 i ，從 i 到 b [ a0 [ i ] ] 都連一條有向邊，那麼根據上面的性質，圖形大概會長的像這樣：

簡單來說就是，從一個點開始跳，如果他在 1~n 的部分，那他只能往左跳，或是跳到 n+1 ~ n+m 的部分。而如果它在 n+1 ~ n+m 的部分，那他只能往右跳，或是跳到 1 ~ n 的部分。而之後這個圖形其實應該代表的是「落在這個位置的數的目的地是哪裡」，所以之後也可以拋開他就是 b[ a0 [ ] ] 這件事了，反正就是每個數都指向他的目的地，並且這些箭頭會有上面那個性質( 在 1~n 就往左跳那個 )。

而藍色線段的起點位置就是 b0 [ a [ x ] ] ，我們需要把位在藍色邊起點的那個數交換來 x 的位置。如果直接把他根 x 交換的話，新的圖形就會變成：

這樣箭頭們就違背了他的良好性質了！我們的目的是一直保持箭頭們的良好性質，這樣作到 n+m 的時候就會自然而然的所有元素都排好了，所以直接換不是對的。我們考慮 x 往左跳經過的點是 x_1 , x_2 , ... , x_t , x_(t+1) , ... ，其中目標的藍色點落在 x_t 和 x_(t+1) 之間( 就算有重合也會得到換法是一樣的 )，或是 x_t 在目標點右邊，但 x_(t+1) 跳到 n+1~n+m 的區間了，這樣我們考慮把 x_t , x_(t-1) , ... , x_1 , x 往左轉一格，這樣第一張圖在轉完之後就會變成：

這樣就成功了！！！因為其他沒有動到的箭頭們都不變，而被動到的箭頭也滿足了良好性質，所以我們成功的把 a_x 歸位，並且維持良好性質了！！！所以一路做下去就可以把 1~n+m 換成 a 了，並且在換的過程要記得維護好 a0 和 b0 陣列。

PS. 其實讀前 n+m 個數就可以決定 a 陣列了，但不知道為什麼不把 2n+2m 個數讀完他就會送我WA  QQ。

code :

#include<bits/stdc++.h>
#include"lib1405.h"
using namespace std;
const int maxn=2000+10 ;
 
int a[maxn],b[maxn] ; /// b is inv of a
int a0[maxn],b0[maxn] ; /// b0 is inv of a0 , swap a0 -> a
int ans[maxn][maxn] ;
int n,m ;
 
void SWAP(int x,int y)
{
    ans[y][x-n]=1 ;
    swap(a0[x],a0[y]) ;
    swap(b0[a0[x]],b0[a0[y]]) ;
}
 
int tmp[maxn] ;
main()
{
    scanf("%d%d",&n,&m) ;
    for(int i=1;i<=n+m;i++)
    {
        int x ; scanf("%d",&x) ;
        if(x<=2*n+m) a[2*n+m+1-x]=i , b[i]=2*n+m+1-x ;
        else a[3*n+2*m+1-x]=i , b[i]=3*n+2*m+1-x ;
    }
    for(int i=1;i<=n+m;i++) { int x ; scanf("%d",&x) ; }
    for(int i=1;i<=n+m;i++) a0[i]=b0[i]=i ;
 
    for(int i=1;i<=n;i++) if(b[i]<=n && b[i]>i) abort() ;
    for(int i=n+1;i<=n+m;i++) if(b[i]>n && b[i]<i) abort() ;
 
    for(int i=n+1;i<=n+m;i++)
    {
        if(a0[i]==a[i]) continue ;
        int cnt=0 ;
        for(int j=i; b[a0[j]]<=n && b[a0[j]]>b0[a[i]];j=b[a0[j]])
            tmp[cnt++]=b[a0[j]] ;
        tmp[cnt++]=b0[a[i]] ;
        for(int j=0;j<cnt;j++) SWAP(i,tmp[j]) ;
    }
    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++)
        Report(ans[i][j]) ;
}