[Fortuna OJ]Jul 6th – Group B 解题报告

A – 调整 Tweak

这道题我在考场上打了一个错解,还骗到了 30 分。

正常的思路是:在最短路图上找到几个边进行修改。然而,最优的解决方案并不一定出现在最短路图上的边上,也可以通过修改次优边进行解决。所以,这道题其实跟最短路没什么太大关系,即使后面会用到 Djisktra 来求最短路。

我们可以把一个\(G(V, E), |V| = n, |E| = m\)复制\(n\)份,然后对于第\(k\)份图中的有向边\((u_k, v_k, w_k)\),可以生成一个副本来连接下一层的目标点,也就是每一条边会派生出\((u_k, v_{k + 1}, 0)\),当最后求最短路时,经过这样的一条边可以被认为是修改一条边,且,这个边是单向向下的,所以不会出现同一层修改多次的情况。最后只需要求这张图的最短路,然后判定满足\(dist[n_k] \leq c\)的最小\(k\)就行了。

继续阅读[Fortuna OJ]Jul 6th – Group B 解题报告

[Fortuna OJ]Jul 5th – Group B 解题报告

A – 铁轨

sb 题,不讲。(为什么 B 组会有这么水的题?)

B – 独立集

这道题翻译过来就是独立集计数,也是一道 sb 题。

首先,这种计数题肯定都是基于树形 DP 的,所以我们来设状态。起初,我设的状态是:该节点所在的子树的独立集个数为 \(dp[u]\)。后面发现不太对劲:状态转移时,大体可以分为两种进行计数,一种是儿子子树内的乘积(包括空集在内,这样就可以算所有的并集个数),还有一种是孙子子树和本节点的独立集。所以,这些信息要分开储存:设\(dp[u][1]\)为独立集个数,\(dp[u][0]\)孙子节点的独立集个数。所以,可以得到下列方程:

继续阅读[Fortuna OJ]Jul 5th – Group B 解题报告

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

C – Serval and Parenthesis Sequence

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

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

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

继续阅读Codeforces Round #551 (Div. 2) 解题报告 (CF1153)