首页 > 其他分享 >CF150C题解

CF150C题解

时间:2024-01-19 15:37:03浏览次数:30  
标签:max ch int 题解 lans rans ans CF150C

Smart Cheater

题目传送门

题解

首先显然的,每个乘客是独立计算的,然后我们发现,一个乘客在 \(i\) 到 \(i+1\) 不买票的期望贡献是一定的,为 \(\dfrac{x_{i+1}-x_i}{2}-c*p_i\),所以我们其实就是要对于每个乘客的区间求最大子段和,简单线段树板子,感觉也没啥细节。

代码:

#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int rd() {
	int s=0,m=0;char ch=getchar();
	while(!isdigit(ch)) {if(ch=='-')m=1;ch=getchar();}
	while( isdigit(ch)) s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
	return m?-s:s;
}
int n,m,c;
double x[150005],p[150005],a[150005];
struct Node {int l,r;double ans,lans,rans,d;};
struct Segment_Tree {
  	Node t[4*150005];
	int ls(int p) {return p<<1;}
	int rs(int p) {return p<<1|1;}
	void pushup(int p) {
		t[p].d=t[ls(p)].d+t[rs(p)].d;
		t[p].ans=max(max(t[ls(p)].ans,t[rs(p)].ans),t[ls(p)].rans+t[rs(p)].lans);
		t[p].lans=max(t[ls(p)].lans,t[ls(p)].d+t[rs(p)].lans);
		t[p].rans=max(t[ls(p)].rans+t[rs(p)].d,t[rs(p)].rans);
	}
	void build(int p,int l,int r) {
		t[p].l=l,t[p].r=r;
		if(l==r) {t[p].d=t[p].lans=t[p].rans=t[p].ans=a[l];return;}
		int m=(l+r)>>1;
		build(ls(p),l,m);build(rs(p),m+1,r);
		pushup(p);
	}
	Node query(int p,int l,int r) {
		if(t[p].r<l||t[p].l>r) return {0,0,0,0,0,0};
		if(l<=t[p].l&&t[p].r<=r) return t[p];
		double s=0;int m=(t[p].l+t[p].r)>>1;
		Node x=query(ls(p),l,r),y=query(rs(p),l,r),ans;
		ans.d=x.d+y.d;
		ans.ans=max(max(x.ans,y.ans),x.rans+y.lans);
		ans.lans=max(x.lans,x.d+y.lans);
		ans.rans=max(x.rans+y.d,y.rans);
		return ans;
	}
}t;
double ans;
signed main() {
	cin>>n>>m>>c;
	for(int i=1;i<=n;i++)
		scanf("%lf",&x[i]);
	for(int i=1;i<n;i++)
		scanf("%lf",&p[i]),p[i]/=100;
	for(int i=1;i<n;i++)
		a[i]=(x[i+1]-x[i])/2.0-c*p[i];
	t.build(1,1,n-1);
	while(m--) {
		int l=rd(),r=rd();
		ans+=t.query(1,l,r-1).ans;
	}
	printf("%.6lf",ans);
	return 0;
}

标签:max,ch,int,题解,lans,rans,ans,CF150C
From: https://www.cnblogs.com/operator-/p/17974754

相关文章

  • CF1286C1题解
    Madhouse(Easyversion)题目传送门题解这种水题还能有蓝?不能因为困难版是黑就把简单版难度往上强拉啊!第一次问\([1,n]\),第二次问\([1,n-1]\),把读入的所有字符串先各自内部把字符排序(反正本来就是乱序)后存入map,第一次询问有,第二次询问没有的字符串就是原串后缀的乱序,都找出......
  • NOIP2023题解
    目录NOIP2023T1词典(dict)T2三值逻辑(tribool)T3双序列拓展(expand)T4天天爱打卡(run)NOIP2023T1词典(dict)考察:贪心题解Link题目传送门首先任意多次操作本质就是随意排序,所以如果要使\(w_i\)最小,我们一定会使\(w_i\)从\(a\)到\(z\)排,其它都\(z\)到\(a\)排......
  • CF1899G题解
    UnusualEntertainment题目传送门题解真的不要太典,,,考虑点\(u\)是\(v\)的后代等价于\(u\)在子树\(v\)中,dfs序直接走起,变成判断是否存在\(i\)使得:\[in_x\lein_{p_i}\leout_x,l\lei\ler\]二维数点,启动!代码:#include<bits/stdc++.h>usingnamespacestd;#defi......
  • CF1899F题解
    Alex'swhims题目传送门题解构造题,感觉比G更难?可能是我不擅长构造。考虑点的度数,发现一次操作\(u,v_1,v_2\)会使\(deg_{v_1}\)减\(1\),使\(deg_{v_2}\)加\(1\),即一次操作最多减少一个叶子,那如果存在一个时刻使我们的叶子数量大于\(3\)个,下一次若问\(n-1\)则直接......
  • P6550题解
    P6550[COCI2010-2011#2]LUNAPARK题目传送门题解论证简单,构造逆天(好吧其实就是烦了点)。每个格子是正整数,所以我们必然尝试多走格子。我们发现,只要\(r,c\)中有一个是奇数,我们就可以全部走到,构造很简单:我们找准奇数边,假设是\(r\),蛇形地走,显然在奇数行我们会结束在末尾,在偶数......
  • P5133题解
    P5133tb148的客人题目传送门题解唯一的一篇题解还是交错题的……很简单的一个二分加差分题。显然是二分答案,考虑检验。如果\(2mid+1\gen\),那么所有人可以自由去到任意位置,一定可行;否则,我们求出每个人可以去到的区间范围,并以此推出要满足这个人的限制,\(1\)号需要在哪个区......
  • P3867题解
    P3867[TJOI2009]排列计数题目传送门题解\(k\)很小,不是分讨就是突破口。如果我们用这种方式生成排列:将\(1\)到\(n\)按顺序插入当前状态,那么你会发现当前的数\(x\)的插入被很大程度的限制住了,我们只需记录当前\(x-k\)到\(x-1\)的位置即可枚举出所有可能的下一状态,因......
  • P7312题解
    P7312[COCI2018-2019#2]Sunčanje题目传送门题解分类讨论的思想有点像P4169?要你对于每一个矩形,求是否存在编号比它大,与它有交的矩形。直接做需要用一个比较神仙的线段树用法,所以我们可以容斥:我们求出编号比它大,与它无交的矩形数量,最后与所有可能覆盖它的矩形共\(n-i\)个......
  • P6554题解
    P6554PromisesICan'tKeep题目传送门题解看题解都有些做烦了,就来发一篇。换根dp。第一遍dfs处理出\(Lef_u\)表示\(u\)子树内的叶子个数(包含自己),然后求出以\(1\)为根时的答案\(\sumLef_u*val_u\),注意特判根为叶子的情况。第二遍dfs大力换根就好了,从根\(u\)......
  • P9744题解
    P9744「KDOI-06-S」消除序列题目传送门题解记错时间错过模拟赛的sb来也。题目中的最关键信息就是\(a_i,b_i,c_i\ge0\),这意味着多做无用的操作一定不优,所以有:结论\(1\):优先进行\(1\)操作。这是因为我们不管我们在\(1\)操作前做什么操作都会被其推平覆盖,是无用操......