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

            <2010年12月>
            2829301234
            567891011
            12131415161718
            19202122232425
            2627282930311
            2345678

            導航

            統計

            公告

            統計系統

            留言簿(1)

            隨筆分類(227)

            文章分類(2)

            OJ

            最新隨筆

            搜索

            積分與排名

            最新評論

            閱讀排行榜

            国产综合免费精品久久久| 欧美激情精品久久久久久| 亚洲精品无码久久一线| 蜜臀av性久久久久蜜臀aⅴ麻豆| 人妻丰满AV无码久久不卡| 日韩精品国产自在久久现线拍 | 精品久久久久久久久免费影院| 亚洲国产日韩欧美综合久久| 亚洲日韩中文无码久久| 亚洲狠狠久久综合一区77777| 一本大道久久香蕉成人网| 97久久精品无码一区二区天美| 久久人人爽人人澡人人高潮AV | 久久er99热精品一区二区| 精品视频久久久久| 色88久久久久高潮综合影院| 久久精品亚洲欧美日韩久久| 久久久精品人妻一区二区三区蜜桃| 久久AAAA片一区二区| 久久99精品久久久久久hb无码| 亚洲?V乱码久久精品蜜桃 | 欧美久久一区二区三区| 99久久国产综合精品五月天喷水 | 人人狠狠综合88综合久久| 99久久久国产精品免费无卡顿 | 久久ww精品w免费人成| 伊人久久无码精品中文字幕| 国产91久久综合| 大伊人青草狠狠久久| 久久精品国产亚洲av麻豆色欲| 怡红院日本一道日本久久| 久久国产欧美日韩精品| 无遮挡粉嫩小泬久久久久久久| 色老头网站久久网| 精品国产日韩久久亚洲| 久久人人爽人人爽人人片AV东京热 | 狠狠色噜噜色狠狠狠综合久久| 婷婷久久五月天| 久久人与动人物a级毛片| 亚洲国产精品无码成人片久久| 亚洲精品无码久久一线|