• <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>
            posts - 7, comments - 13, trackbacks - 0, articles - 37
               :: 首頁(yè) :: 新隨筆 :: 聯(lián)系 ::  :: 管理

            2005百度初賽

            Posted on 2008-10-16 09:18 歲月流逝 閱讀(111) 評(píng)論(0)  編輯 收藏 引用

            百度之星程序設(shè)計(jì)大賽
            試題

            第一題(共四題100分):連續(xù)正整數(shù)(10分)
            題目描述:一個(gè)正整數(shù)有可能可以被表示為n(n>=2)個(gè)連續(xù)正整數(shù)之和,如:
            15=1+2+3+4+5
            15=4+5+615=7+8
            請(qǐng)編寫(xiě)程序,根據(jù)輸入的任何一個(gè)正整數(shù),找出符合這種要求的所有連續(xù)正整數(shù)序列。
            輸入數(shù)據(jù):一個(gè)正整數(shù),以命令行參數(shù)的形式提供給程序。

            輸出數(shù)據(jù):在標(biāo)準(zhǔn)輸出上打印出符合題目描述的全部正整數(shù)序列,每行一個(gè)序列,每個(gè)序列都從該序列的最小正整數(shù)開(kāi)始、以從小到大的順序打印。如果結(jié)果有多個(gè)序列,按各序列的最小正整數(shù)的大小從小到大打印各序列。此外,序列不允許重復(fù),序列內(nèi)的整數(shù)用一個(gè)空格分隔。如果沒(méi)有符合要求的序列,輸出“NONE”。

            例如,對(duì)于15,其輸出結(jié)果是:
              1 2 3 4 5
              4 5 6
              7 8
             
            對(duì)于16,其輸出結(jié)果是:
              NONE

            評(píng)分標(biāo)準(zhǔn):程序輸出結(jié)果是否正確。

            我的程序:

            #include <stdio.h>
            #include <math.h>

            void show(int a1, int n)
            {
                int i;
                printf("%d", a1);
                for (i = 1; i < n; i++)
                {
                    printf(" %d", a1 + i);
                }
                printf("\n");
            }

            int main(int argc, char** argv)
            {
                int x, n, a1;
                int showed = 0;
                if (argc != 2)
                    return -1;

                if (sscanf(argv[1], "%d", &x)!=1)
                    return -1;

                x = x*2;
                // n(1+n)/2 = x
                n = (int)sqrt(x); // a*b = c^2 then a <= c <= b, so n <= sqrt(2x) <= n+1
                for(; n >= 2; n--)
                {
                    if (x % n)
                        continue;

                    a1 = x / n - n + 1;
                    if (a1 % 2 == 0)
                    {
                        a1 /= 2;
                        show(a1, n);
                        showed = 1;
                    }
                }
                if (showed == 0)
                    printf("NONE\n");
                return 0;
            }
            //
            第二題(共四題100分):重疊區(qū)間大小(20分)

            題目描述:請(qǐng)編寫(xiě)程序,找出下面“輸入數(shù)據(jù)及格式”中所描述的輸入數(shù)據(jù)文件中最大重疊區(qū)間的大小。
            對(duì)一個(gè)正整數(shù)n,如果n在數(shù)據(jù)文件中某行的兩個(gè)正整數(shù)(假設(shè)為A和B)之間,即A<=n<=B或A>=n>=B,則n屬于該行;如果n同時(shí)屬于行i和j,則i和j有重疊區(qū)間;重疊區(qū)間的大小是同時(shí)屬于行i和j的整數(shù)個(gè)數(shù)。
             例如,行(10 20)和(12 25)的重疊區(qū)間為[12 20],其大小為9;行(20 10)和(12 18)的重疊區(qū)間為[10 12],其大小為3;行(20 10)和(20 30)的重疊區(qū)間大小為1。

            輸入數(shù)據(jù):程序讀入已被命名為input.txt的輸入數(shù)據(jù)文本文件,該文件的行數(shù)在1到1,000,000之間,每行有用一個(gè)空格分隔的2個(gè)正整數(shù),這2個(gè)正整數(shù)的大小次序隨機(jī),每個(gè)數(shù)都在1和2^32-1之間。(為便于調(diào)試,您可下載測(cè)試input.txt文件,實(shí)際運(yùn)行時(shí)我們會(huì)使用不同內(nèi)容的輸入文件。)

            輸出數(shù)據(jù):在標(biāo)準(zhǔn)輸出上打印出輸入數(shù)據(jù)文件中最大重疊區(qū)間的大小,如果所有行都沒(méi)有重疊區(qū)間,則輸出0。

            評(píng)分標(biāo)準(zhǔn):程序輸出結(jié)果必須正確,內(nèi)存使用必須不超過(guò)256MB,程序的執(zhí)行時(shí)間越快越好。

            我的程序:

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

            #ifndef MIN
            #define MIN(a,b) ((a)<(b)?(a):(b))
            #endif

            int map[1000000][2];

            int cmp(const void *a, const void *b)
            {
                return *(int*)a > *(int*)b;
            }
            inline int cover(int n[2], int e)
            {
                int left = n[0];
                int right = MIN(n[1], e);
                if (left <= right)
                    return right - left + 1;
                return 0;
            }
            int main()
            {
                FILE *fp = fopen("input.txt", "rt");
                int i = 0, n, a, b;
                int end;
                int maxcover = 0, c;
               
                while(fscanf(fp, "%d%d", &a, &b) == 2)
                {
                    if (a < b)
                    {
                        map[i][0] = a;
                        map[i][1] = b;
                    }
                    else
                    {
                        map[i][0] = b;
                        map[i][1] = a;
                    }
                    i++;
                }
                fclose(fp);
                n = i;
               
                qsort(map, n, sizeof(int)*2, cmp);
               
                end = map[0][1];

                for (i = 1; i < n; i++)
                {
                    c = cover(map[i], end);
                    if (c > maxcover)
                        maxcover = c;

                    if (map[i][1] > end)
                    {
                        end = map[i][1];
                    }
                }   
               
                printf("%d\n", maxcover);
                return 0;
            }
            //第三題(共四題100分):字符串替換(30分)

            題目描述:請(qǐng)編寫(xiě)程序,根據(jù)指定的對(duì)應(yīng)關(guān)系,把一個(gè)文本中的字符串替換成另外的字符串。

            輸入數(shù)據(jù):程序讀入已被命名為text.txt和dict.txt的兩個(gè)輸入數(shù)據(jù)文本文件,text.txt為一個(gè)包含大量字符串(含中文)的文本,以whitespace為分隔符;dict.txt為表示字符串(s1)與字符串(s2)的對(duì)應(yīng)關(guān)系的另一個(gè)文本(含中文),大約在1萬(wàn)行左右,每行兩個(gè)字符串(即s1和s2),用一個(gè)\t或空格分隔。dict.txt中各行的s1沒(méi)有排序,并有可能有重復(fù),這時(shí)以最后出現(xiàn)的那次s1所對(duì)應(yīng)的s2為準(zhǔn)。text.txt和dict.txt中的每個(gè)字符串都可能包含除whitespace之外的任何字符。text.txt中的字符串必須和dict.txt中的某s1完全匹配才能被替換。(為便于調(diào)試,您可下載測(cè)試text.txt和dict.txt文件,實(shí)際運(yùn)行時(shí)我們會(huì)使用不同內(nèi)容的輸入文件。)

            輸出數(shù)據(jù):在標(biāo)準(zhǔn)輸出上打印text.txt被dict.txt替換后了的整個(gè)文本。

            評(píng)分標(biāo)準(zhǔn):程序輸出結(jié)果必須正確,內(nèi)存使用越少越好,程序的執(zhí)行時(shí)間越快越好。

            我的程序:

            #pragma warning(disable:4786)
            #include <string>
            #include <map>
            #include <fstream>
            #include <cassert>
            #include <cstdio>

            using namespace std;

            map< string, string > dict;

            void loadDict(const char *filename)
            {
                string a, b;
                ifstream dic;
                assert(filename != NULL);
                dic.open(filename);
                while(dic>>a>>b)
                {
                    dict[a] = b;
                }
                dic.close();
            }

            const char *replaceWord(const string &word)
            {
                map< string, string >::iterator word2 = dict.find(word);
                if (word2 == dict.end())
                {
                    return word.c_str();
                }
                else
                {
                    return word2->second.c_str();
                }
            }

            int main()
            {
                bool isChinese = false;
                char c;
                string word;
                loadDict("dict.txt");
               
                FILE *fp = fopen("text.txt", "rt");
                while(!feof(fp))
                {
                    c = fgetc(fp);
                    if (isChinese)
                    {
                        word += c;
                        isChinese = false;
                    }
                    else
                    {
                        if ((c & 0x80) == 0 && isspace(c))
                        {
                            if (!word.empty())
                            {
                                printf("%s", replaceWord(word));
                                word = "";
                            }
                            printf("%c", c);
                        }
                        else
                        {
                            if (c & 0x80)
                            {
                                isChinese = true;
                            }
                            word += c;
                        }
                    }
                }
                fclose(fp);

                if (!word.empty())
                {
                    printf("%s", replaceWord(word));
                }
                return 0;
            }
            第四題(共四題100分):低頻詞過(guò)濾(40分)

            題目描述:請(qǐng)編寫(xiě)程序,從包含大量單詞的文本中刪除出現(xiàn)次數(shù)最少的單詞。如果有多個(gè)單詞都出現(xiàn)最少的次數(shù),則將這些單詞都刪除。

            輸入數(shù)據(jù):程序讀入已被命名為corpus.txt的一個(gè)大數(shù)據(jù)量的文本文件,該文件包含英文單詞和中文單詞,詞與詞之間以一個(gè)或多個(gè)whitespace分隔。(為便于調(diào)試,您可下載測(cè)試corpus.txt文件,實(shí)際運(yùn)行時(shí)我們會(huì)使用不同內(nèi)容的輸入文件。)

            輸出數(shù)據(jù):在標(biāo)準(zhǔn)輸出上打印刪除了corpus.txt中出現(xiàn)次數(shù)最少的單詞之后的文本(詞與詞保持原來(lái)的順序,仍以空格分隔)。

            評(píng)分標(biāo)準(zhǔn):程序輸出結(jié)果必須正確,內(nèi)存使用越少越好,程序的執(zhí)行時(shí)間越快越好。

            我的程序:


            #pragma warning(disable: 4786)
            #include <map>
            #include <string>
            #include <vector>
            #include <cstdio>
            #include <fstream>
            #include <algorithm>

            using namespace std;

            struct Pair
            {
                Pair(){}
                Pair(const string& w, int c):word(w), count(c)
                {
                }
                string word;
                int count;
            };

            map< string, int > wordmap;
            vector< Pair > wordcount;
            vector< int > wordindex;

            int main()
            {
                // load the file, count word, build index
                string word;
                fstream file("corpus.txt");
                while(file >> word)
                {
                    int id;
                    map< string, int >::iterator itw = wordmap.find(word);
                    if (itw == wordmap.end()) // new word
                    {
                        id = wordcount.size();
                        wordmap[word] = id;
                        wordcount.push_back(Pair(word, id));
                    }
                    else // found it
                    {
                        wordcount[itw->second].count++;
                        id = itw->second;
                    }
                    wordindex.push_back(id);
                }
                file.close();
               
                if (wordcount.empty())
                    return 0;
               
                // find the min count
                vector< Pair >::iterator itc = wordcount.begin();
                int mincount = itc->count;
                for (++itc; itc != wordcount.end(); ++itc)
                {
                    if (mincount > itc->count)
                        mincount = itc->count;
                }
               
                // show all filtered words
                if (wordindex.empty())
                    return 0;

                // skip leading filtered words
                vector< int >::iterator w = wordindex.begin();
                while(w != wordindex.end() && wordcount[*w].count == mincount)
                    ++w;
               
                if (w == wordindex.end())
                    return 0;

                /**//* debug use
                for (vector< Pair >::iterator iw = wordcount.begin(); iw != wordcount.end(); ++iw)
                    printf("%s %d\n", iw->word.c_str(), iw->count);
                printf("mincount = %d\n", mincount);
                /*/

                // show first word, with no space after
                printf("%s", wordcount[*w].word.c_str());
                for (++w; w != wordindex.end(); ++w)
                {
                    if (wordcount[*w].count != mincount)
                    {
                        printf(" %s", wordcount[*w].word.c_str());
                    }
                }
                printf("\n");
                //*/
                return 0;
            }


            只有注冊(cè)用戶登錄后才能發(fā)表評(píng)論。
            網(wǎng)站導(dǎo)航: 博客園   IT新聞   BlogJava   博問(wèn)   Chat2DB   管理


            无遮挡粉嫩小泬久久久久久久| 久久人人爽人人人人爽AV | 久久狠狠爱亚洲综合影院| 久久99精品久久久久久 | 99久久综合国产精品免费| 老司机国内精品久久久久| 77777亚洲午夜久久多喷| 久久久久人妻精品一区| 奇米影视7777久久精品| 精品国产99久久久久久麻豆 | 国产精品免费久久久久影院| 国产精品久久久久久久| 久久这里只精品国产99热| 久久国产亚洲精品麻豆| AAA级久久久精品无码区| 99久久国语露脸精品国产| 久久青青草原国产精品免费| 99久久精品国产一区二区| 青春久久| 久久久久久久久久久久久久| 亚洲国产美女精品久久久久∴| 久久精品国产亚洲精品2020| 97热久久免费频精品99| 久久精品国产精品亜洲毛片| 中文成人无码精品久久久不卡| 亚洲国产另类久久久精品小说| 国产成人久久精品激情| 久久天天躁狠狠躁夜夜2020老熟妇 | 久久久久国产一区二区| 久久久久久久免费视频| 久久天天躁狠狠躁夜夜96流白浆| 久久精品国内一区二区三区 | 国产高潮久久免费观看| 久久久久久久91精品免费观看| 国产精品美女久久久m| 欧美无乱码久久久免费午夜一区二区三区中文字幕 | 久久久久久一区国产精品| 久久SE精品一区二区| 久久久网中文字幕| 国产精品久久久亚洲| 久久精品国产乱子伦|