ACM程序設計競賽基礎教程

• 前言
• 分治算法
• • 計數(shù)問題(統(tǒng)計數(shù)字出現(xiàn)個數(shù))
  • 查找等式的解（思維）
• 遞歸算法
• • 漢諾塔問題
• 貪心算法
• • 釣魚問題

前言

鑒于本人原因，本文記錄的是博主認為之前沒有想過的思路和想法。同時由于博主能力有限，對于沒有掌握的技巧就不在列舉。詳細的可以親自讀這本書。

分治算法

計數(shù)問題(統(tǒng)計數(shù)字出現(xiàn)個數(shù))

題目大意
給定兩個整數(shù)a和b，計算出1在a和b之間出現(xiàn)的次數(shù)。

解題思路
分治的思路是，我們先求出 0~a之間1的個數(shù)，與0 ~ b之間1的個數(shù)，之后這兩者之差就是a ~ b 之間1的個數(shù)了。那么我們的問題變成了如何求0 ~ x 之間1的個數(shù)了。
將0 ~ 197的數(shù)列出來后可以看出以下規(guī)律：
①可以求出1在190_{197之間出現(xiàn)的次數(shù)，然后對于0}189，1在個位數(shù)上出現(xiàn)了1次。
②個位考慮完后，直接考慮197/10-1(即18)中1出現(xiàn)的次數(shù)，同時考慮到，數(shù)字減小了，每一位的權值會增加，也就是說每一個數(shù)字出現(xiàn)的次數(shù)會增加10倍。例如，現(xiàn)在的1，是原來10~19之間的所有的1，即權值變?yōu)樵瓉淼?0倍。

代碼:

#include<iostream> #include<algorithm> #include<cstring> using namespace std;const int N = 11; int d[N]; int val;void deal(int n){if(n <= 0) return ;int one ,ten;one = n % 10 , n /= 10; // one 當前位，ten 是高位ten = n;for(int i = 0 ; i <= one ; ++i)d[i] += val; // 將個位數(shù)上的數(shù)統(tǒng)計下來while(ten){ // 個位對于高位上數(shù)字的貢獻d[ten%10] += (one + 1) * val;ten /= 10;}// 高位對當前位的貢獻for(int i = 0 ; i <= 9 ; ++i)d[i] += n * val;d[0] -= val; // 將第一位是0的情況排除val *= 10; // 權值變化deal(n - 1); }int main(){int a ,b;while(cin>>a>>b , a || b){if(a < b)swap(a,b);val = 1;memset(d , 0 ,sizeof d);deal(a);val = -1; // 為了求 deal(a) - deal(b)deal(b);cout<<d[1]<<endl;}return 0; }

查找等式的解（思維）

題目大意
有3個數(shù)列A,B和C，有一個數(shù)X。計算是否存在三個整數(shù)，$A_i,B_j,C_k$，使得公式$A_i+B_j+C_k=X$成立。

解題思路：
我們首先把 a + b 的情況全部列出來放在一個數(shù)組中，之后對這個數(shù)組c中進行排序。然后二分枚舉 s - c[i] 是否存在。

遞歸算法

漢諾塔問題

這是一個經(jīng)典問題了，就不描述了。

解題思路：
在這本書中描述一個思路，這個思路或許可以用來作為漢諾塔非遞歸解答的一個思路。思路如下:
首先把3根柱子按順序排成“品”字型，把所有的圓盤按從大到小的順序放在柱子a上，根據(jù)圓盤的數(shù)量確定柱子的排放順序；若n為偶數(shù)，按順時針方向依次擺放a、b、c；若n為奇數(shù)，按順時針方向依次擺放a、c、b。
①按順時針方向把圓盤1從現(xiàn)在的柱子移動到下一根柱子，即當n為偶數(shù)時，若圓盤1在柱子α，則把它移動到b；若圓盤1在柱子b，則把它移動到c；若圓盤1在柱子c，則把它移動到a。
②接著，把另外兩根柱子上可以移動的圓盤移動到新的柱子上。即把非空柱子上的圓盤移動到空柱子上，當兩根柱子都非空時，移動較小的圓盤。這一步?jīng)]有明確規(guī)定移動哪個圓盤，你可能以為會有多種可能性，其實不然，可實施的行動是唯一的。
③反復進行①和②操作，最后就能按規(guī)定完成漢諾塔的移動。
所以，結果非常簡單，就是按照移動規(guī)則向一個方向移動金片。
例如，3階漢諾塔的移動為：a→c,a→-b,C→→b,a→c,b→a,b→c,a→c

遞歸代碼如下

思路:

• 我們想象一下，有n個物品，我們先需要借助c，將上邊的n-1個放到b中、之后家將最底下的放到c中。之后我們總借助與沒有物品的柱子將沒放到c柱的物品上邊的n-1個放到其中，這后將底下的再移到c。

#include<iostream> #include<algorithm> #include<cstring> using namespace std;int n;void move(int n ,char a,char b){printf("move %d from %c to %c\n",n,a,b); } // 意義是 n個物體，借助 b ，從 a ，移動到 c void dfs(int n ,char a ,char b,char c){if(n == 1)move(1,a,c);else{dfs(n-1, a, c,b);move(n,a,c);dfs(n-1, b, a, c);} }int main(){cin>>n;dfs(n,'a','b','c');return 0; }

貪心算法

釣魚問題

題目：約翰有h（1≤h≤16）個小時的時間，在該地區(qū)有n（2≤n≤25）個湖，這些湖剛好分布在一條路線上，該路線是單向的。約翰從湖1出發(fā)，他可以在任一個湖結束釣魚。但他只能從一個湖到達另一個與之相鄰的湖，而且不必每個湖都停留。已知在最初5分鐘，湖i預計釣到魚的數(shù)量為fi（fi≥0）。以后每隔5分鐘，預計釣到魚的數(shù)量將以常數(shù)di（di≥0）遞減。如果某個時段預計釣到魚的數(shù)量小于或等于di，那么在下一時段將釣不到魚。為簡單起見，假設沒有其它的釣魚者影響約翰的釣魚數(shù)量。

解題思路
首先須注意的是，約翰只能向前走，若返回只會增加他在路上的時間，因而減少釣魚的時間。因此此題解題步驟如下：
①枚舉約翰經(jīng)過的最后一個湖，每種情況減去所需步行的時間，剩下的就是釣魚的時間。
②每5分鐘選取釣魚量最多的湖進行釣魚，直到時間耗盡。
③在所有枚舉的情況中選擇釣魚量最多的情況，即為問題的最優(yōu)解。此題需要注意以下幾個問題：
②隨著時間的增加，在某個湖中的釣魚數(shù)可能會出現(xiàn)負數(shù)，此時應將該湖中每個時間單位的釣魚數(shù)更新為0。
①如果解不唯一，選擇在第一個湖耗時最多的解；如果仍舊存在不唯一的解，選擇在第二個湖耗時最多的解，以此類推。
③在測試數(shù)據(jù)或程序運行的過程中可能出現(xiàn)每個湖魚數(shù)全為0的情況，需特別處理。④枚舉時，結束的標志是剩余時間≤0。

對于每一次取最大的湖我們可以利用優(yōu)先隊列來維護

#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> #include<queue> using namespace std; int n,h,time1[101],t=0,ans=0,sum,temp; struct lake {int num;int lose;bool operator < (const lake &a) const {return num<a.num;} }l[101]; int main() {priority_queue<lake>q;cin>>n>>h;h=h*60/5;for(int i=1;i<=n;i++)cin>>l[i].num;for(int i=1;i<=n;i++)cin>>l[i].lose;time1[0]=0;time1[1]=0;for(int i=1;i<=n-1;i++)cin>>time1[i+1];for(int i=1;i<=n;i++){t=0;temp=h;sum=0;for(int j=1;j<=i;j++)t+=time1[j];temp-=t;for(int j=1;j<=i;j++)q.push(l[j]);while(temp){lake l1=q.top();q.pop();if(l1.num<=0)break;sum+=l1.num;l1.num-=l1.lose;q.push(l1);temp--;}while(!q.empty())q.pop();if(sum>ans)ans=sum;}cout<<ans<<endl;return 0; }

總結

以上是生活随笔為你收集整理的读ACM程序设计竞赛基础教程之-------技巧小结的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。