洛谷题单指南-分治与倍增-P7167 [eJOI2020 Day1] Fountain

原题链接：https://www.luogu.com.cn/problem/P7167

题意解读：从喷泉任意一个圆盘倒水，水流经的圆盘直径必须递增，水最后流到哪个圆盘。

解题思路：

1、枚举法

有30%的数据范围在N<=1000,Q<=1000，因此枚举也可以得到30分。

可以通过单调栈预计算每个圆盘后面第一个直径更大的圆盘位置Next[N]，这样直接通过模拟，

将水依次流经各个圆盘，计算最后停留在哪。

30分代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 100005;
int n, q;
int d[N], c[N]; //d[i]:第i个圆盘直径 c[i]:第i个圆盘容量
int stk[N], top; //单调栈
int Next[N]; //Next[i]表示第i个圆盘之后第一个直径大于d[i]的位置

int main()
{
    cin >> n >> q;
    for(int i = 1; i <= n; i++) cin >> d[i] >> c[i];

    //利用单调栈计算每个圆盘后面第一个直径更大的圆盘位置
    for(int i = n; i >= 1; i--)
    {
        while(top && d[i] >= d[stk[top]]) top--;
        Next[i] = stk[top];
        stk[++top] = i;
    }

    int r, v;
    while(q--)
    {
        cin >> r >> v;
        while(r) //模拟法，水顺着往下流
        {
            v -= c[r];
            if(v <= 0) break;
            r = Next[r];
        }
        cout << r << endl;
    }
    return 0;
}

2、二分

又有30%的数据，圆盘直径是递增的，因此可以通过前缀和以及区间和公式计算任意两个圆盘之间能存下多少水，然后二分水最后流到的位置，

计算如果起点到终点的存水量超过导入的水量，则不断缩小答案范围，否则扩大答案范围，这样又可以得到30分。

60分代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 100005;
int n, q;
int d[N], c[N]; //d[i]:第i个圆盘直径 c[i]:第i个圆盘容量
int stk[N], top; //单调栈
int Next[N]; //Next[i]表示第i个圆盘之后第一个直径大于d[i]的位置
int s[N]; //c[N]的前缀和

int main()
{
    cin >> n >> q;
    for(int i = 1; i <= n; i++) cin >> d[i] >> c[i];
    for(int i = 1; i <= n; i++) s[i] = s[i - 1] + c[i];

    //利用单调栈计算每个圆盘后面第一个直径更大的圆盘位置
    for(int i = n; i >= 1; i--)
    {
        while(top && d[i] >= d[stk[top]]) top--;
        Next[i] = stk[top];
        stk[++top] = i;
    }

    int r, v;
    while(q--)
    {
        cin >> r >> v;
        if(n <= 1000)
        {
            while(r) //模拟法，水顺着往下流
            {
                v -= c[r];
                if(v <= 0) break;
                r = Next[r];
            }
            cout << r << endl;
        }
        else
        {
            int left = r, right = n + 1;
            while(left < right)
            {
                int mid = (left + right) / 2;
                if(s[mid] - s[r - 1] >= v) right = mid;
                else left = mid + 1;
            }
            if(left == n + 1) cout << 0 << endl;
            else cout << left << endl;
        }
    }
    return 0;
}

3、倍增法

当圆盘直径不是递增时，就不能用前缀和以及区间和来计算两个圆盘之间的存水量，二分也就失效了。

关键还是要计算两个值：

a、水从起点经过一定数量圆盘能到哪个点

b、从起点经过圆盘能存多少水

有了这两个信息，就可以计算答案。

但是本题数据量较大，计算所有区间必然超时，可以借助倍增和ST表的思想，只计算2^k次方范围的数据。

状态表示：

设f[i][j]表示从i点开始，跳过2^j个圆盘后能到的点，注意下一个点直径必须是递增的，所以初始化f[i][0]可以借助单调栈

设g[i][j]表示从i点之后开始，一共2^j个圆盘能存的水量，g[i][0]就是从i之后一个圆盘的存水量

状态转移：

f[i][j] = f[f[i][j-1]][j-1]，从i跳过2^j个圆盘能到的点等于从i跳过2^(j-1)个圆盘能到的点再跳过2^(j-1)个圆盘能到的点

g[i][j] = g[i][j-1] + g[f[i][j-1]][j-1]，从i之后开始共2^j个圆盘能存的水量，等于从i之后开始2^(j-1)个圆盘存的水量，加上从f[i][j-1]之后开始2^(j-1)个圆盘能存的水量

结果计算：

如果v小于等于起点圆盘的存水量，v<=c[r]，则答案就是r

否则，可以从最大区间开始尝试，如果v>该区间的存水量，则跳过整个区间，存水量更新，起点更新，直到无法再往后跳

100分代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 100005;
int n, q;
int d[N], c[N]; //d[i]:第i个圆盘直径 c[i]:第i个圆盘容量
int stk[N], top; //单调栈
//设f[i][j]表示从i点开始，跳过2^j个圆盘后能到的点，注意下一个点直径必须是递增的
//设g[i][j]表示从i点开始，跳过的2^j个圆盘能存的水量
int f[N][20], g[N][20];

int main()
{
    cin >> n >> q;
    for(int i = 1; i <= n; i++) 
    {
        cin >> d[i] >> c[i];
    }

    //利用单调栈初始化f[i][0],g[i][0]
    for(int i = n; i >= 1; i--)
    {
        while(top && d[i] >= d[stk[top]]) top--;
        f[i][0] = stk[top]; //初始化,注意f[n][0] = 0
        g[i][0] = c[stk[top]];
        stk[++top] = i;
    }

    for(int j = 1; (1 << j) <= n; j++)
    {
        for(int i = 1; i + (1 << j) <= n; i++)
        {
            f[i][j] = f[f[i][j-1]][j-1];
            g[i][j] = g[i][j-1] + g[f[i][j-1]][j-1];
        }
    }

    int r, v;
    while(q--)
    {
        cin >> r >> v;
        if(c[r] >= v) cout << r << endl; //如果第r号圆盘能存下v水量
        else 
        {
            v -= c[r]; //先减掉起点圆盘的存水量
            for(int j = 17; j >= 0; j--) //从大到小倍增，每次v减去能跳到最远的位置能存的水量，r更新为跳过之后的位置
            {             
                if(f[r][j] && v > g[r][j]) //f[r][j]==0时说明已跳到底
                {
                    v -= g[r][j];
                    r = f[r][j];
                }
            }
            cout << f[r][0] << endl; //v刚好>g[r][j]，说明水可以留到2^j之后的下一个圆盘
        }
    }
    return 0;
}