Parentheses Matrix
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 0 Accepted Submission(s): 0
Special 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
Sample Output
构造题。找出每行每列最大匹配数的矩阵。
首先分奇偶性讨论。
1.奇奇情况为0，任意输出。
2.奇偶情况最大匹配为偶数值。
3.偶偶要分两种情况，最大匹配为n+n/2-1或2*n-4，
行和列较小的值若小于等于6，第一行（列）为“（”，最后一行（列）为“）”，大于6则第一行列全为“（”，最后一行列全为“）”。
其他的位置行列下标和若偶为“（”，奇为“）”。
#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const int MAX = 205;
typedef long long LL;
int main(void)
{
int t,n,m,i,j;
scanf("%d",&t);
while(t--){
scanf("%d%d",&n,&m);
if((n&1)&&(m&1)){
for(i=1;i<=n;i++){
for(j=1;j<=m;j++){
printf("(");
}
printf("\n");
}
}
else if(n&1){
for(i=1;i<=n;i++){
for(j=1;j<=m;j++){
if(j&1) printf("(");
else printf(")");
}
printf("\n");
}
}
else if(m&1){
for(i=1;i<=n;i++){
for(j=1;j<=m;j++){
if(i&1) printf("(");
else printf(")");
}
printf("\n");
}
}
else{
if(n>=m){
for(i=1;i<=n;i++){
for(j=1;j<=m;j++){
if(i==1&&(m/2-1)>2){
printf("(");
continue;
}
if(i==n&&(m/2-1)>2){
printf(")");
continue;
}
if(j==1){
printf("(");
continue;
}
if(j==m){
printf(")");
continue;
}
if((i+j)&1){
printf(")");
}
else{
printf("(");
}
}
printf("\n");
}
}
else{
for(i=1;i<=n;i++){
for(j=1;j<=m;j++){
if(j==1&&(n/2-1)>2){
printf("(");
continue;
}
if(j==m&&(n/2-1)>2){
printf(")");
continue;
}
if(i==1){
printf("(");
continue;
}
if(i==n){
printf(")");
continue;
}
if((i+j)&1){
printf(")");
}
else{
printf("(");
}
}
printf("\n");
}
}
}
}
return 0;
}
HDU多校8 Parentheses Matrix（构造）
原文：https://www.cnblogs.com/yzm10/p/9482992.html
