首页 > 代码库 > codeforces 495C. Treasure 解题报告
codeforces 495C. Treasure 解题报告
题目链接：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() 函数的考验，那么就输入解。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstdlib> 4 #include <cstring> 5 using namespace std; 6 7 const int maxn = 1e5 + 5; 8 char s[maxn]; 9 int vis[maxn], len;10 11 bool check(char s[])12 {13 int cnt = 0;14 for (int i = 0; i < len; i++)15 {16 if (s[i] == ‘(‘)17 cnt++;18 else if (s[i] == ‘)‘)19 cnt--;20 else // #21 cnt -= vis[i];22 if (cnt < 0) // 任意位置都要保证 ‘)‘ <= ‘(‘23 return false;24 }25 if (cnt == 0)26 return true;27 return false;28 }29 30 int main()31 {32 #ifndef ONLINE_JUDGE33 freopen("in.txt", "r", stdin);34 #endif // ONLINE_JUDGE35 36 while (scanf("%s", s) != EOF)37 {38 memset(vis, 0, sizeof(vis));39 40 len = strlen(s);41 int tot = 0, c = 0;42 for (int i = 0; i < len; i++)43 {44 if (s[i] == ‘(‘)45 tot++;46 else if (s[i] == ‘)‘)47 tot--;48 else // #49 {50 c++;51 vis[i] = 1;52 }53 }54 if (tot-(c-1) <= 0)55 printf("-1\n");56 else57 {58 int last = tot - (c-1); // 最后一个 # 的赋值，至少要为159 for (int i = len-1; i >= 0; i--)60 {61 if (s[i] == ‘#‘)62 {63 vis[i] = last;64 break;65 }66 }67 if (!check(s))68 printf("-1\n");69 else70 {71 for (int i = 1; i <= c-1; i++)72 printf("1\n");73 printf("%d\n", last);74 }75 }76 }77 return 0;78 }
codeforces 495C. Treasure 解题报告