今天總算開學了,當了班長就是麻煩,明明自己沒買書卻要帶著一波人去領書,那能怎麼辦呢,只能說我善人心腸哈哈哈,不過我腦子裡突然浮起一個念頭,大二還要不要繼續當這個班委呢,既然已經體驗過就可以適當放下了吧,用心在自己的研究上。晚上級會開完也就八點多了,開始打打題,今天在HDU杭電的ACM集訓題看到一個奇 ...
今天總算開學了,當了班長就是麻煩,明明自己沒買書卻要帶著一波人去領書,那能怎麼辦呢,只能說我善人心腸哈哈哈,不過我腦子裡突然浮起一個念頭,大二還要不要繼續當這個班委呢,既然已經體驗過就可以適當放下了吧,用心在自己的研究上。晚上級會開完也就八點多了,開始打打題,今天在HDU杭電的ACM集訓題看到一個奇葩的題,前來獻上。
今日推薦:
《全球風暴》 一部宇宙航空和地球氣候片的良心佳作,後期特效建模都是特別杠杠的大片,不會讓你失望的喲,我已經三刷了哈哈哈。這部片在愛奇藝有上線,有興趣的朋友可以看看鴨。
愛奇藝鏈接:https://www.iqiyi.com/v_19rr7pl8vg.html
------------------------------------------------題目----------------------------------------------------------
Jugs
Problem Description
In the movie "Die Hard 3", Bruce Willis and Samuel L. Jackson were confronted with the following puzzle. They were given a 3-gallon jug and a 5-gallon jug and were asked to fill the 5-gallon jug with exactly 4 gallons. This problem generalizes that puzzle.You have two jugs, A and B, and an infinite supply of water. There are three types of actions that you can use: (1) you can fill a jug, (2) you can empty a jug, and (3) you can pour from one jug to the other. Pouring from one jug to the other stops when the first jug is empty or the second jug is full, whichever comes first. For example, if A has 5 gallons and B has 6 gallons and a capacity of 8, then pouring from A to B leaves B full and 3 gallons in A.
A problem is given by a triple (Ca,Cb,N), where Ca and Cb are the capacities of the jugs A and B, respectively, and N is the goal. A solution is a sequence of steps that leaves exactly N gallons in jug B. The possible steps are
fill A
fill B
empty A
empty B
pour A B
pour B A
success
where "pour A B" means "pour the contents of jug A into jug B", and "success" means that the goal has been accomplished.
You may assume that the input you are given does have a solution.
Input
Input to your program consists of a series of input lines each defining one puzzle. Input for each puzzle is a single line of three positive integers: Ca, Cb, and N. Ca and Cb are the capacities of jugs A and B, and N is the goal. You can assume 0 < Ca <= Cb and N <= Cb <=1000 and that A and B are relatively prime to one another.Output
Output from your program will consist of a series of instructions from the list of the potential output lines which will result in either of the jugs containing exactly N gallons of water. The last line of output for each puzzle should be the line "success". Output lines start in column 1 and there should be no empty lines nor any trailing spaces.Sample Input
3 5 4 5 7 3
Sample Output
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; }
(四) AC代碼:
#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; }
(五)AC截圖:
(六) 解後分析:
這道題如果不要求最短路徑的話,其實就是非常簡單的題目了,只要迴圈那三個步驟肯定能出結果,而且代碼量直接大大減少。不過這道題解法我是比較直接的一種解法,在解後去網上找找別的解法,那就是還有一種就是用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)灌水定理研究
這是這周的任務了吧,這周解決這三個點!!~~
註:如果有更好的解法,真心希望您能夠評論留言貼上您的代碼呢~互相幫助互相鼓勵才能成長鴨~~