「usaco2002.4」Power Hungry Cows
题目描述
农夫约翰的奶牛可以很快地计算整数的次方，但是需要你的帮助。因为他们将要计算很大的数的次方（还是数的很大次方……我英语，悲剧），他们只能使用两个工作变量来处存临时结果。
第一个动作变量被赋值为底数（用X表示）；另一个赋值为1.牛们既能把两个变量相乘也能相除，并存储在任一工作变量中，但是所有结果都被存为整数（只能存为整数？我按这个做的AC）。
例如，他们想计算X^31，一种方法是这样的
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
变量1 变量2 开始： ｘ １ １＊１－＞２： x x ＾２ ２＊２－＞２： ｘ ｘ＾４ ２＊２－＞２： ｘ ｘ＾８ ２＊２－＞２： ｘ ｘ＾１６ ２＊２－＞２： ｘ ｘ＾３２ ２／１－＞２： ｘ ｘ＾３１ |
这样ｘ＾３１就被在六次计算中得出，给出需要计算的指数，找出计算它的最少步骤．
输入：
一行，整数P
输出:
一行，最少步骤
样例输入：
|
1 |
31 |
样例输出：
|
1 |
6 |
代码
内存限制30M。。。什么蛋疼
写了个bfs+hash超时了、、
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 |
#include<iostream> #include<cstdio> using namespace std; struct data1{ int v;bool a[20001]; data1(){v=-1;} }hash[500]; struct data2{ int x,y,step; }q[500001]; int n,t=0,w=1;bool ans; bool pd(int x,int y) { int t=x%499; while(1) { if(hash[t].v==x) { if(hash[t].a[y])return 0; else {hash[t].a[y]=1;return 1;} } else if(hash[t].v!=x) { if(hash[t].v==-1){hash[t].v=x;hash[t].a[y]=1;return 1;} else {t++;if(t==500)t=0;} } } } void inq(int x,int y) { if(ans)return; if(x>y)swap(x,y); if(pd(x,y)){ q[w].x=x;q[w].y=y; q[w].step=q[t].step+1; if(x==n||y==n){ans=1;printf("%d",q[w].step);} w++;} } void bfs() { q[0].x=0;q[0].y=1; while(t<w) { int x=q[t].x,y=q[t].y; inq(x,x+x);inq(x,x+y); inq(x,y+y);inq(x,y-x); inq(x+x,y);inq(x+y,y); inq(y+y,y);inq(y-x,y); t++; if(ans)return; } } int main() { scanf("%d",&n); bfs(); return 0; } |
看了下题解发现 if(ans||x>200||y>20000)return;//？？？这是为什么。。算了蒟蒻搞不懂就这么写上去了
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
#include<iostream> #include<cstdio> using namespace std; bool pd[201][20001]; struct data{ int x,y,step; }q[2000001]; int n,t=0,w=1;bool ans; void inq(int x,int y) { if(x>y)swap(x,y); if(ans||x>200||y>20000)return; if(!pd[x][y]){ pd[x][y]=1; q[w].x=x;q[w].y=y; q[w].step=q[t].step+1; if(x==n||y==n){ans=1;printf("%d",q[w].step);} w++;} } void bfs() { q[0].x=0;q[0].y=1; while(t<w) { int x=q[t].x,y=q[t].y; inq(x,x+x);inq(x,x+y); inq(x,y+y);inq(x,y-x); inq(x+x,y);inq(x+y,y); inq(y+y,y);inq(y-x,y); t++; if(ans)return; } } int main() { scanf("%d",&n); bfs(); return 0; } |
应该这题用意是打表吧
Subscribe
计数器 9301900
OI 课件=>
OI 课件=>