首页 > 其他分享 >洛谷 P6010 - [USACO20JAN] Falling Portals P

洛谷 P6010 - [USACO20JAN] Falling Portals P

时间:2023-08-07 16:23:22浏览次数:45  
标签:直线 洛谷 int tp stk P6010 USACO20JAN MAXN 凸包

先考虑怎么对一组询问求解答案。容易想到一种贪心策略:如果 \(a_{q_i}<a_i\),那么我们肯定希望自己能够尽量快地下落,因此如果遇到一个下落速度大于当前世界下落速度的传送门我们肯定就会进那个世界,如此走下去知道能够传送到世界 \(q_i\) 为止。对于 \(a_{q_i}>a_i\) 的情况也类似,只不过要下落速度越慢越好。

考虑处理前一种情况,后一种情况则是镜像的。我们将 \(a_j>a_i\) 的部分插入直线凸包,那么从 \(i\) 开始经过的世界就是插入 \(i\) 这条直线时,\(i\) 这条直线右边的部分,维护出直线凸包以后相当于我们要找到直线凸包上与 \(y=a_{q_i}-q_ix\) 有交的那一段,可以在凸包上二分即可,这样时间可以使用追及问题的方法求出。

时间复杂度 \(O(n\log n)\)。

const int MAXN=2e5;
int n,a[MAXN+5],q[MAXN+5],ord[MAXN+5],ans1[MAXN+5],ans2[MAXN+5],stk[MAXN+5],tp;
bool check(int x,int y,int k){return 1ll*(a[x]-a[k])*(y-k)<1ll*(a[y]-a[k])*(x-k);}
void ins(int x,int flg){
	while((tp&&((stk[tp]<x)^flg))||(tp>1&&check(stk[tp-1],stk[tp],x)))--tp;
	stk[++tp]=x;
	if((a[q[x]]<a[x])^flg){
		if(flg^(q[x]>stk[1]))return;int l=2,r=tp,p=1;
		while(l<=r){
			int mid=l+r>>1;
			if((flg^(q[x]<stk[mid]))&&check(stk[mid],stk[mid-1],q[x]))p=mid,l=mid+1;
			else r=mid-1;
		}
		ans1[x]=abs(a[stk[p]]-a[q[x]]);ans2[x]=abs(stk[p]-q[x]);
		int d=__gcd(ans1[x],ans2[x]);ans1[x]/=d;ans2[x]/=d;
	}
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	for(int i=1;i<=n;i++)scanf("%d",&q[i]);
	for(int i=1;i<=n;i++)ord[i]=i;
	sort(ord+1,ord+n+1,[&](int x,int y){return a[x]>a[y];});
	for(int i=1;i<=n;i++)ins(ord[i],0);tp=0;
	for(int i=n;i;i--)ins(ord[i],1);
	for(int i=1;i<=n;i++){
		if(!ans1[i])puts("-1");
		else printf("%d/%d\n",ans1[i],ans2[i]);
	}
	return 0;
}

标签:直线,洛谷,int,tp,stk,P6010,USACO20JAN,MAXN,凸包
From: https://www.cnblogs.com/tzcwk/p/luogu-P6010.html

相关文章

  • 洛谷 P8500 - [NOI2022] 冒泡排序
    显然将权值离散化是没有问题的,因为必然存在一组最优解,满足每个\(a_i\)都取自于某个\(V_i\),于是不管三七二十一先将\(V_i\)离散化了再说。考虑从部分分入手逐步分析这道题:特殊性质A:\(V_i=1\)相当于这个区间中的数必须是\(1\),先将这些数去掉不管,紧接着考虑\(V_i=0\)的......
  • 【LGR-148-Div.3】洛谷基础赛 #1 & MGOI Round I
    【LGR-148-Div.3】洛谷基础赛#1&MGOIRoundIT1luoguP9502『MGOI』SimpleRoundI|A.魔法数字\(100pts\)水题,场切了。#include<bits/stdc++.h>usingnamespacestd;#definelllonglong#definesortstable_sort#defineendl'\n'intmain(){ ......
  • 【LGR-148-Div.3】洛谷基础赛 #1 & MGOI Round I
    【LGR-148-Div.3】洛谷基础赛#1&MGOIRoundI据说是普及组难度?T1P9502『MGOI』SimpleRoundI|A.魔法数字\(100pts\)题目描述初级魔法士小M的魔法数字是\(2\)。给定一个正整数\(n\),小M需要找到最大的偶数\(m\),使得\(2^m<n\)。又双叒叕是个水题,然后被又双......
  • 【LGR-148-Div.3】洛谷基础赛 #1 & MGOI Round I
    T1简单题,题面十分清晰,就是给我们\(n\),要求使\(2^m<n\)成立的最小偶数\(m\)。(要注意\(log_2N=m,m|2\)的情况)#include<bits/stdc++.h>#definelllonglong#definereregisterusingnamespacestd;constintN=800,INF=0x3f3f3f3f;lln;intmain(){ cin>>n; llk=log......
  • 【反思】洛谷8月月赛 Div.2 & RiOI Round 2 赛后反思
    RiOIR2赛后反思赛时开了一个T1,但是\(0pts\),然后就跑去跟人对线然后复盘(主要是我的锅,我忘记对线怎么开始的了)到了吃饭(雾不过本来我也不会做,不能怪人家赛后是shenshen教我T1+看的若归老师的反思捏推歌:歌爱ユキ&稲葉曇《キミに回帰缐》(希望没打错是我的错吗铅笔......
  • 2023年多校联训NOIP层测试4+洛谷 8 月月赛 I & RiOI Round 2
    2023年多校联训NOIP层测试4爆零了T1幸运数字\(0pts\)T2密码\(0pts\)没做到,咕了。T3小X和他的朋友们\(0pts\)没做到,咕了。T4树上询问\(0pts\)没做到,咕了。【LGR-150-Div.2】洛谷8月月赛I&RiOIRound2T1luoguP9496「RiOI-2」hacker\(100pts\)......
  • 【LGR-150-Div.2】洛谷 8 月月赛 I & RiOI Round 2
    比赛实况赛前看了眼难度分布,红橙黄绿,感觉随便杀(爆我)顺序开题,先看A题,没仔细读,一眼以为单次操作只能翻转一位,写了个十进制转二进制找不同,结果WA了。再看了一眼题,发现题干定义的操作可以一次操作很多位,然后一个操作是把0变1,另一个是把1变0。所以只需要看两个数二进制对......
  • 【LGR-150-Div.2】洛谷 8 月月赛 I & RiOI Round 2
    T1一直没有详细看过位运算的我瑟瑟发抖。出题人给了帮助(有用但是不多)。直接讲考试想法:首先,手玩样例后,果断猜测:将两个数转化为二进制之后,把头对齐,然后找出不同位,再加上二者位数之差。结果:\(0Pts\)之后,又想了很久,发现了按位与等价于将原来二进制数中的1变为0,按位或等价于将原来......
  • LGR-147-Div.3】洛谷网校 7 月普及组月赛 & yLOI2022 总结
    Upd:2023/8/5补T1普及组的题,而且T1,而且叫签到题。所以非常简单,入门难度。没什么好说的。就是统计大写,小写和字母个数。#include<bits/stdc++.h>#definelllonglongusingnamespacestd;constintN=100+5;strings;intmain(){ cin>>s; intx=0,y=0,z=0; for(inti=......
  • 洛谷 P1553 数字反转(升级版)
    题目描述给定一个数,请将该数各个位上数字反转得到一个新数。整数反转是将所有数位对调。小数反转是把整数部分的数反转,再将小数部分的数反转,不交换整数部分与小数部分。分数反转是把分母的数反转,再把分子的数反转,不交换分子与分母。百分数的分子一定是整数,百分数只改变数字......