Chinaunix首页 | 论坛 | 博客
  • 博客访问: 451040
  • 博文数量: 59
  • 博客积分: 345
  • 博客等级: 二等列兵
  • 技术积分: 1380
  • 用 户 组: 普通用户
  • 注册时间: 2011-06-18 22:44
个人简介

to be myself

文章分类

全部博文(59)

文章存档

2017年(5)

2013年(47)

2012年(3)

2011年(4)

分类: C/C++

2013-03-03 12:20:14

好多分支,枚举真的要十分仔细,注意解决问题的全面性!树状数组解决,效率还OK。


  1. #include<stdio.h>
  2. #include <string.h>

  3. #define N 50010
  4. int n, len, c[N];
  5. char s[N];

  6. int getLowBit(int n)
  7. {
  8.     return n&(-n);
  9. }

  10. void add(int i,int m)
  11. {
  12.     
  13.     for(;i<=n;i+=getLowBit(i))
  14.     {
  15.        c[i]+=m;
  16.     }
  17. }

  18. void sub(int i,int m)
  19. {
  20.     for(;i<=n;i+=getLowBit(i))
  21.     {
  22.        c[i]-=m;
  23.     }
  24. }
  25.  
  26. int getSum(int i)
  27. {
  28.     int sum=0;
  29.     for(;i>0;i-=getLowBit(i))
  30.     {
  31.        sum+=c[i];
  32.     }
  33.     return sum;
  34. }

  35. int main()
  36. {
  37.     int m, i, a, b, t, num=0, cnt, j, tb,query, last, init;
  38.     char *p;
  39.     freopen("input","r",stdin);
  40.     scanf("%d", &t);
  41.     while(t--)
  42.     {
  43.        scanf("%d%d",&n,&m);
  44.        memset(c,0,sizeof(c));
  45.        getchar(), gets(s);
  46.        p = s, init = 1;;
  47.        len = strlen(s);
  48.        
  49.        while(p =strstr(p,"wbw"))
  50.        {
  51.            
  52.            add(last=p-s+1, 1);
  53.            while(init < last)
  54.            {
  55.               add(init++, 0);
  56.            }
  57.            init = last + 1;
  58.            p += 2;
  59.        }
  60.        while(init <= len)
  61.        {
  62.            add(init++, 0);
  63.        }
  64.        printf("Case%d:n",++num);
  65.        for(i=0;i<m;i++)
  66.        {
  67.            scanf("%d %d",&query, &a);
  68.            if(query == 0)
  69.            {
  70.               scanf("%d",&b);
  71.               tb = getSum(b-1);
  72.               if(b-a<2)
  73.               {
  74.                   printf("0n");
  75.                   continue;
  76.               }
  77.               if(a==0)
  78.               {
  79.                   printf("%dn",tb);
  80.               }
  81.               else
  82.               {
  83.                   printf("%dn",tb- getSum(a));
  84.               }
  85.            }
  86.            else
  87.            {
  88.               b = getchar();
  89.               scanf("%c",&b);
  90.               if(a==len-1 || a==0) //左或右没有,a在起始或末尾
  91.               {
  92.                   if(a==len-1 &&a!=0)//右没有,在起始
  93.                   {
  94.                      if(s[a-2]=='w'&& s[a-1]=='b' && s[a]=='w' && b=='b')//wbw
  95.                      {
  96.                          sub(a-1, 1);
  97.                      }
  98.                      else if(s[a-2]=='w'&& s[a-1]=='b' && s[a]=='b' && b=='w')//wbb
  99.                      {
  100.                          add(a-1, 1);
  101.                      }
  102.                   }
  103.                   else if(a==0 &&a!=len-1)//左没有, 在末尾
  104.                   {
  105.                      if(s[a]=='w'&& s[a+1]=='b' && s[a+2]=='w' && b=='b')//wbw
  106.                      {
  107.                          sub(a+1, 1);
  108.                      }
  109.                      else if(s[a]=='b'&& s[a+1]=='b' && s[a+2]=='w' && b=='w')//bbw
  110.                      {
  111.                          add(a+1, 1);
  112.                      }
  113.                   }
  114.                   
  115.               }
  116.               else //在中间,至少左右都有
  117.               {
  118.                   if(a<len-1 &&a>0 && s[a-1]=='w' && s[a]=='w' && s[a+1]=='w'&& b=='b')//www
  119.                   {
  120.                      add(a, 1);//错写成add(a+1,1);
  121.                   }
  122.                   else if(a<len-1&& a>0 && s[a-1]=='w' && s[a]=='w' &&s[a+1]=='b' && b=='b')//wwb
  123.                   {
  124.                      if(s[a+2] == 'w'&& a<len-2)
  125.                      {
  126.                          sub(a+1, 1);
  127.                      }
  128.                   }
  129.                   else if(a<len-1&& a>0 && s[a-1]=='w' && s[a]=='b' &&s[a+1]=='w' && b=='w')//wbw
  130.                   {
  131.                      sub(a, 1); //错写成sub(a+1,1);
  132.                   }
  133.                   else if(a<len-1&& a>0 && s[a-1]=='b' && s[a]=='w' &&s[a+1]=='w' && b=='b')//bww
  134.                   {
  135.                      if(s[a-2] == 'w'&& a>1)
  136.                      {
  137.                          sub(a-1, 1);
  138.                      }
  139.                   }
  140.                   else if(a<len-1&& a>0 && s[a-1]=='b' && s[a]=='b' &&s[a+1]=='b' && b=='w')//bbb
  141.                   {
  142.                      if(s[a+2] == 'w'&& a<len-2)
  143.                      {
  144.                          add(a+1, 1);
  145.                      }
  146.                      if(s[a-2] == 'w'&& a>1)
  147.                      {
  148.                          add(a-1, 1);
  149.                      }
  150.                   }
  151.                   else if(a<len-1&& a>0 && s[a-1]=='b' && s[a]=='b' &&s[a+1]=='w' && b=='w')//bbw
  152.                   {
  153.                      if(s[a-2] == 'w'&& a>1)
  154.                      {
  155.                          add(a-1, 1);
  156.                      }
  157.                   }
  158.                   else if(a<len-1&& a>0 && s[a-1]=='b' && s[a]=='w' &&s[a+1]=='b' && b=='b')//bwb
  159.                   {
  160.                      if(s[a+2] == 'w'&& a<len-2)
  161.                      {
  162.                          sub(a+1, 1);
  163.                      }
  164.                      if(s[a-2] == 'w'&& a>1)
  165.                      {
  166.                          sub(a-1, 1);
  167.                      }
  168.                   }
  169.                   else if(a<len-1&& a>0 && s[a-1]=='w' && s[a]=='b' &&s[a+1]=='b' && b=='w')//wbb
  170.                   {
  171.                      if(s[a+2] == 'w'&& a<len-2)
  172.                      {
  173.                          add(a+1, 1);
  174.                      }
  175.                   }
  176.               }
  177.               s[a] = b; //一定要记得更新
  178.            }
  179.        }
  180.     }
  181.     return 0;
  182. }

2011-09-19 17:48 发表于百度空间,今搬至CU。

 

阅读(1833) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~