CCF GESP 2024年12月认证 C++ 6级
题目描述
小杨有一棵包含无穷节点的二叉树（即每个节点都有左儿子节点和右儿子节点；除根节点外，每个节点都有父节点），其中根节点的编号为 $1$，对于节点 $i$，其左儿子的编号为 $2\times i$，右儿子的编号为 $2\times i + 1$。
小杨会从节点 $s$ 开始在二叉树上移动，每次移动为以下三种移动方式的任意一种：
- 第 1 种移动方式：如果当前节点存在父亲节点，向上移动到当前节点的父节点，否则不移动；
- 第 2 种移动方式：移动到当前节点的左儿子；
- 第 3 种移动方式：移动到当前节点的右儿子。
小杨想知道移动 $n$ 次后自己所处的节点编号。数据保证最后所处的节点编号不超过 $10^{12}$。
输入格式
第一行包含两个正整数 $n$ 和 $s$，代表移动次数和初始节点编号。
第二行包含一个长度为 $n$ 且仅包含大写字母 $\tt{U}$、$\tt{L}$ 和 $\tt{R}$ 的字符串，代表每次移动的方式，其中 $\tt{U}$ 代表第 1 种移动方式，$\tt{L}$ 代表第 2 种移动方式，$\tt{R}$ 代表第 3 种移动方式。
输出格式
输出一个正整数，代表最后所处的节点编号。
样例说明
样例 1
3 2
URR7小杨的移动路线为 $2 \to 1 \to 3 \to 7$。
数据范围
对于全部数据，保证有 $1\leq n\leq 10^6$，$1\leq s\leq 10^{12}$。
题目描述
小杨管理着 $m$ 辆货车，每辆货车每天需要向 A 市和 B 市运送若干次物资。小杨同时拥有 $n$ 个运输站点，这些站点位于 A 市和 B 市之间。
每次运送物资时，货车从初始运输站点出发，前往 A 市或 B 市，之后返回初始运输站点。A 市、B 市和运输站点的位置可以视作数轴上的三个点，其中 A 市的坐标为 $0$，B 市的坐标为 $x$，运输站点的坐标为 $p$ 且有 $0 \lt p \lt x$。货车每次去 A 市运送物资的总行驶路程为 $2p$，去 B 市运送物资的总行驶路程为 $2(x - p)$。
对于第 $i$ 个运输站点，其位置为 $p_i$ 且至多作为 $c_i$ 辆车的初始运输站点。小杨想知道，在最优分配每辆货车的初始运输站点的情况下，所有货车每天的最短总行驶路程是多少。
输入格式
第一行包含三个正整数 $n,m,x$，代表运输站点数量、货车数量和两市距离。
之后 $n$ 行，每行包含两个正整数 $p_i$ 和 $c_i$，代表第 $i$ 个运输站点的位置和最多容纳车辆数。
之后 $m$ 行，每行包含两个正整数 $a_i$ 和 $b_i$，代表第 $i$ 辆货车每天需要向 A 市运送 $a_i$ 次物资，向 B 市运送 $b_i$ 次物资。
输出格式
输出一个正整数，代表所有货车每天的最短总行驶路程。
样例说明
样例 1
3 4 10
1 1
2 1
8 3
5 3
7 2
9 0
1 1000040186第 $1$ 辆车的初始运输站点为站点 $3$，第 $2$ 辆车的初始运输站点为站点 $2$。第 $3$ 辆车的初始运输站点为站点 $1$，第 $4$ 辆车的初始运输站点为站点 $3$。此时总驶路程最短，为 $40186$。
数据范围
对于全部数据，保证有 $1\leq n,m\leq 10^5$，$2\leq x\leq 10^8$，$0\lt p_i\lt x$，$1\leq c_i\leq 10^5$，$0\leq a_i,b_i\leq 10^5$。数据保证 $\sum c_i\geq m$。