AtCoder Beginner Contest 175

Posted on | In , |

官方题解链接： AtCoder Beginner Contest 175 Editorial

A - Rainy Season

ABC 175 A

求一个字符串中最长连续字符 'R' 的长度， $|S| = 3$ 。

Solution

暴力扫描。

B - Making Triangle

ABC 175 B

给定 $n$ 个数的数组 $L$ , 求三元组 $(i,j,k)$ 的个数 $(1\le i<j<k\le n)$ ，满足：

  • $L_i,L_j,L_k$ 各不相同
  • $L_i,L_j,L_k$ 可构成三角形

满足 $n\le 100$ ，$L_i \le 10^9$

Solution

$\mathcal O(n^3)$ 暴力扫描统计。

C - Walking Takahashi

ABC 175 C

一个人在整数轴坐标 $x$ 处，进行 $k$ 次移动。

每次可以向左或向右移动 $d$ 个单位，求最后坐标 绝对值最小值 。

满足 $-10^{15}\le x\le 10^{15}$ ， $1\le k,d\le 10^{15}$

Solution

如果回不到零点附近就朝着零点方向一直走。

如果回到零点附近就在零点两侧来回走。

1
2
3
ll cnt = (x + d - 1) / d;
if (cnt > k) printf("%lld\n", x - k * d);
else printf("%lld\n", abs(x - cnt * d + ((k - cnt) & 1) * d));

D - Moving Piece

ABC 175 D

（留坑）

Solution

1
2


E - Picking Goods

ABC 175 E

在一个 $r$ 行 $c$ 列的矩阵上，有 $k$ 个 坐标互不相同 的宝物，在 $(r_i,c_i)$ 上的宝物价值 $v_i$。

开始在 $(1,1)$ 处，可以向右或向下走，即从 $(i,j)$ 移动到 $(i+1,j)$ 或 $(i,j+1)$ 。

到某个位置 可以不取 对应位置的宝物，每行最多取三个，问最后总价值最多多少。

满足 $1\le r,c\le 3000$ ， $1\le v_i\le 10^9$

Solution

$f[i][j][0/1/2/3]$ 代表当前位置 $(i,j)$ ，当前行已经拿了 $0/1/2/3$ 个东西，$\mathcal O(n^2)$ DP。

（F 留坑）