• <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)告
            99精品国产在热久久无毒不卡| 久久久久免费视频| 91亚洲国产成人久久精品| 久久99热国产这有精品| 国产精品va久久久久久久| 99国内精品久久久久久久| 久久99精品九九九久久婷婷 | 99国产欧美久久久精品蜜芽| 99久久精品毛片免费播放| 久久久久无码精品| 精品久久久久久亚洲精品| 99久久这里只精品国产免费| 国产精品美女久久久m| AAA级久久久精品无码片| 欧美伊人久久大香线蕉综合| 久久99精品久久久久久不卡| 一本色道久久综合亚洲精品| 久久久久久亚洲精品影院| 色婷婷久久久SWAG精品| 国内精品久久久久伊人av| 久久精品国产99国产精品导航| 久久久这里有精品| 九九精品99久久久香蕉| 久久精品www| 免费观看成人久久网免费观看| 一本一本久久a久久综合精品蜜桃| 亚洲香蕉网久久综合影视| 伊人久久综合热线大杳蕉下载| 亚洲成人精品久久| 亚洲精品无码专区久久久| 国产亚洲美女精品久久久2020| 国产亚州精品女人久久久久久 | 91秦先生久久久久久久| 午夜视频久久久久一区 | 久久久无码一区二区三区| 国产福利电影一区二区三区久久老子无码午夜伦不 | 久久综合给合久久国产免费| 亚洲色欲久久久综合网| 久久久精品人妻一区二区三区蜜桃| 久久久中文字幕| 久久人妻少妇嫩草AV无码专区|