首页 > ACM题库 > HDU-杭电 > HDU 1274 展开字符串-递归和分治-[解题报告] C++
2013
12-04

HDU 1274 展开字符串-递归和分治-[解题报告] C++

展开字符串

问题描述 :

在纺织CAD系统开发过程中,经常会遇到纱线排列的问题。
该问题的描述是这样的:常用纱线的品种一般不会超过25种,所以分别可以用小写字母表示不同的纱线,例如:abc表示三根纱线的排列;重复可以用数字和括号表示,例如:2(abc)表示abcabc;1(a)=1a表示a;2ab表示aab;如果括号前面没有表示重复的数字出现,则就可认为是1被省略了,如:cd(abc)=cd1(abc)=cdabc;这种表示方法非常简单紧凑,也易于理解;但是计算机却不能理解。为了使计算机接受,就必须将简单紧凑的表达方式展开。某ACM队接受了此项任务。现在你就是该ACM队的一员,请你把这个程序编写完成。
已知条件:输入的简单紧凑表达方式的长度不超过250个字符;括号前表示重复的数不超过1000;不会出现除了数字、括号、小写字母以外的任何其他字符;不会出现括号不配对等错误的情况(错误处理已由ACM其他队员完成了)。

输入:

本题有多个测试数据组,第一行输入的就是数据组数N,接着就是N行表达式,表达式是按照前面介绍的意义书写的。

输出:

输出时含有N行,每行对应一个输入的表达式。

样例输入:

2
1(1a2b1(ab)1c)
3(ab2(4ab))

样例输出:

abbabc
abaaaabaaaababaaaabaaaababaaaabaaaab

题目大意:本体是中文的,读者可以直接在OJ上读题。。。

解题思路:

f1:先对数字进行处理。然后判断接下来的是( ,还是字母。若是(则递归调用f1,若是字母则直接输出。

这道题传说中可以用容器来做,但是后来才去的是以下做法:

/*
 * 1274_5.cpp
 *
 *  Created on: 2013年8月7日
 *      Author: Administrator
 *
 *      章泽天,我的女神!!!!
 */


#include <iostream>

using namespace std;

string str;
int fun(int index){

	char c ;
	int k;
	int e = 0;

	for(c = str[index++] ; index < str.length() && c != ')' ; c  = str[index++]){

		for( k = 0 ; isdigit(c) ; c = str[index++]){
			k = 10*k + c - '0';
		}

		if(!k){
			k = 1;
		}

		if( c == '('){
			while(k--){
				e = fun(index);
			}

			index = e;
		}else{
			while(k--){
				cout<<c;
			}
		}


	}

	if( c == ')'){
		return index;
	}
}


int main(){
	int t;
	cin >> t;
	while(t--){
		cin >> str;
		fun(0);
		cout<<endl;
	}
}


  1. 额楼主能否在发布代码的同时对解题思路做个讲解呢?这样大家在学习的时候就方便多了。

  2. 第二块代码if(it != mp.end())应改为if(it != mp.end() && (i+1)!=(it->second +1));因为第二种解法如果数组有重复元素 就不正确

  3. 第一句可以忽略不计了吧。从第二句开始分析,说明这个花色下的所有牌都会在其它里面出现,那么还剩下♠️和♦️。第三句,可以排除2和7,因为在两种花色里有。现在是第四句,因为♠️还剩下多个,只有是♦️B才能知道答案。

  4. 这道题这里的解法最坏情况似乎应该是指数的。回溯的时候
    O(n) = O(n-1) + O(n-2) + ….
    O(n-1) = O(n-2) + O(n-3)+ …
    O(n) – O(n-1) = O(n-1)
    O(n) = 2O(n-1)