比赛链接

A - Airplane

题目描述

有三个地方,编号为 $1,2,3$,给定两两之间的距离,且 $\text{dis}(i,j)=\text{dis}(j,i),\text{dis}(i,i)=0$

求一个 $1 \sim 3$ 的排列 $a,b,c$,最小化 $\text{dis}(a,b)+\text{dis}(b,c)$

数据范围:$1 \le \text{dis} \le 100$

题解

把最短边和次短边加起来输出即可

B - Balance

题目描述

给定 $w_1,w_2,\cdots,w_n$,求一个 $1 \le T < n$,最小化 $\left|\left(\sum_{i=1}^{T}w_i \right)-\left(\sum_{i=T+1}^{n}w_i\right)\right|$

数据范围:$2 \le n \le 100, 1 \le w_i \le 100$

题解

枚举 $T$,然后暴力计算 $LHS,RHS$ 即可

C - Typical Stairs

题目描述

有一个长度为 $n+1$ 的序列,一开始你在 $0$ 号位置,剩余位置编号依次为 $1,2,\cdots,n$

假设当前你在 $x$,下一步你可以走到 $x+1$ 或者 $x+2$

有一些位置是不能走的,它们为 $a_1,a_2,\cdots,a_m$

求从 $0$ 号位置走到 $n$ 号位置的方案数

数据范围:$1 \le n \le 10^5, 0 \le m \le n-1, 1 \le a_1 < a_2 < \cdots < a_m < n - 1$

题解

设 $f_n$ 表示走到 $n$ 的方案数,大概就有:

$$
f_n=\begin{cases}
0 & \quad (\exists1 \le i \le m:a_i=n) \\
f_{n-1}+f_{n-2} & \quad (\text{otherwise})
\end{cases}
$$

D - Lamp

题目描述

给定一个 $H \times W$ 的网格,有一些位置是有障碍的,你需要在其中放一个灯塔,它会直线照亮上下左右的所有格子,直到遇到障碍

最大化照亮的格子个数

数据范围:$1 \le H, W \le 2000$

题解

预处理一下 $up,down,left,right$ 数组后枚举放哪就行了

E - Sum Equals Xor

题目描述

给定 $L$,求有多少个有序非负整数对 $(a,b)$,满足 $a+b \le L$ 且 $a+b=a \text{ xor } b$

数据范围:$1 \le L < 2^{100001}$

题解

显然 $a+b = a \text{ xor } b$ 等价于 $a \text{ and } b=0$,换句话说 $a,b$ 的二进制位上不存在两个同时为 $1$ 的位置

那么可以枚举 $a+b$,假设 $c=a+b$,且 $c$ 有 $x$ 个 $1$,则可行的 $(a,b)$ 有 $2^{x}$ 个

那么就类似于数位 $dp$ 那样,枚举 $c$ 和 $L$ 的 $lcp$,剩下的就是 $\sum_{i=0}^{y}2^i{y \choose i}=3^y$ 就行了

F - Takahashi’s Basics in Education and Learning

题目描述

给定 $L,A,B,M$,求 $A,A+B,A+2B,\cdots,A+(L-1)B$ 在十进制下依次拼接起来的数字模 $M$ 的值

数据范围:$1 \le L,A,B < 10^{18},2 \le M \le 10^9$

题解

考虑到 $A+kB$ 的十进制位数不会超过 $40$,那么就可以枚举位数,转移是一个线性的形式,矩阵乘法即可