顯示具有 NOI 標籤的文章。顯示所有文章

2012年2月7日星期二

WC2012的神牛們.....

由於報名時運氣不好，沒有報上在常州舉辦的NOI WC2012，所以只好在網路圖片上膜拜神牛了～

NOI WC2012開幕式時，我看到滿眼神牛～

其中有CheePok、KingFree、TBK、Michstar

唉～嘆息啊

2012年1月30日星期一

【題目描述】
懶得貼上試題了～發個連結：NOI2007 Day1試題連結
【分析】
這是這幾年NOI中最簡單的題了～就是一個多源最短路+乘法原理。

用Map[i][j]表示i、j之間的最短路徑長度；
用Path[i][j]表示i、j之間最短路徑的條數（初始化為1）。

先用Floyd算法求每兩點之間的最短路，鬆弛時要注意，如果出現：
Map[i][k]+Map[k][j]==Map[i][j] 則說明這又是最短路，所以Path[i][j]+=Path[i][k]*Path[k][j]。
如果可以鬆弛，即Map[i][k]+Map[k][j]<Map[i][j]，則Path[i][j]=Path[i][k]*Path[k][j]即可。

最後亂搞一個三重循環求I(v)，按照題意走即可AC。

閱讀全文 Continue Reading 全文を読む »

2012年1月2日星期一

[並查集]NOI2001 食物鏈 eat 解題報告

Title: 食物链題目連結：COGS

Input: eat.in

Output: eat.out

Time Limit: 1000 ms

Memory Limit: 128 MB

Level: ★★☆

动物王国中有三类动物A,B,C，这三类动物的食物链构成了有趣的环形。A吃B， B吃C，C吃A。
现有N个动物，以1－N编号。每个动物都是A,B,C中的一种，但是我们并不知道它到底是哪一种。
有人用两种说法对这N个动物所构成的食物链关系进行描述：

第一种说法是“1 X Y”，表示X和Y是同类。
第二种说法是“2 X Y”，表示X吃Y。

此人对N个动物，用上述两种说法，一句接一句地说出K句话，这K句话有的是真的，有的是假的。当一句话满足下列三条之一时，这句话就是假话，否则就是真话。

当前的话与前面的某些真的话冲突，就是假话；
当前的话中X或Y比N大，就是假话；
当前的话表示X吃X，就是假话。

你的任务是根据给定的N（1<=N<=50,000）和K句话（0<=K<=100,000），输出假话的总数。

输入文件
第一行是两个整数N和K，以一个空格分隔。
以下K行每行是三个正整数 D，X，Y，两数之间用一个空格隔开，其中D表示说法的种类。

若D=1，则表示X和Y是同类。
若D=2，则表示X吃Y。

输出文件
只有一个整数，表示假话的数目。
输入样例
100 7
1 101 1
2 1 2
2 2 3
2 3 3
1 1 3
2 3 1
1 5 5
输入文件

输出样例

3
样例说明
对7句话的分析

1 101 1 假话
2 1 2 真话
2 2 3 真话
2 3 3 假话
1 1 3 假话
2 3 1 真话
1 5 5 真话

「分析」

本題是並查集的經典應用。
每次判斷時，前兩個條件都能O（1）判斷，關鍵在於第3個條件。
由於無法判斷可以另外虛設2*N個物種，分別表示能吃第i個物種的物種和被第i個物種所吃的物種。那麼剩下就是裸並查集了，每次合併就把那個三角環依次合併即可。

「我的代碼」

C++语言: Codee#24995

/*

*Problem: NOI2001-eat

*Author: Yee-fan Zhu

*Time: Jan 02,2012

*Method: UFS

*/

#include <iostream>

#include <cstdlib>

#include <cstdio>

using namespace std;

const int MAX=150010;

 

int N,K;

int Ani[MAX];

int Eat[MAX];

int Eaten[MAX];

int False=0;

 

int UFS_Find(int x)

{

    int t,p;

    p=x;

    while(Ani[p]!=p)

        p=Ani[p];

    while(Ani[x]!=x)  //Compress Path

    {

        t=Ani[x];

        Ani[x]=p;

        x=t;

    }

    return p;

}

 

bool UFS_Check(int a,int b)

{

    int x=UFS_Find(a);

    int y=UFS_Find(b);

    return (x==y);

}

 

void UFS_Merge(int a,int b)

{

    Ani[UFS_Find(b)]=UFS_Find(a);

}

 

void init()

{

    scanf("%d %d\n",&N,&K);

    for (int i=1;i<=N;i++)

    {

        int x=N+i;

        int y=N*2+i;

        Ani[i]=i,Ani[x]=x,Ani[y]=y;

        Eaten[i]=x,Eat[i]=y;

        Eaten[x]=y,Eat[x]=i;

        Eaten[y]=i,Eat[y]=x;

    }

}

 

void work()

{

    int D,X,Y;

    for (int i=1;i<=K;i++)

    {

        scanf("%d %d %d\n",&D,&X,&Y);

        if(X>N || Y>N)

        {

            False++;

            continue;

        }

        if(D==2 && X==Y)

        {

            False++;

            continue;

        }

 

        if(D==1)

        {

            if(UFS_Check(X,Y))

                continue;

            if(UFS_Check(Eat[X],Y) ||  UFS_Check(Eaten[X],Y) )

            {

                False++;

                continue;

            }

 

            UFS_Merge(X,Y);

            UFS_Merge(Eaten[X],Eaten[Y]);

            UFS_Merge(Eat[X],Eat[Y]);

            continue;

        }

 

        if(D==2)

        {

            if(UFS_Check(Eat[X],Y))

                continue;

 

            if(UFS_Check(X,Y) || UFS_Check(Eaten[X],Y))

            {

                False++;

                continue;

            }

 

            UFS_Merge(Eat[X],Y);

            UFS_Merge(X,Eaten[Y]);

            UFS_Merge(Eaten[X],Eat[Y]);

            continue;

        }

    }

}

 

int main()

{

    freopen("eat.in","r",stdin);

    freopen("eat.out","w",stdout);

    init();

    work();

    printf("%d\n",False);

    return 0;

}

2011年11月25日星期五

[最短路]NOI1997：最優乘車 bustravel 解題報告

【描述】
H城是一個旅遊勝地，每年都有成千上萬的人前來觀光。爲方便遊客，巴士公司在各個旅遊景點及賓館，飯店等地都設置了巴士站並開通了一些單程巴上綫路。每條單程巴士綫路從某個巴士站出發，依次途經若干個巴士站，最終到達終點巴士站。

一名旅客最近到H城旅遊，他很想去S公園遊玩，但如果從他所在的飯店沒有一路巴士可以直接到達S公園，則他可能要先乘某一路巴士坐幾站，再下來換乘同一站臺的另一路巴士, 這樣換乘幾次後到達S公園。

現在用整數1,2,…N 給H城的所有的巴士站編號，約定這名旅客所在飯店的巴士站編號爲1,S公園巴士站的編號爲N。

寫一個程序，幫助這名旅客尋找一個最優乘車方案,使他在從飯店乘車到S公園的過程中換車的次數最少。

輸入輸出

輸入文件的第一行有兩個數字M和N(1<=M<=100 1<N<=500)，表示開通了M條單程巴士綫路，總共有N個車站。從第二行到第M+1行依次給出了第1條到第M條巴士綫路的信息。其中第 i+1行給出的是第i條巴士綫路的信息，從左至右按運行順序依次給出了該綫路上的所有站號相鄰兩個站號之間用一個空格隔開。

輸出文件只有一行。如果無法乘巴士從飯店到達S公園，則輸出"N0"，否則輸出你的程序所找到的最少換車次數，換車次數爲0表示不需換車即可到達

樣例

輸入文件

3 7

6 7

4 7 3 6

2 1 3 5

輸出文件

【分析】

最短路徑問題，可以用Floyd算法求解。只是讀入時不太方便，需要先讀一整行。

【我的代碼】

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
const int MAXN=10000000;
int Bus[101][501];
int Map[501][501];
int N,M;

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

    for (int i=1;i<=N;i++)
        for (int j=1;j<=N;j++)
            Map[i][j]=MAXN;

    for (int i=1;i<=M;i++)
    {
        Bus[i][0]=0;
        getline(cin,line);
        int tmp=0;
        int len=line.length();
        int top=0;
        while(top<len)
        {
            if(isdigit(line[top]))
            {
                tmp=tmp*10+line[top]-'0';
                top++;
                continue;
            }
            if(line[top]==' ')
            {
                Bus[i][0]++;
                Bus[i][Bus[i][0]]=tmp;
                tmp=0;
                top++;
                continue;
            }
        }
        if(tmp>0)
        {
            Bus[i][0]++;
            Bus[i][Bus[i][0]]=tmp;
        }
    }

    int t1,t2;
    for (int i=1;i<=M;i++)
    {
        for (int j=1;j<=Bus[i][0];j++)
        {
            for (int k=j;k<=Bus[i][0];k++)
            {
                t1=Bus[i][j];
                t2=Bus[i][k];
                Map[t1][t2]=0;
            }
        }
    }
}

void Floyd()
{
    int tmp;
    for (int k=1;k<=N;k++)
    {
        for (int i=1;i<=N;i++)
        {
            for (int j=1;j<=N;j++)
            {
                tmp=Map[i][k]+Map[k][j]+1;
                if(tmp<Map[i][j])
                    Map[i][j]=tmp;
            }
        }
    }
    printf("%d\n",Map[1][N]);
}

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

【評測結果】

正在连接评测机...

已连接到评测机

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

正在编译...
编译成功

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

运行完成
运行时间 0.325 s
平均内存使用 1452 KB
测试点通过状况 AAAAAAAAAA
得分：100
恭喜你通过了全部测试点!
已完成数据库校验。

2011年11月4日星期五

NOI1998 個人所得稅 personaltax 解題報告

【題目描述】

某國個人所得稅法規定，普通公民的主要應納稅收入項目及納稅金額如下：

工資、薪金所得。按月計算徵稅，以每月收入額減除費用800元后的餘額作爲該月應納稅所得額，稅率如下表所示：

級數月應納稅所得額稅率（%）

1 不超過500元的 5

2 超過500元~2000元的部分 10

3 超過2000元~5000元的部分 15

4 超過5000元~20000元的部分 20

5 超過20000元~40000元的部分 25

6 超過40000元~60000元的部分 30

7 超過60000元~80000元的部分 35

8 超過80000元~100000元的部分 40

9 超過100000元的部分 45

一次性勞動報酬所得。按次計算徵稅，每次不超過4000元的，減除費用800元；4000元以上的，減除20%的費用，餘額爲應納稅所得額。徵稅稅率如下表所示：

級數每次應納稅所得額稅率（%）

1 不超過20000元的部分 20

2 超過20000元~50000元的部分 30

3 超過50000元的部分 40

由上面可以看出，個人工資、薪金及一次性勞動報酬所得都是按照超額累進稅率來徵稅的。超額累進稅率將應納稅所得額按數額大小分成若乾等級，每一等級規定一個稅率，稅率依次提高，但每一納稅人的的應納稅所得額依照所屬等級同時適用幾個稅率分別計算，將計算結果相加後的總額作爲應納稅款。

例如，某人某月工資總額爲3800元，減去800元后，應納稅所得額爲3000元。其中1級500元，2級1500元，3級1000元，稅率分別爲5%、10%、15%，應納稅總額爲500*5%+1500*10%+1000*15%=325（元）。現在需要你編一程序，根據該國某公司的所有職員一年內的各項收入信息（收入項目、收入時間、收入金額）計算該公司所有職員這一年應交納的個人所得稅總額。

輸入

輸入文件的第一行爲一個正整數M（M<= 50000），表示該公司的職員總數（職員編號依次爲1,2,…,M）。接下來的各行每行表示一年內某一個職員的一項收入信息。具體格式如下：工資、薪金收入信息：PAY 職員編號收入時間收入金額

一次性勞務報酬收入信息：INCOME 職員編號收入時間收入金額

其中，收入時間格式爲：MM/DD，MM表示月份（1<= MM<=12），DD表示日期（1<= DD<=31）；收入金額是一個正整數（單位：元），並假設每人每項收入金額小於100萬元。

輸入文件以字符“#”表示結束。輸入文件中同一行相鄰兩項之間用一個或多個空格隔開。

輸出

輸出文件只有一個正數P(保留兩位小數)，P表示該公司所有職員一年內應交納的個人所得稅總額（單位：元）。

樣例輸入

PAY 1 2/23 3800

INCOME 2 4/8 4010

INCOME 2 4/18 800

PAY 1 8/14 6700

PAY 1 8/10 1200

PAY 2 12/10 20000

樣例輸出

5476.60

【分析】

又是一道NOI的水題啊～這道題不需要什麼算法或者數據結構，模擬即可。

讀題時應注意：工資、薪金所得是按月計算，一次性勞動報酬所得是按此次計算，所以說，輸入數據中給的日期對於一次性勞動報酬所得的計算沒有任何作用，而對於工資、薪金所得是按月來說，只有月份有用而日無用。所以讀入時應忽略干擾數字。用C++/C中的scanf()函數很容易做到這一點。

剩下的就很簡單了，就是初中時學習的分段函數，只要看清題目就不會出錯。

【代碼】

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

class PAY
{
public:
    int Mon[13];
    double TP;
    double TI;
    PAY()
    {
        for (int i=1;i<=12;i++)
            Mon[i]=0;
        TP=0;
        TI=0;
    }
}PE[50001];

double Jianzhi(int Num)
{
    double MM=0;
    double NN=Num;
    if(Num<=800)
        return MM;

    if(Num<=4000)
        NN=NN-800;
    else
    {
        NN=NN-NN/5;
    }

    if(NN<=20000)
    {
        MM=NN/5;
        return MM;
    }

    if(NN<=50000)
    {
        MM=4000;
        NN=NN-20000;
        MM=MM+NN*0.3;
        return MM;
    }

    MM=4000+9000;
    NN=NN-50000;
    MM=MM+NN*0.4;
    return MM;
}

double Gongzi(int Num)
{
    double NN=Num;
    double MM=0;
    if(Num<=800)
    {
        return MM;
    }

    NN=NN-800;

    if(NN<=500)
    {
        MM=NN/20;
        return MM;
    }

    if(NN<=2000)
    {
        MM=25;
        NN=NN-500;
        MM=MM+NN*0.1;
        return MM;
    }

    if(NN<=5000)
    {
        MM=175;
        NN=NN-2000;
        MM=MM+NN*0.15;
        return MM;
    }

    if(NN<=20000)
    {
        MM=625;
        NN-=5000;
        MM=MM+NN*0.2;
        return MM;
    }

    if(NN<=40000)
    {
        MM=3625;
        NN-=20000;
        MM=MM+NN*0.25;
        return MM;
    }

    if(NN<=60000)
    {
        MM=8625;
        NN-=40000;
        MM=MM+NN*0.3;
        return MM;
    }

    if(NN<=80000)
    {
        MM=14625;
        NN-=60000;
        MM=MM+NN*0.35;
        return MM;
    }

    if(NN<=100000)
    {
        MM=21625;
        NN-=80000;
        MM=MM+NN*0.4;
        return MM;
    }

    MM=29625;
    NN-=100000;
    MM=MM+NN*0.45;
    return MM;
}

void init()
{
    string PAY="PAY";
    string INCOME="INCOME";
    scanf("%d\n",&M);
    string P;
    P.clear();
    cin>>P;
    int Peo;
    int Mon;
    int Day;
    int Money;

    while(P[0]!='#')
    {
        if(P==PAY)
        {
            scanf("%d %d/%d %d",&Peo,&Mon,&Day,&Money);
            PE[Peo].Mon[Mon]+=Money;
        }
        if(P==INCOME)
        {
            scanf("%d %d/%d %d",&Peo,&Mon,&Day,&Money);
            PE[Peo].TI=PE[Peo].TI+Jianzhi(Money);
        }
        cin>>P;
    }

    for (int i=1;i<=M;i++)
    {
        for (int j=1;j<=12;j++)
        {
            if(PE[i].Mon[j]!=0)
                PE[i].TP+=Gongzi(PE[i].Mon[j]);
        }
    }

    double Tot=0;
    for (int i=1;i<=M;i++)
    {
        Tot+=PE[i].TP;
        Tot+=PE[i].TI;
    }
    //cout<<Tot<<endl;
    printf("%.2lf\n",Tot);
}

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

NOI1997 競賽排名 competitionsort 解題報告

【題目描述】
題目網上都有，比如說http://www.byvoid.com/blog/noi-1997-solution/ 。

【分析】

這是道NOI中的水題，簡單的模擬即可，只需要看清楚題目中給的糾結的式子即可。最後需要結構體的三級排序。

【代碼】

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

class Student
{
public:
    int G[9];
    double Sum;
    double Pos[9];
    double SumP;
    int n;
}S[1001];
int N;
double Av[8];

double Abs(double n)
{
    if(n>0)
        return n;
    return -n;
}

void Averge(int I)
{
    int Tot=0;
    for (int i=1;i<=N;i++)
        Tot+=S[i].G[I];
    double TT=Tot;
    double NN=N;
    Av[I]=TT/NN;
}

bool flag=true;

void print()
{
    for (int i=1;i<=N;i++)
    {
        for (int j=1;j<=8;j++)
            cout<<S[i].G[j]<<" ";
        cout<<" "<<S[i].Sum<<" "<<S[i].SumP<<" "<<S[i].n<<endl;
    }
    cout<<endl;
    for (int i=1;i<=8;i++)
        cout<<Av[i]<<" ";
   }

void Position(int I)
{
    for (int k=1;k<=8;k++)
    {
        double E=0;
        for (int i=1;i<=N;i++)
        {
            double Tmp;
            Tmp=S[i].G[k];
            E+=( Abs(Tmp-Av[k]) );
        }

        if(E==0)
        {
            S[I].Pos[k]=0;
            continue;
        }

        /*計算Xij-AVGj*/
        double Xij;
        double Up;
        double Down;
        Xij=S[I].G[k];
        Up=Xij-Av[k];
        Down=E/N;
        S[I].Pos[k]=Up/Down;
    }

    double Sp=0;
    for (int i=1;i<=3;i++)
        Sp+=S[I].Pos[i];

    for (int i=4;i<=8;i++)
        Sp+=(S[I].Pos[i]*0.8);
    S[I].SumP=Sp;
    return;
}

int cmp(const void *a,const void *b)
{
    class Student *c=(class Student *)a;
    class Student *d=(class Student *)b;
    if(c->SumP!=d->SumP)
    {
        if(d->SumP>=c->SumP)
            return 1;
        else
            return -1;
    }
    else
    {
        if(c->Sum!=d->Sum)
            return d->Sum>c->Sum?1:-1;
        else
            return c->n-d->n;
    }
}


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

    for (int i=1;i<=N;i++)
    {
        int Tmp=0;
        for(int j=1;j<=8;j++)
        {
            cin>>S[i].G[j];
            Tmp+=S[i].G[j];
        }
        S[i].Sum=Tmp;
        S[i].n=i;
    }

    for (int i=1;i<=8;i++)
        Averge(i);
    for (int i=1;i<=N;i++)
        Position(i);
    qsort(S+1,N,sizeof(S[0]),cmp);
    return;
}

int main()
{
    freopen("competitionsort.in","r",stdin);
    freopen("competitionsort.out","w",stdout);
    init();
    //print();
    if(!flag)
        return 0;
    for (int i=1;i<=N;i++)
        cout<<S[i].n<<endl;
    return 0;
}

2011年10月25日星期二

NOIP2007普及組 scholar 獎學金解題報告

【問題描述】

某小學最近得到了一筆贊助，打算拿出其中一部分爲學習成績優秀的前5名學生發獎學金。期末，每個學生都有3門課的成績：語文、數學、英語。先按總分從高到低排序，如果兩個同學總分相同，再按語文成績從高到低排序，如果兩個同學總分和語文成績都相同，那麼規定學號小的同學排在前面，這樣，每個學生的排序是唯一確定的。

任務：先根據輸入的3門課的成績計算總分，然後按上述規則排序，最後按排名順序輸出前5名學生的學號和總分。注意，在前5名同學中，每個人的獎學金都不相同，因此，你必須嚴格按上述規則排序。例如，在某個正確答案中，如果前兩行的輸出數據(每行輸出兩個數：學號、總分)是：

7 279

5 279

這兩行數據的含義是：總分最高的兩個同學的學號依次是7號、5號。這兩名同學的總分都是279(總分等於輸入的語文、數學、英語三科成績之和)，但學號爲7的學生語文成績更高一些。如果你的前兩名的輸出數據是：

5 279

7 279

則按輸出錯誤處理，不能得分。

【輸入】

輸入文件pj07-1.in 包含行n+1行：

第l行爲一個正整數n，表示該校參加評選的學生人數。

第2到年n+l行，每行有3個用空格隔開的數字，每個數字都在0到100之間。第j行的3個數字依次表示學號爲j-1的學生的語文、數學、英語的成績。每個學生的學號按照輸入順序編號爲1～n(恰好是輸入數據的行號減1)。

所給的數據都是正確的，不必檢驗。

【輸出】

輸出文件pj07-1.out 共有5行，每行是兩個用空格隔開的正整數，依次表示前5名學生的學號和總分。

【輸入輸出樣例l】

pj07-1.in

90 67 80

87 66 91

78 89 91

88 99 77

67 89 64

78 89 98

pj07-1.out

6 265

4 264

3 258

2 244

1 237

【輸入輸出樣例2】

pj07-1.in

80 89 89

88 98 78

90 67 80

87 66 91

78 89 91

88 99 77

67 89 64

78 89 98

pj07-1.out

8 265

2 264

6 264

1 258

5 258

【限制】

50％的數據滿足：各學生的總成績各不相同

100％的數據滿足：6<=n<=300

【分析】

模擬題目，直接調用C++中的快速排序，使用結構體（或類）的三級排序即可。

注意qsort中cmp函數的寫法。

【我的代碼】

//NOIP2007-Senior-Scholar
#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
typedef unsigned short int usint;
const int maxn=301;

class Student
//struct Student
{
public:
    usint total;
    usint chs;
    usint mth;
    usint eng;
    usint num;
}Grade[maxn];
int n;

void init()
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
    {
        //Grade[i].num=i;
        scanf("%d%d%d",&Grade[i].chs,&Grade[i].mth,&Grade[i].eng);
        Grade[i].total=Grade[i].chs+Grade[i].mth+Grade[i].eng;
        Grade[i].num=i;
    }
    return;
}
void print()
{
    for (int i=1;i<=n;i++)
        cout<<Grade[i].num<<" "<<Grade[i].total<<" "<<Grade[i].chs<<" "<<Grade[i].mth<<" "<<Grade[i].eng<<endl;
}

void printresult()
{
    for (int i=1;i<=5;i++)
        cout<<Grade[i].num<<" "<<Grade[i].total<<endl;
}

int Compare(const void *a,const void *b)
{
    class Student *c=(class Student *)a;
    class Student *d=(class Student *)b;
    if (c->total != d->total)
        return d->total - c->total;
    else
    {
        if (d->chs != c->chs)
            return d->chs - c->chs;
        else return c->num - d->num;
    }
}

int main()
{
    freopen("pj07-1.in","r",stdin);
    freopen("pj07-1.out","w",stdout);
    init();
    qsort(Grade+1,n,sizeof(Student),Compare);
    printresult();
    return 0;
}

正在连接评测机...

已连接到评测机

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

正在编译...
编译成功

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

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

2011年10月24日星期一

NOI2000 單詞查找樹解題報告

【NOI2000】单词查找树

Description

在进行文法分析的时候，通常需要检测一个单词是否在我们的单词列表里。为了提高查找和定位的速度，通常都要画出与单词列表所对应的单词查找树，其特点如下：
1)根节点不包含字母，除根节点外每一个节点都仅包含一个大写英文字母；
2)从根节点到某一节点，路径上经过的字母依次连起来所构成的字母序列，称为该节点对应的单词。单词列表中的每个词，都是该单词查找树某个节点所对应的单词；
3)在满足上述条件下，该单词查找树的节点数最少。

Input

每组输入一个单词列表，每一行仅包含一个单词和一个换行/回车符。每个单词仅由大写的英文字符组成，长度不超过63个字符。每组数据总长度不超过32K，至少有一行数据。

Output

输出仅包含一个整数和一个换行/回车符。该整数为单词列表对应的单词查找树的节点数。

Sample Input

A
AN
ASP
AS
ASC
ASCII
BAS
BASIC

Sample Output

【閒扯】
話說NOI2000的題目真是水，第一題是【瓷片項鍊】，就是一個一元二次函數的最值問題，第二題是這個題，真是簡單啊！

【分析】
單詞查找樹就是字典樹（Trie Tree），可以參看我以前的文章。先用字典樹把所有的字符串均插入字典樹，然後再遍歷(Travel)整個樹，先序、中序、後序，怎麼遍歷都可以，可以寫遞歸函數來壓縮代碼複雜度。

【滿分代碼】
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;

const int sonnum=26;
const char base='A';
class Trie
{
public:
    bool isStr;
    int Page;
    class Trie *son[sonnum];
};

Trie *NewTrie()
{
    Trie *temp=new Trie;
    temp->isStr=false;
    for (int i=0;i<sonnum;i++)
        temp->son[i]=NULL;
    return temp;
}

void Insert(Trie *pnt,char *s,unsigned int len)
{
    Trie *temp=pnt;
    for (unsigned int i=0;i<len;i++)
    {
        if (temp->son[s[i]-base]==NULL)
            temp->son[s[i]-base]=NewTrie();
        temp=temp->son[s[i]-base];
    }
    temp->isStr=true;
}

Trie *pnt=NewTrie();
int T=0;

void Digui(Trie *temp)
{
    T++;
    for (int i=0;i<sonnum;i++)
    {
        if(temp->son[i]!=NULL)
            Digui(temp->son[i]);
    }
}

void init()
{
    char str[65];
    while (cin>>str)
        Insert(pnt,str,strlen(str));
    Digui(pnt);
}

int main()
{

    freopen("trie.in","r",stdin);
    freopen("trie.out","w",stdout);
    init();
    cout<<T<<endl;
    fclose(stdin);
    fclose(stdout);
    return 0;
}

訂閱：文章 (Atom)

Yeefan's Blog

申請SAE

2012年2月7日星期二

WC2012的神牛們.....

2012年1月30日星期一

NOI2007 社交網絡 network 解題報告

2012年1月2日星期一

[並查集]NOI2001 食物鏈 eat 解題報告

「分析」

「我的代碼」

2011年11月25日星期五

[最短路]NOI1997：最優乘車 bustravel 解題報告

2011年11月4日星期五

NOI1998 個人所得稅 personaltax 解題報告

NOI1997 競賽排名 competitionsort 解題報告

2011年10月25日星期二

NOIP2007普及組 scholar 獎學金解題報告

2011年10月24日星期一

NOI2000 單詞查找樹解題報告

申請SAE

2012年2月7日 星期二

2012年1月30日 星期一

2012年1月2日 星期一

「分析」

「我的代碼」

2011年11月25日 星期五

2011年11月4日 星期五

2011年10月25日 星期二

2011年10月24日 星期一

2012年2月7日星期二

2012年1月30日星期一

2012年1月2日星期一

2011年11月25日星期五

2011年11月4日星期五

2011年10月25日星期二

2011年10月24日星期一