首页 > 其他分享 >【题解】洛谷P7287: 「EZEC-5」魔法

【题解】洛谷P7287: 「EZEC-5」魔法

时间:2024-11-12 20:30:59浏览次数:1  
标签:洛谷 int 题解 魔法 mid P7287 EZEC

P7287 「EZEC-5」魔法

感觉好题有思维,但是我没认真读题,看到样例就我以为了,他让任意一个区间满足大于 \(S\) 即可不是全部。

我们手搓一下样例就可以发现,对于加法我们不加白不加的话肯定全部的数都加上,乘法肯定要等到加完后才开始,这些都是贪心思路。

然后就是开始搭配操作了,我遇到的一些题直接就开始暴搜了,但是这题数据不是很好,看到数据范围想到二分答案,我们 \(\times 2\) 操作明显更少,所以我们枚举乘、二分答案加。

我们将操作后的数赋到一个新的数组上,然后因为只要一个区间,所以直接最大子段和。

然后这道 easy 题就简单秒掉了!!!

#include <bits/stdc++.h>
#define int long long
#define ls p<<1
#define rs p<<1|1 
#define re register 
#define ll long long
const int N=1e5+10;
const int mod=998244353;
using namespace std;

int n,x,y,k;

int a[N];

__int128 b[N];

bool check(__int128 add,__int128 mul){
	for(int i=1;i<=n;i++){
		b[i]=(a[i]+add)*mul; 
	}
	int maxx=0,now=0;
	for(int i=1;i<=n;i++){
		now=max(now+b[i],b[i]);
		maxx=max(maxx,now);
	}	
	return maxx>=k;
}

int getans(int mul){
	int ans=mul*y;
	int l=0,r=2e9+10,mid;
	while(l<r){
		mid=(l+r)>>1;
		if(check(mid,1ll<<mul)){
			r=mid;
		}
		else{
			l=mid+1;
		}
	}
	ans+=l*x;
	return ans;
} 

signed main(){
//	freopen("kingdom3.in","r",stdin);
//	freopen("a.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(nullptr); 
	
	cin>>n>>x>>y>>k;
	
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	int ans=1e18;
	for(int i=0;i<=30;i++){
		ans=min(ans,getans(i));
	} 
	cout<<ans;
	return 0;
}

标签:洛谷,int,题解,魔法,mid,P7287,EZEC
From: https://www.cnblogs.com/sadlin/p/18542593

相关文章

  • 题解:「2017 山东一轮集训 Day7」逆序对
    LibreOJ6077前置知识:生成函数、组合数先考虑平方怎么做。\(f_{i,j}\)表示处理了前\(i\)个值,逆序对有\(j\)个。显然可以转移到\(f_{i+1,j},f_{i+1,j+1},f_{i+1,j+2},...,f_{i+1,j+i}\)。然后发现这个东西是个很简单的递推,而且长得很生成函数,于是可以很自然的写成\[1\t......
  • 题解:[SCOI2016] 美味
    前置知识:可持久化线段树(主席树)洛谷3293[SCOI2016]美味问题有一个长度为\(n\)的序列\(a_1,a_2,...,a_n\)。每次询问给你\(b\)、\(x\),你需要求出\(\max\{a_i+x\bigoplusb\}\)。\(1\lel\ler\len\le2\times10^5,0\lea_i,b,x<10^5\)首先,有\(l,r\)应该......
  • AtCoder Beginner Contest 378 题解
    AtCoderBeginnerContest378题解比赛链接A-Pairing贪心#include<bits/stdc++.h>usingnamespacestd;usingi64=longlong;voidShowball(){vector<int>a(5);for(inti=0;i<4;i++){intx;cin>>x;a[x]++;......
  • 题解:[XIX Open Cup, Grand Prix of Korea] Dev, Please Add This!
    前置知识:2-SAT题意[XIXOpenCup,GrandPrixofKorea]Dev,PleaseAddThis!在一张网格上有以下几种物品:空地(.)墙(#)星星(*)一个球(O)现在你要玩一个游戏。你可以让球朝上下左右某一个方向移动,但是一旦移动就必须走到底,也就是说直到前面是墙或者边界才能停。另外,如果你走......
  • 【题解】洛谷P7286:「EZEC-5」人赢
    P7286「EZEC-5」人赢可以想到对于每个数要找到比他大的数中下标最大的数,我们按照数的大小排序,我们维护原序列的一个指针,对于每个数如果比指针大那么就左移指针,可以思考下为什么:指针上的数比现在这个数要小那比后面的数都小,于是我们左移指针直到大于这个数,可以发现我们也在一直......
  • 洛谷 P1772 [ZJOI2006] 物流运输 做题记录
    很神经的一道题。令\(val_{i,j}\)表示从第\(i\)天到第\(j\)天每天都走一条道路,单次的最小花费。可以枚举\(\{i,j\}\)然后把在这个区间里的所有点设置成不可达,每一个\(\{i,j\}\)都可以用floyd算,时间复杂度\(O(n^2m^3)\)。令\(f_i\)表示第\(i\)天的最小花费,那么......
  • 洛谷解题日记||基础篇4
     #include<iostream>usingnamespacestd;intmain(){intn,m;cin>>n>>m;//计算所有矩形的数量longlongtotalRectangles=(longlong)(n*(n+1)/2)*(longlong)(m*(m+1)/2);//计算正方形的数量longlongt......
  • 【题解】洛谷P8346:最澄澈的空与海
    【题解】洛谷P8346:最澄澈的空与海猜结论题,本身其实很简单,在纸上画个差不多就能想出来,我一开始想二分图最大匹配,但是还是太大了,不可以。当一个二分图有且仅有一种解时,必定有节点的入度为\(1\)。我们想到有多种匹配的情况,可以想到如果这是一个环的情况,一个左边的点将他右边的点......
  • MX-S5 T1~T2 题解
    MX-S5题解A.王国边缘题目链接见到循环结构,先把下标转成从\(0\)开始,以方便用同余描述位置。倍增。用二元组来表示位置:\((u,v)\)表示第\(u\)个循环节的第\(v\)个位置。设\(f(i,j)\)表示从位置\((0,i)\)开始跳\(2^j\)次以后的位置。假设已经可以初始化\(f(i,......
  • CF 705 题解
    CF705题解AHulk模拟即可.BSpiderMan打sg表可以发现,奇数个球先手必败(sg=0),偶数先手必胜(sg=1).多个组合只要把sg值异或起来就好.CThor暴力模拟就可以了,用队列模拟.DAntMan结论:按照编号由小到大加入链表,每次尽量让答案最小贪心就是对的.若原来是......