专栏文章

题解：P13724 [GCPC 2024] Interference

yyytmcjs
P13724题解参与者 1已保存评论 0

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@mio6n21x
此快照首次捕获于
2025/12/02 14:13
3 个月前
此快照最后确认于
2025/12/02 14:13
3 个月前
查看原文

P13724 [GCPC 2024] Interference

题目概括

在水槽内有一些波，每列波的波长都为四，且第一个正波峰都在波的区间的第一个位置。每个位置上的波高度会相加。有 nn 次操作，每次给出两种操作其中一种：
  • 当输入为 ! 时，描述一个波的起始位置 pp、长度 ll 与振幅 aa（振幅就是波的高度）。
  • 当输入为 ? 时，给定一个点，查询在此点上的波（相加）的高度。

思路

注意到，水池的宽度最长可达到 10910^9，显然，每次遍历每个点修改是不可行的，于是我们想到记录每个波的参数，在查询时遍历每个波，计算其贡献。
同时我们观察到，因为每个波峰之间的距离都为四，所以从波的一个波峰走向相邻的波谷时，中间只会经过一个整点，那便是波高度为零的时候。
所以不难得出结论：每个波只在其波峰与波谷时取到有价值的整点，也就是当其偏移起始位置的长度 len mod 4=1len \bmod 4 = 1 或 len mod 4=3len \bmod 4 = 3 时。

实现思路

  1. 在每次读入波的参数时记录在一个结构体数组中。
  2. 对于每次询问 PP，遍历数组中每个波，如果 PP 不在当前波的范围内，跳过遍历下一个。
  3. 每找到一个可行的波，计算 PP 对于这个波起始位置的偏移量 lenlen，然后对 44 取模，余 11 则当前点的答案 ansans 加上波的波峰高度 aa，余 33 则减去，否则不变。
  4. 输出答案。
顺便提一嘴，因为每个询问都保证在水池宽度以内，所以读入的水池宽度没有任何用处。

代码

CPP
#include <bits/stdc++.h>
using namespace std;

struct wave{		//记录每个波的参数 
	int p,l;
	long long a;
}w[10005];

int n,W,tot;

int main(){
	cin >> n >> W;		//读入 
	for (int i=1;i<=n;i++){
		char op;
		cin >> op;
		if (op=='!'){		//将波的参数读入 
			int p,l;
			long long a;
			cin >> p >> l >> a;
			w[++tot].p=p;
			w[tot].l=l;
			w[tot].a=a;
		}
		else{
			int P;
			cin >> P;
			long long ans=0;
			for (int i=1;i<=tot;i++){		//遍历每个波 
				wave x=w[i];
				if (P<x.p || P>x.p+x.l-1) continue;		//不在范围内 
				int len=P-x.p+1;		//偏移量 
				if (len%4==1)		//在波峰上 
					ans+=x.a;
				else if (len%4==3)		//在波谷上 
					ans-=x.a;
			}
			cout << ans << endl;		//输出 
		}
	}
	return 0;
}

评论

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

正在加载评论...