Parentheses Matrix
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)Total Submission(s): 728 Accepted Submission(s): 294Special Judge
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
(
()
)(
(((
)))
这题。。。。WA到死啊 在h=2那里摔倒了好几次都没看出来
题意是构造一个 h×w 的括号矩阵，并且使其匹配的行数、列数之和最大的矩阵之一。
当 h 和 w 中有一个是奇数时，构造的方法是显然的。下面仅讨论 h 和 w 都是偶数的情况。不妨设 h≤w。 首先，第一行、最后一列中最多只有一个能够匹配，第一列、最后一行也只有一个能够匹配（考虑右上角和左下角的括号选取方法），故答案不会超过 w+h−2。
当 h = 2 时，每一列可以构造一对匹配，这样答案已经到达上界。 当 h = 4 时，可以如下构造：
((((((
)))(((
((()))
))))))
这样答案是 w+h−3。若存在更优的答案，则必有一个边界能够匹配，不妨设是第一列。这样，就已 经有除第一行以外的两行（右括号开头的行）不匹配了，而第一行和最后一列中至少有一个不匹配， 因此最优解不会超过 w+h−3。
当 h≥6 时，可以如下构造：
((((((((
()()()()
(()()())
()()()()
(()()())
))))))))答案是 w+h−4。同理可证明不存在更优的方法。
1 #include2 3 using namespace std; 4 5 int main() 6 { 7 ios::sync_with_stdio(false); 8 int t; 9 cin >> t; 10 while (t--) 11 { 12 int h, w; 13 cin >> h >> w; 14 15 if (h % 2 && w % 2) 16 { 17 for (int i = 0; i < h; i++) 18 { 19 for (int j = 0; j < w; j++) 20 cout << "("; 21 cout << endl; 22 } 23 } 24 else if (!(h % 2) && w % 2) 25 { 26 for (int i = 0; i < h; i++) 27 { 28 for (int j = 0; j < w; j++) 29 { 30 if (i % 2) 31 cout << ")"; 32 else 33 cout << "("; 34 } 35 cout << endl; 36 } 37 } 38 else if (!(w % 2) && h % 2) 39 { 40 for (int i = 0; i < h; i++) 41 { 42 for (int j = 0; j < w; j++) 43 { 44 if (j % 2) 45 cout << ")"; 46 else 47 cout << "("; 48 } 49 cout << endl; 50 } 51 } 52 else if (w == 2 || h == 2) 53 { 54 if (w >= h) 55 { 56 for (int j = 0; j < w; j++) 57 cout << "("; 58 cout << endl; 59 for (int j = 0; j < w; j++) 60 cout << ")"; 61 cout << endl; 62 } 63 else 64 { 65 for (int i = 0; i < h; i++) 66 cout << "()" << endl; 67 } 68 } 69 else if (w == 4 || h == 4) 70 { 71 if (w >= h) 72 { 73 for (int i = 0; i < h; i++) 74 { 75 for (int j = 0; j < w; j++) 76 { 77 if (!i) 78 cout << "("; 79 else if (i == 2) 80 { 81 if (j < w / 2) 82 cout << "("; 83 else 84 cout << ")"; 85 } 86 else if (i == 1) 87 { 88 if (j >= w / 2) 89 cout << "("; 90 else 91 cout << ")"; 92 } 93 else 94 cout << ")"; 95 } 96 cout << endl; 97 } 98 } 99 else100 {101 for (int i = 0; i < h; i++)102 {103 for (int j = 0; j < w; j += 2)104 {105 if (i < h / 2)106 cout << "()";107 else108 {109 if (j < w / 2)110 cout << "((";111 else112 cout << "))";113 }114 }115 cout << endl;116 }117 }118 }119 else120 {121 for (int i = 0; i < h; i++)122 {123 for (int j = 0; j < w; j++)124 {125 if (!i)126 cout << "(";127 else if (i == h - 1)128 cout << ")";129 else if (i % 2 == 0)130 {131 cout << "()";132 j++;133 }134 else if (i % 2)135 {136 if (!j)137 cout << "(";138 else if (j == w - 1)139 cout << ")";140 else141 {142 cout << "()";143 j++;144 }145 }146 }147 cout << endl;148 }149 }150 }151 152 return 0;153 }