AtCoder Beginner Contest 190

## C - Bowls and Dishes

We have dishes numbered and conditions numbered .

Condition is satisfied when both Dish and Dish have (one or more) balls on them.

There are people numbered . Person will put a ball on Dish or Dish .
At most how many conditions will be satisfied?

Constraints

• All values in input are integers.

Sample Input 1

Sample Output 1

## D - Staircase Sequences

How many arithmetic progressions consisting of integers with a common difference of have a sum of ?

Constraints

• is an integer.

Sample Input 1

Sample Output 1

We have four such progressions:

## E - Magical Ornament

There are kinds of magical gems, numbered , distributed in the AtCoder Kingdom.

Takahashi is trying to make an ornament by arranging gems in a row.

For some pairs of gems, we can put the two gems next to each other; for other pairs, we cannot. We have pairs for which the two gems can be adjacent: (Gem , Gem ), (Gem , Gem ), , (Gem , Gem ). For the other pairs, the two gems cannot be adjacent. (Order does not matter in these pairs.)

Determine whether it is possible to form a sequence of gems that has one or more gems of each of the kinds . If the answer is yes, find the minimum number of stones needed to form such a sequence.

Constraints

• All values in input are integers.
• If.

Sample Input 1

Sample Output 1

### 解法一

bfs+状态压缩，因为很小，所以我们可以将给定的输入转换成一个双向图，然后将关键点之间的最短路径求出来，这里直接 BFS 就行了，时间复杂度，得到一个，表示第-th 关键点和第-th 个关键点的最短路径

• 入口：，只选取一个关键宝石，序列长度为 1
• 转移：，枚举所有的选取状态，枚举所有以关键宝石作为结尾的状态，递推求最小值
• 出口：，选取到所有的关键石头，并且以某个关键石头结尾的最小值

## F - Shift and Inversions

Given is a sequence that is a permutation of .

For each , find the inversion number of the sequence defined as .

Constraints

• All values in input are integers.
• is a permutation of .

Sample Input 1

Sample Output 1

We have .

• For , the inversion number of is .
• For , the inversion number of is .
• For , the inversion number of is .
• For , the inversion number of is .

### 解法二

• 本文标题：AtCoder Beginner Contest 190
• 本文作者：Resolmi
• 创建时间：2021-02-04 00:00:00
• 本文链接：https://imlgw.top/2021/02/04/891c3448/
• 版权声明：本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！
评论