夕阳之约图片,爱佳游,股市春节放假安排2015
今天总算开学了,当了班长就是麻烦,明明自己没买书却要带着一波人去领书,那能怎么办呢,只能说我善人心肠哈哈哈,不过我脑子里突然浮起一个念头,大二还要不要继续当这个班委呢,既然已经体验过就可以适当放下了吧,用心在自己的研究上。晚上级会开完也就八点多了,开始打打题,今天在hdu杭电的acm集训题看到一个奇葩的题,前来献上。
今日推荐:
《全球风暴》 一部宇宙航空和地球气候片的良心佳作,后期特效建模都是特别杠杠的大片,不会让你失望的哟,我已经三刷了哈哈哈。这部片在爱奇艺有上线,有兴趣的朋友可以看看鸭。
爱奇艺链接:https://www.iqiyi.com/v_19rr7pl8vg.html
------------------------------------------------题目----------------------------------------------------------
3 5 4 5 7 3
fill b pour b a empty a pour b a fill b pour b a success fill a pour a b fill a pour a b empty b pour a b success
------------------------------------------------题目----------------------------------------------------------
你有两个杯子,a、b;你只有三种操作,(1)清空任何一个杯子 (2)当被子是空的时候可以填满任何一个杯子 (3)将某一杯的水倒到另一杯中(不会溢出计算)直到b杯达到目标数aim c。
输入的a、b升数有要求,一定需要相邻互质。并且a小于b,且目标数aim c要小于b即可。
题目好像想象挺容易,手写也好像能解出来,但就是电脑老是犯傻逼。扔hdu的oj上老是显示超时,我看了一下时间限制也很足够啊:
time limit: 2000/1000 ms (java/others) memory limit: 65536/32768 k (java/others)
后来我发现坑在哪里了。
这道题我居然在一个小学课本的趣味题发现的,真的是,现在的小学益智题怕是很多都能改成编程题了,而且改了编程题之后你还不一定解的出来哈哈哈。
其实方法很简单,你们可以试一下下面这个步骤,是一定能得到结果的:
(1)装满a
(2)从a倒b
(3)如果b满了清空
基本以上三个步骤都能找打准确的结果。
这就是经典的“灌水定理”,这里提一下,在下面我会引出这个定理,理论上倒水的步骤是不唯一的,所以我就太在意样例。
然而在无数次交oj的时候疯狂的wa超时,我终于从样例发现了不对劲。在其他oj上是可以过的,但在hdu oj好像并没有被智能处理化:
如果目标数c小于a,必须从a开始倒满。如果目标数c大于a,则必须从b开始倒满。原因是为了寻求最短步骤操作,拿样例来说,3 5 4,如果先倒a,那么你需要八步,而如果先到b,那么你需要六步,所以这道题杭电oj是默认要求最短步骤了,题目并没有说,所以害我 一股脑热直接从a循环交,就错了。
首先:我先构造三个步骤出来:fill、pour、empty
void pour(bool x) { if(x) { if(cap_b + cap_a <= temp_b) { cap_b = cap_b + cap_a; cap_a = 0; } else { cap_a = cap_a - (temp_b - cap_b); cap_b = temp_b; } printf("pour a b\n"); } else { if(cap_b + cap_a <= temp_a) { cap_a = cap_b + cap_a; cap_b = 0; } else { cap_b = cap_b - (temp_a - cap_a); cap_a = temp_a; } printf("pour b a\n"); } } void fill(bool x) { if(x) { cap_a = temp_a; printf("fill a\n"); } else { cap_b = temp_b; printf("fill b\n"); } } void empty(bool x) { if(x) { cap_b = 0; printf("empty b\n"); } else { cap_a = 0; printf("empty a\n"); } }
其中x为真是以a为主,为假时是b为主操作。难点应该在于pour倾倒函数的书写,你需要区分从a倒到b时,是否b满了,如果满了就不能倒,a要留剩下,如果没满,就相当于把a清空了。这是要注意的地方。
第二步:特殊处理
if(aim == 0) { printf("success\n"); continue; } if(temp_b == aim) { printf("fill b\n"); printf("success\n"); continue; } if(temp_a == aim) { printf("fill a\n"); printf("pour a b\n"); printf("success\n"); continue; }
这个就是我超时的原因之一了,因为我没有考虑到 3 5 3 或者是 3 5 5这种情况,当目标数直接等于其中一个杯子量时的操作,就会让程序一直循环操作得不到结果超时了。各位要注意。
第三步:进行循环了
if(temp_a >= aim) { if(cap_a == 0) fill(true); pour(true); if(cap_b == temp_b) empty(true); } else { if(cap_b == 0) fill(false); pour(false); if(cap_a == temp_a && cap_b != aim) empty(false); }
这里就要提到我刚刚分析的时候说的最短步骤问题了,如果目标数c小于a,必须从a开始倒满。如果目标数c大于a,则必须从b开始倒满。就在这里体现,核心步骤其实很简单,就是刚刚的三步,填满、移动、清空已满。
第四步:得到结果退出永真循环
if(cap_a == aim) { if(cap_b != 0) printf("empty b\n"); printf("pour a b\n"); printf("success\n"); break; } if(cap_b == aim) { printf("success\n"); break; }
#include<bits/stdc++.h> using namespace std; int temp_a,temp_b,aim; int cap_a,cap_b; void pour(bool x) { if(x) { if(cap_b + cap_a <= temp_b) { cap_b = cap_b + cap_a; cap_a = 0; } else { cap_a = cap_a - (temp_b - cap_b); cap_b = temp_b; } printf("pour a b\n"); } else { if(cap_b + cap_a <= temp_a) { cap_a = cap_b + cap_a; cap_b = 0; } else { cap_b = cap_b - (temp_a - cap_a); cap_a = temp_a; } printf("pour b a\n"); } } void fill(bool x) { if(x) { cap_a = temp_a; printf("fill a\n"); } else { cap_b = temp_b; printf("fill b\n"); } } void empty(bool x) { if(x) { cap_b = 0; printf("empty b\n"); } else { cap_a = 0; printf("empty a\n"); } } int main() { while(~scanf("%d %d %d",&temp_a,&temp_b,&aim)) { if(aim == 0) { printf("success\n"); continue; } if(temp_b == aim) { printf("fill b\n"); printf("success\n"); continue; } if(temp_a == aim) { printf("fill a\n"); printf("pour a b\n"); printf("success\n"); continue; } cap_a = cap_b = 0;//记得每个样例要清空杯子 for(;;) { if(temp_a >= aim) { if(cap_a == 0) fill(true); pour(true); if(cap_b == temp_b) empty(true); } else { if(cap_b == 0) fill(false); pour(false); if(cap_a == temp_a && cap_b != aim) empty(false); } if(cap_a == aim) { if(cap_b != 0) printf("empty b\n"); printf("pour a b\n"); printf("success\n"); break; } if(cap_b == aim) { printf("success\n"); break; } } } return 0; }
这道题如果不要求最短路径的话,其实就是非常简单的题目了,只要循环那三个步骤肯定能出结果,而且代码量直接大大减少。不过这道题解法我是比较直接的一种解法,在解后去网上找找别的解法,那就是还有一种就是用bfs(宽度优先搜索)
代码贴上:
#include <cstdio> #include <algorithm> #include <cstring> #include <queue> #include <vector> using namespace std; const int maxn=1050; struct node{ int a,b; node(int _a,int _b):a(_a),b(_b){} }; int a,b,n; int vis[maxn][maxn]; vector<int> path[maxn][maxn]; void op(int &a,int &b,int i){ switch(i){ case 1:{ a=a; break; } case 2:{ b=b; break; } case 3:{ a=0; break; } case 4:{ b=0; break; } case 5:{ if(a+b>b){ a=(a+b)-b; b=b; } else{ b+=a; a=0; } break; } case 6:{ if(b+a>a){ b=(b+a)-a; a=a; } else{ a+=b; b=0; } break; } } } void op_print(int i){ switch(i){ case 1:{ printf("fill a\n"); break; } case 2:{ printf("fill b\n"); break; } case 3:{ printf("empty a\n"); break; } case 4:{ printf("empty b\n"); break; } case 5:{ printf("pour a b\n"); break; } case 6:{ printf("pour b a\n"); break; } } } void bfs(){ memset(vis,-1,sizeof(vis)); for(int i=0;i<a;i++){ for(int j=0;j<b;j++){ path[i][j].clear(); } } queue<node> que; que.push(node(0,0)); vis[0][0]=0; while(!que.empty()){ node tmp=que.front(); que.pop(); int ta=tmp.a; int tb=tmp.b; if(tb==n){ for(int i=0;i<path[ta][tb].size();i++){ op_print(path[ta][tb][i]); } printf("success\n"); return; } for(int i=1;i<=6;i++){ int ta=tmp.a; int tb=tmp.b; op(ta,tb,i); if(vis[ta][tb]==-1){ vis[ta][tb]=vis[tmp.a][tmp.b]+1; for(int j=0;j<vis[tmp.a][tmp.b];j++){ path[ta][tb].push_back(path[tmp.a][tmp.b][j]); } path[ta][tb].push_back(i); que.push(node(ta,tb)); } } } } int main(void){ while(~scanf("%d%d%d",&a,&b,&n)){ bfs(); } return 0; }
参考:https://blog.csdn.net/westbrook1998/article/details/80937164
好了由于时间关系,先写在这,因为要睡觉了hhhh,明天满课,从早八点到晚九点半,要死,所以还是先早睡啦~
(1)大数计算:加减乘除乘方开根问题
(2)bfs搜索算法了解
(3)灌水定理研究
这是这周的任务了吧,这周解决这三个点!!~~
注:如果有更好的解法,真心希望您能够评论留言贴上您的代码呢~互相帮助互相鼓励才能成长鸭~~
如对本文有疑问,请在下面进行留言讨论,广大热心网友会与你互动!! 点击进行留言回复
如何在没有core文件的情况下用dmesg+addr2line定位段错误
用QT制作3D点云显示器——QtDataVisualization
网友评论