空间换时间例题学习笔记

To The Sun

2026-05-31 11:55:18

发布于：上海

7阅读

0回复

0点赞

求和
空间换时间，其实是一个宽泛的概念。所以这其实只是做了求和这道题目的题解。

题目大意：
n个格子，每个格子有其对应的颜色和数值。
定义一种三元组： $(x,y,z)$ 其中 $x,y,z$ 都是格子上的编号，该三元组满足两个条件：
1. $x,y,z$ 都是整数， $x<y<z,y-x=z-y$
2. $b[x]=b[z]$ (b存储颜色,即x和z的颜色相同)

满足上述条件的三元组的“分数”规定为： $(x+z)*(a[x]+a[z])$ 。整个纸带的分数规定为所有满足条件的三元组的“分数”之和。输出整个纸带的分数除以10007所得的余数即可。

数据范围：
$1\le n \le 1e5$
$1\le m \le 1e5$

分析：
我们一共要进行两次优化。
先说最暴力的思路：三重循环枚举 $x,y,z$ 但是这样时间复杂度实在太高。

先研究一下第一个式子： $y-x=z-y$ 将它变形成为： $y=(x+z)/2$
题目要求 $y$ 是整数。也就是代表 $x$ 和 $z$ 的奇偶性一致。
在先前的条件下，如果 $b[x]=b[z]$ ，那么有且仅有一组 $(x,y,z)$ 。

而后我们不难发现： $y$ 对整个三元组没有任何决定性贡献。
所以我们可以直接把第二层枚举 $y$ 的循环舍去。

现在的时间复杂度是 $O(n^2)$ 。但是还不够。
如何进一步优化呢》

我们再把目光放在第二个式子上： $(x+z)*(a[x]+a[z])=xa[z]+xa[z]+za[x]+za[z]$
这是每一对三元组对答案的贡献。那么如何快速计算出所有三元组的贡献？

尝试简化问题：计算对于一个数列 $a[1],a[2],a[3],a[4],a[5]$ ，每一对满足 $1 \le x \le 5$ 的 $(a[x],a[z])$ ，对答案都有 $xa[z]+xa[z]+za[x]+za[z]$ 的贡献。那么贡献的综合是多少？

计算结果：对于所有系数为 $i$ 的项，有5-1个 $ia[i]$ 和 $i(a[1]+a[2]+a[3]+a[4]+a[5]-a[i])$ 。
对于所有统一颜色同一奇偶性的一类格子，我们都可以用这种方式计算。

使用 $s1$ 数组记录某种颜色且编号为奇数或偶数格子的数目，用 $s2$ 记录魔种颜色且编号为奇数或偶数格子的数字之和。对于每一个 $i$ ，对答案的贡献是i*((s2[y][i%2]-a[i])+a[i]*(s1[y][1%2]-1))。（这个式子我不知道为什么没办法用latex）

最终时间复杂度为 $O(n)$ 。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int ans;
const int mod=10007;
int a[N],b[N];//数字，颜色 
int s1[N][2],s2[N][2];//某种编号且颜色为奇数或偶数的格子的数目，总和 
//0为偶数，1为奇数 
int main(){
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=n;i++){
		cin>>b[i];
		s1[b[i]][i%2]++;
		s2[b[i]][i%2]=(a[i]+s2[b[i]][i%2])%mod;
	}
	for(int i=1;i<=n;i++){
		ans=(ans+i*(s2[b[i]][i%2]+a[i]*(s1[b[i]][i%2]-2)%mod)%mod)%mod;
	}
	cout<<ans;
	return 0;
}

这边有一个需要注意的点：减法取模。
可以注意到我对ans的增加进行了代码修改。

它原本应该是这样的：

ans=(ans+i*((s2[b[i]][i%2]-a[i])+a[i]*(s1[b[i]][i%2]-1)%mod)%mod)%mod;

修改前和修改后可能会被误认为是相同的。
但是因为取模之后，a[i]*(s1[b[i]][i%2])会变小。
那么本来应该是正数的添加就会变成负数。
所以需要提前移动。

有帮助，赞一个

去预览

0/2000

这里空空如也

热门讨论