2011年11月2日星期三

[字符串處理][模擬]OI練習題：IP網絡管理員 networkip

【問題描述】

Alex 是一個 IP 網絡管理員。他的顧客擁有一堆私人 IP 地址，他想把這些 IP 地址組成一個最小的 IP 網絡。

每個 IP 地址是由 4 個 byte 類型數順次由 3 個 dot 連接而成，形如 'byte0.byte1.byte2.byte 3' （不計引號）。每個 byte 類型數是一個 0 至 255 （包括 0 和 255 ）的首位不爲零的十進制整數。

IP 網絡由網絡地址和網絡掩碼來描述，他們的描述方式與 IP 地址相同。爲了準確的理解 IP 地址、網絡地址和網絡掩碼的意義，你需要把它們按照二進制表示寫出。他們的二進制表示都由 32 bits 組成： 8 bits 描述 byte0 、然後 8 bits 描述 byte1 、然後 8 bits 描述 byte2 、最後 8 bits 描述 byte3 。

特定的 IP 網絡包含 2^n 個 IP 地址。它的網絡掩碼的前 32-n 個 bits 爲 1 ，後 n 個 bits 爲 0 ；其網絡地址的前 32–n 個 bits 爲 0 或者 1 ，後 n 個 bits 爲 0 。這個 IP 網絡包含了所有前 32–n 個 bits 與其網絡地址相同且後 n 個 bits 任意的所有 IP 地址，總共 2^n 個。我們說一個 IP 網絡比另一個 IP 網絡小，當且僅當它包含更少的 IP 地址。

比如，網絡地址和網絡掩碼分別爲 194.85.160.176 和 255.255.255.248 的 IP 網絡包含了從 194.85.160.176 至 194.85.160.183 的 IP 地址。

【輸入格式】

第一行一個正整數 m （ 1 <= m <= 1000 ）表示 Alex 的 IP 地址數。然後 m 行每行描述一個 IP 地址。

【輸出格式】

兩行，分別表示能夠包含所有 IP 地址的最小 IP 網絡的網絡地址和網絡掩碼。

【輸入輸出樣例】

networkip.in

194.85.160.177

194.85.160.183

194.85.160.178

networkip.out

194.85.160.176

255.255.255.248

【分析】

這題看著很難，其實很簡單，就是一個簡單的字符串處理問題。

首先是IP地址的讀入，用scanf讀入會很方便的。

然後統計這N個IP地址二進制表示從前面開始的最長的公共部分，記為S，即這N個IP地址二進制表示從前面數S個數都是相同的。

根據題意：把子網掩碼的前S位置為1，後32-S位為0。

把IP地址的後32-S位置為0，然後再轉換為10進制輸出即可。

例如樣例：
這三個IP地址的二進制表示為：
194.85.160.177 11000010 01010101 10100000 10110001 194.85.160.183 11000010 01010101 10100000 10110111 194.85.160.178 11000010 01010101 10100000 10110010
可以看出，這三個IP地址的二進制表示有29位是相同的。

根據題意，把子網掩碼的前S位置為1，後32-S位為0：
Subnet Mark：11111111 11111111 11111111 11111000

把IP地址的後32-S位置為0，即為最小IP地址：
IP Adress：11000010 01010101 10100000 10110000

然後把Subnet Mark和IP Address轉換為10進制輸出即可。

11111111 11111111 11111111 11111000 =>255.255.255.248

11000010 01010101 10100000 10110000 =>194.85.160.176

【我的代碼】

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;

class IPAddress
{
public:
    int b[5];
    char B[5][10];
    IPAddress()
    {
       for (int i=1;i<=4;i++)
           memset(B[i],'\0',sizeof(B[i]));
    }
}IP[1001];

int N;
int Same=0;
char Sam[5][10];

int power(int base,int index)
{
    int l=1;
    for (int i=1;i<=index;i++)
       l*=base;
    return l;
}

void num2str(int num,char *s,int base)
{
    char map[] = {"0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"};
    char dst[64];
    int i=0,n;
    while(num)
    {
       dst[i++]=map[num%base];
       num/=base;
    }
    dst[i]='\0';
    n=i;
    for(i=n-1;i>=0;--i)
    {
       s[n-1-i]=dst[i];
    }
    s[n]='\0';
}

void init()
{
    for (int i=1;i<=4;i++)
       memset(Sam[i],'\0',sizeof(Sam[i]));

    scanf("%d\n",&N);
    char tmp[10];
    for (int i=1;i<=N;i++)
    {
       scanf("%d.%d.%d.%d\n",&IP[i].b[1],&IP[i].b[2],&IP[i].b[3],&IP[i].b[4]);
       for (int j=1;j<=4;j++)
       {
           memset(tmp,'\0',sizeof(tmp));
           num2str(IP[i].b[j],tmp,2);
           int len=strlen(tmp);
           int top=0;
           for (int k=0;k<8-len;k++)
           {
               IP[i].B[j][k]='0';
               top++;
           }
           for (int k=0;k<len;k++)
           {
               IP[i].B[j][top]=tmp[k];
               top++;
           }
       }
    }
}

void work()
{
    for (int k=1;k<=4;k++)
    {
       for (int i=0;i<8;i++)
       {
           //bool ok=true;
           //int tmp=IP[1].B[k][i];
           for (int j=2;j<=N;j++)
           {
               if(IP[j].B[k][i]!=IP[1].B[k][i])
                   return;
           }
           Sam[k][i]=IP[1].B[k][i];
           Same++;
       }
    }
}

void computer()
{
    /*Subnet Mask*/
    char SM[5][10];
    for (int i=1;i<=4;i++)
    {
       for (int j=0;j<8;j++)
       {
           SM[i][j]=Sam[i][j];
           if(SM[i][j]!='\0')
               SM[i][j]='1';
           else
               SM[i][j]='0';
       }
    }

    /*IP Address*/
    char AD[5][10];
    for (int i=1;i<=4;i++)
    {
       for (int j=0;j<8;j++)
       {
           AD[i][j]=Sam[i][j];
           if(AD[i][j]=='\0')
               AD[i][j]='0';
       }
    }



    for (int i=1;i<=4;i++)
    {
       int T=0;
       for (int j=0;j<8;j++)
       {
           T=T+(AD[i][j]-'0')*power(2,7-j);
       }

       if(i<4)
           cout<<T<<".";
       else
           cout<<T<<endl;
    }


    for (int i=1;i<=4;i++)
    {
       int T=0;
       for (int j=0;j<8;j++)
       {
           T=T+(SM[i][j]-'0')*power(2,7-j);
       }
            if(i<4)
           cout<<T<<".";
       else
           cout<<T<<endl;
    }

}

int main()
{
    freopen("networkip.in","r",stdin);
    freopen("networkip.out","w",stdout);
    init();

    work();

    computer();

    return 0;
}

【評測結果】
正在连接评测机...

已连接到评测机

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

正在编译...
编译成功

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

运行完成
运行时间 0.010 s
平均内存使用 347 KB
测试点通过状况 AAAAAAAAAA
得分：100
恭喜你通过了全部测试点!

2011年11月1日星期二

[動態規劃]BYVoid魔獸世界模擬題: 艾薩拉的激流 azshara 解題報告

艾薩拉的激流 azshara
問題描述

沿着卡利姆多北方邊界延展的破碎的海岸，在世界大分裂之前曾經是暗夜精靈首都艾薩琳的一部分，艾薩拉。惡魔終於從這個世界被消除，這片土地被撕碎並被大海吞沒，剩下的只有曾經雄偉城市的廢墟。自那以後，這個岩石交錯的島嶼、峭壁懸崖和珊瑚叢生的海洋成爲許多傳說來源。暗夜精靈們認爲這是個被詛咒的地方，從來沒有人敢來探險，連經驗最豐富的船長都從這裏繞行。因爲這裏有巨大的水生物，可怕的暗礁，強大的激流與巨浪。然而傳聞這裏水下有着驚人的寶藏，一直吸引着地精們。

地精菲利克斯購買了最好的探險艇，來探索艾薩拉海岸水下傳說中的寶藏。不出所料，海底果然有大量的寶藏。但是這些寶藏被一個激流覆蓋，菲利克斯不可能把他的探險艇停下來。這個激流可以被描述爲一個W×L的矩形，分成個一個個單元格。每個單元格可能是寶藏，也可能是一塊礁石。從上遊開始，每過1秒，菲利克斯的探險艇就會被衝往下游的一個單位。在被衝往下游的過程中，菲利克斯可以控制方向，選擇他的正前，左邊，或右邊的一個單位，以免觸碰礁石。菲利克斯從這個激流的最上游的任意一個單元格開始向下漂流，每經過一個單元格就可以取走這個單元格上的寶藏。菲利克斯千萬不能碰到礁石，否則他的探險艇會損壞。請你算出，菲利克斯最多一共能拿到多少個單位的寶藏。

輸入格式

第一行，兩個整數W，L。

接下來的L行，每行W個整數，以”從上游到下游，面朝水流方向從左向右“的順序依次爲每個單元格中的寶藏的單位數目，如果爲-1則表示這個單元格是礁石。

輸出格式

一個整數，表示得到的寶藏。

數據規模

1<=W<=1000

1<=L<=10000

所有涉及到的數字不會超過32位帶符號整型的範圍

樣例輸入

3 5

5 1 3

-1 7 -1

5 1 10

4 -1 7

20 10 5

樣例輸出

樣例說明

上游->下游	1	2	3	4	5
1	5	-1	5	4	20
2	1	7	1	-1	10
3	3	-1	10	7	5

如上表，菲利克斯可以從(1,1)開始，第1秒向右轉一下，被衝到(2,2)。第2秒向左轉一下，被衝到(3,1)。接下來正前行走，經過(4,1),(5,1)，一共拿到5+7+5+4+20=41個單位的寶藏。

本文由BYVoid大牛開發的開源的中文轉換引擎——Opencc翻譯。

(話說我用BYVoid開發的翻譯引擎翻譯BYVoid出的題目。。大牛啊！)

【分析】

簡單的動態規劃題目。

用mat[i][j]表示讀入的那個矩陣。

mat[i][j]=Max{mat[i-1][j-1],mat[i][j-1],mat[i+1][j-1]}+mat[i][j]

目標狀態：

Max{mat[i][L]}

注意-1的判斷即可。

【我的代碼】

#include <iostream>
#include <cstdlib>
#include <cstdio>
#define Max(a,b) a>=b?a:b;
using namespace std;

int W,L;
int mat[1002][10002];
int M=0;

void init()
{
    scanf("%d %d\n",&W,&L);
    for (int i=1;i<=L;i++)
        for (int j=1;j<=W;j++)
            scanf("%d",&mat[j][i]);
}

void print()
{
    for (int i=1;i<=W;i++)
    {
        for (int j=1;j<=L;j++)
            cout<<mat[i][j]<<" ";
        cout<<endl;
    }
    cout<<endl;
}

void dp()
{
    int tmp;
    for (int i=2;i<=L;i++)
    {
        for (int j=1;j<=W;j++)
        {
            if(mat[j][i]==-1)
                continue;
            tmp=0;
            if(j-1>=1 && mat[j-1][i-1]!=-1)
                tmp=Max(tmp,mat[j-1][i-1]);

            if(mat[j][i-1]!=-1)
                tmp=Max(tmp,mat[j][i-1]);

            if(j+1<=W && mat[j+1][i-1]!=-1)
                tmp=Max(tmp,mat[j+1][i-1]);
            mat[j][i]+=tmp;
            //if(mat[j][i]>M)
                //M=mat[j][i];
        }
    }
}

int main()
{
    freopen("azshara.in","r",stdin);
    freopen("azshara.out","w",stdout);
    init();
//    print();
    dp();
    //print();
    //int M=0;
    for (int i=1;i<=W;i++)
        M=Max(M,mat[i][L]);
    cout<<M<<endl;
    return 0;
}

【測評結果】

正在连接评测机...

已连接到评测机

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

正在编译...
编译成功

测试点	结果	得分	运行时间	内存使用	退出代码
1	正确	10	0.000 s	39421 KB	0
2	正确	10	0.579 s	39421 KB	0
3	正确	10	0.000 s	39421 KB	0
4	正确	10	0.000 s	39421 KB	0
5	正确	10	0.014 s	39421 KB	0
6	正确	10	0.572 s	39421 KB	0
7	正确	10	0.572 s	39421 KB	0
8	正确	10	0.570 s	39421 KB	0
9	正确	10	0.567 s	39421 KB	0
10	正确	10	0.573 s	39421 KB	0

运行完成
运行时间 3.447 s
平均内存使用 39421 KB
测试点通过状况 AAAAAAAAAA
得分：100
恭喜你通过了全部测试点!

[最短路]OI練習題：醫院設置 hospital

信息學競賽練習題：醫院設置(hospital)

【問題描述】

設有一棵二叉樹，如圖 5-1 ：

其中，圈中的數字表示結點中居民的人口。圈邊上數字表示結點編號，現在要求在某個結點上建立一個醫院，使所有居民所走的路程之和爲最小，同時約定，相鄰接點之間的距離爲 1 。

如上圖中，若醫院建在：

1 處，則距離和 =4+12+2*20+2*40=136

3 處，則距離和 =4*2+13+20+40=81

【輸入】

第一行一個整數 n ，表示樹的結點數。 (n ≤ 100)

接下來的 n 行每行描述了一個結點的狀況，包含三個整數，整數之間用空格 ( 一個或多個 ) 分隔，其中：第一個數爲居民人口數；第二個數爲左鏈接，爲 0 表示無鏈接；第三個數爲右鏈接。

【輸出】

一個整數，表示最小距離和。

【樣例】

hospital.in

13 2 3

4 0 0

12 4 5

20 0 0

40 0 0

hospital.out

【分析】

這是最短路徑問題，可以用Floyd算法求出。

由於相鄰兩點之間的距離為1，所以任意兩地之間的距離等於這兩地之間間隔的節點個數+1。

可以把任意兩點之間的距離初始化為-1，把同一地點的距離初始化為0。

即：mat[i][j]=-1(i!=j) ;mat[i][i]=0。

然後用Floyd算法求出任意兩點之間的最短路。

最後枚舉最小的總路程即可。

【我的代碼】

#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;

int mat[101][101];
int People[101];
int N;

void Floyd()
{
    int temp;
    for (int k=1;k<=N;k++)
    {
        for(int i=1;i<=N;i++)
        {
            for(int j=1;j<=N;j++)
            {
                if ( mat[i][k]!=-1 && mat[k][j]!=-1)
                {
                    temp=mat[i][k]+mat[k][j];
                    if ( (mat[i][j]==-1) || ( mat[i][j]>temp ) )
                        mat[i][j]=temp;
                }
            }
        }
    }
}

void init()
{
    scanf("%d\n",&N);

    for (int i=1;i<=N;i++)
        for (int j=1;j<=N;j++)
            mat[i][j]=-1;

    for(int i=1;i<=N;i++)
        mat[i][i]=0;

    int l,r,p;
    for (int i=1;i<=N;i++)
    {
        scanf("%d %d %d\n",&p,&l,&r);
        mat[i][r]=1;
        mat[i][l]=1;
        mat[r][i]=1;
        mat[l][i]=1;
        People[i]=p;
    }
    return;
}

void Work()
{
    int Min=0x7fffffff;
    int Tmp=0;
    for (int i=1;i<=N;i++)
    {
        Tmp=0;
        for (int j=1;j<=N;j++)
        {
            Tmp+=(mat[i][j]*People[j]);
        }
        if(Tmp<Min)
            Min=Tmp;
    }
    cout<<Min<<endl;
}

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

[廣度優先搜索]USACO Jan07:The Bale Tower (btwr)解題報告

The Bale Tower

Always bored with cud-chewing, the cows have invented a new game. One cow retrieves a set of N (3 ≤ N ≤ 20) hay bales from the shed each of which is one unit high. Each bale also has some unique width and unique breadth.
A second cow tries to choose a set of bales to make the tallest stack of bales in which each bale can be placed only on a bale whose own width and breadth are smaller than the width and breadth of the bale below. Bales can not be rotated to interchange the width and breadth.
Help the cows determine the highest achievable tower that can be legally built form a set of bales.
Input

Line 1: A single integer, N

Lines 2..N + 1: Each line describes a bale with two space-separated integers,respectively the width and breadth

Output

Line 1: The height of the tallest possible tower that can legally be built from the bales.

Sample Input

Sample Output

Input Details Six bales of various widths and breadths
Output Details These bales can be stacked for a total height of 5:

[another stacking exists, too]

【分析】
Google翻譯的真扯淡啊～“罷了塔”！最後我還是看著英文做出來這道題。

這題明顯是搜索題，我不知道深度優先搜索能否過全，我用的是廣度優先搜索。一開始，把所有的bale全部加入隊列，然後逐個判斷哪些bale可以放上去，把能放上去的bale加入隊列，直到隊列為空了，輸出最大高度即可。

【我的代碼】
#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
class Bale
{
public:
    int W;
    int B;
}S[21];
int Tot=0;
int N;

class QQ
{
public:
    int A;
    int T;
}Q[10000000];

void init()
{
    scanf("%d\n",&N);
    for (int i=1;i<=N;i++)
        scanf("%d %d\n",&S[i].W,&S[i].B);
    return;
}

void bfs()
{
    for (int i=1;i<=N;i++)
    {
        Q[i-1].A=i;
        Q[i-1].T=1;
    }

    int b=N;
    int s=0;

    int Ta;
    int Tw,Tb;
    int Nw,Nb;

    while(s<=b)
    {
        Ta=Q[s].A;
        Tw=S[Ta].W;
        Tb=S[Ta].B;

        for (int i=1;i<=N;i++)
        {
            if(i==Ta)
                continue;
            Nw=S[i].W;
            Nb=S[i].B;
            if(Nb>=Tb || Nw>=Tw)
                continue;
            Q[b].A=i;
            Q[b].T=Q[s].T+1;
            if(Tot<Q[b].T)
                Tot=Q[b].T;
            b++;
        }
        s++;
    }
    cout<<Tot<<endl;
}

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

2011年10月31日星期一

[動態規劃]USACO Jan07 Bronze:Making Change解題報告

【題目描述】

Poor Bessie has taken a job in the convenience store located just over the border in Slobbovia. Slobbovians use different coinages than the USA; their coin values change day-by-day!
Help Bessie make optimal change for Slobbovian shoppers. You will need to create C (1 ≤ C ≤ 1000) cents of change using N (1 ≤ N ≤ 10) coins of various values. All test cases will be solvable using the supplied coins.
If 5 coins of values 50, 25, 10, 5, and 1 were available, Bessie would make optimum change (minimal coins) of 93 cents by using 1 x 50, 1 x 25, 1 x 10, 1 x 5, and 3 x 1 coins (a total of 7 coins).
How hard could it be? The final two test cases will be challenging.
Input

Line 1: Two space-separate integers: C and N

Lines 2..N + 1: Each line contains a single unique integer that is a coin value that can be used to create change

Output

Line 1: A single integer that is the minimum number of coins to create C cents

Sample Input

Sample Output

【分析】
（官方題解：http://ace.delos.com/TESTDATA/JAN07.change.htm）
（官方數據：http://ace.delos.com/TESTDATA/change.zip）

這是一道動態規劃題，如果用貪心做，可以過8組測試數據，最後兩組會錯掉的。（這數據也太弱了吧。）

[貪心做法]
先對所有的硬幣面值進行快速排序，然後每次用C減去面值最大的那種硬幣，直到C小於硬幣的最大面值，然後更新硬幣的最大面值......，直到C被減到0為止，輸出C被減去的次數即可。
這種算法可以過8組測試數據！

[動態規劃做法]
由於每種硬幣沒有使用次數的限制，所以每種狀態對其以前狀態沒有影響，所以可用DP來求解。

狀態設定
     F[i]：拼出i元的最小硬幣數。
     M[1~N]：1~N中硬幣的面值。
邊界條件
    F[0]=0
狀態轉移方程
    F[i]=Min{F[i-M[k]+1} (i-M[k]>=0, 1<=k<=N)
目標結果
    F[N]

【我的代碼】
#include <cstdio>
#include <cstdlib>
#include <iostream>
#define Min(a,b) a<=b?a:b
using namespace std;
int T;
int N;
int C[11];
int F[1001];

void init()
{
    cin>>T>>N;
    for (int i=1;i<=N;i++)
        cin>>C[i];
    return;
}

void dp()
{
    F[0]=0;
    for (int i=1;i<=T;i++)
    {
        F[i]=10000;
        for (int j=1;j<=N;j++)
        {
            if(i-C[j]>=0)
                F[i]=Min(F[i],F[i-C[j]]+1);
        }
    }
    cout<<F[T]<<endl;
}

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

正在连接评测机...

已连接到评测机

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

正在编译...
编译成功

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

运行完成
运行时间 0.003 s
平均内存使用 273 KB
测试点通过状况 AAAAAAAAAA
得分：100
恭喜你通过了全部测试点!

2011年10月30日星期日

[廣度優先搜索]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

樣例輸出

樣例說明

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

【命題人的分析】

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

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

時間複雜度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;
}

訂閱：文章 (Atom)

Yeefan's Blog

申請SAE

2011年11月2日星期三

[字符串處理][模擬]OI練習題：IP網絡管理員 networkip

2011年11月1日星期二

[動態規劃]BYVoid魔獸世界模擬題: 艾薩拉的激流 azshara 解題報告

[最短路]OI練習題：醫院設置 hospital

[廣度優先搜索]USACO Jan07:The Bale Tower (btwr)解題報告

2011年10月31日星期一

[動態規劃]USACO Jan07 Bronze:Making Change解題報告

2011年10月30日星期日

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

血色先鋒軍

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

問題描述

輸入格式

輸出格式

樣例輸入

樣例輸出

樣例說明

申請SAE

2011年11月2日 星期三

[字符串處理][模擬]OI練習題：IP網絡管理員 networkip

2011年11月1日 星期二

[動態規劃]BYVoid魔獸世界模擬題: 艾薩拉的激流 azshara 解題報告

[最短路]OI練習題：醫院設置 hospital

[廣度優先搜索]USACO Jan07:The Bale Tower (btwr)解題報告

2011年10月31日 星期一

[動態規劃]USACO Jan07 Bronze:Making Change解題報告

2011年10月30日 星期日

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

血色先鋒軍

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

問題描述

輸入格式

輸出格式

樣例輸入

樣例輸出

樣例說明

2011年11月2日星期三

2011年11月1日星期二

2011年10月31日星期一

2011年10月30日星期日