海创网站建设,wordpress外观,北京网站开发培训,泰安北京网站建设公司哪家好题干#xff1a;
小希现在要从寝室赶到机房#xff0c;路途可以按距离分为N段#xff0c;第i个和i1个是直接相连的#xff0c;只需要一秒钟就可以相互到达。 炫酷的是#xff0c;从第i个到第i2pi2p个也是直接相连的#xff08;其中p为任意非负整数#xff09;#x…题干
小希现在要从寝室赶到机房路途可以按距离分为N段第i个和i1个是直接相连的只需要一秒钟就可以相互到达。 炫酷的是从第i个到第i2pi2p个也是直接相连的其中p为任意非负整数只需要一秒钟就可以相互到达。 更炫酷的是有K个传送法阵使得某些u,v之间也是直接相连的只需要一秒钟就可以相互到达当然由于设备故障可能会有一些uv的情况发生。 现在小希为了赶路她需要在最短的时间里从寝室(编号为1)到达机房(编号为N)她不希望到达这N个部分以外的地方不能到达位置N1也不能走到比自己当前位置编号小的地方比如从5走到3是非法的。 她想知道最短的时间是多少。
输入描述:
第一行输入两个整数N,K表示路途的段数和传送法阵的数量。从第二行开始K行每行两个整数aiai,bibi表示两个位置之间相连。
2≤N≤1,000,000,0002≤N≤1,000,000,0000≤K≤150≤K≤15
输出描述:
输出一个整数表示从寝室到机房最短的时间是多少秒。
示例1
输入
复制
12 2
1 5
6 6
输出
复制
3
示例2
输入
复制
17 2
2 5
8 9
输出
复制
1 解题报告 两种方法差不多快因为数据比较小最多也就30步左右、、所以怎么写都行
AC代码1
#includecstdio
#includeiostream
#includealgorithm
#includequeue
#includemap
#includevector
#includeset
#includestring
#includecmath
#includecstring
#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 1e97;
ll qpow(ll a, ll k) {ll res 1;while(k) {if(k1) res (a*res)%mod;k1;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; i0 cur ! tar; i--) {if(cur db[i] tar) res,cur db[i];}return res;
}
int main()
{db[0] 1;//printf(%d,11);for(ll i 1; i40; i) db[i] db[i-1]*2;ll n,k;cinnk;for(int i 0; ik; 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,nodek,cmp);ll up qpow(2,k),ans 0x3f3f3f3f;for(ll bit 0; bitup; bit) {int tot 0;for(int i 0; ik; i) {if( ( (1i) 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(qi1,qitot1,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( ( (1i) bit ) ! 0)这一句 刚开始写的是1 这样就错了因为你运算时非零不代表是1、、之前也在这错过、、这次一定要记住了就写if((1i) bit ) 多好、、
不过人家写的好短、、、应该是我多考虑了很多情况、然而这个代码忘了读入的时候判断u和v的大小
#includebits/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, nodek);int ans step(n-1);for(int i 0; i 1k; i) {int x 1, tmp 0;for(int j 0; j k; j) {if(i 1j) {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建图最短路
#includecstdio
#includeiostream
#includealgorithm
#includequeue
#includemap
#includevector
#includeset
#includestring
#includecmath
#includecstring
#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;cinnk;for(int i 1; ik; 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(a1,atot1);int x unique(a1,atot1) - a - 1;memset(dis,INF,sizeof dis); //求出1到另外一点的最短路 dis[1] 0;for(int i 1; ix; i) {for(int j i1; jx; j) {for(int q 1; qk; 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代码3dfs这题也很快
#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 r0;while(x){if(x%21) r;xx/2;}return r;
}
int dfs(int pos,int L,int R){if(posk1) return go(R-L);int llpath[pos].s,rrpath[pos].e;int s1dfs(pos1,L,R),s2 INF;if(llLrrR){s2dfs(pos1,L,ll)dfs(pos1,rr,R)1;}return min(s1,s2);
}
int main()
{scanf(%d%d,n,k);for(int i1;ik;i){scanf(%d%d,path[i].s,path[i].e);if(path[i].s path[i].e) swap(path[i].s,path[i].e);}coutdfs(1,1,n);return 0;
}
