Sgu/179 2015年2月17日 (二) 11:19云璟月（讨论 | 贡献）的版本 (差异) ←上一版本 | 最后版本 (差异) | 下一版本→ (差异)

摘要

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

（AC 1476）

题意

生成一个的矩阵，使得矩阵中相邻的两个数之间二进制差不超过一位。

题解

首先观察最普通的情况：

( ( ( ) ) ) 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; }