「CF1214X」Codeforces Round #583

2019年9月13日550

A. Optimal Currency Exchange

只有 1 美元和 5 欧元是有用的,直接枚举美元数即可通过

B. Badges

枚举一下蓝色校徽的个数,并得出红色校徽的个数,这时判断一下有没有超过男女生人数

C. Bad Sequence

我把这一题想复杂了。合法的括号序列判断方法是,把左括号看作 +1,右括号看作 -1,只要前缀和都大等于 0 就可以。

当不合法的括号序列使得前缀和为 -1 时,只要把这个右括号扔到最后去就行。

D. Treasure Island

题意看起来很像一个网络流问题,分析性质后发现:

首先答案是 1 或 2,因为可以把起点直接堵上。斜着看成一个分层图,如果某一层只有一个结点和起点终点连通,答案就是 1,否则答案是 2。

这个判断只要从起点和终点各做一次 dp 就可以。

比赛的时候偷懒用 map,TLE#101

E. Petya and Construction Set

这个构造很有趣。

考虑按深度从大到小排序依次满足每对结点,先把每对结点的前一个排成一条链,按照距离计算一下另一个结点在哪就行。

avatar
  Subscribe  
提醒