用户工具

站点工具


2020-2021:teams:manespace:atcoder_beginner_contest_176

Atcoder beginner contest 175

A - Rainy Season

题意:语法题

题解:略

B Making Triangle

题意:给一些数,问从这些数当中选取$3$个数能够组成三角形的种数有多少?

题解:排序之后三层循环就完事了

C Walking Takahashi

题意:给三个数据,第一个数据$x$表示数轴上的一个点,第二个数据$k$表示能够移动的最大步数,第三个数据$d$表示每次能移动的距离。 问在$k$步之后,能够达到的离原点最近的点

题解:首先可以发现,一开始一定是向原点的方向靠近,有可能在k步之后,该点也不会到达原点的另一个方向,则最终能到达的点就是终点,否则,若能够到达另一个方向,继续向原来的方向的走一定不会更优,所以可以来回跳,最终停下的点的绝对值便是最终的答案。

D - Moving Piece

题意:给了一串数$p$和一串数$c$,可以最多经行k次操作,每次如果当前在位置i,则答案加上$c_{p_i}$,将下一个初始位置移动到$p_i$ 重复上述操作,最多可以经行k次操作,问最大能得到多少?

题解:老套路题了,一看就是找环,由于数字是循环出现的,所以只要计算一个周期的情况,枚举每一个$dfs$出来得环,对每个环先看一周期下来获得的总和是否大于0,若大于0,则可以重复移动到最后,否则只能在一个周期内移动,否则必定不会是最优的。之后枚举取最大值即可。

E Picking Goods

题意:有一个$n*m$的矩阵,一共有$k$个物品,放在$k$个不同的位置,每个物品都有一个权值。一个人从$(1,1)$点出发,只能向右或者向下走,走到终点$(n,m)$,过程中可以收集沿路的物品,问最终能收集到物品权值最大的方案是什么。

题解:整体思想是$dp$,设数组$dp[i][j][k]$表示走到$(i,j)$点在该行已经收集到$k$种物品的答案,每次可以从上一行转移,就是从$dp[i-1][j][k](k=0,1,2,3)$取最大,或者从左边的转移,即考虑$dp[i][j-1][k]$之后采用一般的背包$dp$的思想转移即可。

2020-2021/teams/manespace/atcoder_beginner_contest_176.txt · 最后更改: 2020/08/29 20:05 由 iuiou