青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

coreBugZJ

此 blog 已棄。

PageRank,HUST Monthly 2011.04.09 之 A,1431

PageRank

Time Limit: 10 Sec Memory Limit: 256 MB
Submissions: 168 Solved: 8

Description

Google is famous over the world, much of the reason for their success lies with the effective search result for their user. In the final, support this effective is the technique called PageRank which largely used the huge url link network. A simple example is a hyperlink in Page A linked to Page B is viewed as A give a vote of support to B.

For us, PageRank is a complex technique, to simplify the problem, let’s analysis a simple model first. For every hyperlink, we just give 2 kind of attribute, the tag on the hyperlink, and the target url hyperlink point. So a hyperlink is viewed as a tag vote to an url.

As a user of search engine, each time we search, we will offer an keywork. Now the problem is for each given keywork, check all given hyperlink, if the tag on hyperlink contain this keywork, we count it’s a effective vote, then list the top 10 most voted url. (if 2 urls get the same votes, we sort it with lexicographic order)

 

Input

First line is N, indicate N hyperlinks. (1<=N<=20000)

Next N lines:

Each line contain two string, the first is the tag of hyperlink and the second is the url.

We guarantee that tags just contain lowcase and the length is less than 7, and urls just not contain blank characters(blank spaces, tabs and line break characters), the length of urls is less than 30.

 

Next line is Q, indicate Q times search. (1<=Q<=50000)

Next Q lines:

Each line just contain a string, indicate the keyword offered by user.

 

Output

For each search, list the top10 most voted urls, and a blankspace and the vote number.(if less then 10 urls be voted, just list all). If no url get votes, just output “Sorry, no result satisfied." In a single line.

For the answer of difference search, output a blank line between them.(Never leave a redundant blank line before the end of file)

 

Important hint, huge output, printf is recommended.

 

Sample Input

10
hustacm http://acm.hust.edu.cn
acmicpc http://acm.hust.edu.cn
acm http://acm.hust.edu.cn
hoj http://acm.hust.edu.cn/thx
vjudge http://acm.hust.edu.cn/vt
forum http://acm.hust.edu.cn/forum
hhoj http://acm.hust.edu.cn/vt
isun http://acm.hust.edu.cn/vt
sempr http://acm.hust.edu.cn/thx
gaewah http://acm.hust.edu.cn/forum
6
acm
m
hoj
zy
j
h

Sample Output

http://acm.hust.edu.cn 3
http://acm.hust.edu.cn 3
http://acm.hust.edu.cn/forum 1
http://acm.hust.edu.cn/thx 1
http://acm.hust.edu.cn/thx 1
http://acm.hust.edu.cn/vt 1
Sorry, no result satisfied.
http://acm.hust.edu.cn/vt 2
http://acm.hust.edu.cn/thx 1
http://acm.hust.edu.cn 1
http://acm.hust.edu.cn/forum 1
http://acm.hust.edu.cn/thx 1
http://acm.hust.edu.cn/vt 1

HINT

 

Source

HONG Zehua / HUST Monthly 2011.04.09


繁瑣的字符串插入查找,Trie 靈活應(yīng)用,因?yàn)榭臻g問題,用了一級指針,二級指針,鏈表。

預(yù)先開一個字符串buffer,用于存儲 tag 和 url,其它保存 url 的地方只保存相應(yīng)指針。

先根據(jù) url 字典序?qū)⑤斎氲?< tag,url > 排序,利用 Trie 統(tǒng)計對于同一個 url 的所有tag的所有子串對此 url 的 vote,同一tag的相同子串不要重復(fù)計數(shù),通過在 Trie 中加入mask實(shí)現(xiàn)。

Trie 中節(jié)點(diǎn)只保存本關(guān)鍵字投票的 Vote 鏈表的指針,若此節(jié)點(diǎn)對某 url 有投票,則 Vote 鏈表非空,且只保存得票最高的前 10 名。

程序用時 1932 MS。

  1#include <stdio.h>
  2#include <string.h>
  3#include <stdlib.h>
  4
  5
  6#define  N   20009
  7#define  INF 0x3f3f3f3f
  8
  9#define  STR_LEN  35
 10#define  BUF_TM   (N+N)
 11
 12char buf[ BUF_TM ][ STR_LEN ];
 13int  buf_end;
 14
 15#define  buf_init()  buf_end = 0
 16#define  buf_new()   buf[ buf_end++ ]
 17
 18
 19struct __Data
 20{
 21        char *tag, *url;
 22}
;
 23typedef struct __Data Data;
 24
 25int cmpData( const void *a, const void *b ) {
 26        return strcmp( ((Data*)a)->url, ((Data*)b)->url );
 27}

 28Data  data[ N ];
 29
 30
 31#define  VOTE_TM   3200000
 32#define  VOTE_LIM  10
 33
 34struct __Vote
 35{
 36        char *pSz;
 37        int  vote;
 38        struct __Vote *next;
 39}
;
 40typedef struct __Vote Vote;
 41Vote  vote_mem[ VOTE_TM ];
 42int   vote_end;
 43
 44#define vote_init()   vote_end = 0
 45#define vote_bef(a,b) ( ((a)->vote > (b)->vote) || (((a)->vote == (b)->vote)&&(strcmp((a)->pSz,(b)->pSz)<=0)) )
 46
 47Vote* vote_new() {
 48        Vote *= vote_mem + vote_end++;
 49        memset( p, 0sizeof(Vote) );
 50        return p;
 51}

 52
 53
 54#define  TRIE_TC   26
 55#define  TRIE_TM   2000000
 56
 57struct __Trie
 58{
 59        int flag, mask, cnt;
 60        Vote *pVote;
 61        struct __Trie *ch[ TRIE_TC ];
 62}
;
 63typedef struct __Trie Trie;
 64Trie  trie_mem[ TRIE_TM ];
 65int   trie_end;
 66
 67#define trie_init()   trie_end = 0
 68
 69Trie* trie_new() {
 70        Trie *= trie_mem + trie_end++;
 71        memset( p, 0sizeof(Trie) );
 72        return p;
 73}

 74
 75void trie_addcnt( Trie **pRoot, char *p, int mask ) {
 76        for ( ; ; ) {
 77                if ( (*pRoot) == NULL ) {
 78                        (*pRoot) = trie_new();
 79                }

 80                if ( *p ) {
 81                        pRoot = &( (*pRoot)->ch[ (*p) - 'a' ] );
 82                        ++p;
 83                }

 84                else {
 85                        if ( (*pRoot)->mask != mask ) {
 86                                (*pRoot)->mask = mask;
 87                                ++((*pRoot)->cnt);
 88                        }

 89                        return;
 90                }

 91        }

 92}

 93
 94int trie_getcnt( Trie *root, char *p ) {
 95        for ( ; ; ) {
 96                if ( root == NULL ) {
 97                        return 0;
 98                }

 99                if ( *p ) {
100                        root = root->ch[ (*p) - 'a' ];
101                        ++p;
102                }

103                else {
104                        return root->cnt;
105                }

106        }

107        return 0;
108}

109
110void trie_insert( Trie **pRoot, char *p, char *url, int vote, int mask ) {
111        for ( ; ; ) {
112                if ( (*pRoot) == NULL ) {
113                        (*pRoot) = trie_new();
114                }

115                if ( *p ) {
116                        pRoot = &( (*pRoot)->ch[ (*p) - 'a' ] );
117                        ++p;
118                }

119                else {
120                        (*pRoot)->cnt = 0;
121                        if ( (*pRoot)->mask != mask ) {
122                                Vote *pred, **ppVote, *nv;
123                                int cnt;
124
125                                (*pRoot)->flag = 1;
126                                (*pRoot)->mask = mask;
127
128                                ppVote = &((*pRoot)->pVote);
129                                if ( (*ppVote) == NULL ) {
130                                        (*ppVote) = vote_new();
131                                        (*ppVote)->vote = INF;
132                                }

133
134                                nv = vote_new();
135                                nv->pSz = url;
136                                nv->vote = vote;
137
138                                pred = (*ppVote);
139                                ppVote = &(pred->next);
140                                while ( (*ppVote) != NULL ) {
141                                        if ( vote_bef(pred,nv) && vote_bef(nv,(*ppVote)) ) {
142                                                if ( strcmp( nv->pSz, (*ppVote)->pSz ) != 0 ) {
143                                                        nv->next = pred->next;
144                                                        pred->next = nv;
145                                                }

146                                                break;
147                                        }

148                                        pred = (*ppVote);
149                                        ppVote = &(pred->next);
150                                }

151
152                                if ( (*ppVote) == NULL ) {
153                                        (*ppVote) = nv;
154                                }

155
156                                cnt = 1;
157                                for ( nv = (*pRoot)->pVote->next; (nv!=NULL)&&(cnt<VOTE_LIM); nv=nv->next ) {
158                                        ++cnt;
159                                }

160                                if ( nv != NULL ) {
161                                        nv->next = NULL;
162                                }

163                        }

164                        return;
165                }

166        }

167}

168
169Trie* trie_find( Trie *root, char *p ) {
170        for ( ; ; ) {
171                if ( root == NULL ) {
172                        return NULL;
173                }

174                if ( *p ) {
175                        root = root->ch[ (*p) - 'a' ];
176                        ++p;
177                }

178                else {
179                        return root;
180                }

181        }

182}

183
184void solve( Trie *root, char *pSz ) {
185        Trie *= trie_find( root, pSz );
186        Vote *i;
187        if ( (p==NULL) || (!p->flag) ) {
188                printf( "Sorry, no result satisfied.\n" );
189                return;
190        }

191        for ( i = p->pVote->next; i!=NULL; i=i->next ) {
192                printf( "%s %d\n", i->pSz, i->vote );
193        }

194}

195
196int main() {
197        char  tmp[ STR_LEN ];
198        int n, mask = 10, i, j, k, x, y, vote;
199        Trie *root = NULL;
200
201        vote_init();
202        trie_init();
203        buf_init();
204        scanf( "%d"&n );
205        for ( i = 0; i < n; ++i ) {
206                data[ i ].tag = buf_new();
207                data[ i ].url = buf_new();
208                scanf( "%s%s", data[ i ].tag, data[ i ].url );
209        }

210        qsort( data, n, sizeof(data[0]), cmpData );
211
212        i = j = 0;
213        do {
214                while ( (j<n) && (strcmp(data[j].url,data[i].url)==0) ) {
215                        ++j;
216                }

217
218                for ( k = i; k < j; ++k ) {
219                        ++mask;
220                        for ( x = 0; data[k].tag[x]; ++x ) {
221                                for ( y = x; data[k].tag[y]; ++y ) {
222                                        tmp[ y-x ] = data[k].tag[y];
223                                        tmp[ y-x+1 ] = 0;
224                                        trie_addcnt( &root, tmp, mask );
225                                }

226                        }

227                }

228
229                for ( k = i; k < j; ++k ) {
230                        ++mask;
231                        for ( x = 0; data[k].tag[x]; ++x ) {
232                                for ( y = x; data[k].tag[y]; ++y ) {
233                                        tmp[ y-x ] = data[k].tag[y];
234                                        tmp[ y-x+1 ] = 0;
235                                        vote = trie_getcnt( root, tmp );
236                                        if ( vote > 0 ) {
237                                                trie_insert( &root, tmp, data[i].url, vote, mask );
238                                        }

239                                }

240                        }

241                }

242
243                i = j;
244        }
 while ( j < n );
245
246        scanf( "%d"&n );
247        while ( n-- > 0 ) {
248                scanf( "%s", tmp );
249                solve( root, tmp );
250                if ( n > 0 ) {
251                        printf( "\n" );
252                }

253        }

254        return 0;
255}

256

posted on 2011-04-10 21:23 coreBugZJ 閱讀(324) 評論(0)  編輯 收藏 引用 所屬分類: ACM

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            麻豆精品视频在线观看| 快射av在线播放一区| 欧美系列一区| 亚洲欧美激情视频在线观看一区二区三区 | 国产精品免费一区二区三区在线观看 | 伊人成人开心激情综合网| 蜜桃av噜噜一区| 免费成人网www| 一区二区三区精密机械公司 | 欧美精品一区二区三区四区| 在线亚洲精品福利网址导航| 亚洲一区免费网站| 国内精品久久久久久影视8| 欧美1区免费| 欧美日韩一区精品| 久久国产精品一区二区三区四区| 久久免费高清| 亚洲私人影院在线观看| 欧美在线视频免费观看| 亚洲精选中文字幕| 亚洲综合色婷婷| 亚洲国产精品国自产拍av秋霞| 99av国产精品欲麻豆| 精品成人国产| 国产精品99久久久久久久久久久久| 国产一区二区三区四区在线观看| 亚洲国产精品va在线看黑人动漫| 国产精品乱人伦一区二区 | 欧美激情第二页| 国产精品入口尤物| 亚洲日本成人| 精品成人乱色一区二区| 亚洲一区久久久| 亚洲精品一区在线观看| 欧美亚洲综合久久| 亚洲一区黄色| 欧美激情网站在线观看| 麻豆精品视频在线观看| 国产精品久久久久久影视 | 欧美一区二区啪啪| 欧美精品一区二区三区在线播放| 久久尤物视频| 国产欧美一区二区色老头| 亚洲美女性视频| 亚洲精品国产日韩| 美女亚洲精品| 欧美国产精品人人做人人爱| 国产深夜精品| 亚洲欧美中文日韩在线| 亚洲一区网站| 欧美日韩国产一中文字不卡| 亚洲国产精品悠悠久久琪琪| 精品99一区二区三区| 欧美专区在线播放| 久久激情五月激情| 国产一区二区日韩精品欧美精品| 亚洲午夜精品一区二区| 亚洲网站在线| 欧美性猛交xxxx乱大交退制版| 最新国产の精品合集bt伙计| 亚洲日韩欧美一区二区在线| 欧美va天堂| 91久久国产综合久久蜜月精品| 亚洲国产综合91精品麻豆| 久久免费精品视频| 欧美大色视频| 999在线观看精品免费不卡网站| 欧美成年人网| 亚洲日本aⅴ片在线观看香蕉| 日韩一区二区电影网| 欧美日韩成人综合| 一区二区成人精品 | 一区二区三区精品国产| 欧美三日本三级少妇三99| 亚洲最新中文字幕| 欧美亚洲综合网| 国产亚洲毛片在线| 美女视频一区免费观看| 亚洲韩日在线| 亚洲女性裸体视频| 国产揄拍国内精品对白| 久久综合激情| aa级大片欧美三级| 欧美在线一级va免费观看| 好吊视频一区二区三区四区| 老牛嫩草一区二区三区日本 | 欧美一级专区| 在线观看久久av| 欧美日韩成人综合在线一区二区| 一区二区三区四区五区精品| 久久精品久久99精品久久| 在线观看一区二区精品视频| 欧美日韩免费精品| 欧美一区三区三区高中清蜜桃| 免费日本视频一区| 亚洲一区二区三区乱码aⅴ蜜桃女| 国产精品午夜久久| 免费成人网www| 亚洲欧美激情一区二区| 欧美激情亚洲一区| 欧美在线免费一级片| 亚洲精品欧美| 国语自产精品视频在线看| 欧美日韩精品欧美日韩精品| 久久精品欧美| 亚洲午夜精品网| 亚洲三级国产| 免费观看日韩av| 久久成人在线| 亚洲午夜小视频| 日韩视频一区二区三区| 禁久久精品乱码| 国产精品热久久久久夜色精品三区| 久久亚洲综合网| 欧美亚洲一区二区在线| 一区二区三欧美| 亚洲精品乱码久久久久久日本蜜臀| 久久九九久精品国产免费直播| 亚洲视频久久| 亚洲精品视频在线观看网站| 国模吧视频一区| 国产日韩欧美在线看| 欧美午夜精品久久久久久超碰| 欧美高清在线视频观看不卡| 久久精品国产亚洲精品| 午夜精品久久久久久久久久久久| 日韩亚洲国产精品| 亚洲国产精品一区在线观看不卡| 免费成人网www| 毛片基地黄久久久久久天堂| 欧美在线3区| 久久精品av麻豆的观看方式 | 亚洲日本中文字幕免费在线不卡| 一区二区三区自拍| 在线不卡中文字幕| 韩国v欧美v日本v亚洲v| 国外成人网址| 一区二区三区在线高清| 极品裸体白嫩激情啪啪国产精品| 国产一区在线播放| 经典三级久久| 亚洲欧洲视频在线| 日韩视频不卡| 国产精品99久久久久久人| 在线一区二区三区做爰视频网站| 亚洲免费激情| 亚洲伊人网站| 久久av一区二区三区漫画| 性欧美超级视频| 久久久精品国产一区二区三区| 久久精品国产999大香线蕉| 久久久久欧美精品| 鲁大师成人一区二区三区| 蘑菇福利视频一区播放| 欧美激情一级片一区二区| 亚洲国产一区二区a毛片| 99re66热这里只有精品3直播| 一区二区久久久久| 午夜久久电影网| 久久五月婷婷丁香社区| 欧美激情一区二区在线| 国产精品黄页免费高清在线观看| 国产日韩成人精品| 亚洲国产另类精品专区 | 亚洲高清三级视频| 国产精品99久久久久久白浆小说| 性久久久久久久久久久久| 久久精品夜色噜噜亚洲a∨| 欧美第一黄色网| 亚洲一区二区三区四区在线观看| 久久国产一区二区三区| 欧美国产日韩一区二区三区| 国产精品久久99| 亚洲大胆人体在线| 亚洲在线国产日韩欧美| 免费一级欧美在线大片| 亚洲九九精品| 久久夜色精品国产噜噜av| 欧美视频在线看| 亚洲电影免费在线| 午夜精品一区二区在线观看| 免费欧美视频| 午夜一级在线看亚洲| 欧美精品在线视频观看| 国产在线精品自拍| 亚洲视频久久| 亚洲成人自拍视频| 欧美在线视频网站| 欧美午夜在线| 日韩亚洲一区二区| 欧美不卡在线| 欧美一级视频精品观看| 欧美日韩免费看| 亚洲欧洲一二三| 另类av导航| 欧美在线免费看| 国产精品午夜在线观看| 99精品福利视频| 亚洲国产精品久久久久婷婷老年| 久久精品成人一区二区三区蜜臀|