COCI 2019/2020 #4 题解

A. Spiderman

题目大意

有 $n$ 个数，求对于每一个数 $a[i]$，有多少个数在以 $a[i]$ 作被除数，该数作除数时余数为 $k$。

思路

其实思路很简单，跟暴力没区别，但是需要证明时间复杂度（os：考场上以为正解是暴力于是没写，写了个好写的暴力上去，喜提20分╥﹏╥）。

具体来说是这样的：对于每一个数，先统计它出现了多少次，然后按值域去枚举，如果当前枚举到的数在原序列中出现过的话，就枚举它能对哪些数产生贡献，不难发现，它只能对它的倍数加 $k$ 产生贡献，贡献为它在原数列中的出现次数，代码如下。

点击展开代码

代码：

#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;

const int N=3e5+5,M=1e6+5;
int n,k,ma;
int a[N];
int h[N],f[M],ans[M];

int main()
{
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		f[a[i]]++;
		ma=max(ma,a[i]);
	}
	for(int i=k+1;i<=ma;i++){
		if(!f[i]) continue;
		for(int j=0;i*j+k<=ma;j++){
			ans[i*j+k]+=f[i];
		}
	}
	for(int i=1;i<=n;i++) cout<<ans[a[i]]-(k==0)<<" ";
	cout<<'\n';

	return 0;
}

时间复杂度

这段代码的时间开销主要在两个循环，外层循环显然是 $O(ma)$ 的，也就是值域大小，那么我们需要分析的地方就集中在内层循环的部分对于固定的 i，循环条件是：

$$i*j+k\le ma$$

因此：

$$j\le (ma-k)/i=ma/i$$

所以 $j$ 大约执行：

$$floor(ma/i)+1$$

次。

因此所有内层循环总次数为：

$$T=\sum[i=k+1 到 ma] (floor(ma)+1)$$

拆开：

$$T = Σ floor(ma/i)+ma$$

由于：

$$floor(ma/i)\le ma/i$$

所以：

$$T\le L*\sum[i=k+1到ma] 1/i + ma$$

而调和级数满足：

$$\sum[i=1 到 m] 1/i = O(log m)$$

因此：

$$T = O(ma log ma)$$

B. Holding