【二进制】炫酷路途

传送门:炫酷路途

题目描述

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

炫酷的是,从第i个到第

i+2p

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

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

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

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

输入描述:

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

从第二行开始K行,每行两个整数
ai

 

,
bi

 

表示两个位置之间相连。

2N1,000,000,000

 




0K15

 

输出描述:

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

输入

复制

12 2
1 5
6 6

输出

复制

3
示例2

输入

复制

17 2
2 5
8 9

输出

复制

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

发表评论

电子邮件地址不会被公开。