3264 -- Balanced Lineup

 

很裸的一道RMQ題目，開始不知道Sparse Table怎么寫，后面問了之后才知道是用二進制的思想，用DP的方法的方法求出。

 

Sparse Table其實就相當于一個高效的打表方法（算法時間&&空間復雜度為O(nlogn)），我們設f(i, j)表示[i, i+2^j-1]區間中的最小值，即

         f(0, 0)表示[0, 0]中的最小值

         f(0, 2)表示[0, 3]中的最小值

         f(2, 4)表示[2, 17(2+16-1)]中的最小值

         ………………

在做最值的稀疏表（Sparse Table）時，因為是自頂向下推理，要注意循環嵌套的順序

其中j從0→log₂(n)                            //j = 0 的情況，將f(i, 0) 初始化為 d[i]

         i從0→i+2^j-1 < n

                   求最值f[i][j]：具體參考程序

 

打完了Sparse Table之后，假設我們要找[a, b]區間中的最小值，則我們

1先求出一個最大的k，使得(b – a +1) > 2^k

這樣就能把[a, b]分成兩個（部分重疊的）長度為2^k的空間

         2所以要求[a, b]的最小值，只需返回（因為前面求了的）[m, m+2^k-1]和[n-2^k+1, n]中的最小值即可，算法復雜度為O(n)。

 

對于i從0開始還是從1開始，其實這個無所謂，從0開始的話，只需將每個question中的位置-1即可，而且跟符合C中編程思想一些。

 

#include <iostream>

#include <cstring>

#include <cmath>

using namespace std;

#define maxs(a, b)   ((a>b)?(a):(b))

#define mins(a, b)    ((a<b)?(a):(b))

 

const int MAXN = 50010;

int d[MAXN];

int dpmin[MAXN][17];

int dpmax[MAXN][17];     //2^16 = 65536 > 50000

int n, q;

 

void createDpmin() {

         int i, j, k;

         // initial situation: j = 0;

         for (i = 0; i < n; i++)

                   dpmin[i][0] = d[i];     //遞推的初值：一個數的最值肯定是自己

         //bottom-top approach: so j is in the outer loop

         for (j = 1; j <= log((double)(n))/log(2.0); j++){

                   for (i = 0; i+(1<<j)-1 < n; i++) {

                            dpmin[i][j] = mins(dpmin[i][j-1], dpmin[i+(1<<(j-1))][j-1]);

                   }

         }

}

 

void createDpmax() {

         int i, j;

         for (i = 0; i < n; i++)

                   dpmax[i][0] = d[i];

         for (j = 1; j <= log((double)(n))/log(2.0); j++) {

                   for (i = 0; i+(1<<j)-1 < n; i++) {

                            dpmax[i][j] = maxs(dpmax[i][j-1], dpmax[i+(1<<(j-1))][j-1]);

                   }

         }

}

 

 

void initi() {

         createDpmin();

         createDpmax();

         //dump(n);

}

 

int rminq(int a, int b) {

         int k = (int)(log((double)(b - a + 1))/log(2.0));

         return mins(dpmin[a][k], dpmin[b-(1<<k)+1][k]);

}

 

int rmaxq(int a, int b) {

         int k = (int)(log((double)(b - a + 1))/log(2.0));

         return maxs(dpmax[a][k], dpmax[b-(1<<k)+1][k]);

}

 

int main() {

         int i;

         int a, b;

         int ans;

         while (scanf("%d %d", &n, &q) != EOF) {

                   for (i = 0; i < n; i++)

                            scanf("%d", &d[i]);

                   initi();

                   while(q--) {

                            scanf("%d %d", &a, &b);

                            ans = rmaxq(a-1, b-1) - rminq(a-1, b-1);

                            printf("%d\n", ans);

                   }

         }

         return 0;

}

Gone Fishing

       這道題其實難在讀題上，因為這道題的細節太多，往往容易搞混，造成WA的情況，所以，學好英語還是有作用的。

 

       解此題的主要方法是枚舉+貪心。剛開始的時候還沒想到一個好方法，因為當前魚最多的池塘是變化的，而題目所給描述里面的釣魚又是有順序的，即：John starts at lake 1, but he can finish at any lake he wants. He can only travel from one lake to the next one, but he does not have to stop at any lake unless he wishes to.所以，不可能在池塘中間瞬移，所以貪心貌似不能用。

 

       但轉念一想，瞬移還是有可能的，當確定了結束池塘ep（endpond）之后（結束池塘由1枚舉到n），我們便可以把從1到ep的交通費用從h中減去，然后用剩下的時間貪心即可。因為在分析問題時，對于一個池塘，John在它上面什么時候釣魚并不重要，所以可以先把John看成很聰明的人，然后假設他已經知道了在確定了結束池塘后，在每個池塘花多少時間使收益最大（實際上John是在貪心之后才知道的），這時我們就可以先減去交通費用，然后在1~ep的池塘中找現在的最大的即可。

 

       這道題還比較容易WA，但最容易WA的地方還是全零的情況。

S2.3 Cow Pedigrees

This is a typical DP problem. Since all the trees have either two children or none, we know that all trees with depth i can be built upon those ones with depth i+1. And this is crucial to solving this problem.

 

We define table[i][j] as the number of legal trees with depth i and j nodes. There are 3 possibilities to build a i-depth tree.

1.       The left subtree’s depth is i-1  while  the right one’s smaller than i-1;

2.       The left subtree’s depth is small than i-1  while  the right one’s i-1;

3.       Both the left and the right subtrees’ depth are i-1.

 

According what we have analysed. We can define another 2-dimensional array smalltrees[i][j] to restore all the sum of trees shorter than i—from 1 to i-1—to avoid unnecessary loops when calculating. Thus, we got:

 

(k loops from 1 to j, increment is 1, indicating the nodes of the left subtree)

Table[i][j] += table[i-1][k] * smalltrees[i-2][j-k-1];

Table[i][j] += smalltrees[i-2][k] * table[i-1][j-k-1];

Table[i][j] += table[i-1][k] * table[i-1][j-k-1]. ①

 

And remember to refresh smalltrees every time:

(k indicate the depth of the tree)

smalltrees[i-1][k] += table[i-1][k] + smalltrees[i-2][k]. ①

 

①:After getting each value, mod process is needed.