Parentheses Matrix

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)Total Submission(s): 0    Accepted Submission(s): 0Special 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 ( () )( ((( )))       构造题。找出每行每列最大匹配数的矩阵。 首先分奇偶性讨论。 1.奇奇情况为0，任意输出。 2.奇偶情况最大匹配为偶数值。 3.偶偶要分两种情况，最大匹配为max(h,w)+min(h,w)/2-1或h+w-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; }

 

转载于:https://www.cnblogs.com/yzm10/p/9482992.html

相关资源：DirectX修复工具V4.0增强版