专栏文章

题解：P13423 [COCI 2019/2020 #4] Spiderman

封封禁用户
P13423题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mio4fb9j
此快照首次捕获于
2025/12/02 13:11
3 个月前
此快照最后确认于
2025/12/02 13:11
3 个月前
查看原文
苯蒻的第一篇题解（轻喷）

Part 1 读题

题意转化：有nn个数，对于每个ai(1≤i≤n)a_i(1\le i\le n)，求满足aimod  aj=ka_i\mod a_j = k的jj的个数。

Part 2 分析时间复杂度

n≤3×105，k≤106n \le 3\times 10^5，k \le 10^6。 需要O(n)，O(nlogn)，O(k)，O(klogk)O(n)，O(nlogn)， O(k)，O(klogk)的算法。
似乎O(n)和O(k)O(n)和O(k)不太可能，于是我们将目光投向O(nlogn)和O(klogk)O(nlogn)和O(klogk)。

Part 3 设计算法

根据带余除法，aimod  aj=ka_i\mod a_j=k可以转化成ai=m∗aj+ka_i=m*a_j+k。
于是我们就可以枚举aja_j和mm，那么aia_i也就唯一确定了。
预处理每个xx可以跳到几栋楼，到时候求aia_i的答案，只需调用即可
时间复杂度呢？
有双重循环，看上去是max⁡(ai)2的\max(a_i)^2的。
不知道大家还记不记得埃氏筛的复杂度。
N1+N2+N3+⋯+NN−1≈Nln⁡N\frac{N}{1}+\frac{N}{2}+\frac{N}{3}+\cdots+\frac{N}{N-1} \approx N \ln N
没错，这就是我们要的O(klogk)！O(klogk)！
1e61e6的数据完全可过。

Part 4 UNAC code

CPP
#include <bits/stdc++.h>
using namespace std;
int n,k,h,cnt[1000100],a[300010],ans[1000010];
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		cnt[a[i]]++;
		h=max(a[i],h);
	}
	for(int i=1+k;i<=h;i++){
		for(int j=0;j*i+k<=h;j++){
			int x=j*i+k;
			if(x==i) continue;
			ans[x]+=cnt[i];
		}
	}
	for(int i=1;i<=n;i++){
		cout<<ans[a[i]]<<" ";
	}
	return 0;
}
然鹅，这份代码交上去只有63。

Part 5 Hack

试试这组数据。
CPP
2 0
6 6
你会发现，程序会把aia_i自身算进答案里。
于是，在k=0k=0时需要将所有答案−1-1。

Part 6 AC code

CPP
#include <bits/stdc++.h>
using namespace std;
int n,k,h,cnt[1000100],a[300010],ans[__1__];
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		__2__;
		h=max(a[i],h);
	}
	for(int i=__3__;i<=h;i++){
		for(int j=0;j*i+k<=h;j++){
			int x=__4__;
			ans[x]+=cnt[i];
		}
	}
	for(int i=1;i<=n;i++){
		cout<<(__5__?ans[a[i]]-1:ans[a[i]])<<" ";
	}
	return 0;
}
为防止作弊，空白部分需要自己填。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...