• <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 閱讀(440) 評論(0)  編輯 收藏 引用 所屬分類: combination math

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

            導航

            統計

            公告

            統計系統

            留言簿(1)

            隨筆分類(227)

            文章分類(2)

            OJ

            最新隨筆

            搜索

            積分與排名

            最新評論

            閱讀排行榜

            曰曰摸天天摸人人看久久久| 亚洲精品tv久久久久久久久| 久久婷婷五月综合色高清| 亚洲国产欧美国产综合久久| 国产69精品久久久久9999APGF| 久久亚洲私人国产精品vA| 激情伊人五月天久久综合| 久久久久国产精品麻豆AR影院| 久久香蕉国产线看观看猫咪?v| 精品久久久久久久无码 | 99久久无码一区人妻| 欧美伊人久久大香线蕉综合69| 精品国产乱码久久久久久呢| 香蕉久久夜色精品国产小说| 伊人久久大香线蕉精品不卡| 国产AV影片久久久久久| 国产成人综合久久综合| 欧美国产成人久久精品| 国产一区二区三精品久久久无广告| 亚洲国产精品无码久久| 国产高清美女一级a毛片久久w | 无码伊人66久久大杳蕉网站谷歌| 免费观看成人久久网免费观看| 天堂久久天堂AV色综合| 久久久久久久综合综合狠狠| 99久久免费国产精精品| 久久精品人妻中文系列| 一级做a爰片久久毛片看看 | 久久久精品人妻一区二区三区四| 狠狠色婷婷久久一区二区| 94久久国产乱子伦精品免费| 久久人人妻人人爽人人爽| 亚洲中文字幕无码久久2017| 久久久久久免费视频| 亚洲国产小视频精品久久久三级| 亚洲国产成人久久综合碰碰动漫3d| 国产69精品久久久久APP下载| 久久有码中文字幕| 一本久道久久综合狠狠躁AV| 亚洲国产精品无码久久青草| 人妻无码精品久久亚瑟影视|