[遞推]CTSC1999 月亮之眼 Moon 解題報告

         IOI1999 中國國家隊選拔賽 月亮之眼
【問題描述】
    吉兒是一家古董店的老闆娘，由於她經營有道，小店開得紅紅火火。昨天，吉兒無意之中得到了散落民間幾百年的珍寶—月亮之眼。吉兒深知“月亮之眼”價值連城：它是由許多珍珠相連而成的，工匠們用金線連接珍珠，每根金線連接兩個珍珠；同時又對每根金線染上兩種顏色，一半染成銀白色，一半染成黛黑色。由于吉兒自小熟讀古籍，所以還曉得“月亮之眼”的神祕傳說：“月亮之眼”原是一個古代寺廟的寶物，原本是掛在佛堂的一根頂樑柱上的，整個寶物垂直懸掛，所有珍珠排成一線，且都鑲嵌在柱子裡，而每一根金線又都是繃緊的，並且金線的銀白色一端始終在黛黑色一端的上方；然而，在一個月圓之夜，“月亮之眼”突然從柱裡飛出，掉落下來，寶物本身完好無損，只是僧侶們再也無法以原樣把“月亮之眼”嵌入柱子中了。吉兒望著這個神祕的寶物，回憶著童年讀到的傳說，頓時萌發出恢復“月亮之眼”的衝動，但是擺弄了幾天依舊沒有成功。

現在，要麻煩您來幫助吉兒完成這項使命。

您要設計一個程序，對於給定的“月亮之眼”進行周密分析，然後給出這串寶物幾百年前嵌在佛堂頂樑柱上的排列模樣。給定的“月亮之眼”有N個珍珠和P根金線，所有珍珠按一定順序有了一個序號：1、2…、N。

[廣度優先搜索]BYVoid魔獸世界模擬賽Stage.1 血色先鋒軍

血色先鋒軍

出題者連結：http://www.byvoid.com/

問題描述

巫妖王的天災軍團終於捲土重來，血色十字軍組織了一支先鋒軍前往諾森德大陸對抗天災軍團，以及一切沾有亡靈氣息的生物。孤立於聯盟和部落的血色先鋒軍很快就遭到了天災軍團的重重包圍，現在他們將主力只好聚集了起來，以抵抗天災軍團的圍剿。可怕的是，他們之中有人感染上了亡靈瘟疫，如果不設法阻止瘟疫的擴散，很快就會遭到滅頂之災。大領主阿比迪斯已經開始調查瘟疫的源頭。原來是血色先鋒軍的內部出現了叛徒，這個叛徒已經投靠了天災軍團，想要將整個血色先鋒軍全部轉化爲天災軍團！無需驚訝，你就是那個叛徒。在你的行蹤敗露之前，要儘快完成巫妖王交給你的任務。

軍團是一個N行M列的矩陣，每個單元是一個血色先鋒軍的成員。感染瘟疫的人，每過一個小時，就會向四周擴散瘟疫，直到所有人全部感染上瘟疫。你已經掌握了感染源的位置，任務是算出血色先鋒軍的領主們感染瘟疫的時間，並且將它報告給巫妖王，以便對血色先鋒軍進行一輪有針對性的圍剿。

輸入格式

第1行：四個整數N，M，A，B，表示軍團矩陣有N行M列。有A個感染源，B爲血色敢死隊中領主的數量。

接下來A行：每行有兩個整數x，y，表示感染源在第x行第y列。

接下來B行：每行有兩個整數x，y，表示領主的位置在第x行第y列。

輸出格式

第1至B行：每行一個整數，表示這個領主感染瘟疫的時間，輸出順序與輸入順序一致。如果某個人的位置在感染源，那麼他感染瘟疫的時間爲0。

樣例輸入

5 4 2 3

1 1

5 4

3 3

5 3

2 4

樣例輸出

3

1

3

樣例說明

如下圖，標記出了所有人感染瘟疫的時間以及感染源和領主的位置。

 【命題人的分析】

重溫題意，能夠注意到，瘟疫是以時間爲階段逐步擴張的，而題目又要求輸出某個血色領主最早的感染時間。所以，根據這個特性，自然地想到了寬搜的方法。

首先，將所有感染源加入隊列。然後，進入寬搜過程，將所有的格子搜索完畢，得到的即爲每個格子得最早感染時間。

時間複雜度O(M*N)

另外，還有一種算法：

對於所有的領主，枚舉這個領主到所有感染源的距離，取最小值即可。

時間複雜度O(A*B)

這種方法不能獲得滿分

這是一道簡單題，考察基礎算法。

 
【我的代碼】

/*BYVoid 魔獸世界模擬賽 Stage.1 血色先鋒軍*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
const int MAXN=0x7fffffff-2;
//bool used[501][501];
int mat[501][501];
int N,M;
int A,B;
const int step[5][2]={{0,0},{1,0},{-1,0},{0,1},{0,-1}};

class POINT
{
public:
    int x;
    int y;
};

POINT Bos[250001];
POINT Q[2000000];

void init()
{
    scanf("%d %d %d %d\n",&N,&M,&A,&B);
    for (int i=1;i<=N;i++)
    {
        for (int j=1;j<=M;j++)
        {
        //    used[i][j]=true;
            mat[i][j]=MAXN;
        }
    }
   
    int a,b;
    for (int i=1;i<=A;i++)
    {
        scanf("%d %d\n",&a,&b);
        mat[a][b]=0;
        //used[a][b]=false;
        Q[i-1].x=a;
        Q[i-1].y=b;
    }
   
    for (int i=1;i<=B;i++)
    {
        scanf("%d %d\n",&a,&b);
        Bos[i].x=a;
        Bos[i].y=b;
    }
    return;
}

void BFS()
{
    int q=A;
    int h=0;
    int Tx,Ty;
    int Nx,Ny;
   
    while(h<q)
    {
        Tx=Q[h].x,Ty=Q[h].y;
        //used[Tx][Ty]=false;
       
        for (int i=1;i<=4;i++)
        {
            Nx=Tx+step[i][0];
            Ny=Ty+step[i][1];
            if(Nx>=1 && Nx<=N && Ny>=1 && Ny<=M)
            {
                if(mat[Tx][Ty]+1<mat[Nx][Ny])
                {
                    mat[Nx][Ny]=mat[Tx][Ty]+1;
                    Q[q].x=Nx,Q[q].y=Ny;
                    q++;
                }
            }
        }
        h++;
    }
   
    for (int i=1;i<=B;i++)
    {
        Tx=Bos[i].x;
        Ty=Bos[i].y;
        cout<<mat[Tx][Ty]<<endl;
    }
   
    return;
}

int main()
{
    freopen("crusade.in","r",stdin);
    freopen("crusade.out","w",stdout);
    init();
    BFS();
    return 0;
}

[數據結構][隊列]USACO Dec07 Bronze Card Stacking 洗牌作弊 cheat

題目描述

譯 by CmYkRgB123

貝茜正在和她的N-1個奶牛朋友們玩撲克牌，她們用了一疊有K (N ≤ K ≤ 100,000 K是N的整倍數) 張牌的撲克。這疊撲克有 M = K/N 張“好牌”和 K-M 張“壞牌”。貝茜負責給大家發牌，當然，她想把所有的好牌發給自己。她非常喜歡贏。

她們坐成一圈，逆時針方向發牌。她的朋友們懷疑她會搞鬼，於是發明瞭一個特殊的發牌規則，試圖阻止貝茜搞鬼。她們把規則列舉如下：

從貝茜的右面的奶牛開始發牌。

每發一張牌，貝茜必須把接下來的 P (1 ≤ P ≤ 10) 張牌按原順序放到這疊撲克的最後。

逆時針方向發牌，對每個人都這樣。

然而，貝茜發了瘋，不顧一切的想贏。她請你幫她設計洗牌一個方案，使她能得到所有的“好牌”。每張牌按順序標號，第一張爲#1，第二張爲#2，等等。

輸入

第 1 行: 三個整數 N , K , P

輸出

第 1..M 行: 升冪順序排列，每行爲一張好牌的位置，使得貝茜她能得到所有的“好牌”。

樣例輸入

3 9 2

樣例輸出

3

7

8

【分析】

這是一個比較簡單的隊列題，隊列不用開的很大，11,000,000就行了。

設置兩個指針，一個隊頭、一個隊尾，每次發完牌後，隊頭指針和隊尾指針都向後移動P位。發牌時，判斷這張牌是不是Bessie的（如果A%N==0，則第A張發下去的牌是Bessie的），最後把Bessie的牌按從大到小的順序快排一下，輸出即可。

這種算法的效率很高，看看我的評測結果：

正在连接评测机...

已连接到评测机

GRID	1
名称	Flitty
系统版本	1.00
备注	COGS 1号评测机 Flitty

正在编译...

编译成功

测试点	结果	得分	运行时间	内存使用	退出代码
1	正确	9	0.000 s	47149 KB	0
2	正确	9	0.000 s	47149 KB	0
3	正确	9	0.000 s	47149 KB	0
4	正确	9	0.000 s	47149 KB	0
5	正确	9	0.000 s	47149 KB	0
6	正确	9	0.001 s	47149 KB	0
7	正确	9	0.003 s	47149 KB	0
8	正确	9	0.004 s	47149 KB	0
9	正确	9	0.009 s	47149 KB	0
10	正确	9	0.011 s	47149 KB	0
11	正确	9	0.193 s	47149 KB	0

运行完成

运行时间 0.223 s

平均内存使用 47149 KB

测试点通过状况 AAAAAAAAAAA

得分：100

恭喜你通过了全部测试点!

本題測試數據下載：http://ace.delos.com/TESTDATA/cheat.zip

【我的代碼】

#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
int Bessie[1000001];
int B=0;

int Q[11000001];
int N,P,K;
int G=0;
int q,h;

void init()
{
    scanf("%d %d %d",&N,&K,&P);
    for (int i=1;i<=K;i++)
        Q[i]=i;
    G=K/N;
}

void Put(int i)
{
    for (int j=i+1;j<=P+i;j++)
    {
        q++;
        Q[q]=Q[j];
        h++;
    }
}

int cmp(const void *a,const void *b)
{
    return *(int *)a-*(int *)b;
}

void Work()
{
    q=K;
    h=0;
    int tmp=0;
    while(B<G && h<=q)
    {
        h++;
        tmp++;
        if(tmp%N==0)
        {
            B++;
            Bessie[B]=Q[h];
        }
        Put(h);
    }
   
    qsort(Bessie+1,B,sizeof(int),cmp);
    for (int i=1;i<=B;i++)
        cout<<Bessie[i]<<endl;
}

int main()
{
    freopen("cheat.in","r",stdin);
    freopen("cheat.out","w",stdout);
    init();
    Work();
    return 0;
}

[廣度優先搜索]USACO Feb07 Bronze 青銅蓮花池 Bronze Lilypad (bronlily) 解題報告

譯 By CmYkRgB123

【題目描述】

Farmer John 建造了一個美麗的池塘，用於讓他的牛們審美和鍛鍊。這個長方形的池子被分割成了 M 行和 N 列( 1 ≤ M ≤ 30 ; 1 ≤ N ≤ 30 ) 正方形格子的 。某些格子上有驚人的堅固的蓮花，還有一些岩石，其餘的只是美麗，純淨，湛藍的水。

貝茜正在練習芭蕾舞，她從一個蓮花跳躍到另一個蓮花，當前位於一個蓮花。她希望在蓮花上一個一個的跳，目標是另一個給定蓮花。她能跳既不入水，也不到一個岩石上。

令門外漢驚訝的是，貝茜的每次的跳躍像國際象棋中的騎士一樣：橫向移動M1(1 ≤M1 ≤ 30 )，縱向移動然後量M2 (1 ≤M2 ≤ 30 ;M1 ≠ M2 ) ，或縱向移動然後量M1，橫向移動M2。貝茜有時可能會有多達8個選擇的跳躍。

給定池塘的佈局和貝茜的跳躍格式，請確定貝茜從從她的出發位置，到最終目的地，最小的跳躍次數，貝茜在給出測試數據一定可以跳到目的地。

輸入

第 1 行: 四個用空格隔開的整數: M, N, M1, M2

第 2..M + 1 行: 第 i + 1 行 有 N 個整數，表示該位置的狀態: 0 爲水; 1 爲蓮花; 2 爲岩石; 3 爲貝茜開始的位置; 4 爲貝茜要去的目標位置.

輸出

第 1 行: 一個整數，從起始點到要去的位置，貝茜最小的跳躍次數。

樣例輸入

4 5 1 2

1 0 1 0 1

3 0 2 0 4

0 1 2 0 0

0 0 0 1 0

樣例輸出

2

輸入解釋

貝茜從第2行第1個位置開始，她的目標在第2行最右邊。幾個

輸出解釋

貝茜聰明地跳躍到了第1行第3個位置，然後就到了目的地。

【分析】

這是跳馬問題的變形，但是這個題不能使用深度優先搜索，因為遞歸會爆棧的。我們可以開一個二維的布爾數組，當然整型數組亦可，由於題目中給的岩石和水的作用一樣，直接賦值為false或0，讀入時如果遇到3就記錄下起點的橫縱坐標，如果遇到4就記錄下終點的橫縱坐標，然後把所有的荷花置為true或1。然後處理8種移動方式，可參照2002年NOIP普及組的“過河卒”一題。

接著進行廣度優先搜索，把每一個到過的點全部賦值為false或0，以免重複。還可以加一個剪枝優化：如果當前的跳躍次數不小於已經得到的最優值，直接跳過這個點即可。這樣，就可以把時間複雜度壓得很低了。

 我的測評結果：

正在连接评测机...

已连接到评测机

GRID	1
名称	Flitty
系统版本	1.00
备注	COGS 1号评测机 Flitty

正在编译...

编译成功

测试点	结果	得分	运行时间	内存使用	退出代码
1	正确	7	0.000 s	58877 KB	0
2	正确	7	0.000 s	58877 KB	0
3	正确	7	0.001 s	58877 KB	0
4	正确	7	0.001 s	58877 KB	0
5	正确	7	0.001 s	58877 KB	0
6	正确	7	0.000 s	58877 KB	0
7	正确	7	0.000 s	58877 KB	0
8	正确	7	0.000 s	58877 KB	0
9	正确	7	0.000 s	58877 KB	0
10	正确	7	0.000 s	58877 KB	0
11	正确	7	0.000 s	58877 KB	0
12	正确	7	0.000 s	58877 KB	0
13	正确	7	0.000 s	58877 KB	0

运行完成

运行时间 0.005 s

平均内存使用 58877 KB

测试点通过状况 AAAAAAAAAAAAA

得分：100

恭喜你通过了全部测试点!

【代碼】

#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
class BRON
{
public:
    int x;
    int y;
    int t;
};

int mat[50][50];
int step[9][2];
int S=0x7fffffff;
int M,N,M1,M2;
int Sx,Sy;
int Ex,Ey;
bool flag[31][31];


void init()
{
    scanf("%d %d %d %d",&M,&N,&M1,&M2);
   
    for (int i=1;i<=M;i++)
        for (int j=1;j<=N;j++)
            flag[i][j]=true;
   
    int tmp;
    for (int i=1;i<=M;i++)
    {
        for (int j=1;j<=N;j++)
        {
            scanf("%d",&tmp);
            if(tmp==0 || tmp==2)
                mat[i][j]=0;
            else
                mat[i][j]=tmp;
            if(mat[i][j]==3)
            {
                Sx=i;
                Sy=j;
                continue;
            }
            if(mat[i][j]==4)
            {
                Ex=i;
                Ey=j;
                continue;
            }
        }
    }
    step[1][0]=M1,step[1][1]=M2;
    step[2][0]=M1,step[2][1]=-M2;
    step[3][0]=-M1,step[3][1]=M2;
    step[4][0]=-M1,step[4][1]=-M2;
    step[5][0]=M2,step[5][1]=M1;
    step[6][0]=M2,step[6][1]=-M1;
    step[7][0]=-M2,step[7][1]=M1;
    step[8][0]=-M2,step[8][1]=-M1;
    return;
}

BRON Q[5000000];
void bfs()
{
    int q=1;
    int h=0;
    Q[0].x=Sx,Q[0].y=Sy,Q[0].t=0;
    int Tx,Ty,Tt;
    int Nx,Ny;
    while(h<q)
    {
        Tx=Q[h].x,Ty=Q[h].y,Tt=Q[h].t;
       
        if(Tx==Ex && Ty==Ey)
        {
            if(Tt<S)
                S=Tt;
            h++;
            continue;
        }
       
        if(Tt>=S)
        {
            h++;
            continue;
        }
       
        if(!flag[Tx][Ty])
        {
            h++;
            continue;
        }
       
        flag[Tx][Ty]=false;
       
        for (int i=1;i<=8;i++)
        {
            Nx=step[i][0]+Tx;
            Ny=step[i][1]+Ty;
            if(Nx>=1 && Nx<=M && Ny>=1 && Ny<=N && flag[Nx][Ny])
            {
                if(mat[Nx][Ny]!=0)
                {
                    Q[q].x=Nx;
                    Q[q].y=Ny;
                    Q[q].t=Tt+1;
                    q++;
                }
            }
        }
        h++;
    }
    cout<<S<<endl;
}

int main()
{
    freopen("bronlily.in","r",stdin);
    freopen("bronlily.out","w",stdout);
    init();
    bfs();
    return 0;
}