摘要

题目链接 难度等级 完成状态 完成分数 最后编辑时间 需要注意
Brackets light ★☆☆☆☆ 答案正确 100 2015-2-17 11:19:12 无解情况

(AC 1476)

题意

生成一个2^m*2^n的矩阵,使得矩阵中相邻的两个数之间二进制差不超过一位。

题解

首先观察最普通的情况:

( ( ( ) ) ) 000111
( ( ) ) ( ) 001101
( ) ( ( ) ) 010011
( ) ( ) ( ) 010101

相当于一个二进制数从小变大,但是又要保持括号匹配。 我们参照二进制的+1,它是从后往前找到第一个0变成1,后面清零,例如:

00101100111
00101101000

同样的,我们也完成这两步即可。

  1. 类似于"0变1"的过程,我们可以从右往左找到第一个'('变成')',但是能这么做的前提是左边需要添加一个')',否则就违反了括号匹配。因而需要保证左边'('多于')',也就是找到第一个满足该要求的'('进行变化。[为了处理方便,相当于它及其右边的'('少于')']
  2. 类似于"后面清零"的过程,我们只要保证变化了的这个'('后面字典序最小,那也就是'('尽量排在前面,')'尽量排在后面,形成"((())))))"这样的序列即可。

代码

179.cpp代码已折叠
展开折叠内容
#include<cstdio>
#include<string>
#include<iostream>
using namespace std;
int main()
{
    int m,n;
    string s;
    int a[2]={};
    cin>>s;
    for(int i=s.size()-1;i>=0;--i)
    {
        ++a[s[i]=='('];
        if(a[1]<a[0]&&s[i]=='(')
        {
            s[i]=')';
            for(int j=i+1;j!=s.size();++j)
                if(a[1])
                    --a[1],s[j]='(';
                else
                --a[0],s[j]=')';
            cout<<s;
            return 0;
        }
    }
    cout<<"No solution";//fixed:无解情况//
    return 0;
}

著作权声明[编辑]

关于[编辑]