HDU6400 Parentheses Matrix(2018HDU多校联赛第八场,构造)

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

(
()
)(
(((
)))

# 思路

题目首先是一个匹配括号的定义。然后对于一个只包含(和)的矩阵，定义了一个goodness值,对于矩阵的一行或者一列，只有当这一行或者列的所有括号全部匹配，这个矩阵的goodness值+1$+1$,题目给了一个n和m，让构造出一个矩阵，使得矩阵规模为n∗m$n\ast m$的goodness值最大。

首先我们确定n$n$和m$m$的奇偶性。

所以有四种情况:

1. 奇奇
   
   • 对于这种情况，因为是奇数，无论怎么构造都不可能有符合条件的，所以只需要随便构造一个矩阵输出即可
2. 奇偶
   
   • 对于这种因为行是奇数，所以对于每一列我们无法构造出符合条件的括号匹配序列，但是对于每一行，犹豫列是偶数，我们一定可以构造出每一行都是()()()()这种，所以它的goodness值为n$n$
3. 偶奇
   
   • 和上种情况相似，我们可以构造列来匹配，那么他的goodness值为m$m$

4. 偶偶

   • 对于这种情况，比较复杂:

   • 当n和m中有一个为2或4时,我们先把每一行构造满，当n>=m$n>=m$时，我们把每一行构造满，然后再交换列，否则，先把列构造满，再交换行

     比如要构造6 4,首先构造出这样:

     ()()
     ()()
     ()()
     ()()
     ()()
     ()()

     然后转变成这样

     (())
     (())
     (())
     ()()
     ()()
     ()()

     如果是4 6 ，首先这样:

     ((((((
     ))))))
     ((((((
     ))))))

     然后变成这样

     ((((((
     ((()))
     )))(((
     ))))))

   • 对于其余情况，我们最多可以构造出n+m−4$n+m-4$的方法，比如8 8：

     ((((((()
     ()()()()
     (()()())
     ()()()()
     (()()())
     ()()()()
     (()()())
     ()))))))

     先把第一行变成(把最后一行变成),再把第一列变成(,把最后一列变成),然后当前矩阵的四个边就填好了，剩下的按照()匹配即可.

附上官方题解:

代码

#include <bits/stdc++.h>
using namespace std;
const int N=1e3+200;
#define mem(a,b) memset(a,b,sizeof(a))
const int inf=0x3f3f3f3f;
char s[210][210];
void calc1(int n,int m)
{
    if(n>=m)
    {
        for(int i=1; i<=n; i++)
        {
            for(int j=1; j<=m; j++)
            {
                if(j&1)s[i][j]='(';
                else s[i][j]=')';
            }
        }
        for(int i=1; i<=n/2; i++)
        {
            for(int j=2; j<=m-1; j++)
                if(s[i][j]=='(')
                    s[i][j]=')';
                else
                    s[i][j]='(';
        }
        for(int i=1; i<=n; i++)
        {
            for(int j=1; j<=m; j++)
            {
                printf("%c",s[i][j]);
            }
            puts("");
        }
    }
    else
    {
        for(int i=1; i<=m; i++)
        {
            for(int j=1; j<=n; j++)
            {
                if(j&1)s[j][i]='(';
                else s[j][i]=')';
            }
        }
        for(int i=1; i<=m/2; i++)
        {
            for(int j=2; j<=n-1; j++)
                if(s[j][i]=='(')
                    s[j][i]=')';
                else
                    s[j][i]='(';
        }
        for(int i=1; i<=n; i++)
        {
            for(int j=1; j<=m; j++)
            {
                printf("%c",s[i][j]);
            }
            puts("");
        }
    }
}
void solve()
{
    int n,m,f1,f2;
    scanf("%d%d",&n,&m);
    f1=n&1,f2=m&1;
    if(f1==0&f2==0)
    {
        mem(s,'\0');
        if(n<=4||m<=4)calc1(n,m);
        else
        {
            for(int i=1; i<=m; i++)
            {
                s[1][i]='(';
                s[n][i]=')';
            }

            for(int i=1; i<=n; i++)
            {
                s[i][1]='(';
                s[i][m]=')';
            }
            for(int i=2; i<=n-1; i++)
            {
                for(int j=2; j<=m-1; j++)
                {
                    if((i+j)%2==0)
                        s[i][j]=')';
                    else
                        s[i][j]='(';
                }
            }
            for(int i=1; i<=n; i++)
            {
                for(int j=1; j<=m; j++)
                {
                    printf("%c",s[i][j]);
                }
                puts("");
            }
        }
    }
    else if(f1==0&&f2==1)
    {
        for(int i=1; i<=n; i++)
        {
            if(i&1)
            {
                for(int j=1; j<=m; j++)
                    printf("(");
            }
            else
            {
                for(int j=1; j<=m; j++)
                    printf(")");
            }
            puts("");
        }
    }
    else if(f1==1&&f2==0)
    {
        for(int i=1; i<=n; i++)
        {
            for(int j=1; j<=m; j++)
            {
                if(j&1)printf("(");
                else printf(")");
            }
            printf("\n");
        }

    }
    else if(f1==1&&f2==1)
    {
        for(int i=1; i<=n; i++)
        {
            for(int j=1; j<=m; j++)
                printf("(");
            puts("");
        }

    }
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
        solve();
    return 0;
}