hdu6400 Parentheses Matrix 构造
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
(
()
)(
(((
)))
Source
2018 Multi-University Training Contest 8
Recommend
chendu | We have carefully selected several similar problems for you: 6408 6407 6406 6405 6404
/*
题意
构造一个 h×w 的括号矩阵,使得匹配的行数、列数之和最大。
题解
当 h 和 w 中有一个是奇数时,构造的方法是显然的。下面仅讨论 h 和 w 都是偶数的情况。不妨设
h ≤ w。
首先,第一行、最后一列中最多只有一个能够匹配,第一列、最后一行也只有一个能够匹配(考
虑右上角和左下角的括号选取方法),故答案不会超过 w+h−2。
当 h = 2 时,每一列可以构造一对匹配,这样答案已经到达上界。
当 h = 4 时,可以如下构造:
((((((
)))(((
((()))
))))))
这样答案是 w+h−3。若存在更优的答案,则必有一个边界能够匹配,不妨设是第一列。这样,就已
经有除第一行以外的两行(右括号开头的行)不匹配了,而第一行和最后一列中至少有一个不匹配,
因此最优解不会超过 w+h−3。
当 h ≥ 6 时,可以如下构造:
((((((((
()()()()
(()()())
()()()()
(()()())
))))))))
答案是 w+h−4。同理可证明不存在更优的方法。
*/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
char a[505][505];
int main()
{
int t,i,j,n,m;
cin>>t;
while(t--)
{
cin>>n>>m;
if((n&1)&&(m&1))
{
for(i=0;i<n;i++)
{
for(j=0;j<m;j++)
a[i][j]='(';
}
}
else if(n&1)
{
for(i=0;i<n;i++)
{
for(j=0;j<m;j++)
{
if(j%2)
a[i][j]=')';
else
a[i][j]='(';
}
}
}
else if(m&1)
{
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
{
if(j%2)
a[j][i]=')';
else
a[j][i]='(';
}
}
}
else
{
if(n==2)
{
for(int i=0;i<m;i++)
{
a[0][i]='(';
a[1][i]=')';
}
}
else if(m==2)
{
for(int i=0;i<n;i++)
{
a[i][0]='(';
a[i][1]=')';
}
}
else if(n==4)
{
for(i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
if(i==0) a[i][j]='(';
else if(i==n-1) a[i][j]=')';
else if((i&1)&&(j<m/2)) a[i][j]=')';
else if(i&1) a[i][j]='(';
else if(j<m/2) a[i][j]='(';
else a[i][j]=')';
}
}
}
else if(m==4)
{
for(i=0;i<m;i++)
{
for(int j=0;j<n;j++)
{
if(i==0) a[j][i]='(';
else if(i==m-1) a[j][i]=')';
else if((i&1)&&(j<n/2)) a[j][i]=')';
else if(i&1) a[j][i]='(';
else if(j<n/2) a[j][i]='(';
else a[j][i]=')';
}
}
}
else if(n>=m)
{
for(i=0;i<m;i++)
{
for(int j=0;j<n;j++)
{
if(i==0) a[j][i]='(';
else if(i==m-1) a[j][i]=')';
else if((i&1)&&(j&1)) a[j][i]=')';
else if(i&1) a[j][i]='(';
else if(j==0) a[j][i]='(';
else if(j==n-1) a[j][i]=')';
else if(j&1) a[j][i]='(';
else a[j][i]=')';
}
}
}
else
{
for(i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
if(i==0) a[i][j]='(';
else if(i==n-1) a[i][j]=')';
else if((i&1)&&(j&1)) a[i][j]=')';
else if(i&1) a[i][j]='(';
else if(j==0) a[i][j]='(';
else if(j==m-1) a[i][j]=')';
else if(j&1) a[i][j]='(';
else a[i][j]=')';
}
}
}
}
for(i=0;i<n;i++)
{
for(j=0;j<m;j++)
cout<<a[i][j];
cout<<endl;
}
}
return 0;
}
首先分奇偶性讨论。
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()
{
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;
}
上一篇: 如何使用POI导入导出到excel表格
推荐阅读
-
hdu6400 Parentheses Matrix 构造
-
杭电多校04补题 HDU6336 Problem E. Matrix from Arrays【构造】
-
agc027D - Modulo Matrix(构造 黑白染色)
-
HDU6400 Parentheses Matrix(2018HDU多校联赛第八场,构造)
-
Codeforces Round #630 (Div. 2) D. Walk on Matrix(思维+构造)
-
Educational Codeforces Round 48 (Rated for Div. 2) D. Vasya And The Matrix(思维/构造)
-
agc027D - Modulo Matrix(构造 黑白染色)