HDU - 6400 多校8 Parentheses Matrix(构造)
2024-08-30 02:13:49
Parentheses Matrix
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 0 Accepted Submission(s): 0
Special Judge
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
(
()
)(
(((
)))
构造题。找出每行每列最大匹配数的矩阵。
首先分奇偶性讨论。
1.奇奇情况为0,任意输出。
2.奇偶情况最大匹配为偶数值。
3.偶偶要分两种情况,最大匹配为max(h,w)+min(h,w)/2-1或h+w-4,
行和列较小的值若小于等于6,第一行(列)为“(”,最后一行(列)为“)”,大于6则第一行列全为“(”,最后一行列全为“)”。
其他的位置行列下标和若偶为“(”,奇为“)”。
#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const int MAX = ;
typedef long long LL; int main(void)
{
int t,n,m,i,j;
scanf("%d",&t);
while(t--){
scanf("%d%d",&n,&m);
if((n&)&&(m&)){
for(i=;i<=n;i++){
for(j=;j<=m;j++){
printf("(");
}
printf("\n");
}
}
else if(n&){
for(i=;i<=n;i++){
for(j=;j<=m;j++){
if(j&) printf("(");
else printf(")");
}
printf("\n");
}
}
else if(m&){
for(i=;i<=n;i++){
for(j=;j<=m;j++){
if(i&) printf("(");
else printf(")");
}
printf("\n");
}
}
else{
if(n>=m){
for(i=;i<=n;i++){
for(j=;j<=m;j++){
if(i==&&(m/-)>){
printf("(");
continue;
}
if(i==n&&(m/-)>){
printf(")");
continue;
}
if(j==){
printf("(");
continue;
}
if(j==m){
printf(")");
continue;
}
if((i+j)&){
printf(")");
}
else{
printf("(");
}
}
printf("\n");
}
}
else{
for(i=;i<=n;i++){
for(j=;j<=m;j++){
if(j==&&(n/-)>){
printf("(");
continue;
}
if(j==m&&(n/-)>){
printf(")");
continue;
}
if(i==){
printf("(");
continue;
}
if(i==n){
printf(")");
continue;
}
if((i+j)&){
printf(")");
}
else{
printf("(");
}
}
printf("\n");
}
}
}
}
return ;
}
最新文章
- linux拷贝命令,移动命令
- 我所了解的chrome
- SharePoint 2013 配置基于表单的身份认证
- 使用VNC远程连接Windows Azure Linux虚拟机
- 1.配置EditPuls-编译和运行java程序
- 翻译:如何编译 Gunz 源代码
- jQuery操作select option
- 底部菜单栏(三)Fragment+FragmentTabHost实现仿新浪微博底部菜单栏
- QR代码简单
- 【Spring】web开发 javaConfig方式 图解
- mvc-dispatchar-servlet.xml文件报错
- layerX参数构建
- gradle上传本地文件到远程maven库(nexus服务器)
- bootstrap-实现loading效果
- UdPloyer交付系统设计思路
- Java日志框架(Commons-logging,SLF4j,Log4j,Logback)
- Android自带的TTS功能
- 【剑指Offer学习】【面试题23:从上往下打印二叉树】
- poj2117 Electricity
- Subnetting
热门文章
- C#中的new和override(转)
- A good example is a User-Agent switcher which changes User-Agent on every request:
- Java for LeetCode 097 Interleaving String 【HARD】
- Linux安装ElasticSearch启动报错的解决方法
- C++ 结构体多元素sort排序调用时的写法
- 51nod 1610
- iOS审核策略重磅更新:Guideline 2.1批量拒审
- HDU 1166 敌兵布阵 (线段树单点修改和区间和查询)
- MySQL整体架构与内存结构
- bzoj 5093 图的价值 —— 第二类斯特林数+NTT