Parentheses Matrix

题目连接

[HDU 6440] 2018 Multi-University Training Contest 8--1004 Parentheses Matrix

题解

中档题,结论题。题意大概是构造一个h行w列的矩阵由'(',')'组成,使得每行每列所组成的匹配的括号串数最大。

首先考虑行或列为奇数的情况,显然任意一个匹配的字符串其长度必然为偶数,所以我们只要考虑为偶数的那一侧即可。
当行或列均为偶数时,首先我们必然可以保证行或列单独一个完全符合匹配。具体如下

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

在此基础之上可以稍加改进使得另一侧有(n-2)/2的数量可以获得匹配,具体如下

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

之后可以发现,若要使得第一行匹配,至多只可能有一半的列匹配,第一列匹配的情况同理。所以我们首相将第一行列与最后一行列稍加改进,具体如下

((((((
(....)
(....)
))))))

在此基础之上将中间空白部分交替排列即可做到行数+列数-4的匹配数量,具体如下:

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

当数据较小时这种匹配方式可能未必比前几种更优秀,但当数据量增大时显著比前几种更优。

代码

#include <bits/stdc++.h>

using namespace std;
char output[205][205];
int main() {
    ios::sync_with_stdio(0);
    cout.tie(0);
    cin.tie(0);
    int t;
    for (cin >> t; t; t--) {
        int h,w;
        cin >> h >> w;
        if (h % 2) {
            for (int i = 1; i <= h; i++) {
                for (int j = 1; j <= w; j++) {
                    putchar((j) % 2 ? '(' : ')');
                }
                putchar('\n');
            }
        } else
            if (w % 2) {
                for (int i = 1; i <= h; i++) {
                    for (int j = 1; j <= w; j++) {
                        putchar((i) % 2 ? '(' : ')');
                    }
                    putchar('\n');
                }
            } else {
                if (max(h,w)+(min(h,w)-2)/2>=h+w-4){
                if (h >= w) {
                    for (int i=1;i<=h;i++){
                        output[i][1]='(';
                        output[i][w]=')';
                    }
                    for (int i=1;i<=h;i++){
                        for (int j=2;j<=w-1;j++){
                            output[i][j]=(i+j)%2?'(':')';
                        }
                    }
                }
                else {
                    for (int i=1;i<=w;i++){
                        output[1][i]='(';
                        output[h][i]=')';
                    }
                    for (int i=2;i<=h-1;i++){
                        for (int j=1;j<=w;j++){
                            output[i][j]=(i+j)%2?'(':')';
                        }
                    }
                }
                for (int i=1;i<=h;i++){
                    for (int j=1;j<=w;j++){
                        putchar(output[i][j]);
                    }
                    putchar('\n');
                }}
                else {
                    for (int i=1;i<=h;i++){
                        for (int j=1;j<=w;j++){
                            if (i==1||j==1)output[i][j]='(';
                            else if (i==h||j==w)output[i][j]=')';
                            else output[i][j]=(i+j)%2?')':'(';
                        }
                    }
                    for (int i=1;i<=h;i++) {
                        for (int j = 1; j <= w; j++) {
                            putchar(output[i][j]);
                        }
                        putchar('\n');
                    }
                }
            }
    }
}

标签: implementation, constructive algorithms

添加新评论