b217. 2. 線串式主題閱讀系統＠Morris' Blog

2011-08-27 07:49:38| 人氣566| 回應0 | 上一篇 | 下一篇

b217. 2. 線串式主題閱讀系統

推薦 0 收藏 0 轉貼0 訂閱站台

內容：

因為網路論壇的流行，吸引大量的內容討論文章。但傳統的閱讀方式是條列式、依照時間出現順序排列，一旦討論數量龐大，很難找到集中的討論主題。線串主題 (subject threading)就是一種將相同主題 (subject)集中，以方便閱讀的瀏覽方式。我們希望設計線串主題排列系統，挑選集中相同的主題文章，再依照最早出現主題的時間，依序排列。為了簡化系統，我們將文章的主題與發表時間摘要出來，成為一個集中的索引檔案，請根據此索引檔，輸出線串主題。

文章索引檔表示法說明：
索引檔內為每一篇文章建立三個欄位，分別為主題(Subject)、日期(Date)、與識別碼(ID)。主題表示為：
Subject: xxxxx
其中“Subject:’’ 之後有一空白，“xxxxx” 為主題內容。主題內容可含除換行之外的任何字元。主題內容前三個字元若為 “Re:”或“RE:”則忽略不計。若內容有多組“Re:”或“RE:”刪除第一組即可，內容字串第一個非空白字元前之任何數量的空白(0x20)皆忽略不計；而主題字串最後一個非空白字元之後的所有空白字元也忽略不計，除此之外，比較兩主題是否相同時，所有字元必須完全相同，例如以下前三個主題皆視為相同主題，但最後一個則視為不同的主題：
Subject: 有關高中程式競賽
Subject: Re: 有關高中程式競賽
Subject: Re:有關高中程式競賽
Subject: Re: Re: 有關高中程式競賽

日期欄位表示如右： M D H Y
其中，M 為 1 至 12 的整數，分別代表 1 月到 12 月。D 為 1 到 31 的整數，表示當月份第 1 日至 31 日。H 表示時，為 0 到 23 的整數。Y 代表年，為四位整數。數字間以一個空白相隔。例如以下日期表示 2008 年 11 月 3 日 12 時：
Date: 11 3 12 2008
“Date:’’ 之後有一空白。
識別碼則以最多十位整數表示每一篇文章之識別碼在索引檔中都是唯一例如，。：
ID: 1234567
“ID:’’ 之後有一空白。

輸入說明：

輸入為文章索引檔每一篇文章有三個欄位，每一欄位單獨一行，依序為 Subject:Date: 與 ID:。 Subject: 欄位長度最多 1024 個字元(byte)，不同的文章索引欄位以一空白行間隔。連續兩個空白行表示資料結束。每個索引檔最多含有 10,000 篇文章索引（每篇文章三個欄位），至少有兩個線串。

輸出說明：

輸出主題（已濾除 Re: RE: 與空白字元）相同的文章索引欄位為一主題線串，以線串中時間最早的文章為基準，依據時間先後次序輸出主題，倘若時間相同，則以在索引檔中出現的順序輸出。再將此線串中的文章依據出現時間輸出其對應ID，若時間相同，以在索引檔中出現的順序排列，並以逗點隔開。線串之間以一空白行隔開。連續兩空白行表示結束，請輸出最早出現的 2 個線串資料即可，例如：
Subject: 有關高中程式競賽
ID: 1234657,123456,98765
Subject: 高中程式競賽地點
ID: 8888,9999,1000

範例輸入：

輸入範例 1：
Subject: 經濟風暴
Date: 11 20 10 2008
ID: 1

Subject: 美國總統當選人
Date: 11 19 12 2008
ID: 12

Subject: Re: 經濟風暴
Date: 11 21 20 2008
ID: 34

Subject: Re: 美國總統當選人
Date: 11 22 13 2008
5
ID: 98

輸入範例 2：
Subject: 失業率升高
Date: 11 28 10 2008
ID: 1

Subject: 美國總統當選人
Date: 11 19 12 2008
ID: 12

Subject: 經濟風暴
Date: 11 21 20 2008
ID: 34

Subject: Re: 美國總統當選人
Date: 11 22 13 2008
ID: 98

範例輸出：

輸出範例 1：(只需輸出最早出現的 2 個線串)
Subject: 美國總統當選人
ID: 12,98
Subject: 經濟風暴
ID: 1,34

輸出範例 2：(只需輸出最早出現的 2 個線串)
Subject: 美國總統當選人
ID: 12,98

Subject: 經濟風暴
ID: 34

提示：

出處：

97全國資訊學科能力競賽

紀錄時間點最早的兩個線串

/**********************************************************************************/
/* Problem: b217 "2. 線串式主題閱讀系統" from 97全國資訊學科能力競賽*/
/* Language: C                                                                   */
/* Result: AC (7ms, 336KB) on ZeroJudge                                          */
/* Author: morris1028 at 2011-08-26 23:59:37                                     */
/**********************************************************************************/

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct {
   char Subject[1025];
   int Date[4];
   int ID[100], IDl;
   int input;
}Article;
Article in[10000];
int cmp(const void *a, const void *b) {
   Article *aa, *bb;
   aa = (Article *)a, bb = (Article *)b;

    if(aa->Date[3] > bb->Date[3])    return 1;
    else if(aa->Date[3] < bb->Date[3])    return 0;
    else {
        if(aa->Date[0] > bb->Date[0])    return 1;
        else if(aa->Date[0] < bb->Date[0])    return 0;
        else {
            if(aa->Date[1] > bb->Date[1])    return 1;
            else if(aa->Date[1] < bb->Date[1])    return 0;
            else {
                if(aa->Date[2] > bb->Date[2])    return 1;
                else if(aa->Date[2] < bb->Date[2])    return 0;
                else {
                    return aa->input > bb->input;
                }
            }
        }
    }
}
main() {
    char Subject[10], Date[10], ID[10], name[1025];
    int M, D, H, Y, id, index = 0, a, b, C = 0;
    while(scanf("%s", Subject) == 1) {
        ++C;
        getchar(), gets(name);
        scanf("%s %d %d %d %d", Date, &M, &D, &H, &Y);
        scanf("%s %d", ID, &id);
        int i = 0, j = 0, l = strlen(name);
        if(name[0] == 'R' && (name[1] == 'E' || name[1] == 'e')&& name[2] == ':')
            i = 3;
        while(name[i] == ' ')    i++;
        for(; i < l; i++)    name[j++] = name[i];
        i = j-1;
        while(name[i] == ' ')    i--;
        name[i+1] = '\0';
        for(a = 0; a < index; a++) {
            if(!strcmp(in[a].Subject, name)) {
                in[a].ID[in[a].IDl++] = id;
                break;
            }
        }
        if(a == index) {
            for(b = 0; name[b]; b++)
                in[a].Subject[b] = name[b];
            in[a].Subject[b] = '\0';
            in[a].Date[0] = M, in[a].Date[1] = D, in[a].Date[2] = H, in[a].Date[3] = Y;
            in[a].IDl = 0, in[a].ID[in[a].IDl++] = id;
            in[a].input = C;
            index++;
            if(index > 3) {
                for(b = 0; b < index-1; b++)
                    if(cmp(&in[b], &in[index-1]) == 1) {
                        break;
                    }
                if(b != index-1)
                    in[b] = in[index-1];
                index--;
            }
        }
    }
    qsort(in, index, sizeof(Article), cmp);
    for(a = 0; a < 2; a++) {
        printf("Subject: %s\nID: ", in[a].Subject);
        for(b = 0; b < in[a].IDl; b++)
            if(b == 0)    printf("%d", in[a].ID[b]);
            else printf(",%d", in[a].ID[b]);
        puts("");
    }
    return 0;
}

我要檢舉

#b217#2 #線串式主題閱讀系統

台長： Morris

您可能對以下文章有興趣

[ZJ][一年後修裝版][C++] b113. 6. 線性系統求解

[ZJ][LCA] b237. CSAPC'09 迷宮任務

d915. 3. 洗街車路線問題

[ZJ][模擬水] a349. 2. 指令解譯器

人氣(566) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: 資訊競賽 |
此分類下一篇:b180. 1. 遊園接駁車
此分類上一篇:b177. 山景 Skyline

回應(0)