专栏文章

题解：P3543 [POI 2012] WYR-Leveling Ground

CCryn_Frog195
P3543题解参与者 1已保存评论 0

文章操作

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

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

题意

给一个序列，序列中可以做若干次区间加减 aa 或 bb 的操作，问至少多少次操作可以使序列变为全 00 或判无解。

解法

首先因为当 a,ba,b 不互质时只有所有数是 gcd⁡(a,b)\gcd(a,b) 的倍数才有可能有解，所以可以将所有数除以 gcd⁡(a,b)\gcd(a,b)，这样后续的过程中，我们都可以认为 gcd⁡(a,b)=1\gcd(a,b) = 1，也默认 a<ba < b。
其次，区间操作不好处理，这时我们考虑使用差分，同样目标是化为全 00 序列，但是这样我们的过程将更方便，因为操作转化为一个元素加另一个元素减，将改变量为 a,ba,b 的分开，可以发现答案相当于在改变和为 00 的情况下取绝对值和的一半。
我们先用扩欧求出 xi,yix_i,y_i，也就是 ii 号元素转化为 00 的一组解，发现单元素中取 xi mod bx_i \bmod b 或 xi mod b−bx_i \bmod b - b 绝对值和最小，那就都设成 xix_i 取最小正整数的解，此时 xix_i 和不小于 00，会将 xix_i 向下调整，接下来就是用 set 维护调整带来的额外代价，通过贪心将 xix_i 的和调成 00，此时 yiy_i 和也会是 00，易得调整是 O⁡(n)\operatorname{O}(n) 的。

代码

CPP
#include<bits/stdc++.h>
using namespace std;
int n,a,b,d,p[100009],o[100009];
long long x[100009],y[100009],X,ans;
int gcd(int x,int y){
	return y == 0 ? x : gcd(y,x % y);
}
int exgcd(int a,int b,long long &x,long long &y){
	if(b == 0){
		x = 1,y = 0;
		return a;
	}
	int d = exgcd(b,a % b,y,x);
	y -= a / b * x;
	return d;
}
set<pair<int,int> >s1,s2;
int main(){
	scanf("%d %d %d",&n,&a,&b);
	int d = gcd(a,b);
	a /= d,b /= d;
	if(a > b)
		swap(a,b);
	for(int i = 1; i <= n + 1; i ++){
		if(i <= n)
			scanf("%d",&o[i]);
		p[i] = o[i] - o[i - 1];
		if(p[i] % d != 0){
			printf("-1\n");
			return 0;
		}
		else
			p[i] /= d; 
		exgcd(a,b,x[i],y[i]);
		x[i] = (1ll * x[i] * p[i] % b + b) % b;
		y[i] = (1ll * p[i] - 1ll * x[i] * a) / b;
		X += x[i];
		//printf("%d %d\n",x[i],y[i]);
		ans += abs(x[i]) + abs(y[i]);
		s1.insert(make_pair((abs(x[i] + b) + abs(y[i] - a)) - (abs(x[i]) + abs(y[i])),i));
		s2.insert(make_pair((abs(x[i] - b) + abs(y[i] + a)) - (abs(x[i]) + abs(y[i])),i));
	}
	
	while(X != 0){
		//printf("%lld\n",X);
		if(X > 0){
			auto t = *s2.begin();
			s2.erase(s2.begin());
			int i = t.second;
			s1.erase(s1.find(make_pair((abs(x[i] + b) + abs(y[i] - a)) - (abs(x[i]) + abs(y[i])),i)));
			ans += t.first;
			x[i] -= b;
			y[i] += a;
			s1.insert(make_pair((abs(x[i] + b) + abs(y[i] - a)) - (abs(x[i]) + abs(y[i])),i));
			s2.insert(make_pair((abs(x[i] - b) + abs(y[i] + a)) - (abs(x[i]) + abs(y[i])),i));
			X -= b; 
		}
		else{
			auto t = *s1.begin();
			s1.erase(s1.begin());
			int i = t.second;
			s2.erase(s2.find(make_pair((abs(x[i] - b) + abs(y[i] + a)) - (abs(x[i]) + abs(y[i])),i)));
			ans += t.first;
			x[i] += b;
			y[i] -= a;
			s1.insert(make_pair((abs(x[i] + b) + abs(y[i] - a)) - (abs(x[i]) + abs(y[i])),i));
			s2.insert(make_pair((abs(x[i] - b) + abs(y[i] + a)) - (abs(x[i]) + abs(y[i])),i));
			X += b;
		} 
	}
	printf("%lld\n",ans >> 1);
}

评论

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

正在加载评论...