Daily Archives

3 Articles

信息学奥林匹克竞赛

Codeforces Round #551 (Div. 2) 解题报告 (CF1153)

Posted by kal0rona on

C – Serval and Parenthesis Sequence

这道题主要是运用贪心。首先我们可以确定以下几种情况是肯定无解的:

  • 第一个字符是 ‘)’,最后一个字符是 ‘(‘。
  • 字符串长度为奇数。

我们发现整个字符串\(s[1 \dots n]\)中,第一个和最后一个字符一定要是 ‘(‘ 和 ‘)’。所以我们只用关心\(s[2 \dots n-1]\)就好。统计需要补充的括号个数:也就是\((n-2)\)减去现已确定的括号个数,分\(remL\)为左括号需要补充的个数、\(remR\)为右括号需要补充的个数。