B3832 [NICA #2] 回来吧我的小波 - 题解

· · 题解

本题第一篇题解，本人第二篇题解。

（考场上脑子一片空白，卡在暴力做不出来了，赛后才想到正解，就差这一题啊……）

题目大意

题目传送门

对于一个不含 0 的数字串，如果能选出两个不交区间 [l_1,r_1],[l_2,r_2](1\le l_1\le r_1<l_2\le r_2\le |S|)，满足若设这两个区间取出来的数分别为 x 和 y，则 x\mid y，那么称这个子串是“好的”。

现给定一个不含 0 的数字串，求有多少个（位置）不同的（连续）子串是“好的”。

解题思路

容易想到一个暴力的方法：枚举所有的子串，对于每个子串，枚举 l_1,r_1,l_2,r_2 并判断是否整除。

可惜这样的算法效率过于低下，时间复杂度大概是 O(|S|^7)，而 |S|\le10^6，难以通过本题。（还不包括大数除法的效率问题……）

经过仔细的思考，我们会发现一些性质：

且慢！这里的“比较长”是多长？换句话说，是不是足够长的串一定是好的？这个“足够长”是多长？

然后我们会发现，由于串中只有 1,2,3,4,5,6,7,8,9，根据抽屉原理，如果串长 \ge10，那么一定会出现相同的数字，这个串就一定是好的！

于是，我们只需要用上述暴力做法，数一数串长 \le9 的好的串有几个，而串长 \ge10 的串的数量，可以用数学方法算出，加在一起就是答案了！

时间复杂度大概是 O(|S|\times g^6)，其中 g=9，可以通过本题！

（这过的也比较玄学，但是半秒过掉了，应该是因为常数小，跑不满……？还是我复杂度式子推错了？）

代码

细节见代码和注释，还有就是开 long long。

#include<iostream>
#include<string>
using namespace std;
string s;
long long ans,n,cnt; //记得开 long long
int val(int pos,int x,int y) { // 从 pos+x 到 pos+y 组成的数值
    int ans=0;
    for (int i=x;i<=y;i++)
        ans=ans*10+s[pos+i]-'0';
    return ans;
}
bool judge(int pos,int len) { // 判定 pos 开始长为 len 是否为好的
    for (int i=0;i<len;i++) // 暴力枚举
        for (int j=i;j<len;j++)
            for (int k=j+1;k<len;k++)
                for (int l=k;l<len;l++) {
                    int a=val(pos,i,j);
                    int b=val(pos,k,l);
                    if (b%a==0)
                        return true;
                }
    return false;
}
int main() {
    cin>>s;
    n=s.size();
    for (int d=2;d<=9;d++) // 只看长度不超过 9 的串
        for (int i=0;i<=n-d;i++)
            if (judge(i,d))
                cnt++;
    ans=n*(n+1)/2;
    for (int d=1;d<=9 && d<=n;d++)
        ans-=n-d+1; // 计算长度超过 9 的子串数
    ans+=cnt;
    cout<<ans<<endl;
    return 0;
}

本人第二篇题解，如有问题和建议欢迎指出！