HDU 6400 Parentheses Matrix（构造）
HDU 6400 Parentheses Matrix（构造）
用户2965768
发布于 2018-08-30 15:07:50
发布于 2018-08-30 15:07:50
题意：给你r,c求一个矩阵让它的行和列的匹配度最大，匹配就要一行一列全都匹配
每个位置只能是左括号或者右括号， “（）”这算一个匹配，那么“（（））”，“（）（）”也是匹配的。
题解：当r,c都为奇数时，不可能匹配；
当r或c为奇数时，答案就是r，c
难的是r和c都是偶数，遇事不决先打表。
想一想，第一行要匹配要一半的左括号，一般的右括号，（（（（）））），像这样，第一行有右括号该列就无法匹配了
就很浪费，那么第一行就全是（（（（（（（（（，同理第一列也全都是（(((((((，然后吧，最后一列是））））））
最后一行除了第一列都是））））））））））））））
然后就是中间的，打表或者自己画找找规律什么的，发现行或者列有一个小于等于4第一行有（（）），就不会很浪费
就算特殊情况，然后构造。
比如4 16
(((((((((((((((( ))))))))(((((((( (((((((()))))))) ))))))))))))))))
这样排列就多赚了第三行，但是往后如果行列没有小于4的，就还是按照上面的处理
比如这个最多是16，（比赛真是服了一群14wa,14wa,14wa,然后最后几分钟浙大宁波学院的一哥们？说是16我还没信，emmmmm）
10 10 (((((((((( ()()()()() (()()()()) ()()()()() (()()()()) ()()()()() (()()()()) ()()()()() (()()()()) ()))))))))
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int r,c;
scanf("%d %d",&r,&c);
if((r&1)&&(c&1))//都是奇数随便输出
{
for(int i=0;i<r;i++)
for(int j=0;j<c;j++)
{
printf("(");
if(j==c-1)printf("\n");
}
}
else if((r&1))//行为奇数，答案为行数
{
for(int i=0;i<r;i++)
for(int j=1;j<=c/2;j++)
{
printf("()");
if(j==c/2)printf("\n");
}
}
else if((c&1))
{
for(int i=1;i<=r;i++)
for(int j=0;j<c;j++)
{
if((i&1))
{
printf("(");
}
else printf(")");
if(j==c-1)printf("\n");
}
}
else {
int p=min(r,c),q=max(r,c);
if(p<=4)
{
if(r<c)//r<c有小于4的
{
for(int i=1;i<=r;i++)
for(int j=1;j<=c;j++)
{
if(i==1)printf("(");
else if(i==r)printf(")");
else {
if((i&1))
{
if(j<=c/2)printf("(");
else printf(")");
}else {
if(j<=c/2)printf(")");
else printf("(");
}
}
if(j==c)printf("\n");
}
}
else//c>=r r小于等于4
{
for(int i=1;i<=r;i++)
for(int j=1;j<=c;j++)
{
if(i<=r/2)
{
if(j<=c/2)printf("(");
else printf(")");
if(j==c)printf("\n");
}
else {
if((j&1))printf("(");
else printf(")");
if(j==c)printf("\n");
}
}
}
}
else//都为偶数没有小于4的
{
for(int i=0;i<r;i++)
for(int j=0;j<c;j++)
{
if(i==0||j==0)printf("(");
else if(i==r-1||j==c-1)printf(")");
else if(((i+j)&1))printf("(");
else printf(")");
if(j==c-1)printf("\n");
}
}
}
}
return 0;
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2018年08月15日，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读