自动搬运

查看原文

来自洛谷，原作者为

	MTFlowCzq 我是心流czq

搬运于2025-08-24 21:15:21，当前版本为作者最后更新于2023-08-23 22:59:53，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

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

题目大意

题目传送门

对于一个不含 $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$，难以通过本题。（还不包括大数除法的效率问题……）

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

• 一个子串如果是好的，则包含它的串也是好的；
• 一个串如果有相同的数字，那么它是好的（$x\mid x$）；
• 一个串如果含有 $1$，则大概率是好的（$1\mid x$，除非这个 $1$ 在最后）；
• 一个串如果比较长，则大概率是好的……

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

然后我们会发现，由于串中只有 $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;
}

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