题目链接：http://codeforces.com/problemset/problem/495/C
题目意思：给出一串只有三种字符（ ')'，'(' 和 '#'）组成的字符串，每个位置的这个字符 '#'可以替换成不少于 1 个的 ')'，问如何对每个'#'进行替换，使得对于字符串的任意一个位置， ')' 的数量始终不大于'(' 的数量。注意，'#'被替换成')'的总数以及原先有的')'的数量之和 == '(' 的总数。
花了两个晚上的一点时间，今天在图书馆里终于想到解决方案了，大感动 ~~~~ >__<
/********************************************* （错误思路请忽略= =）
第一个晚上做的时候，只知道最好的填法就是，除了最后一个'#'之外，其他都替换为一个 ')'，最后一个就根据公式： 数量 '(' - 数量 ')' - （总的'#'数 - 1） 来填入。
但是问题是，如何确定有解。我当时很天真地以为，如果 '(' == ')' 但是'#'还有剩（'#' > 0）就无解，test7：#)))) 证明此想法是错的，本来答案是-1，我程序输出 -4，因为这个判断是有缺陷的，排除不了这种情况。后来干脆直接保存每个位置的'(' (cnt[]) 和 ')'(cnt1[])的数量还有 '#'的数量，如果是'('，cnt[i] = cnt[i-1]+1，cnt1[i] = cnt[i-1]；如果是')'，cnt1[i] = cnt1[i-1]+1，cnt[i] = cnt[i-1]；如果是'#'，cnt[i] = cnt[i-1]，cnt1[i] = cnt1[i-1]。'(', ')', '#'总数量分别对应c1, c2, c0，然后加多一个check()函数来判断如果cnt[i] < cnt1[i] 就 返回false，我只能说：有点不知所谓 = =....因为压根就没有考虑'#' 的值！不知道'#'具体填什么【test12 ##((((((() 】。改改改接着就是test14........噩梦啊～～～～煎熬啊
**********************************************/
早上重新想过，终于有头绪了。我的做法应该叫做所谓的反证法吧～～～～容易知道最保守最可行的方法就是：除了最后一个'#'之外的所有 '#' 都替换为 一个')'。
设两个整型数tot 和c（初始值都为 0, c 用来保存'#'的数量），一个数组vis[]，保存每个'#'的位置的替换个数，遍历一遍数组s[i]
if 【'('】 tot++
if 【')'】 tot--
if 【'#'】 c++, vis[i] = 1
然后反向遍历数组s[i]，找出最后一个'#'的位置，使得vis[i] = tot - (c-1)。但是前期要做一个判断工作，tot-(c-1) <= 0是无解的！，它专门处理 '(' == ')'，c >= 1 的情况（类似(#)，或者 #）。
最后当然就是判断无解情况啦。开一个整数 cnt = 0，从前往后遍历数组s[]，
if 【'('】 cnt++
if 【')'】 cnt--
if 【'#'】 cnt -= vis[i]
需要检查每个位置的cnt的值，if (cnt < 0) 就返回false。即表示 ) > ( ，不满足题目要求。
最后返回true的情况是 cnt == 0，这样才能保证 '#' 替换为 ')' 以及本来存在的 ')' 的数量之和 等于 ‘(' 的数量
如果经得起 check() 函数的考验，那么就输出解。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std; const int maxn = 1e5 + ;
char s[maxn];
int vis[maxn], len; bool check(char s[])
{
int cnt = ;
for (int i = ; i < len; i++)
{
if (s[i] == '(')
cnt++;
else if (s[i] == ')')
cnt--;
else // #
cnt -= vis[i];
if (cnt < ) // 任意位置都要保证 ')' <= '('
return false;
}
if (cnt == )
return true;
return false;
} int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif // ONLINE_JUDGE while (scanf("%s", s) != EOF)
{
memset(vis, , sizeof(vis)); len = strlen(s);
int tot = , c = ;
for (int i = ; i < len; i++)
{
if (s[i] == '(')
tot++;
else if (s[i] == ')')
tot--;
else // #
{
c++;
vis[i] = ;
}
}
if (tot-(c-) <= )
printf("-1\n");
else
{
int last = tot - (c-); // 最后一个 # 的赋值，至少要为1
for (int i = len-; i >= ; i--)
{
if (s[i] == '#')
{
vis[i] = last;
break;
}
}
if (!check(s))
printf("-1\n");
else
{
for (int i = ; i <= c-; i++)
printf("1\n");
printf("%d\n", last);
}
}
}
return ;
}