首页 > ACM题库 > HDU-杭电 > HDU 4046-Panda-字符串-[解题报告]HOJ
2015
04-16

HDU 4046-Panda-字符串-[解题报告]HOJ

Panda

问题描述 :

When I wrote down this letter, you may have been on the airplane to U.S.
We have known for 15 years, which has exceeded one-fifth of my whole life. I still remember the first time we went to the movies, the first time we went for a walk together. I still remember the smiling face you wore when you were dressing in front of the mirror. I love your smile and your shining eyes. When you are with me, every second is wonderful.
The more expectation I had, the more disappointment I got. You said you would like to go to U.S.I know what you really meant. I respect your decision. Gravitation is not responsible for people falling in love. I will always be your best friend. I know the way is difficult. Every minute thinking of giving up, thinking of the reason why you have held on for so long, just keep going on. Whenever you’re having a bad day, remember this: I LOVE YOU.
I will keep waiting, until you come back. Look into my eyes and you will see what you mean to me.
There are two most fortunate stories in my life: one is finally the time I love you exhausted. the other is that long time ago on a particular day I met you.
Saerdna.

It comes back to several years ago. I still remember your immature face.
The yellowed picture under the table might evoke the countless memory. The boy will keep the last appointment with the girl, miss the heavy rain in those years, miss the love in those years. Having tried to conquer the world, only to find that in the end, you are the world. I want to tell you I didn’t forget. Starry night, I will hold you tightly.

Saerdna loves Panda so much, and also you know that Panda has two colors, black and white.
Saerdna wants to share his love with Panda, so he writes a love letter by just black and white.
The love letter is too long and Panda has not that much time to see the whole letter.
But it’s easy to read the letter, because Saerdna hides his love in the letter by using the three continuous key words that are white, black and white.
But Panda doesn’t know how many Saerdna’s love there are in the letter.
Can you help Panda?

输入:

An integer T means the number of test cases T<=100
For each test case:
First line is two integers n, m
n means the length of the letter, m means the query of the Panda. n<=50000,m<=10000
The next line has n characters ‘b’ or ‘w’, ‘b’ means black, ‘w’ means white.
The next m lines
Each line has two type
Type 0: answer how many love between L and R. (0<=L<=R<n)
Type 1: change the kth character to ch(0<=k<n and ch is ‘b’ or ‘w’)

输出:

An integer T means the number of test cases T<=100
For each test case:
First line is two integers n, m
n means the length of the letter, m means the query of the Panda. n<=50000,m<=10000
The next line has n characters ‘b’ or ‘w’, ‘b’ means black, ‘w’ means white.
The next m lines
Each line has two type
Type 0: answer how many love between L and R. (0<=L<=R<n)
Type 1: change the kth character to ch(0<=k<n and ch is ‘b’ or ‘w’)

样例输入:

2

5 2
bwbwb
0 0 4
0 1 3
5 5
wbwbw
0 0 4
0 0 2
0 2 4
1 2 b
0 0 4

样例输出:

Case 1: 
1 
1 
Case 2: 
2 
1 
1 
0

题意:给你一个字符串,由’w' 和 ‘b’ 组成,对该字符串有俩个操作,

当输入为0 a, b时,询问区间[a,b] 内有多少个串 为 "wbw";

当输入为1,k,,ch时,将下标为k的字符改为字符ch;

#include <cstdio>
#include <iostream>
using namespace std;

int n, m;
int c[60000];
char str[60000];

int lowbit ( int x )  
{  
    return x & ( -x );  
}  
  
void update ( int x, int v )  
{  
    for ( int i = x; i <= n; i += lowbit(i) )  
        c[i] += v;   
} 

int getSum ( int x )  
{  
    int sum = 0;  
    for ( int i = x; i > 0; i -= lowbit(i) )  
        sum += c[i];  
    return sum;  
}  

bool check ( char x, char y, char z )
{
	if ( x == 'w' && y == 'b' && z == 'w' )
		return true;
	return false;
}

void init ()
{
	for ( int i = 3; i <= n; i++ )
		if ( check(str[i-2],str[i-1],str[i]) )
			update ( i, 1 );
}

int main()
{
	char change;
	int t, l, r, pos, oper;
	int cnt = 0;

	scanf("%d",&t);

	while ( t-- )
	{
		scanf("%d%d",&n,&m);
		scanf("%s",str+1);

		memset(c,0,sizeof(c));
		init();
		printf("Case %d:\n",++cnt);

		while ( m-- )
		{
			scanf("%d",&oper);
			if ( oper == 0 )
			{
				scanf("%d%d",&l,&r);
				l++; r++;
				if ( l > r )  swap ( l, r );
				if ( r - l < 2 )  printf("0\n");
				else printf ("%d\n", getSum(r) - getSum(l+1) ); /* 边界值一定得搞清楚, 由于是三个字符一组,sum[l+1]里面还可能记录了
str[l-1],str[l], str[l+1]构成的组合,所以要减去getSum(l+1) */
			}
			else
			{
				int i;
				scanf("%d %c",&pos, &change);
				pos++;
				if ( str[pos] == change ) continue;

				i = pos;
				if ( 3 <= i && i <= n )
				{
				    if ( check(str[i-2],str[i-1],str[i]) && !check(str[i-2],str[i-1],change) )
					    update(i,-1);
				    if ( !check(str[i-2],str[i-1],str[i]) && check(str[i-2],str[i-1],change) )
					    update(i,1);
				}

				i = pos + 1;
				if ( 3 <= i && i <= n )
				{
					if ( check(str[i-2],str[i-1],str[i]) && !check(str[i-2],change,str[i]) )
						update(i,-1);
					if ( !check(str[i-2],str[i-1],str[i]) && check(str[i-2],change,str[i]) )
						update(i,1);
				}

				i = pos + 2;
				if ( 3 <= i && i <= n )
				{
					if ( check(str[i-2],str[i-1],str[i]) && !check(change,str[i-1],str[i]) )
						update(i,-1);
					if ( !check(str[i-2],str[i-1],str[i]) && check(change,str[i-1],str[i]) )
						update(i,1);
				}
				str[pos] = change;
			}
		}
	}
	return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/tsaid/article/details/6787968


  1. 算法是程序的灵魂,算法分简单和复杂,如果不搞大数据类,程序员了解一下简单点的算法也是可以的,但是会算法的一定要会编程才行,程序员不一定要会算法,利于自己项目需要的可以简单了解。

  2. 可以根据二叉排序树的定义进行严格的排序树创建和后序遍历操作。如果形成的排序树相同,其树的前、中、后序遍历是相同的,但在此处不能使用中序遍历,因为,中序遍历的结果就是排序的结果。经在九度测试,运行时间90ms,比楼主的要快。

  3. 很高兴你会喜欢这个网站。目前还没有一个开发团队,网站是我一个人在维护,都是用的开源系统,也没有太多需要开发的部分,主要是内容整理。非常感谢你的关注。