Practice for algorithm
1.0.0
Practice for algorithm
一種用於字典搜索的樹，代碼中用數組實現對應題目為字典樹
KMP算法是一種字符串模式匹配算法，借助一個NEXT數組進行字符串的高速匹配。以下是KMP算法模板：
void setNext (){
NEXT[ 0 ] = - 1 ;
int j = 0 , k = - 1 ;
while (j < par. length ()) {
if (k == - 1 || par[k] == par[j]) {
j++;
k++;
NEXT[j] = k;
}
else
k = NEXT[k];
}
}
void solve (){
int p = 0 , q = 0 ;
while (p < ori. length ()) {
if (q == - 1 || par[q] == ori[p]) {
q++;
p++;
}
else
q = NEXT[q];
if (q == par. length ()) {
ans++;
}
}
}來自Hdu 1027
字典序的輸出方法在STL是有現成的，next_permutation(a, a + 4)就可以獲得size為4的數組的下一個全排列。非遞歸算法則是從最後一位開始，尋找第一個a[i - 1] < a[i]的位置，記錄i － 1，從i開始往後找到最後一個大於a[i - 1]的數字，記錄它的位置k，交換a[i - 1]和a[k],然後倒置i位置之後的所有數就得到了下一個全排列。 來自Hdu 1711
一種二分思想
int quickMPow ( int a, int b){
if (b == 0 ) {
return 1 ;
}
int reslut = 1 ;
while (b) {
if (b & 1 ) {
reslut *= a;
}
a *= a;
b >>= 1 ;
}
return reslut;
}利用字符串來進行加減，不受位數的限制
void solve (){
int lenNum1 = strlen (num1), lenNum2 = strlen (num2), min = 0 , c = 0 , count = 0 ;
if (lenNum1 >= lenNum2) {
min = lenNum2;
} else {
min = lenNum1;
}
while (min) {
int temp;
temp = num1[lenNum1 - 1 ] + num2[lenNum2 - 1 ] - 96 ;
min--;
lenNum1--;
lenNum2--;
sum[count] = (temp % 10 + c) % 10 + 48 ;
count++;
if (temp % 10 + c >= 10 ){
c = 1 ;
}
else {
c = 0 ;
}
if (temp >= 10 ) {
c++;
}
}
while (lenNum1) {
sum[count] = (num1[lenNum1 - 1 ] - 48 + c) % 10 + 48 ;
count++;
if (num1[lenNum1 - 1 ] - 48 + c >= 10 ){
c = 1 ;
} else {
c = 0 ;
}
lenNum1--;
}
while (lenNum2) {
sum[count] = (num2[lenNum2 - 1 ] - 48 + c) % 10 + 48 ;
count++;
if (num2[lenNum2 - 1 ] - 48 + c >= 10 ){
c = 1 ;
} else {
c = 0 ;
}
lenNum2--;
}
if (c) {
sum[count] = ' 1 ' ;
count++;
}
count--;
for ( int i = 0 ; i <= count; i++) {
if (sum[i] != ' 0 ' )
break ;
if (i == count){
cout << ' 0 ' << endl;
return ;
}
}
while (count >= 0 ) {
cout << sum[count];
count--;
}
cout << endl;
}
來自Hdu 1002
Given a sequence a[1],a[2],a[3]......a[n], your job is to calculate the max sum of a sub-sequence. For example, given (6,-1,5,4,-7), the max sum in this sequence is 6 + (-1) + 5 + 4 = 14.
for ( int i = 0 ; i < T; i++) {
int count, start = 1 , end = 1 , max = - 1 << 31 , dp = 0 , temp = 1 ;
cin >> count;
for ( int k = 0 ; k < count; k++) {
int num;
cin >> num;
dp += num;
if (dp > max) {
max = dp;
start = temp;
end = k + 1 ;
}
if (dp < 0 ){
dp = 0 ;
temp = k + 2 ;
}
}
cout << " Case " << i + 1 << " : " << endl;
cout << max << " " << start << " " << end << endl;
if (i != T - 1 ) {
cout << endl;
}
}來自Hdu 1003
##動態規劃之數塔數塔是一種典型的動態規劃問題。可以想像成是從楊輝三角這樣的結構上的頂點開始向下走，可左可右。到底時要求達到最大值。利用動態規劃，自底向上計算，就可以得到一個最優解。
int H1176_Solve (){
for ( int i = maxTime - 1 ; i >= 0 ; i--) {
for ( int k = 0 ; k < 11 ; k++) {
int maxValue = arr[k][i + 1 ];
if (k - 1 >= 0 ) {
if (arr[k - 1 ][i + 1 ] > maxValue) {
maxValue = arr[k - 1 ][i + 1 ];
}
}
if (k + 1 <= 10 ){
if (arr[k + 1 ][i + 1 ] > maxValue) {
maxValue = arr[k + 1 ][i + 1 ];
}
}
arr[k][i] = arr[k][i] + maxValue;
}
}
int max = arr[ 4 ][ 1 ];
for ( int i = 4 ; i < 7 ; i++) {
if (arr[i][ 1 ] > max){
max = arr[i][ 1 ];
}
}
return max;
}來自Hdu 1176
##BFS 廣度優先搜索因為可以一層一層地搜索圖，所以可以作為一種求最短路徑的方式，當然啦，是那種權值都相等的圖。一般會有一個數組去標記是否訪問來防止反复訪問，但是有的題目會有重複走的情況，則視情況而定。基本上是有一個統一的模板的。需要用到隊列，有的時候題目會有用到優先隊列的需求。
void solve (){
queue<Node> s;
memset (flag, 0 , sizeof (flag));
now. x = inx;
now. y = iny;
now. time = 6 ;
now. output = 0 ;
flag[inx][iny] = 6 ;
s. push (now);
while (!s. empty ()) {
now = s. front ();
s. pop ();
for ( int i = 0 ; i < 4 ; i++) {
nex = now;
nex. x = now. x + fx[i];
nex. y = now. y + fy[i];
if (nex. x >= 0 && nex. x < N && nex. y >= 0 && nex. y < M && flag[nex. x ][nex. y ] < now. time - 1 ){
if (mp[nex. x ][nex. y ] == 0 ) {
}
if (mp[nex. x ][nex. y ] == 3 ){
}
if (mp[nex. x ][nex. y ] == 1 ) {
}
if (mp[nex. x ][nex. y ] == 4 ) {
}
}
}
}
printf ( " -1 n " );
}來自Hdu 1072
##DFS DFS是和BFS方法截然不同的圖的遍歷方法，在一條路線上走到底再回溯而不是一層層地搜索。往往用於尋找可行路線或是對圖進行探索。是否需要加地圖標記看題目需求。在一條路線檢索完畢之後往往需要一步步將標記取消，這樣別的路線可以再次走在地圖上的該點。數據結構第三題迷宮我就是用DFS寫的。代碼類似如下：
int fx[ 4 ] = { 0 , 0 , 1 , - 1 };
int fy[ 4 ] = { 1 , - 1 , 0 , 0 };
void solve ( int x, int y){
if ((mp[x][y] == ' . ' || mp[x][y] == ' @ ' ) && vis[x][y] == 0 ){
num++;
vis[x][y] = 1 ;
for ( int i = 0 ; i < 4 ; i++) {
int nexX = x, nexY = y;
nexX += fx[i];
nexY += fy[i];
if (nexX >= 0 && nexX < N && nexY >= 0 && nexY < M) {
solve (nexX, nexY);
}
}
}
}來自Hdu 1312
##背包問題###01背包01背包是最基礎的一類背包：有N件物品和一個容量為V的背包。第i件物品的費用是c[i]，價值是w[i]。求解將哪些物品裝入背包可使價值總和最大。 狀態方程為：f[i][v]=max{f[i-1][v],f[i-1][vc[i]]+w[i]}
基本的解法為對於背包容量的逆推： for i=1..N for v=V..cost f[v]=max{f[v],f[vc[i]]+w[i]};
題目可參考Hdu1203&&Hdu2602 ###完全背包完全背包是每件物品可以放置無數次的一類背包，因為可以無數次放置，所以在遞推的時候我們將不再需要逆推，所以它的解法是： for i=1..N for v=cost..V f[v]=max{f[v],f[vc[i]]+w[i]}; 就只是和01背包有那麼一丟丟的差###多重背包多重背包相對複雜，怎麼說呢，就是物品有了數量的限制。當數量足夠多時，我們採用的還是完全背包的方法，當數量不夠多的時候我們將數量拆分，再簡化為01背包去求解。 方法是：將第i種物品分成若干件物品，其中每件物品有一個係數，這件物品的費用和價值均是原來的費用和價值乘以這個係數。使這些係數分別為1,2,4,...,2^(k-1),n[i]-2^k+1，且k是滿足n[i]-2^k+1>0的最大整數。例如，如果n[i]為13，就將這種物品分成係數分別為1,2,4,6的四件物品。 解法為： procedure MultiplePack(cost,weight,amount)
if cost*amount>=V
CompletePack(cost,weight)
return
integer k=1
while k<amount
ZeroOnePack(k*cost,k*weight)
amount=amount-k
k=k*2
ZeroOnePack(amount*cost,amount*weight)
完全背包和多重背包的題目參考Hdu 2159 Hdu 2191 Hdu 1171
