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

            HDU 3682 To Be an Dream Architect 容斥原理

            題意;
            每次可以刪除一個木條x=?,y=?或者x=?,z=?或者y=?,z=?,求最后刪除的木塊總數

            開始寫的時候出現個BUG,無奈,上網找題解,更無奈,都是些幾句話hash然后就是一堆難懂的代碼。。
            后來仔細想了想,把重復的操作去除后(就是兩次刪除的同一個木條),下面就是個很簡單的容斥原理了
            因為去除了重復操作,一個木塊最多被刪除3次,然后刪除的個數就為被刪除至少一次的個數-刪除至少兩次的個數+刪除至少3次的個數。不能強行枚舉,可以用map或者傳說中的hash記錄被刪除掉木塊的次數。這里,由于操作最多m=1000,刪除木塊數最多為C(m,2),然后兩兩枚舉操作,把相交木塊刪除次數+1,然后最后map中所有木塊刪除次數只能有2個值:1和3,當值為1時,total-1,值為3時,total-2
            為什么?因為我說了,一個木塊最多被刪除3次,然后倆倆枚舉的時候,你懂的。
             1 # include <cstdio>
             2 # include <utility>
             3 # include <cstring>
             4 # include <algorithm>
             5 # include <functional>
             6 # include <set>
             7 # include <cstdlib>
             8 # include <map>
             9 using namespace std;
            10 struct node
            11 {
            12     int p[3];
            13     bool operator<(const node &pos) const
            14     {
            15         for(int i=0;i<3;i++)
            16             if(p[i]!=pos.p[i]) 
            17                 return p[i]<pos.p[i];
            18         return false;
            19     }
            20 };
            21 pair<int,int> data[1000][2];
            22 set<pair<pair<int,int>,pair<int,int> > > r1;
            23 map<node,int> r2;
            24 int main()
            25 {
            26     int test;
            27     scanf("%d",&test);
            28     while(test--)
            29     {
            30        int n,m,p=0;
            31        char str[128];
            32        scanf("%d%d",&n,&m);
            33        r1.clear();r2.clear();
            34        while(m--)
            35        {
            36            scanf("%s",str);
            37            char *t=strtok(str,",");
            38            data[p][0].first=(*t)-'X';
            39            data[p][0].second=atoi(t+2);
            40            t=strtok(NULL," ");
            41            data[p][1].first=(*t)-'X';
            42            data[p][1].second=atoi(t+2);
            43            if(data[p][0].first>data[p][1].first) swap(data[p][0],data[p][1]);
            44            pair< pair<int,int>,pair<int,int> > tt;
            45            tt.first=data[p][0];
            46            tt.second=data[p][1];
            47            if(data[p][0].second>=1&&data[p][0].second<=n&&data[p][1].second>=1&&data[p][1].second<=n&&r1.find(tt)==r1.end()) p++,r1.insert(tt);
            48        }
            49        m=p;
            50        for(int i=0;i<m;i++)
            51         for(int j=i+1;j<m;j++)
            52           if(data[i][0]==data[j][0]&&data[i][1].first!=data[j][1].first||
            53              data[i][1]==data[j][0]&&data[i][0].first!=data[j][1].first||
            54              data[i][0]==data[j][1]&&data[i][1].first!=data[j][0].first||
            55              data[i][1]==data[j][1]&&data[i][0].first!=data[j][0].first)
            56           {
            57               node t;
            58               t.p[data[i][0].first]=data[i][0].second;
            59               t.p[data[i][1].first]=data[i][1].second;
            60               t.p[data[j][0].first]=data[j][0].second;
            61               t.p[data[j][1].first]=data[j][1].second;
            62               r2[t]++;
            63           }
            64        int total=m*n;
            65        for(map<node,int>::iterator i=r2.begin();i!=r2.end();i++)
            66            if(i->second==1) total--;
            67            else total-=2;
            68        printf("%d\n",total);
            69     }
            70     //system("pause");
            71     return 0;
            72 
            73 

            posted on 2011-10-03 00:06 yzhw 閱讀(439) 評論(0)  編輯 收藏 引用 所屬分類: combination math

            <2011年10月>
            2526272829301
            2345678
            9101112131415
            16171819202122
            23242526272829
            303112345

            導航

            統計

            公告

            統計系統

            留言簿(1)

            隨筆分類(227)

            文章分類(2)

            OJ

            最新隨筆

            搜索

            積分與排名

            最新評論

            閱讀排行榜

            国内精品伊人久久久久av一坑| 久久国产精品偷99| 无码人妻精品一区二区三区久久| 亚洲乱码中文字幕久久孕妇黑人| 国产精品一区二区久久国产| 99久久亚洲综合精品成人| 性做久久久久久免费观看| 久久精品水蜜桃av综合天堂| 国产真实乱对白精彩久久| 中文字幕无码精品亚洲资源网久久| 爱做久久久久久| 一本色道久久HEZYO无码| 国产精品99久久不卡| 日韩精品久久久肉伦网站| 久久久久国色AV免费观看| AV无码久久久久不卡蜜桃| 亚洲v国产v天堂a无码久久| 国产91色综合久久免费| 偷窥少妇久久久久久久久| 精品久久久久久久中文字幕| 久久精品九九亚洲精品| 婷婷久久综合| 欧美一级久久久久久久大| 日韩精品久久久久久| 久久人爽人人爽人人片AV| 香蕉久久av一区二区三区| 伊人 久久 精品| 亚洲一级Av无码毛片久久精品| 国产精品欧美久久久久天天影视| av无码久久久久不卡免费网站| 热re99久久6国产精品免费| 亚洲а∨天堂久久精品9966| 三级韩国一区久久二区综合 | 久久久久夜夜夜精品国产| 久久综合香蕉国产蜜臀AV| 久久久久久综合网天天| 伊人热热久久原色播放www| 一本色道久久综合狠狠躁篇 | 久久最新免费视频| 久久精品国产色蜜蜜麻豆| 久久久久久国产精品免费免费|