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

            O(1) 的小樂

            Job Hunting

            公告

            記錄我的生活和工作。。。
            <2010年9月>
            2930311234
            567891011
            12131415161718
            19202122232425
            262728293012
            3456789

            統(tǒng)計(jì)

            • 隨筆 - 182
            • 文章 - 1
            • 評(píng)論 - 41
            • 引用 - 0

            留言簿(10)

            隨筆分類(70)

            隨筆檔案(182)

            文章檔案(1)

            如影隨形

            搜索

            •  

            最新隨筆

            最新評(píng)論

            閱讀排行榜

            評(píng)論排行榜

            TCO Round1

            1 比較簡單,不過不是那么容易想。
              給定初始字符串,然后兩個(gè)緩沖隊(duì)列,把初始字符串經(jīng)過一部分操作變成目標(biāo)字符串。
             
              由于具有兩個(gè)緩沖隊(duì)列,而且初始字符串中字符只有兩類,所以可以一次搞定!利用substr() 判斷一下就OK
             
            2  應(yīng)該觀察到對(duì)最后的期望有貢獻(xiàn)的只是具有連續(xù)洼地的地方,所以只要枚舉出現(xiàn)連續(xù)洼地的期望就可以了,復(fù)雜度是O(n^2)的,然后下面的代碼就非常清楚了!主要是沒有注意這個(gè)關(guān)鍵點(diǎn)!
            class MuddyRoad{
              public:
              double getExpectedValue(vector <int> road){
                vector<double> prob;
                for(int i=0;i<road.size();i++)prob.push_back((double)road[i]/100);
                int n=prob.size();
                double ans=0;
                for(int i=1;i<=n-2;i++){
                  for(int j=i;j<=n-2;j++){
                    int c=(j-i+1)/2;
                    double p=1;
                    p*=(1-prob[i-1]);
                    p*=(1-prob[j+1]);
                    for(int k=i;k<=j;k++)p*=prob[k];
                    ans+=p*c;
                  }
                }
                return ans;
              }
            };

            當(dāng)時(shí)比賽的時(shí)候,我在想DP的狀態(tài)轉(zhuǎn)移,貌似寫挫了,不太清楚O(n)的算法思路和我的是否相似。。
             
             
            3
            看來還是蠻簡單的,就是一個(gè)容斥原理啊,復(fù)雜度是O(nlogn)+O(n)* O(容斥)
            容斥其實(shí)是蠻難做的!看下面這個(gè):
            The simplest approach would be to go over all 1,000,000,000,000 IP addresses individually, and for each one, check all the requests to see who offers the highest price, and then add that to the total.

            This works perfectly except it will obviously be too slow. So instead of looking at individual IP addresses, we should partition the set of all IP addresses, so that each part will be assigned to a single buyer. Then, we simply need to find the size and price for each part, and we can easily multiply and add them together.

            For example, if we have requests for "1.2.3.0", "1.2.3.1" and "1.2.3.*" then interesting parts would be {"1.2.3.0"}, {"1.2.3.1"}, and {"1.2.3.2","1.2.3.3",...,"1.2.3.999"}. All of these can be represented implicitly if we take a special value (like -1 in bmerry's code) to mean "all other, unused values".

            Since the interesting values for each component come from the N requests in the input, there are at most N4 parts to check (or (N+1)4 in bmerry's code). With an additional loop for each part this yields an O(N5) algorithm.

            posted on 2011-06-26 13:21 Sosi 閱讀(211) 評(píng)論(1)  編輯 收藏 引用

            評(píng)論

            # re: TCO Round1 2011-07-26 16:14 雙星休閑鞋

            看得還真是挺復(fù)雜的。

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


            統(tǒng)計(jì)系統(tǒng)
            中文字幕亚洲综合久久| 亚洲午夜久久影院| 亚洲欧美久久久久9999| 久久亚洲中文字幕精品一区| 蜜臀av性久久久久蜜臀aⅴ麻豆 | 日本国产精品久久| 久久久久久久免费视频| 激情伊人五月天久久综合| 精品国产乱码久久久久久浪潮| 亚洲欧美精品一区久久中文字幕| 久久久久人妻一区二区三区vr| 91久久国产视频| 人妻丰满AV无码久久不卡| 久久播电影网| 精品一区二区久久| 99久久精品国产一区二区| 久久av免费天堂小草播放| 亚洲av成人无码久久精品| 久久久久国产精品麻豆AR影院 | 久久免费小视频| 性欧美丰满熟妇XXXX性久久久 | 久久精品免费一区二区三区| 怡红院日本一道日本久久 | 国产2021久久精品| 亚洲av成人无码久久精品| 一个色综合久久| 无码人妻久久一区二区三区蜜桃| 国产亚洲色婷婷久久99精品| 久久狠狠爱亚洲综合影院 | 精品久久久久久国产牛牛app| 久久亚洲精品国产精品| 99久久精品免费看国产一区二区三区 | 国产综合精品久久亚洲| 久久国产亚洲高清观看| 婷婷久久久亚洲欧洲日产国码AV| 久久国内免费视频| 久久亚洲国产精品成人AV秋霞 | 波多野结衣中文字幕久久| 天堂久久天堂AV色综合| 无码精品久久久天天影视| 久久久久高潮毛片免费全部播放|