2018 Multi-University Training Contest 8 D.Parenth

2018 Multi-University Training Contest 8 D.Parentheses Matrix

传送门

题目大意

一个由左括号和右括号组成的矩阵，定义矩阵的权值是矩阵中匹配的行数和列数的和。

题解

一道比较典型的构造题。

如果行数或者列数是奇数那么矩阵显然是奇数的行或列匹配不了。

(())

(())

(())

当情况很多有两个变量的时候我们可以假设一个变量小于另一个变量，假设$h\leq m$。

构造过程还是题解比较清晰。

首先，第一行、最后一列中最多只有一个能够匹配，第一列、最后一行也只有一个能够匹配（考 虑右上角和左下角的括号选取方法），故答案不会超过 w+h−2。 当 h = 2 时，每一列可以构造一对匹配，这样答案已经到达上界。 当 h = 4 时，可以如下构造：

( ( ( ( ( (

) ) ) ) ) )

( ( ( ( ( (

) ) ) ) ) )

这样答案是 w+h−3。

若存在更优的答案，则必有一个边界能够匹配，不妨设是第一列。这样，就已 经有除第一行以外的两行（右括号开头的行）不匹配了，而第一行和最后一列中至少有一个不匹配， 因此最优解不会超过 w+h−3。

当 h≥6 时，可以如下构造：

( ( ( ( ( ( ( (

( ) ( ) ( ) ( )

( ( ) ( ) ( ) )

( ( ( ( ) ) ) )

( ( ) ( ) ( ) )

) ) ) ) ) ) ) )

答案是 w+h−4。同理可证明不存在更优的方法。

在实际操作的时候如果$h>m$可以将矩阵反转一下。就ok了。

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
int t,h,w;
char g[300][300];
int main(){
#ifdef LOCAL
    freopen("d.in","r",stdin);
#endif
    scanf("%d",&t);
    while(t--){
        bool flag = 0;
        scanf("%d%d",&h,&w);
        if(h&1){
            rep(i,0,h){
                rep(j,0,w){
                    g[i][j] = (j<w/2 ? '(' : ')');
                }
            }
        }else if(w&1){
            rep(i,0,h){
                rep(j,0,w){
                    g[i][j] = (i<h/2 ? '(' : ')');
                }
            }
        }
        else{
            if(h>w){
                int temp = h;
                h = w;
                w = temp;
                flag = 1;
            }
            if(h==2){
                rep(i,0,w){
                    g[0][i] = '(';
                    g[1][i] = ')';
                }
            }else if(h == 4){
                rep(i,0,w){
                    g[0][i] = '(';
                    g[1][i] = (i<w/2 ? ')' : '(');
                    g[2][i] = (i<w/2 ? '(' : ')');
                    g[3][i] = ')';
                }
            }else{
                rep(i,0,h){
                    rep(j,0,w){
                        if(i==0 || j==0) g[i][j] = '(';
                        else if(i == h-1 || j == w-1) g[i][j] = ')';
                        else if((i^j)&1) g[i][j] = ')';
                        else g[i][j] = '(';
                    }
                }
            }
        }
        if(flag){
            rep(j,0,w){
                rep(i,0,h){
                    putchar(g[i][j]);
                }
                puts("");
            }
        }else{
            rep(i,0,h){
                rep(j,0,w){
                    putchar(g[i][j]);
                }
                puts("");
            }
        }
    }
    return 0;
}