AtCoder Beginner Contest 245

本文主要是介绍AtCoder Beginner Contest 245，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

比赛链接

A - Good morning

输入输出。

B - Mex

用个数组\(a_i\)标记\(i\)是否出现过，然后遍历一遍就能知道答案。

C - Choose Elements

可以动态规划。

\(dp_{i, j}\)表示前\(i\)个元素，结尾元素为\(j\)的状态是否可达， 其中\(j = 0\)表示结尾是\(A_i\)，\(j = 1\)表示结尾为\(B_i\)。

\(dp_{0}\)显然都可达，然后\(dp_i\)可以很简单的从\(dp_{i-1}\)转移算出：枚举当前的结尾元素，枚举前一位的结尾元素，若二者差的绝对值小于\(K\)则可以转移。

看\(dp_{n}\)是否包含可达状态即可。

D - Polynomial division

多项式除法，就竖式除法模拟一下。

E - Wrapping Chocolate

贪心。

对于所有巧克力和盒子，按宽为第一关键字降序排序。

枚举巧克力，把所有宽度大于它的盒子加入候选。

现在候选中每一个盒子的宽度都比当前巧克力大，只需要长度再比他大即可。

然后由于候选中的宽度都是满足条件的，现在长度更珍贵，所以就贪心地选候选中长度条件满足且最小的那个。

F - Endless Walk

拓扑排序。

拓扑排序中环不会被遍历到，而环能走到的点会由于环这个前置条件没有满足而不会被遍历到，而其余点的前置条件都回逐渐被满足然后遍历到。

但是题目要的是能走到环的点，所以就在反图上搞，在反图上搞就是能走到环的点了。

存图的反图，然后拓扑排序，没有入过队的点均为答案。

G - Foreign Friends

最短路。

首先，设置一个虚拟源点，往所有popular连边长为0的边，这样点到虚拟源点的最短路就是到popular的最短距离。

然后，还要求说国籍要不同，所以再入队时可以标记一下路径的类型为国籍，并且传递下去，这样就可以知道枚举到的路径最终是到哪一个国籍的popular了。

但是这样复杂度还是会比较高，不过因为只要求国籍不同，所以维护最短和次短两个不同类型的最短路就可以了。

然后如果最短路的类型是不同国籍的，就直接用最短；不然就切换到次短。

Ex - Product Modulo 2

不会数数，给题解都看不懂。

这篇关于AtCoder Beginner Contest 245的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！