首页 > 其他分享 >洛谷P3543 [POI2012] WYR-Leveling Ground

洛谷P3543 [POI2012] WYR-Leveling Ground

时间:2024-04-01 16:46:48浏览次数:16  
标签:frac WYR Leveling int 最小 return 操作 洛谷 gcd

题目描述

给定 \(n\) 个数和 \(a,b\) 每次可以选择一段区间 \(+a,-a,+b ,或 -b\),问最少操作几次能把它们都变成 \(0\)。如果无解请输出 \(-1\)。

样例输入

5 2 3
1 2 1 1 -1
5

分析

对于区间修改是很麻烦的,为了简化复杂度,这里可以将数组转化为差分数组以降低难度,对于每一个数,我们实际上都可以找

出一个方程 \(0+ax+by=c\) 这里的 \(c\) 实际上就是原序列数,看着是不是很眼熟,没错,就是扩展欧几里得定理,这里的\(x,y\)

指的是对 \(a,b\) 进行加或减的操作和,因为一次对一个数只有一次操作 \(x\) , \(y\) 是对其他数操作时的影响,所以一次操作被算了两

边,所以最后答案实际上是 \(\frac{x+y}{2}\) ,这里要先处理出方程等于 \(gcd(a,b)\) 的两特解,即为

  • 1 \(x\)最小正整数解,\(y\) 最大负整数解

  • 2 \(x\)最大负整数解,\(y\) 最小正整数解

这里是因为要保证代价最小,接着根据裴蜀定理,让序列里的数膜上 \(gcd(a,b)\) 判断是否有解,然后我们要不断去找\(x,y\)的最小

加和最小解,因为\(x,y\) 之间具有方程关系,所以只需要考虑 \(x\) 的操作,再进行判断就可以了,这里可以用一个小根堆去维护,

每次取出最小代价操作,这里需要注意一个点,因为操作 \(a,b\) 时有加有减,所以\(x,y\) 可能出现负数,在这里先假设对 \(x\) 的

操作更多且为正,然后根据通解公式$$x=x_0+k*\frac{b}{gcd(a,b)}$$,

\[y=y_0+k*\frac{a}{gcd(a,b)} \]

每次让取出的 \(x\) 减去 \(\frac{b}{gcd(a,b)}\) ,对应的 \(y\) 加上 \(\frac{a}{gcd(a,b)}\),不断更新即可,这里可以提前求一下 \(x\) 操作数的和,最多更新次数就是

把这个和变为 \(0\) ,因为已经保证了 \(cnt_x\) \(>\) \(cnt_y\) ,所以对于所有的 \(y\) 一定进行更新了,最后把所有操作的 \(x,y\) 加起来再除二即

为答案

solution

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=(1<<17)+10;

long long n,m,sum[maxn],a,b,X[maxn],Y[maxn];

priority_queue <pair<int,int> >q;

int exgcd(int a,int b,int &x,int &y)
{
	if(b==0)
	{
		x=1;
		y=0;
		return a;
	}
	int res=exgcd(b,a%b,x,y);
	int t=x;
	x=y;
	y=t-y*(a/b);
	return res;
}

bool pd(int x,int y,int xx,int yy)
{
	return abs(x)+abs(y)<abs(xx)+abs(yy);
}

signed main()
{
	scanf("%lld%lld%lld",&n,&a,&b);
	for(int i=1;i<=n;i++)
		scanf("%lld",&sum[i]);
	for(int i=n+1;i>=1;i--)
	{
		sum[i]=sum[i]-sum[i-1];//差分,要多处理一个数0,对答案无影响
	}
	int x=0,y=0;
	int d=exgcd(a,b,x,y);
	a/=d,b/=d;
	for(int xx,yy,i=1;i<=n+1;i++)
	{
		int c=sum[i]/d;
		if(sum[i]%d!=0){puts("-1");return 0;}
		xx=X[i]=(x*c%b+b)%b;//x最小正解
		yy=Y[i]=(c-xx*a)/b;//y最大负解
		xx-=b,yy+=a;
		if(pd(xx,yy,X[i],Y[i]))X[i]=xx,Y[i]=yy;
		yy=(y*c%a+a)%a;//y最小正解
		xx=(c-yy*b)/a;//x最小负解
		if(pd(xx,yy,X[i],Y[i]))X[i]=xx,Y[i]=yy; 
		yy-=a,xx+=b;
		if(pd(xx,yy,X[i],Y[i]))X[i]=xx,Y[i]=yy;
	}
	int temp=0;
	for(int i=1;i<=n+1;i++) temp+=X[i];
	temp/=b;
	if(temp<0)temp=-temp,swap(a,b),swap(X,Y);//保证X为正
	for(int i=1;i<=n+1;i++) q.push(make_pair(-(abs(X[i]-b)+abs(Y[i]+a)-abs(X[i])-abs(Y[i])),i));
	while(temp--)
	{
		int u=q.top().second;
		q.pop();
		X[u]-=b,Y[u]+=a;
		q.push(make_pair(-(abs(X[u]-b)+abs(Y[u]+a)-abs(X[u])-abs(Y[u])),u));
	} 
	int ans=0;
	for(int i=1;i<=n+1;i++)ans+=abs(X[i])+abs(Y[i]);
	printf("%lld",ans>>1);
	
	return 0;
}

标签:frac,WYR,Leveling,int,最小,return,操作,洛谷,gcd
From: https://www.cnblogs.com/oceansofstars/p/18108817

相关文章

  • 洛谷 P8405 [COCI2021-2022#6] Naboj 题解
    题意简述给定一张无向图,每条边有个哨兵,初始在边的中间。你可以把某个结点旁边的哨兵全部吸引或远离这个结点。给出最后每个哨兵在边的哪一端,请构造出一种可能的操作方案或报告无解。多种情况输出任意解,你不需要最小化操作步数。题目分析发现一个哨兵和且仅和最后一次关联这条边......
  • 洛谷P1102 A-B数对
    双指针做法:  反过来,从后往前看也是一样的:#include<iostream>#include<stdio.h>#include<algorithm>#include<string>#include<cmath>#defineFor(i,j,n)for(inti=j;i<=n;++i)usingnamespacestd;constintN=2e5+5;int......
  • 【洛谷P1036】 [NOIP2002 普及组] 选数
    一、题目:二、解题思路:本文章采用的解决方法是递归与DFS(深度优先搜索)。以下图是思路图:1.首先-确定位置题目说4个数字取三个数,所以考虑的只有三个位置和这三个位置分别放什么数值。从第一个位置开始放数。2.其次-开始放数分为4种可能,第一位置可以先放3,那么第二个位置......
  • 【洛谷】P1004 [NOIP2000提高组]方格取数
    题目描述题目描述设有N×N 的方格图(N≤9),我们将其中的某些方格中填入正整数,而其他的方格中则放入数字 0。如下图所示(见样例):某人从图的左上角的 A 点出发,可以向下行走,也可以向右走,直到到达右下角的 B 点。在走过的路上,他可以取走方格中的数(取走后的方格中将变为......
  • 洛谷题单指南-图的基本应用-P2853 [USACO06DEC] Cow Picnic S
    原题链接:https://www.luogu.com.cn/problem/P2853题意解读:找到所有奶牛都可以到达的牧场,就是要从奶牛所在位置开始遍历,求所有奶牛能重合的点的个数。解题思路:直接从从牛奶所在位置进行DFS,记录每个位置有奶牛能到的个数,个数等于奶牛总数的即合适的牧场。100分代码:#include<bi......
  • 洛谷题单指南-图的基本应用-P1127 词链
    原题链接:https://www.luogu.com.cn/problem/P1127题意解读:按字典序排列单词,使得相邻单词的首位字母一样。解题思路:由于单词之间可以相邻的条件是前一个单词的末尾字母和后一个单词的开头字母一样,因此可以遍历每一个单词,再找到每一个可以接在其后面的单词,建立一个邻接表,然后从......
  • 【洛谷】P1060 开心的金明
    P1049装箱问题确认所需算法题目链接:P1060开心的金明这题是一道01背包问题,如果你还不知道什么是背包问题,那么请看我的背包问题学习笔记思路这道题的输入有一点点奇怪,v[i]=2~n+1行的第一个数*第二个数。其他的稍微抽象一点就可以变为标准的01背包问题了。关于状态转移方程......
  • 【洛谷】P1049 装箱问题
    P1049装箱问题确认所需算法题目链接:P1049装箱问题通过看标签得知这题是一道背包问题,如果你还不知道什么是背包问题,那么请看我这篇文章既然我们知道了这道题是一道背包问题,那么下一步我们要确认他是01背包还是完全背包。首先我们回顾01背包和完全背包的区别:通过题意可知,每......
  • 【洛谷】 P1006 [NOIP2008提高组]传纸条
    题目描述小渊和小轩是好朋友也是同班同学,他们在一起总有谈不完的话题。一次素质拓展活动中,班上同学安排坐成一个 m 行 n 列的矩阵,而小渊和小轩被安排在矩阵对角线的两端,因此,他们就无法直接交谈了。幸运的是,他们可以通过传纸条来进行交流。纸条要经由许多同学传到对方手里,......
  • 洛谷1803
    P1803凌乱的yyy/线段覆盖-洛谷|计算机科学教育新生态(luogu.com.cn)所需知识:贪心本来还想用dfsbfs搜索来一点一点做的,看到了大佬的思路之后,直接orz了整体思路:因为要想尽可能的多参加比赛,所以越早结束比赛对后面留出来的时间就更多,可以参加更多场比赛,所以直接将每场......