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

            糯米

            TI DaVinci, gstreamer, ffmpeg
            隨筆 - 167, 文章 - 0, 評論 - 47, 引用 - 0
            數據加載中……

            POJ 2009 Moo University - Emergency Pizza Order 無恥貪心解法

            這題能不能貪心,是很難說的。。
            因為沒有能什么證明貪心是對的,但也沒找到什么反例。
            代碼寫出來,WA了。
            但總覺得是對的,因為嗎的實在找不到反例。
            結果找到數據測了下,果然十個過了九個。。
            你看,如果這是NOIP,跟滿分都沒啥區別的對吧。我已經滿足了。。
            沒過的那組,比較大,肉眼看不出是啥問題。
            想了下,給排序加多了一個判斷,然后那組數據就過了。。
            然后提交,嗎的還上榜了。。無語。

            這樣做比較無恥,網上有人說用最大流做,不理解。下次想一想。

            思路:
            如果牛喜歡的種類個數小于 K,那這種牛是無法滿足的。。
            把牛按照喜歡的種類個數排序,先處理小的。
            就是用組合數枚舉每一種可能的 pizza 情況。
            用 hash 保存這些情況。

            代碼:
            #include <stdio.h>
            #include 
            <stdlib.h>

            #define HASH_SIZE 65536

            struct cow_node {
                
            int val, cnt;
            }
            ;

            int C, T, K, ans;
            struct cow_node cows[1024];
            int hash[HASH_SIZE];

            int cmp(const void *a, const void *b)
            {
                
            if (((struct cow_node *)a)->cnt == ((struct cow_node *)b)->cnt)
                    
            return ((struct cow_node *)a)->val - ((struct cow_node *)b)->val;
                
            return ((struct cow_node *)a)->cnt - ((struct cow_node *)b)->cnt;
            }


            inline 
            int insert(int val)
            {
                
            int i, h;

                h 
            = val & (HASH_SIZE - 1);
                
            for (i = h + 1; i != h && hash[i] && hash[i] != val; )
                    i 
            = (i + 1& (HASH_SIZE - 1);
                
            if (i == h || hash[i] == val)
                    
            return 0;
                hash[i] 
            = val;
                
            return 1;
            }


            inline 
            int calc(struct cow_node *t)
            {
                
            int arr[32], map[32], i, j, val;

                
            for (i = j = 0; i < 32; i++)
                    
            if (t->val & (1 << i))
                        map[j
            ++= (1 << i);
                
            for (i = 0; i < K; i++)
                    arr[i] 
            = i;
                
            while (1{
                    val 
            = 0;
                    
            for (i = 0; i < K; i++)
                        val 
            |= map[arr[i]];
                    
            if (insert(val))
                        
            return 1;
                    
            for (i = K - 1; i >= 0 && arr[i] == i + t->cnt - K; i--);
                    
            if (i < 0)
                        
            break;
                    arr[i]
            ++;
                    
            for (i++; i < K; i++)
                        arr[i] 
            = arr[i - 1+ 1;
                }


                
            return 0;
            }


            int main()
            {
                
            int i, j, k;

                freopen(
            "e:\\test\\in.txt""r", stdin);

                scanf(
            "%d%d%d"&C, &T, &K);
                
            for (i = 0; i < C; i++{
                    scanf(
            "%d"&cows[i].cnt);
                    cows[i].val 
            = 0;
                    
            for (j = 0; j < cows[i].cnt; j++{
                        scanf(
            "%d"&k);
                        k
            --;
                        cows[i].val 
            |= 1 << k;
                    }

                    
            if (cows[i].cnt < K) {
                        i
            --; C--;
                        
            continue;
                    }

                }

                qsort(cows, C, 
            sizeof(cows[0]), cmp);

                
            for (i = 0; i < C; i++
                    ans 
            += calc(&cows[i]);
                printf(
            "%d\n", ans);

                
            return 0;
            }


            posted on 2010-04-27 14:25 糯米 閱讀(805) 評論(0)  編輯 收藏 引用 所屬分類: POJ

            国产精品乱码久久久久久软件| 欧美午夜精品久久久久免费视| 亚洲国产精品狼友中文久久久| 久久露脸国产精品| 无码精品久久一区二区三区| 日韩精品久久久久久免费| 国产精品久久久久久久| 色婷婷久久久SWAG精品| 久久99国产一区二区三区| 久久99精品久久久久久hb无码| 久久被窝电影亚洲爽爽爽| 久久久久无码精品国产app| 久久婷婷色综合一区二区| 久久久久久久久久久精品尤物| 狠狠综合久久AV一区二区三区| 久久国产高潮流白浆免费观看| 99久久精品免费看国产一区二区三区 | 久久国产欧美日韩精品| 久久精品亚洲男人的天堂| 日本久久久久亚洲中字幕| 久久精品成人欧美大片| 99久久精品费精品国产一区二区| 久久精品国产亚洲av瑜伽| 韩国免费A级毛片久久| 欧美日韩精品久久久免费观看| 久久国产乱子精品免费女| 中文字幕人妻色偷偷久久| 天天做夜夜做久久做狠狠| 国产成人99久久亚洲综合精品| 久久精品水蜜桃av综合天堂| 免费无码国产欧美久久18| 久久人妻少妇嫩草AV无码蜜桃 | 2021国内精品久久久久久影院| 日本道色综合久久影院| 国产精品一区二区久久| 日韩AV无码久久一区二区 | 一级做a爰片久久毛片人呢| 久久A级毛片免费观看| 国内精品久久久久伊人av| 精品久久久久久久久午夜福利| 99久久婷婷国产综合亚洲|