• <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>
            算法學(xué)社
            記錄難忘的征途
            posts - 141,comments - 220,trackbacks - 0
            題目描述:
                在一個(gè)N*M(N<=200,M<=50000)像素的畫板上畫Q(Q<=50000)個(gè)圖形,有矩形,圓形,倒等腰三角形,菱形四種,每個(gè)圖形有九種顏色可選擇。對(duì)于一個(gè)像素,后畫的顏色會(huì)覆蓋前面的顏色,請(qǐng)求出最后每種顏色的像素有多少個(gè)?
            吐槽:
                1. 線段樹會(huì)MLE...大概...
                2. ...并查集ms只能在這種問題上優(yōu)化
            算法分析:
                
                額,嚴(yán)格的說不是并查集啊... 只是在一個(gè)數(shù)組上亂搞出一個(gè)類似并查集的東西...
                現(xiàn)在我來簡要講述一下這個(gè)方法,這個(gè)方法非常好寫,也就10行左右... 而且比線段樹快很多~~
                我目前知道的這個(gè)優(yōu)化必須要把所有的線段"一視同仁",插入線段[1,3]和[2,4]后,一同視為[1,4]....
                所以在任何時(shí)候,這個(gè)數(shù)組存的都是一段一段的不相交區(qū)間~~
                對(duì)于一個(gè)區(qū)間[l,r],l到r上的所有點(diǎn)的“代表”都是r+1.....
                如果要插入某線段[l',r'],那么從l'到r'掃一遍就可以了:
                    如果某個(gè)點(diǎn)p代表是自己的話,那么就把p的代表改為Parent[r],然后檢查p+1。
                    如果p的代表不是自己的話,那么就檢查parent[p]就可以了,因?yàn)閜arent[p]一定是未被覆蓋的點(diǎn)。
                在查找p的代表中,用并查集中的“路徑壓縮”優(yōu)化就可以了
             1 #include<iostream>
             2 #include<cstdio>
             3 using namespace std;
             4 #define re(i,n) for(int i=0;i<n;i++)
             5 #define re1(i,n) for(int i=1;i<=n;i++)
             6 #define re2(i,n) for(int i=0;i<=n;i++)
             7 #define re3(i,n) for(int i=1;i<n;i++)
             8 const int N = 205;
             9 const int M = 50005;
            10 int ans[10];
            11 int seg[N][M];
            12 int n,m,q;
            13 void init(){
            14     re(i,n) re2(j,m) {
            15         seg[i][j] = j;
            16     }
            17     re(i,10) ans[i] = 0;
            18 }
            19 int find(int pos, int x){ return seg[pos][x] == x ? x: seg[pos][x] = find(pos,seg[pos][x]);}
            20 void ins(int pos,int l, int r,int c){
            21 //    cout<<pos<<" "<<l<<" "<<r-1<<" "<<c<<endl;
            22     r = find(pos, r);
            23     while(l < r) {
            24         if(find(pos,l) == l){
            25             ans[c] ++;
            26             seg[pos][l] = r;
            27             l++;
            28         }
            29         else {
            30             l = seg[pos][l];
            31         }
            32     }
            33 }
            34 struct query{
            35     int x,y,r,c,w,l;
            36     char Q;
            37 }num[M];
            38 int main(){
            39     while(~scanf("%d%d%d",&n,&m,&q)){
            40         char ch[10];
            41         init();
            42         re(i,q) {
            43             scanf("%s%d%d",ch,&num[i].x,&num[i].y);
            44             num[i].Q = ch[0];
            45             if(ch[0] == 'R'){
            46                 scanf("%d%d%d",&num[i].l,&num[i].w,&num[i].c);
            47             }
            48             else if(ch[0] == 'T'){
            49                 scanf("%d%d",&num[i].w,&num[i].c);
            50             }
            51             else {
            52                 scanf("%d%d",&num[i].r,&num[i].c);    
            53             }
            54         }
            55         for(int i=q-1;i>=0;i--){
            56             int x = num[i].x,y=num[i].y, r= num[i].r, w=num[i].w,l = num[i].l,c = num[i].c;
            57             if(num[i].Q=='C'){
            58                 int left = max(y - r ,0), right = min(y + r, m-1);
            59                 ins(x,left,right+1,c);
            60                 for(int j = 1; j <= r; j++){
            61                     if(x + j >= n && x - j < 0) break;
            62                     while((y-left)*(y-left) + j*j > r*r) left ++;;
            63                     while((right-y)*(right-y) + j*j > r*r) right--;
            64                     if(x + j < n) ins(x + j, left, right +1 ,c);
            65                     if(x - j >=0) ins(x - j, left, right +1 ,c);
            66                 }
            67             }
            68             else if(num[i].Q=='D'){
            69                 int left = max(y - r ,0), right = min(y + r, m-1);
            70                 ins(x,left,right+1,c);
            71                 for(int j = 1; j <= r; j++){
            72                     if(x + j >= n && x - j < 0) break;
            73                     while((y-left)+j > r) left ++;;
            74                     while((right-y)+j > r) right--;
            75                     if(x + j < n) ins(x + j, left, right +1 ,c);
            76                     if(x - j >=0) ins(x - j, left, right +1 ,c);
            77                 }
            78             }
            79             else if(num[i].Q=='R'){
            80                 for(int X = x;X < n && X < x + l ; X++){
            81                     ins(X,y,min(y+w,m),c);
            82                 }
            83             }
            84             else {
            85                 for(int X = x,W = w/2; X<n && W>=0; X++,W--){
            86                     int left = max(0,y-W);
            87                     int right = min(m-1,y+W);
            88                     ins(X,left,right+1,c);
            89                 }
            90             }
            91         }
            92         re1(i,9) {cout<<ans[i]; if(i != 9) cout<<" ";} cout<<endl;
            93     }
            94 }
            95 
            posted on 2012-04-30 17:38 西月弦 閱讀(500) 評(píng)論(0)  編輯 收藏 引用 所屬分類: 解題報(bào)告
            国产激情久久久久久熟女老人 | 久久精品国产91久久麻豆自制 | 久久久噜噜噜久久| 久久婷婷午色综合夜啪| 久久天天躁狠狠躁夜夜不卡 | 国产高清国内精品福利99久久| 亚洲精品高清一二区久久| 久久精品人人做人人妻人人玩| 91久久精品国产91性色也| 色综合久久中文字幕无码| 久久久久97国产精华液好用吗| 7777久久久国产精品消防器材| 国内精品久久久久久久涩爱| 久久婷婷五月综合色高清| 欧美日韩精品久久久免费观看| 久久99国产精品一区二区| 亚洲AV无码久久精品色欲| 欧美激情精品久久久久久久| 久久久青草久久久青草| 一本色综合网久久| 欧美一级久久久久久久大片| 97热久久免费频精品99| 亚洲色婷婷综合久久| 精品国产乱码久久久久软件 | 久久精品天天中文字幕人妻| 国产成人久久精品一区二区三区 | 精品久久人人妻人人做精品| 色综合久久综精品| 中文字幕亚洲综合久久| 久久精品嫩草影院| 99久久精品国产综合一区| 99久久精品国产麻豆| 久久精品视频网| 国产精品成人无码久久久久久 | 中文精品99久久国产| 亚洲&#228;v永久无码精品天堂久久| 色综合合久久天天综合绕视看| 久久综合狠狠综合久久激情 | 伊人久久大香线焦综合四虎| 久久99精品九九九久久婷婷| 精品久久久久久久中文字幕|