传送门:炫酷路途
题目描述
小希现在要从寝室赶到机房,路途可以按距离分为N段,第i个和i+1个是直接相连的,只需要一秒钟就可以相互到达。
炫酷的是,从第i个到第
个也是直接相连的(其中p为任意非负整数),只需要一秒钟就可以相互到达。
更炫酷的是,有K个传送法阵使得某些u,v之间也是直接相连的,只需要一秒钟就可以相互到达,当然,由于设备故障,可能会有一些u=v的情况发生。
现在小希为了赶路,她需要在最短的时间里从寝室(编号为1)到达机房(编号为N),她不希望到达这N个部分以外的地方(不能到达位置N+1),也不能走到比自己当前位置编号小的地方(比如从5走到3是非法的)。
她想知道最短的时间是多少。
输入描述:
第一行输入两个整数N,K,表示路途的段数和传送法阵的数量。
从第二行开始K行,每行两个整数
,
表示两个位置之间相连。
输出描述:
输出一个整数,表示从寝室到机房最短的时间是多少秒。
示例2
输出
1
这个题让我明白了二进制还可以这么用......之前二进制接触的太少了。
1e9的范围,也就2的30多次方,如果不用传送阵,也就是说走30多步即可到达。
那具体的怎么求呢?
把两个点的距离转换成二进制,二进制中有几个1就需要走几步,因为可以一下走2的次方的距离,所以二进制有几个1就说明要走多少步。可以用树状数组lowbit(x)来求,就是x & -x,求的是x中最低位的1,例如:6(110),lowbit(6)=2=2^1
如果用传送阵,K<=15,最多的情况也就是2^15种情况,可以枚举出来,从0到2^15依次是不用传送阵,用第一个,用第二个,用第一个和第二个......
#include <iostream> #include <cmath> #include <algorithm> using namespace std; const int N = 1e9 + 10; int n, k; int lowbit(int x) { return x & -x; } struct node { int u; int v; }p[20]; int step(int x) { int ans = 0; while (x) { x -= lowbit(x); ans++; } return ans; } bool cmp(node x, node y) { return x.u < y.u; } int main() { while (cin>>n>>k) { for (int i = 0; i < k; i++) cin >> p[i].u >> p[i].v; sort(p, p + k, cmp); int ans = step(n - 1); for (int i = 0; i < 1 << k; i++) { //这里就是那最多2^15次的情况, int t = 1, sum = 0; for (int j = 0; j < k; j++) { //这里是枚举每个传送阵 if (i&j << k) { if (t > p[j].u) continue; sum += step(p[j].u - t) + 1; t = p[j].v; } } if (t > n) continue; sum += step(n - t); ans = min(ans, sum); } cout << ans << endl; } }