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

            久久人人爽人人爽人人av东京热| 久久91精品综合国产首页| 久久99国产精品久久99小说 | 热久久视久久精品18| 久久亚洲精品国产亚洲老地址| 久久久亚洲欧洲日产国码是AV| 日韩乱码人妻无码中文字幕久久| 久久精品国产清高在天天线| AA级片免费看视频久久| 亚洲狠狠婷婷综合久久久久| 99久久www免费人成精品| 97精品伊人久久大香线蕉| 99精品国产在热久久无毒不卡| 久久久久黑人强伦姧人妻| 久久综合狠狠综合久久综合88| 久久久WWW成人| 国内精品久久九九国产精品| 久久久久久亚洲精品影院| 日本三级久久网| 久久亚洲欧美国产精品| 亚洲伊人久久成综合人影院| 国产精品99久久久久久人| 国产69精品久久久久久人妻精品| 99麻豆久久久国产精品免费| 久久人人爽人人爽人人片AV麻烦| 国产毛片久久久久久国产毛片| 久久久一本精品99久久精品88| 三级三级久久三级久久| 欧美一级久久久久久久大片| 国产精品欧美久久久久天天影视| 久久久久久无码Av成人影院| 97精品伊人久久久大香线蕉| 一本大道久久东京热无码AV| 精品久久久久久国产免费了| 99久久无码一区人妻| 人人狠狠综合久久亚洲88| 久久精品国产精品亚洲精品| 国产精品99久久精品| 国内精品伊人久久久久影院对白| 国产三级观看久久| 久久久久亚洲AV成人网人人网站 |