查看Sgu/179的源代码 ←Sgu/179

[[分类:位运算]][[分类:字符串处理]]
==摘要==
{{信息题|Brackets light|http://acm.sgu.ru/problem.php?contest{{=}}0&problem{{=}}179|1|100|无解情况|32|time=2015-2-17 11:19:12}}
（AC 1476）

==题意==
生成一个<m>2^m*2^n</m>的矩阵，使得矩阵中相邻的两个数之间二进制差不超过一位。
==题解==
首先观察最普通的情况：
::( ( '''(''' ) ) ) 000111
::( '''(''' ''')''' ) ( ) 001101
::( ''')''' ( '''(''' ) ) 010011
::( ) ( ''')''' ( ) 010101
相当于一个二进制数从小变大，但是又要保持括号匹配。
我们参照二进制的+1，它是从后往前找到第一个0变成1，后面清零，例如：
::0010110'''0'''111
::0010110'''1'''000
同样的，我们也完成这两步即可。
#类似于"0变1"的过程，我们可以从右往左找到第一个'('变成')'，但是能这么做的前提是左边需要添加一个')'，否则就违反了括号匹配。因而需要保证左边'('多于')'，也就是找到第一个满足该要求的'('进行变化。<small>[为了处理方便，相当于它及其右边的'('少于')']</small>
#类似于"后面清零"的过程，我们只要保证变化了的这个'('后面字典序最小，那也就是'('尽量排在前面，')'尽量排在后面，形成"((())))))"这样的序列即可。
==代码==
{{折叠|179.cpp代码已折叠
|<pre>
#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;
}
</pre>
|sgu179}}