• <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, 評(píng)論 - 47, 引用 - 0
            數(shù)據(jù)加載中……

            POJ 1231 The Alphabet Game 貪心

            近來(lái)實(shí)驗(yàn)室給派了新活,跟原來(lái)做的東西,以及我們熟悉的東西都比較不搭邊的,郁悶。
            折騰了兩個(gè)星期,昨天終于有了些進(jìn)展。
            今天做了兩道水題~  都是貪心


            思路:
            這題看上去挺唬人,提交的人也不多,實(shí)際上都是水題來(lái)的。
            1. 對(duì)于同一種字母,求出它出現(xiàn)位置的最左邊、最右邊、最上邊、最下邊。這就構(gòu)成了一個(gè)矩形。
            2. 對(duì)于在x軸上投影重合的一系列矩形,他們必定處在同一個(gè)方格內(nèi)。給這些方格編號(hào)。
            3. 對(duì)于在y軸上投影重合的一系列矩形,如果其中兩個(gè)編號(hào)相同,就不符合條件了。

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

            using namespace std;

            struct rect {
                
            int left, right, top, bottom;
                
            int rank_x;
            }
             rec[32];
            int T, K, P;

            int cmp_x(const void *a, const void *b)
            {
                
            return ((struct rect *)a)->left - ((struct rect *)b)->left;
            }


            int cmp_y(const void *a, const void *b)
            {
                
            return ((struct rect *)a)->top - ((struct rect *)b)->top;
            }


            inline 
            int solve()
            {
                
            int i, last, rank, mask;

                qsort(rec, K, 
            sizeof(rec[0]), cmp_x);
                rank 
            = 0;
                
            for (i = 0; i < K; ) {
                    last 
            = rec[i].right;
                    
            while (i < K && rec[i].left <= last) {
                        rec[i].rank_x 
            = rank;
                        last 
            = max(last, rec[i].right);
                        i
            ++;
                    }

                    rank
            ++;
                }


                qsort(rec, K, 
            sizeof(rec[0]), cmp_y);
                
            for (i = 0; i < K; ) {
                    mask 
            = 0;
                    last 
            = rec[i].bottom;
                    
            while (i < K && rec[i].top <= last) {
                        
            if (mask & (1 << rec[i].rank_x))
                            
            return 0;
                        mask 
            |= 1 << rec[i].rank_x;
                        last 
            = max(last, rec[i].bottom);
                        i
            ++;
                    }

                }


                
            return 1;
            }


            int main()
            {
                
            int i, j, x, y;

                scanf(
            "%d"&T);
                
            while (T--{
                    scanf(
            "%d%d"&K, &P);
                    
            for (i = 0; i < K; i++{
                        rec[i].left 
            = rec[i].top = 1000000;
                        rec[i].right 
            = rec[i].bottom = 0;
                        
            for (j = 0; j < P; j++{
                            scanf(
            "%d%d"&x, &y);
                            
            if (x < rec[i].left)
                                rec[i].left 
            = x;
                            
            if (x > rec[i].right)
                                rec[i].right 
            = x;
                            
            if (y < rec[i].top)
                                rec[i].top 
            = y;
                            
            if (y > rec[i].bottom)
                                rec[i].bottom 
            = y;
                        }

                    }

                    printf(
            "%s\n", solve() ? "YES" : "NO");
                }


                
            return 0;
            }


            posted on 2010-05-24 23:14 糯米 閱讀(522) 評(píng)論(0)  編輯 收藏 引用 所屬分類: POJ

            无码超乳爆乳中文字幕久久| 99久久精品免费国产大片| 久久91精品国产91| 国色天香久久久久久久小说| 无码人妻少妇久久中文字幕蜜桃| 久久亚洲国产午夜精品理论片| 久久艹国产| 国产一区二区精品久久凹凸| 午夜精品久久久久久影视777| 蜜桃麻豆WWW久久囤产精品| 国产情侣久久久久aⅴ免费| 国产成人综合久久精品尤物| 国产精品中文久久久久久久| 中文字幕日本人妻久久久免费| 狠狠色婷婷综合天天久久丁香| 国产精品内射久久久久欢欢| 久久精品无码一区二区三区免费| 要久久爱在线免费观看| 久久精品久久久久观看99水蜜桃| 99精品久久精品一区二区| 精品久久久久久无码国产| 伊人久久大香线蕉亚洲| 久久久WWW成人免费精品| 久久笫一福利免费导航| 久久精品国产精品青草app| 久久亚洲精品无码aⅴ大香| 99精品久久精品| 久久九九精品99国产精品| 久久香综合精品久久伊人| 久久精品国产亚洲5555| 色综合合久久天天综合绕视看| 香蕉久久夜色精品国产2020| 亚洲国产成人久久综合一 | 久久经典免费视频| 一本伊大人香蕉久久网手机| 99精品久久久久久久婷婷| 国产69精品久久久久99| 国产精品午夜久久| 国产巨作麻豆欧美亚洲综合久久| 蜜臀av性久久久久蜜臀aⅴ麻豆| 国内精品伊人久久久久影院对白|