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$

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

给定 $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$ 即可

有一个长度为 $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}
$$

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

最大化照亮的格子个数

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

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

给定 $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$ 就行了

给定 $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$，那么就可以枚举位数，转移是一个线性的形式，矩阵乘法即可