首页 > 专题系列 > Java解POJ > POJ 2777 Count Color [解题报告] Java
2013
11-12

POJ 2777 Count Color [解题报告] Java

Count Color

问题描述 :

Chosen Problem Solving and Program design as an optional course, you are required to solve all kinds of problems. Here, we get a new problem.

There is a very long board with length L centimeter, L is a positive integer, so we can evenly divide the board into L segments, and they are labeled by 1, 2, … L from left to right, each is 1 centimeter long. Now we have to color the board – one segment with only one color. We can do following two operations on the board:

1. “C A B C” Color the board from segment A to segment B with color C.

2. “P A B” Output the number of different colors painted between segment A and segment B (including).

In our daily life, we have very few words to describe a color (red, green, blue, yellow…), so you may assume that the total number of different colors T is very small. To make it simple, we express the names of colors as color 1, color 2, … color T. At the beginning, the board was painted in color 1. Now the rest of problem is left to your.

输入:

First line of input contains L (1 <= L <= 100000), T (1 <= T <= 30) and O (1 <= O <= 100000). Here O denotes the number of operations. Following O lines, each contains "C A B C" or "P A B" (here A, B, C are integers, and A may be larger than B) as an operation defined previously.

输出:

Ouput results of the output operation in order, each line contains a number.

样例输入:

2 2 4
C 1 1 2
P 1 2
C 2 2 2
P 1 2

样例输出:

2
1

解题代码:

/* @author: [email protected]/
import java.io.*;
import java.util.*;
public class Main
{
  static  tree[] mytree=new tree[300003];
  static boolean[] flag=new boolean[35];
  public static void main(String args[]) throws Exception
  {
     InputStreamReader is=new InputStreamReader(System.in);
     BufferedReader in=new BufferedReader(is);
     String[] ss=in.readLine().split(" ");
     int l=Integer.parseInt(ss[0]);
     int t=Integer.parseInt(ss[1]);
     int o=Integer.parseInt(ss[2]);
     buildtree(1,l,1);
     while(o--!=0)
      {
         ss=in.readLine().split(" ");
         if(ss[0].equals("C"))
         {
           int A=Integer.parseInt(ss[1]);
           int B=Integer.parseInt(ss[2]);
           if(A>B) 
           {
            int temp=A;
            A=B;
            B=temp;
           }
           int p=Integer.parseInt(ss[3]);
           insert(A,B,p,1);
                        	
         }
          if(ss[0].equals("P"))
           {
            int A=Integer.parseInt(ss[1]);
            int B=Integer.parseInt(ss[2]);
            if(A>B) 
            {
              int temp=A;
              A=B;
              B=temp;
           }
           Arrays.fill(flag, false);
           query(A,B,1);
           int count=0;
           for(int i=0;i< 35;i++)
            if(flag[i])
              count++;
           System.out.println(count);
                        	
       }
     }
   }
            
   public static void buildtree(int a,int b,int i)
    {
     	mytree[i]=new tree();
      	mytree[i].left=a;
       mytree[i].right=b;
      	mytree[i].color=1;
       if(a!=b)
        {
          int mid=(a+b)/2;
          buildtree(a,mid,i*2);
          buildtree(mid+1,b,i*2+1);
        }
   }
            
   public static void insert(int a,int b,int c,int i)
    {
       if(mytree[i].left==a&&mytree[i].right==b)
         mytree[i].color=c;
       else
       {
         if( mytree[i].color !=-1)         
          {
            mytree[i*2].color =mytree[i].color ;
            mytree[i*2+1].color =mytree[i].color ;
            mytree[i].color =-1;        
          }
        int mid=(mytree[i].left+mytree[i].right)/2;
        if(b<=mid)
           insert(a,b,c,2*i);
        else if(a>=mid+1)
           insert(a,b,c,2*i+1);
        else
        {
           insert(a,mid,c,2*i);
           insert(mid+1,b,c,2*i+1);
        }  
     }
   	
  }
            
   public static void query(int a,int b,int i)
    {
     if(mytree[i].color==-1)
     {
        if(mytree[2*i]==mytree[2*i+1]&&mytree[2*i].color!=-1)
            mytree[i].color=mytree[2*i+1].color;
     }
     if(mytree[i].color!=-1)
     {
         flag[mytree[i].color]=true;
      }
     else
     {
        int mid=(mytree[i].left+mytree[i].right)/2;
        if(b<=mid&&mytree[2*i]!=null)
           query(a,b,2*i);
        else if(a>=mid+1&&mytree[2*i+1]!=null)
           query(a,b,2*i+1);
        else
        {
           if(mytree[2*i]!=null)
            query(a,mid,2*i);
           if(mytree[2*i+1]!=null)
            query(mid+1,b,2*i+1);
        }
      }
   }
}

class tree
{
	int left;
	int right;
	int color;
}

  1. /*
    * =====================================================================================
    *
    * Filename: 1366.cc
    *
    * Description:
    *
    * Version: 1.0
    * Created: 2014年01月06日 14时52分14秒
    * Revision: none
    * Compiler: gcc
    *
    * Author: Wenxian Ni (Hello World~), [email protected]
    * Organization: AMS/ICT
    *
    * =====================================================================================
    */

    #include
    #include

    using namespace std;

    int main()
    {
    stack st;
    int n,i,j;
    int test;
    int a[100001];
    int b[100001];
    while(cin>>n)
    {
    for(i=1;i>a[i];
    for(i=1;i>b[i];
    //st.clear();
    while(!st.empty())
    st.pop();
    i = 1;
    j = 1;

    while(in)
    break;
    }
    while(!st.empty()&&st.top()==b[j])
    {
    st.pop();
    j++;
    }
    }
    if(st.empty())
    cout<<"YES"<<endl;
    else
    cout<<"NO"<<endl;
    }
    return 0;
    }