【二进制】炫酷路途

2019年2月1日 0条评论 691次阅读 0人点赞于衡

传送门：炫酷路途

题目描述

小希现在要从寝室赶到机房，路途可以按距离分为N段，第i个和i+1个是直接相连的，只需要一秒钟就可以相互到达。

炫酷的是，从第i个到第 $i + 2^{p}$

i + 2^{p}

个也是直接相连的（其中p为任意非负整数），只需要一秒钟就可以相互到达。

更炫酷的是，有K个传送法阵使得某些u,v之间也是直接相连的，只需要一秒钟就可以相互到达，当然，由于设备故障，可能会有一些u=v的情况发生。

现在小希为了赶路，她需要在最短的时间里从寝室(编号为1)到达机房(编号为N)，她不希望到达这N个部分以外的地方（不能到达位置N+1），也不能走到比自己当前位置编号小的地方（比如从5走到3是非法的）。

她想知道最短的时间是多少。

输入描述:

第一行输入两个整数N,K，表示路途的段数和传送法阵的数量。

从第二行开始K行，每行两个整数 $a_{i}$

 $a_{i}$ , $b_{i}$

 $b_{i}$ 表示两个位置之间相连。
 $2 \leq N \leq 1, 000, 000, 000$

 $2 \leq N \leq 1, 000, 000, 000$ 

 $0 \leq K \leq 15$

输出描述:

输出一个整数，表示从寝室到机房最短的时间是多少秒。

示例1

输入

复制

12 2
1 5
6 6

输出

复制

示例2

输入

复制

17 2
2 5
8 9

输出

复制

这个题让我明白了二进制还可以这么用......之前二进制接触的太少了。

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;
  }
}