HDU 6400 Parentheses Matrix(构造+分类处理)

Problem Description

A parentheses matrix is a matrix where every element is either '(' or ')'. We define the goodness of a parentheses matrix as the number of balanced rows (from left to right) and columns (from up to down). Note that:

- an empty sequence is balanced;
- if A is balanced, then (A) is also balanced;
- if A and B are balanced, then AB is also balanced.

For example, the following parentheses matrix is a 2×4 matrix with goodness 3, because the second row, the second column and the fourth column are balanced:

)()(
()()

Now, give you the width and the height of the matrix, please construct a parentheses matrix with maximum goodness.

Input

The first line of input is a single integer T (1≤T≤50), the number of test cases.

Each test case is a single line of two integers h,w (1≤h,w≤200), the height and the width of the matrix, respectively.

Output

For each test case, display h lines, denoting the parentheses matrix you construct. Each line should contain exactly w characters, and each character should be either '(' or ')'. If multiple solutions exist, you may print any of them.

Sample Input

3 1 1 2 2 2 3

Sample Output

( () )( ((( )))

Source

2018 Multi-University Training Contest 8

题解：

这个题当时做了2个小时。。。最后h>=6的构造都造出来了就是没注意h=4时要分类讨论。。。难受ε=(´ο｀*)))唉

代码：

#include <cstdio>
#include <algorithm>

using namespace std;

char board[205][205];

int main(){
    
	int T;
	scanf("%d",&T);
	while(T--){
		bool flag = false;
		int a,b;
		scanf("%d %d",&a,&b);
		if(b < a){
			swap(a,b);
			flag = true;
		} 
		if(a&1){
		    for(int i=0 ; i<a ; ++i)
		        for(int j=0 ; j<b ; ++j){
		            if(j&1)board[i][j] = ')';
		            else board[i][j] = '(';
		        }
		}
		else if(b&1){
		    for(int j=0 ; j<b ; ++j)
		        for(int i=0 ; i<a ; ++i){
		            if(i&1)board[i][j] = ')';
		            else board[i][j] = '(';
		        }
		}
		else if(a == 2){
			for(int j=0 ; j<b ; ++j){
				board[0][j] = '(';
				board[1][j] = ')';
			}
		}
		else if(a == 4){
			for(int j=0 ; j<b ; ++j){
				board[0][j] = '(';
				board[a-1][j] = ')';
			}
			for(int i=1 ; i<a-1 ; ++i){
				if(i&1){
					for(int j=0 ; j<b/2 ; ++j)board[i][j] = ')';
					for(int j=b/2 ; j<b ; ++j)board[i][j] = '(';
				}
				else {
					for(int j=0 ; j<b/2 ; ++j)board[i][j] = '(';
					for(int j=b/2 ; j<b ; ++j)board[i][j] = ')';
				}
			}
		}
		else {
			for(int j=0 ; j<b ; ++j){
				board[0][j] = '(';
				board[a-1][j] = ')';
				if(j&1)board[1][j] = ')';
				else board[1][j] = '(';
			}
			board[1][0] = '(';
			board[1][b-1] = ')';
			for(int i=2 ; i<a-1 ; ++i){
				board[i][0] = '(';
				board[i][b-1] = ')';
				for(int j=1 ; j<b-1 ; ++j){
					if(board[i-1][j] == '(')board[i][j] = ')';
					else board[i][j] = '(';
				}	
			}
		}
		if(flag){
			for(int j=0 ; j<b ; ++j){
		        for(int i=0 ; i<a ; ++i)printf("%c",board[i][j]);
		        printf("
");
		    }
		}
		else {
			for(int i=0 ; i<a ; ++i){
		        for(int j=0 ; j<b ; ++j)printf("%c",board[i][j]);
		        printf("
");
		    }
		}
	}
    
    return 0;
}