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

            • 隨筆 - 182
            • 文章 - 1
            • 評論 - 41
            • 引用 - 0

            留言簿(10)

            隨筆分類(70)

            隨筆檔案(182)

            文章檔案(1)

            如影隨形

            搜索

            •  

            最新隨筆

            最新評論

            閱讀排行榜

            評論排行榜

            TCO Round1

            1 比較簡單,不過不是那么容易想。
              給定初始字符串,然后兩個緩沖隊列,把初始字符串經(jīng)過一部分操作變成目標(biāo)字符串。
             
              由于具有兩個緩沖隊列,而且初始字符串中字符只有兩類,所以可以一次搞定!利用substr() 判斷一下就OK
             
            2  應(yīng)該觀察到對最后的期望有貢獻(xiàn)的只是具有連續(xù)洼地的地方,所以只要枚舉出現(xiàn)連續(xù)洼地的期望就可以了,復(fù)雜度是O(n^2)的,然后下面的代碼就非常清楚了!主要是沒有注意這個關(guā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)時比賽的時候,我在想DP的狀態(tài)轉(zhuǎn)移,貌似寫挫了,不太清楚O(n)的算法思路和我的是否相似。。
             
             
            3
            看來還是蠻簡單的,就是一個容斥原理啊,復(fù)雜度是O(nlogn)+O(n)* O(容斥)
            容斥其實是蠻難做的!看下面這個:
            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 閱讀(213) 評論(1)  編輯 收藏 引用

            評論

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

            看得還真是挺復(fù)雜的。
              回復(fù)  更多評論    
            統(tǒng)計系統(tǒng)
            精品久久久久久久久久久久久久久 | 模特私拍国产精品久久| 无码8090精品久久一区| 18禁黄久久久AAA片| 麻豆成人久久精品二区三区免费 | 欧美日韩精品久久免费| 亚洲AV无码久久精品色欲| 99久久精品影院老鸭窝| 久久综合色区| 99热成人精品免费久久| 亚洲欧美成人综合久久久| 久久99精品国产99久久6| 久久人人爽人人人人片av| 成人午夜精品久久久久久久小说| 久久精品国产男包| 国产一区二区三精品久久久无广告 | av国内精品久久久久影院| 久久精品国产亚洲Aⅴ香蕉| 久久免费的精品国产V∧| 青青青青久久精品国产h久久精品五福影院1421 | 亚洲国产精品综合久久一线| 91精品国产乱码久久久久久| 午夜精品久久久久久久无码| 久久这里只有精品久久| 国产精品女同久久久久电影院| 婷婷久久综合九色综合绿巨人| 精品水蜜桃久久久久久久| 1000部精品久久久久久久久| 久久综合国产乱子伦精品免费| 亚洲日本久久久午夜精品| 亚洲AⅤ优女AV综合久久久| 99国内精品久久久久久久| 国产AV影片久久久久久| 97超级碰碰碰碰久久久久| 国产激情久久久久影院老熟女| 精品一区二区久久| 久久综合九色综合精品| 国产高潮久久免费观看| 精品久久久久久国产牛牛app| 久久精品免费大片国产大片| 国产精品成人99久久久久91gav |