题干：
小希现在要从寝室赶到机房，路途可以按距离分为N段，第i个和i+1个是直接相连的，只需要一秒钟就可以相互到达。
炫酷的是，从第i个到第i+2pi+2p个也是直接相连的（其中p为任意非负整数），只需要一秒钟就可以相互到达。
更炫酷的是，有K个传送法阵使得某些u,v之间也是直接相连的，只需要一秒钟就可以相互到达，当然，由于设备故障，可能会有一些u=v的情况发生。
现在小希为了赶路，她需要在最短的时间里从寝室(编号为1)到达机房(编号为N)，她不希望到达这N个部分以外的地方（不能到达位置N+1），也不能走到比自己当前位置编号小的地方（比如从5走到3是非法的）。
她想知道最短的时间是多少。
输入描述:
第一行输入两个整数N,K，表示路途的段数和传送法阵的数量。
从第二行开始K行，每行两个整数aiai,bibi表示两个位置之间相连。
2≤N≤1,000,000,0002≤N≤1,000,000,000
0≤K≤150≤K≤15 输出描述:
输出一个整数，表示从寝室到机房最短的时间是多少秒。 示例1
输入
12 2
1 5
6 6 输出
3 示例2
输入
17 2
2 5
8 9 输出
1
解题报告：
两种方法差不多快，，因为数据比较小，，最多也就30步左右、、所以怎么写都行
AC代码1：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define ll long long
#define pb push_back
#define pm make_pair
#define fi first
#define se second
using namespace std;
const int MAX = 2e5 + 5;
struct Node {
ll u,v;
} node[55],use[55];
ll db[55],qi[55];
const ll mod = 1e9+7;
ll qpow(ll a, ll k) {
ll res = 1;
while(k) {
if(k&1) res = (a*res)%mod;
k>>=1;
a = (a*a)%mod;
}
return res;
}
bool cmp(Node a,Node b) {
if(a.u != b.u) return a.u < b.u;
else return a.v < b.v;
}
ll go(ll cur,ll tar) {
ll res = 0;
tar = tar - cur;
cur = 0;
for(int i = 33; i>=0 && cur != tar; i--) {
if(cur + db[i] <= tar) res++,cur += db[i];
}
return res;
}
int main()
{
db[0] = 1;
//printf("%d",1<<1);
for(ll i = 1; i<=40; i++) db[i] = db[i-1]*2;
ll n,k;
cin>>n>>k;
for(int i = 0; i<k; i++) {
scanf("%lld %lld",&node[i].u,&node[i].v);
if(node[i].u == node[i].v || node[i].u > n || node[i].v > n) {k--,i--;continue;}
if(node[i].u > node[i].v) swap(node[i].u,node[i].v);
}
sort(node,node+k,cmp);
ll up = qpow(2,k),ans = 0x3f3f3f3f;
for(ll bit = 0; bit<up; bit++) {
int tot = 0;
for(int i = 0; i<k; i++) {
if( ( (1<<i) & bit ) != 0) use[++tot] = node[i],qi[tot] = node[i].u;
}
ll now = 1,step = 0;
while(now <= n) {
if(now == n) break;
if(now > qi[tot]) {
step += go(now,n);break;
}
int pos = lower_bound(qi+1,qi+tot+1,now) - qi;
if(qi[pos] == now) step++,now = use[pos].v;
else step += go(now,qi[pos]),now = qi[pos];
}
ans = min(step,ans);
}
printf("%lld\n",ans);
return 0 ;
}
/*
14 2
1 14
1 13
2
*/ 注意这种方式第一次被坑了，，if( ( (1<<i) & bit ) != 0)这一句 刚开始写的是==1 这样就错了，，因为你&运算时，非零不代表是1、、之前也在这错过、、这次一定要记住了，就写if((1<<i) & bit ) 多好、、
不过人家写的好短、、、应该是我多考虑了很多情况、（然而这个代码忘了读入的时候判断u和v的大小）
#include<bits/stdc++.h>
using namespace std;
struct Node {
int u, v;
bool operator < (const Node& node) const {
return u <= node.u;
}
} node[20];
int step(int d) {
int ans = 0;
while(d) {
d -= d & -d;
ans++;
}
return ans;
}
int main() {
int n, k; scanf("%d%d", &n, &k);
for(int i = 0; i < k; i++) scanf("%d%d", &node[i].u, &node[i].v);
sort(node, node+k);
int ans = step(n-1);
for(int i = 0; i < 1<<k; i++) {
int x = 1, tmp = 0;
for(int j = 0; j < k; j++) {
if(i & 1<<j) {
if(x > node[j].u) continue;
tmp += step(node[j].u-x) + 1;
x = node[j].v;
}
}
if(x > n) continue;
tmp += step(n-x);
ans = min(ans, tmp);
}
printf("%d\n", ans);
return 0;
}
AC代码2：（建图最短路）
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define ll long long
#define pb push_back
#define pm make_pair
#define fi first
#define se second
using namespace std;
const int MAX = 2e5 + 5;
const int INF = 0x3f3f3f3f;
int a[MAX];
int dis[MAX];
int tot;
struct Node {
ll u,v;
} node[MAX];
int main()
{
int n,k;
int tmp1,tmp2;
cin>>n>>k;
for(int i =1; i<=k; i++) {
scanf("%d %d",&tmp1,&tmp2);
if(tmp1 == tmp2 || tmp1 > n || tmp2 > n) {k--,i--;continue;}
node[i].u = tmp1,node[i].v = tmp2;
if(node[i].u > node[i].v) swap(node[i].u,node[i].v);
a[++tot] = tmp1,a[++tot] = tmp2;
}
a[++tot] = 1;
a[++tot] = n;
sort(a+1,a+tot+1);
int x = unique(a+1,a+tot+1) - a - 1;
memset(dis,INF,sizeof dis);
//求出1到另外一点的最短路
dis[1] = 0;
for(int i = 1; i<=x; i++) {
for(int j = i+1; j<=x; j++) {
for(int q = 1; q<=k; q++) {
if(a[i] == node[q].u && a[j] == node[q].v)
dis[j] = min(dis[i]+1,dis[j]);
}
dis[j] = min(dis[i] + __builtin_popcount(a[j] - a[i]),dis[j]);
}
}
printf("%d\n", dis[x]);
return 0 ;
}
AC代码3：（dfs这题也很快）
#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define mod 998244353
#define MAXN 1000005
const int INF = 0x3f3f3f3f;
int n,k;
struct no{
int s,e;
}path[16];
int go(int x){
int r=0;
while(x){
if(x%2==1) r++;
x=x/2;
}
return r;
}
int dfs(int pos,int L,int R){
if(pos==k+1) return go(R-L);
int ll=path[pos].s,rr=path[pos].e;
int s1=dfs(pos+1,L,R),s2 = INF;
if(ll>=L&&rr<=R){
s2=dfs(pos+1,L,ll)+dfs(pos+1,rr,R)+1;
}
return min(s1,s2);
}
int main()
{
scanf("%d%d",&n,&k);
for(int i=1;i<=k;i++){
scanf("%d%d",&path[i].s,&path[i].e);
if(path[i].s > path[i].e) swap(path[i].s,path[i].e);
}
cout<<dfs(1,1,n);
return 0;
}
京公网安备 11010502036488号