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.