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

            公告

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

            統計

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

            留言簿(10)

            隨筆分類(70)

            隨筆檔案(182)

            文章檔案(1)

            如影隨形

            搜索

            •  

            最新隨筆

            最新評論

            閱讀排行榜

            評論排行榜

            TCO Round1

            1 比較簡單,不過不是那么容易想。
              給定初始字符串,然后兩個緩沖隊列,把初始字符串經過一部分操作變成目標字符串。
             
              由于具有兩個緩沖隊列,而且初始字符串中字符只有兩類,所以可以一次搞定!利用substr() 判斷一下就OK
             
            2  應該觀察到對最后的期望有貢獻的只是具有連續洼地的地方,所以只要枚舉出現連續洼地的期望就可以了,復雜度是O(n^2)的,然后下面的代碼就非常清楚了!主要是沒有注意這個關鍵點!
            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;
              }
            };

            當時比賽的時候,我在想DP的狀態轉移,貌似寫挫了,不太清楚O(n)的算法思路和我的是否相似。。
             
             
            3
            看來還是蠻簡單的,就是一個容斥原理啊,復雜度是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 閱讀(211) 評論(1)  編輯 收藏 引用

            評論

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

            看得還真是挺復雜的。
              回復  更多評論    
            統計系統
            一级a性色生活片久久无| 人妻少妇久久中文字幕一区二区| 久久综合给合久久国产免费| 国产精品99久久久精品无码| 国产成年无码久久久免费| 亚洲国产精品无码久久久秋霞2| AV无码久久久久不卡蜜桃| 久久播电影网| 婷婷久久久亚洲欧洲日产国码AV| 99久久99久久| 久久久SS麻豆欧美国产日韩| 久久91综合国产91久久精品| 四虎国产精品成人免费久久| 久久久久久久亚洲Av无码| 久久亚洲国产精品123区| 婷婷久久香蕉五月综合加勒比| 国产成人久久777777| 日产精品99久久久久久| 品成人欧美大片久久国产欧美... 品成人欧美大片久久国产欧美 | 久久露脸国产精品| 精品久久久久久亚洲精品| 蜜桃麻豆www久久国产精品| 精品久久久久久亚洲精品| 2021国内久久精品| 色综合合久久天天给综看| 国产欧美一区二区久久| 久久AV高潮AV无码AV| 欧洲国产伦久久久久久久| 色噜噜狠狠先锋影音久久| 东京热TOKYO综合久久精品| 久久久久免费精品国产| 日韩一区二区三区视频久久| 国产成人精品久久亚洲高清不卡| 久久天天躁狠狠躁夜夜躁2O2O| 久久天天躁狠狠躁夜夜avapp| 无码人妻久久一区二区三区蜜桃 | 久久AAAA片一区二区| 国产激情久久久久影院老熟女免费| 国产69精品久久久久777| 国产精品久久毛片完整版| 久久99国产精品99久久|