程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> POJ 2777 Count Color

POJ 2777 Count Color

編輯:關於C++

這題其實之前寫過,應該算是線段樹中比較簡單的,不過自己還是被坑了很長時間,就是因為一個小小的錯誤,怎麼找都找不到,哎,急哭了。

這題在找顏色種類的時候,因為最多只有30種顏色,所以可以用一個整型變量來存儲,一個位代表一種顏色。這裡就要考慮對位的處理了,具體見代碼。

#include
#include
const int N=100005;
int L,T,O;
struct board
{
    int left,right,color;
    bool ischange;
}node[N<<2];

void set_tree(int id,int l,int r)
{
    node[id].left=l,node[id].right=r,node[id].color=1,node[id].ischange=false;
    if(l==r)
        return;
    int lson=id<<1,rson=lson+1,mid=(l+r)/2;
    set_tree(lson,l,mid);
    set_tree(rson,mid+1,r);
}
void update(int id,int l,int r,int c)
{
    if(node[id].left==l&&node[id].right==r)
    {
        node[id].color=1<<(c-1);
        node[id].ischange=true;
        return;
    }
    int lson=id<<1,rson=lson+1,mid=(node[id].left+node[id].right)/2;
    if(node[id].ischange)
    {
        node[lson].ischange=true,node[rson].ischange=true;
        node[lson].color=node[id].color,node[rson].color=node[id].color;
        node[id].ischange=false;
    }
    if(r<=mid)
        update(lson,l,r,c);
    else if(l>mid)
        update(rson,l,r,c);
    else
    {
        update(lson,l,mid,c);
        update(rson,mid+1,r,c);
    }
    node[id].color=node[lson].color|node[rson].color;
}
void query(int id,int l,int r,int &ans)
{
    if(node[id].ischange||(node[id].left==l&&node[id].right==r))
    {
        ans|=node[id].color;//就是這裡被坑了,我沒有加或,而是直接賦值了,當時估計腦袋秀逗了。
        return;
    }
    int lson=id<<1,rson=lson+1,mid=(node[id].left+node[id].right)/2;
    if(r<=mid)
        query(lson,l,r,ans);
    else if(l>mid)
        query(rson,l,r,ans);
    else
    {
        query(lson,l,mid,ans);
        query(rson,mid+1,r,ans);
    }
}

int main()
{
    int a,b,c;
    char s[3];
    while(scanf("%d%d%d",&L,&T,&O)!=EOF)
    {
        set_tree(1,1,L);
        for(int i=1;i<=O;i++)
        {
            scanf("%s",s);
            if(s[0]=='C')
            {
                scanf("%d%d%d",&a,&b,&c);
                if(a>b)//這裡要比較a,b的大小
                    update(1,b,a,c);
                else
                    update(1,a,b,c);
            }
            else
            {
                scanf("%d%d",&a,&b);
                int ans=0,cnt=0;
                if(a>b)
                    query(1,b,a,ans);
                else
                    query(1,a,b,ans);
                for(int i=0;i>1;
                }
                printf("%d\n",cnt);
            }
        }
    }
    return 0;
}


  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved