题解：UVA12572 RMQ Overkill

吐槽一下：题面复制不全，需要阅读 PDF 才能看懂题意。

题意

给定一个由数字组成的字符串，询问其中每个子串中出现过的最小的一位数字和。

由于数据规模不能支持我们真的去查询每个子串（或者像原题所说的区间），我们需要一些更好的查询方式。

我们注意到一个区间的最小值取决于区间的最小值（废话），那么反过来看，是不是区间的最小值决定了区间的最小值（并非废话）？换句话说，考虑每个位置的值能够决定多少个区间的最小值，也就是对答案产生了多少贡献，就可以快速地统计最终答案了。

考虑一个问题：在一个区间中，有若干个点被打上了标记，那么至少包含有一个标记的点的区间有多少个？对于这个问题，为了不重复不遗漏地统计，我们考虑对每个标记点，钦定其为区间中最右边的标记点，假设这个区间为

[l,r]

且当前考虑的标记点下标为

i

并且下一个标记点下标为

j

（如果没有下一个标记点，则认为

j

是正无穷）的话，合法的区间左端点在

[l,i]

之间，合法的区间端点在

[i,\min(j,r)]

之间。对于每个标记点，预处理出下一个标记点即可，预处理复杂度是

O(n)

的，可以看代码。

注意到数据范围，数字范围是

[0,9]

，取值范围只有10，那么只用考虑 10 次不同标记就可以完成答案的计算了，复杂度

O(10n)=O(n)

。从小到大考虑数字，并且让当前标记的数字分割区间（因为考虑更大的数字时，区间不能有比正在考虑的数字更小的数字），再进行下一个数字的考虑即可。我简单地模拟一下过程就好理解了。

模拟过程

PYTHON

4
1231

我们先考虑完整区间以及数字 0，发现没有数字 0。

接下来考虑完整区间以及数字 1，发现第一位（下标个人习惯从 1 开始）是数字 1，下一个数字 1 在第四位，所以第一位的一贡献了

1\times3

个区间，答案加三。

接下来考虑第四位的数字 1，后面没有数字 1 了，贡献了

4\times1

个区间，答案加四。

接下来考虑区间

[2,3]

以及数字 2。为什么是这个小区间呢，因为接下来要标记的数字是 2，区间里就不能包含小于 2 的数字了，否则计算贡献时会多计算某些包含 1 的区间。详细过程略去，贡献

1\times2

个区间，答案加

1\times2\times2

，最后乘上 2 是因为这些区间的最小值都是 2 了。

接下来考虑区间

[3,3]

以及数字 3，算得贡献为

1\times1

，答案加

1\times1\times3

。

我们得到最终答案为 14。

代码如下：

CPP

#include<bits/stdc++.h>
#define ll long long
#define MOD 1000000007
using namespace std;
string s;
ll n,answer,a[10004],last[10],jump[10004];
void f(ll l,ll r,ll k)
{
    if(l>r||k>9)return;
    ll lastl=l;
    for(ll i=l;i<=r;i++)
    {
        if(a[i]==k)
        {
            answer+=k*(i-l+1)*(min(jump[i]-1,r)-i+1);
            answer%=MOD;
            f(lastl,i-1,k+1);//考虑更小的区间和更大的标记数字
            lastl=i+1;//考虑更大数字时要绕过当前位
        }
    }
    f(lastl,r,k+1);
}
int main()
{
    while(cin>>n)
    {
        answer=0;
        cin>>s;
        for(ll i=0;i<n;i++)a[i+1]=s[i]-'0';//string->integers
        memset(last,127,sizeof(last));
        for(ll i=n;i>=1;i--)//预处理下一次出现本数字的位置
        {
            jump[i]=last[a[i]];
            last[a[i]]=i;
        }
        f(1,n,0);
        cout<<answer<<'\n';
    }
}

最后斗胆评价一下题目难度，刚好是在我的舒适区内，能很快看出来但又要多想两下的程度，应该是普及+/提高左右？

题解：UVA12572 RMQ Overkill

文章操作

相关推荐

评论

题解：UVA12572 RMQ Overkill