• <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>

            A Za, A Za, Fighting...

            堅信:勤能補(bǔ)拙

            求平面最近點對的核心思想乃是二分,用遞歸實現(xiàn)。具體操作如下:

                 若點的個數(shù)很少(比如小于3或者小于5),就直接枚舉。

                 如點的個數(shù)很多,按現(xiàn)將所有點按X排序,并按X坐標(biāo)平均的分成左右兩個部分(假設(shè)分割線為X=nx),分別求出兩邊的最短距離minl與minr并令ans=min(minl,minr)。

                 求出左右兩邊的最小值之后,剩下的工作就是合并。易見若該點集存在點對(a,b)的最近距離小于ans,則a,b一定分別在x=nx的兩邊,切nx-a.x與nx-b.x的絕對值肯定小于ans。

                 據(jù)此我們可以將點集中所有X值在(nx-ans,nx+ans)的點都選出來,那么滿足條件的(a,b)肯定都在其中。

                 易見若存在(a,b)兩點他們之間的距離小于ans,那么a.y-b.y的絕對值也肯定小于ans。

                 綜上存在(a,b)兩點他們之間的距離小于ans那,(a,b)一定在一個長為2*ans寬為ans的矩形之中。而 且這個矩形被X=nx平分成兩個ans*ans的矩形,由于無論是在左邊還是在右邊,任意兩點的之間的距離總是小于等于ans的,所以兩個ans*ans 的矩形中最多只有4個點(分別在四個頂點上),長為2*ans寬為ans的矩形最多有8個點。

                 據(jù)此我們將所有X值在(nx-ans,nx+ans)的點按他們的Y值進(jìn)行排序。依次看每個點與它之后的7個點的距離是否小于ans,若小于則更新ans,最后求出來的結(jié)果就是平面最近點對的距離。保留產(chǎn)生該距離的兩個點即可得到最近點對。

                 練手題目:Pku2107,Vijos1012

            附C++代碼(Pku2107):

            #include <iostream>
            #include <cmath>

            const long maxsize = 100000;

            typedef struct 

            double x, y; 
            } PointType;

            long list[maxsize], listlen,n;
            PointType point[maxsize];

            int sortcmp(const void *,const void *); 
            double dis(PointType,PointType);
            double getmin(double,double);
            int listcmp(const void *,const void *); 
            double shortest(long,long);
            int init(void);

            int main() 

            while (init())
               printf("%.2lf\n",shortest(0, n - 1)/2);    
            return 0;
            }

            int sortcmp(const void *a, const void *b) 

            if (((PointType*)a)->x < ((PointType*)b)->x)    
               return -1;   
            else 
               return 1; 
            }

            double dis(PointType a, PointType b) 

            return sqrt((a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y)); 
            }

            double getmin(double a, double b) 

            return a<b?a:b;
            }

            int listcmp(const void *a, const void *b) 

            if (point[*(int*)a].y < point[*(int*)b].y)    
               return -1;   
            else 
               return 1; 
            }

            double shortest(long l, long r) 

            if (r - l == 1) 
               return dis(point[l], point[r]);   
            if (r - l == 2)    
               return getmin(getmin(dis(point[l], point[l+1]), dis(point[l], point[r])), dis(point[l+1], point[r]));   
            long i, j, mid = (l + r) >> 1;   
            double curmin = getmin(shortest(l, mid), shortest(mid + 1, r));   
            listlen = 0;   
            for (i = mid; i >= l && point[mid+1].x - point[i].x <= curmin; i --)    
               list[listlen++] = i;   
            for (i = mid + 1; i <= r && point[i].x - point[mid].x <= curmin; i ++)    
               list[listlen++] = i;   
            qsort(list, listlen, sizeof(list[0]), listcmp);   
            for (i = 0; i < listlen; i ++)    
               for (j = i + 1; j < listlen && point[list[j]].y - point[list[i]].y <= curmin; j ++)     
                curmin = getmin(curmin, dis(point[list[i]], point[list[j]]));   
            return curmin; 
            }

            int init(void)
            {
            int i;
            scanf("%d", &n);      
            for (i=0;i<n;i++) 
               scanf("%lf%lf",&point[i].x,&point[i].y);      
            qsort(point,n,sizeof(point[0]),sortcmp);
            return n;
            }


            自己寫的代碼:

            /*
             * Problem(classic):
             *    there're many points in a plane surface, find the nearest two points
             *    see: <CLRS> 33.4 section
             
            */
            #include
            <stdio.h>
            #include
            <stdlib.h>
            #include
            <string.h>
            #include
            <math.h>
            #define INF 0x7FFFFFFF
            #define NUM_MAX 100000
            #define THRESHOLD 3

            struct Point {
                
            double x, y;
            };
            struct Point points[NUM_MAX];
            int total, yindex[NUM_MAX];

            double
            min(
            double arg1, double arg2)
            {
                
            return (arg1 <= arg2 ? arg1 : arg2);
            }

            double
            distance(
            struct Point *arg1, struct Point *arg2)
            {
                
            double x_diff = arg1->- arg2->x;
                
            double y_diff = arg1->- arg2->y;
                
            return sqrt(x_diff*x_diff + y_diff*y_diff);
            }

            int
            compare_x(
            const void *arg1, const void *arg2)
            {
                
            struct Point *p1 = (struct Point *)arg1;
                
            struct Point *p2 = (struct Point *)arg2;
                
            return (p1->- p2->x);
            }

            int
            compare_y(
            const void *arg1, const void *arg2)
            {
                
            struct Point *p1 = points + *(int *)arg1;
                
            struct Point *p2 = points + *(int *)arg2;
                
            return (p1->- p2->y);
            }

            void
            init_preprocess()
            {
                
            int i;
                scanf(
            "%d"&total);
                
            for(i=0; i<total; ++i)
                    scanf(
            "%lf %lf"&points[i].x, &points[i].y);
                qsort(points, total, 
            sizeof(struct Point), compare_x);
            }

            double
            find_nearest(
            int begin, int end)
            {
                
            int i, j;
                
            double ret = INF;
                
            if(end-begin+1 <= THRESHOLD) {
                    
            for(i=begin; i<end; ++i) {
                        
            for(j=i+1; j<=end; ++j)
                            ret 
            = min(ret, distance(points+i, points+j));
                    }
                    
            return ret;
                }
                
            int mid = begin + ((end - begin) >> 1);
                
            double dis = min(find_nearest(begin, mid), find_nearest(mid+1, end));
                
            int len = 0;
                
            for(j=mid; j>=begin && points[mid+1].x-points[j].x<=dis; --j)
                    yindex[len
            ++= j;
                
            for(j=mid+1; j<=end && points[j].x-points[mid].x<=dis; ++j)
                    yindex[len
            ++= j;
                qsort(yindex, len, 
            sizeof(int), compare_y);
                ret 
            = dis;
                
            for(i=0; i<=len-7++i) {
                    
            for(j=i+1; j<=i+7++j)
                        ret 
            = min(ret, distance(points+yindex[i], points+yindex[j]));
                }
                
            return ret;
            }

            double
            brute_force(
            int begin, int end)
            {
                
            double ret = INF;
                
            int i, j;
                
            for(i=begin; i<end; ++i) {
                    
            for(j=i+1; j<=end; ++j)
                        ret 
            = min(ret, distance(points+i, points+j));
                }
                
            return ret;
            }

            int
            main(
            int argc, char **argv)
            {
                init_preprocess();
                
            double ret = find_nearest(0, total-1);
                printf(
            "\nNearest Distance[Brute Force]: %f\n", brute_force(0, total-1));
                printf(
            "\nNearest Distance: %f\n", ret);
            }


            posted @ 2011-09-03 23:17 simplyzhao 閱讀(1160) | 評論 (1)編輯 收藏
             在socket網(wǎng)絡(luò)程序中,TCP和UDP分別是面向連接和非面向連接的。因此TCP的socket編程,收發(fā)兩端(客戶端和服務(wù)器端)都要有一一成對的socket,因此,發(fā)送端為了將多個發(fā)往接收端的包,更有效的發(fā)到對方,使用了優(yōu)化方法(Nagle算法),將多次間隔較小且數(shù)據(jù)量小的數(shù)據(jù),合并成一個大的數(shù)據(jù)塊,然后進(jìn)行封包。這樣,接收端,就難于分辨出來了,必須提供科學(xué)的拆包機(jī)制。
                   對于UDP,不會使用塊的合并優(yōu)化算法,這樣,實際上目前認(rèn)為,是由于UDP支持的是一對多的模式,所以接收端的skbuff(套接字緩沖區(qū))采用了鏈?zhǔn)浇Y(jié)構(gòu)來記錄每一個到達(dá)的UDP包,在每個UDP包中就有了消息頭(消息來源地址,端口等信息),這樣,對于接收端來說,就容易進(jìn)行區(qū)分處理了

            保護(hù)消息邊界和流

            那么什么是保護(hù)消息邊界和流呢?

                   保護(hù)消息邊界,就是指傳輸協(xié)議把數(shù)據(jù)當(dāng)作一條獨立的消息在網(wǎng)上 
            傳輸,接收端只能接收獨立的消息.也就是說存在保護(hù)消息邊界,接收 
            端一次只能接收發(fā)送端發(fā)出的一個數(shù)據(jù)包. 
                   而面向流則是指無保護(hù)消息保護(hù)邊界的,如果發(fā)送端連續(xù)發(fā)送數(shù)據(jù), 
            接收端有可能在一次接收動作中,會接收兩個或者更多的數(shù)據(jù)包.

                   我們舉個例子來說,例如,我們連續(xù)發(fā)送三個數(shù)據(jù)包,大小分別是2k, 
            4k , 8k,這三個數(shù)據(jù)包,都已經(jīng)到達(dá)了接收端的網(wǎng)絡(luò)堆棧中,如果使 
            UDP協(xié)議,不管我們使用多大的接收緩沖區(qū)去接收數(shù)據(jù),我們必須有 
            三次接收動作,才能夠把所有的數(shù)據(jù)包接收完.而使用TCP協(xié)議,我們 
            只要把接收的緩沖區(qū)大小設(shè)置在14k以上,我們就能夠一次把所有的 
            數(shù)據(jù)包接收下來.只需要有一次接收動作.

                   這就是因為UDP協(xié)議的保護(hù)消息邊界使得每一個消息都是獨立的.而 
            流傳輸,卻把數(shù)據(jù)當(dāng)作一串?dāng)?shù)據(jù)流,他不認(rèn)為數(shù)據(jù)是一個一個的消息.

                  所以有很多人在使用tcp協(xié)議通訊的時候,并不清楚tcp是基于流的 
            傳輸,當(dāng)連續(xù)發(fā)送數(shù)據(jù)的時候,他們時常會認(rèn)識tcp會丟包.其實不然, 
            因為當(dāng)他們使用的緩沖區(qū)足夠大時,他們有可能會一次接收到兩個甚 
            至更多的數(shù)據(jù)包,而很多人往往會忽視這一點,只解析檢查了第一個 
            數(shù)據(jù)包,而已經(jīng)接收的其他數(shù)據(jù)包卻被忽略了.所以大家如果要作這 
            類的網(wǎng)絡(luò)編程的時候,必須要注意這一點.

            結(jié)論:
                 根據(jù)以上所說,可以這樣理解,TCP為了保證可靠傳輸,盡量減少額外
            開銷(每次發(fā)包都要驗證),因此采用了流式傳輸,面向流的傳輸,
            相對于面向消息的傳輸,可以減少發(fā)送包的數(shù)量。從而減少了額外開
            銷。但是,對于數(shù)據(jù)傳輸頻繁的程序來講,使用TCP可能會容易粘包。
            當(dāng)然,對接收端的程序來講,如果機(jī)器負(fù)荷很重,也會在接收緩沖里
            粘包。這樣,就需要接收端額外拆包,增加了工作量。因此,這個特
            別適合的是數(shù)據(jù)要求可靠傳輸,但是不需要太頻繁傳輸?shù)膱龊希?br style="line-height: 22px; " />兩次操作間隔100ms,具體是由TCP等待發(fā)送間隔決定的,取決于內(nèi)核
            中的socket的寫法)

            而UDP,由于面向的是消息傳輸,它把所有接收到的消息都掛接到緩沖
            區(qū)的接受隊列中,因此,它對于數(shù)據(jù)的提取分離就更加方便,但是,
            它沒有粘包機(jī)制,因此,當(dāng)發(fā)送數(shù)據(jù)量較小的時候,就會發(fā)生數(shù)據(jù)包
            有效載荷較小的情況,也會增加多次發(fā)送的系統(tǒng)發(fā)送開銷(系統(tǒng)調(diào)用,
            寫硬件等)和接收開銷。因此,應(yīng)該最好設(shè)置一個比較合適的數(shù)據(jù)包
            的包長,來進(jìn)行UDP數(shù)據(jù)的發(fā)送。(UDP最大載荷為1472,因此最好能
            每次傳輸接近這個數(shù)的數(shù)據(jù)量,這特別適合于視頻,音頻等大塊數(shù)據(jù)
            的發(fā)送,同時,通過減少握手來保證流媒體的實時性)

            來自: http://hi.baidu.com/chongerfeia/blog/item/b1e572f631dd7e28bd310965.html

            TCP無保護(hù)消息邊界的解決
             針對這個問題,一般有3種解決方案:

                  (1)發(fā)送固定長度的消息

                  (2)把消息的尺寸與消息一塊發(fā)送

                  (3)使用特殊標(biāo)記來區(qū)分消息間隔

                 

            下面我們主要分析下前兩種方法:

            1、發(fā)送固定長度的消息 
            這種方法的好處是他非常容易,而且只要指定好消息的長度,沒有遺漏未未發(fā)的數(shù)據(jù),我們重寫了一個SendMessage方法。代碼如下:

              private static int SendMessage(Socket s, byte[] msg)

                    { 
                        int offset = 0; 
                        int size = msg.Length; 
                        int dataleft = size;

                        while (dataleft > 0) 
                        {

                            int sent = s.Send(msg, offset, SocketFlags.None); 
                            offset += sent; 
                            dataleft -= sent;

                        }

                        return offset; 
                    }

            簡要分析一下這個函數(shù):形參s是進(jìn)行通信的套接字,msg即待發(fā)送的字節(jié)數(shù)組。該方法使用while循環(huán)檢查是否還有數(shù)據(jù)未發(fā)送,尤其當(dāng)發(fā)送一個很龐大的數(shù)據(jù)包,在不能一次性發(fā)完的情況下作用比較明顯。特別的,用sent來記錄實際發(fā)送的數(shù)據(jù)量,和recv是異曲同工的作用,最后返回發(fā)送的實際數(shù)據(jù)總數(shù)。

               有sentMessage函數(shù)后,還要根據(jù)指定的消息長度來設(shè)計一個新的Recive方法。代碼如下:

              private byte[] ReciveMessage(Socket s, int size) 
                    {

                        int offset = 0; 
                        int recv; 
                        int dataleft = size; 
                        byte[] msg = new byte[size];


                        while (dataleft > 0)

                        {

                            //接收消息 
                            recv = s.Receive(msg, offset, dataleft, 0); 
                            if (recv == 0)

                            {

                                break;

                            } 
                            offset += recv; 
                            dataleft -= recv;

                        }

                        return msg;

                    }

            以上這種做法比較適合于消息長度不是很長的情況。

            2、消息長度與消息一同發(fā)送

            我們可以這樣做:通過使用消息的整形數(shù)值來表示消息的實際大小,所以要把整形數(shù)轉(zhuǎn)換為字節(jié)類型。下面是發(fā)送變長消息的SendMessage方法。具體代碼如下:

              private static int SendMessage(Socket s, byte[] msg) 
                    {

                        int offset = 0; 
                        int sent; 
                        int size = msg.Length; 
                        int dataleft = size; 
                        byte[] msgsize = new byte[2];

                        //將消息尺寸從整形轉(zhuǎn)換成可以發(fā)送的字節(jié)型 
                        msgsize = BitConverter.GetBytes(size);


                        //發(fā)送消息的長度信息 
                        sent = s.Send(size);

                        while (dataleft > 0)

                        {

                            sent = s.Send(msg, offset, dataleft, SocketFlags.None);

                            //設(shè)置偏移量

                            offset += sent; 
                            dataleft -= sent;

                        }

                        return offset;

                    }


            下面是接收變長消息的ReciveVarMessage方法。代碼如下:

            private byte[] ReciveVarMessage(Socket s) 
                    {


                        int offset = 0; 
                        int recv; 
                        byte[] msgsize = new byte[2];


                        //將字節(jié)數(shù)組的消息長度信息轉(zhuǎn)換為整形 
                        int size = BitConverter.ToInt16(msgsize); 
                        int dataleft = size; 
                        byte[] msg = new byte[size];


                        //接收2個字節(jié)大小的長度信息 
                        recv = s.Receive(msgsize, 0, 2, 0); 
                        while (dataleft > 0) 
                        {

                            //接收數(shù)據(jù) 
                            recv = s.Receive(msg, offset, dataleft, 0); 
                            if (recv == 0) 
                            { 
                                break; 
                            } 
                            offset += recv; 
                            dataleft -= recv;

                        }

                        return msg;

                    }

            posted @ 2011-09-01 18:36 simplyzhao 閱讀(653) | 評論 (0)編輯 收藏
            from: Programming Pearl

            /* Copyright (C) 1999 Lucent Technologies */
            /* From 'Programming Pearls' by Jon Bentley */

            /* longdup.c -- Print longest string duplicated M times */

            #include 
            <stdlib.h>
            #include 
            <string.h>
            #include 
            <stdio.h>

            int pstrcmp(char **p, char **q)
            {   
            return strcmp(*p, *q); }

            int comlen(char *p, char *q)
            {    
            int i = 0;
                
            while (*&& (*p++ == *q++))
                    i
            ++;
                
            return i;
            }

            #define M 1
            #define MAXN 5000000
            char c[MAXN], *a[MAXN];

            int main()
            {   
            int i, ch, n = 0, maxi, maxlen = -1;
                
            while ((ch = getchar()) != EOF) {
                    a[n] 
            = &c[n];
                    c[n
            ++= ch;
                }
                c[n] 
            = 0;
                qsort(a, n, 
            sizeof(char *), pstrcmp);
                
            for (i = 0; i < n-M; i++)
                    
            if (comlen(a[i], a[i+M]) > maxlen) {
                        maxlen 
            = comlen(a[i], a[i+M]);
                        maxi 
            = i;
                    }
                printf(
            "%.*s\n", maxlen, a[maxi]);
                
            return 0;
            }
            posted @ 2011-08-19 15:11 simplyzhao 閱讀(589) | 評論 (1)編輯 收藏
            代碼1(STL的map版本)
            #include<iostream>
            #include
            <map>
            #include
            <string>

            using namespace std;

            int
            main(
            int argc, char **argv)
            {
                map
            <stringint> M;
                map
            <stringint>::iterator j;
                
            string t;
                
            while(cin>>t)
                    M[t]
            ++;

                
            for(j=M.begin(); j!=M.end(); ++j)
                    cout
            <<j->first<<"\t"<<j->second<<endl;

                
            return 0;
            }


            代碼2(自己的Hash)
            #include<stdio.h>
            #include
            <stdlib.h>
            #include
            <string.h>
            #define WORD_BUF 128
            #define NHASH 29989 /* prime number just bigger than needed */
            #define MULT 31

            struct HNode {
                
            char *word;
                
            int count;
                
            struct HNode *next;
            };
            struct HNode *Hash[NHASH] = {NULL}; 

            #define NODEGROUP 1000
            struct HNode *nodebuf;
            int nodeleft = 0;

            struct HNode *
            node_alloc()
            {
                
            if(nodeleft == 0) {
                    nodebuf 
            = (struct HNode *)malloc(NODEGROUP * sizeof(struct HNode));
                    nodeleft 
            = NODEGROUP;
                }
                
            --nodeleft;
                
            return (nodebuf++);
            }

            unsigned 
            int
            hash(
            char *str) /* a simple implementation of string-hash, others like ELFHash */
            {
                unsigned 
            int ret = 0;
                
            char *ptr;
                
            for(ptr=str; *ptr; ++ptr)
                    ret 
            = ret * MULT + (*ptr);
                
            return (ret % NHASH);
            }

            void
            insert_hash(
            char *word)
            {
                
            struct HNode *node;
                unsigned 
            int h = hash(word);
                
            for(node=Hash[h]; node!=NULL; node=node->next)
                    
            if(strcmp(node->word, word) == 0) {
                        
            ++(node->count);
                        
            return;
                    }
                
            struct HNode *pend = node_alloc();
                pend
            ->word = strdup(word);
                pend
            ->count = 1;
                pend
            ->next = Hash[h];
                Hash[h] 
            = pend;
            }

            int
            main(
            int argc, char **argv)
            {
                
            char buf[WORD_BUF];
                
            while(scanf("%s", buf) != EOF) {
                    insert_hash(buf);
                }

                
            int i;
                
            struct HNode *node;
                
            for(i=0; i<NHASH; ++i) 
                    
            for(node=Hash[i]; node!=NULL; node=node->next) 
                        printf(
            "%s\t%d\n", node->word, node->count);

                
            return 0;
            }

            posted @ 2011-08-19 14:37 simplyzhao 閱讀(581) | 評論 (0)編輯 收藏
            代碼:

            /* 問題: 兩整數(shù)相除,求循環(huán)節(jié) */
            /* 分析:
             * 模擬整數(shù)相除的步驟,記錄每次的商、余,當(dāng)余重復(fù)時即發(fā)現(xiàn)循環(huán)節(jié) 
             * 余的范圍為[0, 被除數(shù)),因此記錄數(shù)組的大小可根據(jù)被除數(shù)確定
             
            */
            #include
            <stdio.h>
            #include
            <stdlib.h>
            #include
            <string.h>

            void
            get_circle_digits(unsigned 
            int a, unsigned int b)
            {
                
            int i, mod, tmp, index = 0;
                
            int *div = (int *)malloc(sizeof(int* b);
                
            int *mod_pos = (int *)malloc(sizeof(int* b);
                memset(mod_pos, 
            -1sizeof(int)*b);
                mod 
            = a = a%b;
                
            while(1) {
                    
            if(mod==0 || mod_pos[mod]!=-1)
                        
            break;
                    mod_pos[mod] 
            = index;
                    tmp 
            = mod*10;
                    div[index] 
            = tmp / b;
                    mod 
            = tmp % b;
                    
            ++index;
                }
                
            if(mod == 0
                    printf(
            "No Circle\n");
                
            else {
                    printf(
            "0.");
                    
            for(i=0; i<mod_pos[mod]; i++)
                        printf(
            "%d", div[i]);
                    printf(
            "(");
                    
            for(i=mod_pos[mod]; i<index; i++)
                        printf(
            "%d", div[i]);
                    printf(
            ")");
                    printf(
            "\n");
                }
            }

            int
            main(
            int argc, char **argv)
            {
                unsigned 
            int a, b;
                
            while(scanf("%u %u"&a, &b) != EOF) {
                    get_circle_digits(a, b);
                }
                
            return 0;
            }
            posted @ 2011-08-17 16:24 simplyzhao 閱讀(486) | 評論 (0)編輯 收藏
            代碼:
            #include<stdio.h>
            #include
            <stdlib.h>
            #include
            <string.h>
            #define MAX_K 101
            #define MAX_N 1001
            char matrix[MAX_N][MAX_N];
            char visited[MAX_N];
            short count[MAX_N];
            int pastures[MAX_K];

            int K, N, M;

            void
            dfs(
            int pasture)
            {
                
            int i;
                
            ++count[pasture];
                visited[pasture] 
            = 1;
                
            for(i=1; i<=N; ++i) {
                    
            if(matrix[pasture][i] && !visited[i])
                        dfs(i);
                }
            }

            int
            main(
            int argc, char **argv)
            {
                
            int i, x, y, ret = 0;
                scanf(
            "%d %d %d"&K, &N, &M);
                
            for(i=1; i<=K; ++i)
                    scanf(
            "%d", pastures+i);
                
            for(i=1; i<=M; ++i) {
                    scanf(
            "%d %d"&x, &y);
                    matrix[x][y] 
            = 1;
                }
                
                
            for(i=1; i<=K; ++i) {
                    memset(visited, 
            0sizeof(visited));
                    dfs(pastures[i]);
                }

                
            for(i=1; i<=N; ++i)
                    
            if(count[i] == K)
                        
            ++ret;
                printf(
            "%d\n", ret);
            }


            Cow Picnic
            Time Limit: 2000MSMemory Limit: 65536K
            Total Submissions: 3878Accepted: 1576

            Description

            The cows are having a picnic! Each of Farmer John's K (1 ≤ K ≤ 100) cows is grazing in one of N (1 ≤ N ≤ 1,000) pastures, conveniently numbered 1...N. The pastures are connected by M (1 ≤ M ≤ 10,000) one-way paths (no path connects a pasture to itself).

            The cows want to gather in the same pasture for their picnic, but (because of the one-way paths) some cows may only be able to get to some pastures. Help the cows out by figuring out how many pastures are reachable by all cows, and hence are possible picnic locations.

            Input

            Line 1: Three space-separated integers, respectively: KN, and M 
            Lines 2..K+1: Line i+1 contains a single integer (1..N) which is the number of the pasture in which cow i is grazing. 
            Lines K+2..M+K+1: Each line contains two space-separated integers, respectively A and B (both 1..N and A != B), representing a one-way path from pasture A to pasture B.

            Output

            Line 1: The single integer that is the number of pastures that are reachable by all cows via the one-way paths.

            Sample Input

            2 4 4
            2
            3
            1 2
            1 4
            2 3
            3 4

            Sample Output

            2

            Hint

            The cows can meet in pastures 3 or 4.

            Source






            posted @ 2011-08-15 16:13 simplyzhao 閱讀(202) | 評論 (0)編輯 收藏
            代碼:
            #include<stdio.h>
            #include
            <stdlib.h>
            #include
            <string.h>
            #include
            <limits.h>
            #define MAX_NUM 26
            char adj[MAX_NUM][MAX_NUM];
            int num, ret, colors[MAX_NUM];

            int
            is_valid(
            int depth, int color)
            {
                
            int i;
                
            for(i=0; i<depth; ++i) {
                    
            if(adj[i][depth] && colors[i]==color)
                        
            return 0;
                }
                
            return 1;
            }

            void
            dfs(
            int depth, int color_used)
            {
                
            if(color_used >= ret)
                    
            return;
                
            if(depth >= num) {
                    ret 
            = color_used;
                    
            return;
                }

                
            int i;
                
            for(i=0; i<color_used; ++i) {
                    
            if(is_valid(depth, i)) {
                        colors[depth] 
            = i;
                        dfs(depth
            +1, color_used);
                        colors[depth] 
            = -1;
                    }
                }    
                colors[depth] 
            = color_used;
                dfs(depth
            +1, color_used+1);
                colors[depth] 
            = -1;
            }

            int
            main(
            int argc, char **argv)
            {
                
            int i;
                
            char info[MAX_NUM+2], *ptr;

                
            while(scanf("%d"&num)!=EOF && num) {
                    ret 
            = INT_MAX;
                    memset(colors, 
            -1sizeof(colors));
                    memset(adj, 
            0sizeof(adj));
                    
            for(i=0; i<num; ++i) {
                        scanf(
            "%s", info);
                        ptr 
            = info+2;
                        
            while(*ptr != '\0') {
                            adj[i][(
            *ptr)-'A'= 1;
                            
            ++ptr;
                        }
                    }
                    dfs(
            00);
                    printf(
            "%d %s needed.\n", ret, ret<=1?"channel":"channels");
                }
            }

            Channel Allocation
            Time Limit: 1000MSMemory Limit: 10000K
            Total Submissions: 8353Accepted: 4248

            Description

            When a radio station is broadcasting over a very large area, repeaters are used to retransmit the signal so that every receiver has a strong signal. However, the channels used by each repeater must be carefully chosen so that nearby repeaters do not interfere with one another. This condition is satisfied if adjacent repeaters use different channels. 

            Since the radio frequency spectrum is a precious resource, the number of channels required by a given network of repeaters should be minimised. You have to write a program that reads in a description of a repeater network and determines the minimum number of channels required.

            Input

            The input consists of a number of maps of repeater networks. Each map begins with a line containing the number of repeaters. This is between 1 and 26, and the repeaters are referred to by consecutive upper-case letters of the alphabet starting with A. For example, ten repeaters would have the names A,B,C,...,I and J. A network with zero repeaters indicates the end of input. 

            Following the number of repeaters is a list of adjacency relationships. Each line has the form: 

            A:BCDH 

            which indicates that the repeaters B, C, D and H are adjacent to the repeater A. The first line describes those adjacent to repeater A, the second those adjacent to B, and so on for all of the repeaters. If a repeater is not adjacent to any other, its line has the form 

            A: 

            The repeaters are listed in alphabetical order. 

            Note that the adjacency is a symmetric relationship; if A is adjacent to B, then B is necessarily adjacent to A. Also, since the repeaters lie in a plane, the graph formed by connecting adjacent repeaters does not have any line segments that cross. 

            Output

            For each map (except the final one with no repeaters), print a line containing the minumum number of channels needed so that no adjacent channels interfere. The sample output shows the format of this line. Take care that channels is in the singular form when only one channel is required.

            Sample Input

            2
            A:
            B:
            4
            A:BC
            B:ACD
            C:ABD
            D:BC
            4
            A:BCD
            B:ACD
            C:ABD
            D:ABC
            0

            Sample Output

            1 channel needed.
            3 channels needed.
            4 channels needed. 

            Source



            posted @ 2011-08-14 10:32 simplyzhao 閱讀(283) | 評論 (0)編輯 收藏
            代碼:
            #include<stdio.h>
            #include
            <stdlib.h>
            #include
            <string.h>
            #define MAX_NUM 100
            #define VALID(x, y) ((x)>=0 && (x)<m && (y)>=0 && (y)<n)
            int m, n, count;
            char grid[MAX_NUM][MAX_NUM+1];
            char visited[MAX_NUM][MAX_NUM+1];

            const int dx[] = {-1-1-100111};
            const int dy[] = {-101-11-101};
            void
            dfs_inner(
            int x, int y)
            {
                
            int i, next_x, next_y;
                visited[x][y] 
            = 1;
                
            for(i=0; i<8++i) {
                    next_x 
            = x + dx[i];
                    next_y 
            = y + dy[i];
                    
            if(VALID(next_x, next_y) && !visited[next_x][next_y] &&
                            grid[next_x][next_y]
            =='@')
                        dfs_inner(next_x, next_y);
                }
            }

            void
            dfs()
            {
                
            int i, j;
                
            for(i=0; i<m; ++i)
                    
            for(j=0; j<n; ++j)
                        
            if(!visited[i][j] && grid[i][j]=='@') {
                            
            ++count;
                            dfs_inner(i, j);
                        }
            }

            int
            main(
            int argc, char **argv)
            {
                
            int i;
                
            while(scanf("%d %d"&m, &n)!= EOF && m) {
                    count 
            = 0;
                    memset(visited, 
            0sizeof(visited));
                    
            for(i=0; i<m; ++i)
                        scanf(
            "%s", grid[i]);
                    dfs();
                    printf(
            "%d\n", count);
                }
            }

            Oil Deposits
            Time Limit: 1000MSMemory Limit: 10000K
            Total Submissions: 7595Accepted: 4267

            Description

            The GeoSurvComp geologic survey company is responsible for detecting underground oil deposits. GeoSurvComp works with one large rectangular region of land at a time, and creates a grid that divides the land into numerous square plots. It then analyzes each plot separately, using sensing equipment to determine whether or not the plot contains oil. A plot containing oil is called a pocket. If two pockets are adjacent, then they are part of the same oil deposit. Oil deposits can be quite large and may contain numerous pockets. Your job is to determine how many different oil deposits are contained in a grid.

            Input

            The input contains one or more grids. Each grid begins with a line containing m and n, the number of rows and columns in the grid, separated by a single space. If m = 0 it signals the end of the input; otherwise 1 <= m <= 100 and 1 <= n <= 100. Following this are m lines of n characters each (not counting the end-of-line characters). Each character corresponds to one plot, and is either `*', representing the absence of oil, or `@', representing an oil pocket. 

            Output

            are adjacent horizontally, vertically, or diagonally. An oil deposit will not contain more than 100 pockets.

            Sample Input

            1 1 * 3 5 *@*@* **@** *@*@* 1 8 @@****@* 5 5  ****@ *@@*@ *@**@ @@@*@ @@**@ 0 0

            Sample Output

            0 1 2 2 

            Source

            Mid-Central USA 1997

            posted @ 2011-08-14 10:29 simplyzhao 閱讀(326) | 評論 (0)編輯 收藏
                 摘要: 題目:
            給你一個3升的杯子和一個5升的(杯子是沒有刻度的),要你取4升水來(水可以無限取),請問該如何操作。
            泛化:
            給你一個m升的杯子和一個n升的(杯子是沒有刻度的),要你取target升水來(水可以無限取),請問該如何操作.

            思路:
            搜索: BFS or DFS  閱讀全文
            posted @ 2011-08-12 17:40 simplyzhao 閱讀(208) | 評論 (0)編輯 收藏
            前提: 已排序
            時間復(fù)雜度: O(logN)
            例如: 找出某個target出現(xiàn)的位置(隨機(jī)),某個target第一次出現(xiàn)的位置,某個target最后一次出現(xiàn)的位置

            問題: 如果在未排序的數(shù)組中使用二分搜索,結(jié)果會怎么樣?

            答: 如果二分搜索聲稱找到了target,那么該target就一定存在于數(shù)組中,
                 但是,在應(yīng)用于未排序數(shù)組時,算法有時會在target實際存在的情況下報告說該target不存在

            代碼:

            int
            vector_bsearch(
            struct Vector *vector, const void *target, compare_func compare)
            {
                
            int lo, hi, mid, tmp;
                lo 
            = 0;
                hi 
            = (vector->count) - 1;
                
            while(lo <= hi) {
                    mid 
            = lo + ((hi - lo) >> 1);
                    tmp 
            = compare(vector->array[mid], target);
                    
            if(tmp == 0)
                        
            return mid;
                    
            else if(tmp > 0)
                        hi 
            = mid - 1;
                    
            else
                        lo 
            = mid + 1;
                }
                
            return -1;
            }

            int
            vector_lower(
            struct Vector *vector, const void *target, compare_func compare)
            {
                
            int lo, hi, mid;
                lo 
            = -1;
                hi 
            = vector->count;
                
            /* distance between lo and hi at least larger than 1, which ensure mid won't equals to either lo or hi */
                
            while(lo+1 != hi) { 
                    
            /* loop invariant: vector[lo]<target && vector[hi]>=target && lo<hi */
                    mid 
            = lo + ((hi - lo) >> 1);
                    
            if(compare(vector->array[mid], target) >= 0)
                        hi 
            = mid;
                    
            else 
                        lo 
            = mid;
                }
                
            if(hi>=(vector->count) || compare(vector->array[hi], target)!=0)
                    
            return -1;
                
            return hi;
            }

            int
            vector_upper(
            struct Vector *vector, const void *target, compare_func compare)
            {
                
            int lo, hi, mid;
                lo 
            = -1;
                hi 
            = vector->count;
                
            /* distance between lo and hi at least larger than 1, which ensure mid won't equals to either lo or hi */
                
            while(lo+1 != hi) {
                    
            /* loop invariant: vector[lo]<=target && vector[hi]>target && lo<hi */
                    mid 
            = lo + ((hi - lo) >> 1);
                    
            if(compare(vector->array[mid], target) <= 0)
                        lo 
            = mid;
                    
            else
                        hi 
            = mid;
                }
                
            if(lo<0 || compare(vector->array[lo], target)!=0)
                    
            return -1;
                
            return lo;
            }









            posted @ 2011-08-12 17:19 simplyzhao 閱讀(182) | 評論 (0)編輯 收藏
            僅列出標(biāo)題
            共21頁: 1 2 3 4 5 6 7 8 9 Last 

            導(dǎo)航

            <2010年6月>
            303112345
            6789101112
            13141516171819
            20212223242526
            27282930123
            45678910

            統(tǒng)計

            常用鏈接

            留言簿(1)

            隨筆分類

            隨筆檔案

            搜索

            最新評論

            閱讀排行榜

            評論排行榜

            久久国产福利免费| 亚洲欧洲精品成人久久曰影片 | 久久精品毛片免费观看| 99久久国产宗和精品1上映| 偷偷做久久久久网站| 久久99国产精品久久99果冻传媒| 国产日产久久高清欧美一区| 精品久久久久久无码国产| 亚洲愉拍99热成人精品热久久| 久久国产精品-久久精品| 性做久久久久久久久久久| 91久久婷婷国产综合精品青草| 亚洲狠狠久久综合一区77777| 99久久综合国产精品免费| 亚洲国产精久久久久久久| 99蜜桃臀久久久欧美精品网站| 99久久99久久精品国产片果冻| 蜜臀av性久久久久蜜臀aⅴ麻豆 | 2022年国产精品久久久久| 色综合合久久天天给综看| 国产精品久久久久影院嫩草| 久久人人爽人人人人片av| 国产精品九九久久精品女同亚洲欧美日韩综合区| 久久国产香蕉一区精品| 色综合久久综精品| 精品999久久久久久中文字幕| 久久久久99这里有精品10| 久久久噜噜噜久久| 99久久无码一区人妻| 99久久国产免费福利| 国产精品久久久久久久久鸭| 色88久久久久高潮综合影院| 漂亮人妻被中出中文字幕久久| 亚洲午夜福利精品久久| 久久久精品波多野结衣| 国产精品va久久久久久久| 亚洲国产精品久久久久婷婷软件| 久久久无码一区二区三区| 国产精品国色综合久久| 欧美伊香蕉久久综合类网站| 狠狠精品久久久无码中文字幕 |