首页 > 其他分享 >CF576C Points on Plane

CF576C Points on Plane

时间:2024-07-02 20:32:01浏览次数:14  
标签:CF576C int Plane sqrt isdigit Points 区间 莫队 getchar

牛逼套路

看inf眼都不会,看眼题解就会了(bushi

题目让我们求一堆点按某种顺序排列后相邻点曼哈顿距离总和小于等于\(2.5\times10^9\)

然后很牛的东西:把坐标\((x,y)\)当作区间\((l,r)\),那欲求式就等于每一个区间的\((l_1,r_1)\)移到另一个相邻区间的\((l2,r2)\)的步数的总和了,于是很像莫队算法的精髓:通过排序来使得移动区间的步数最小,因为莫队区间移动是\(n\sqrt{n}\)级别的,小于等于\(10^9\),于是我们就可以通过莫队区间的排序来算出顺序了

#include<bits/stdc++.h>
#define vd void 
int gi(){
	char c;int x=0,f=0;
	while(!isdigit(c=getchar()))f|=(c=='-');
	while(isdigit(c))x=(x*10)+(c^48),c=getchar();
	return f?-x:x;
}
struct Q{
	int l,r,id;
}q[1000005];
int n,len;
int main(){
	n=gi();len=sqrt(n);
	for(int i=1;i<=n;i++)q[i].l=gi(),q[i].r=gi(),q[i].id=i;
	std::sort(q+1,q+n+1,[&](Q a,Q b){if(a.l/len!=b.l/len)return a.l<b.l;return ((a.l/len)&1)?a.r<b.r:a.r>b.r;});
	for(int i=1;i<=n;i++)printf("%d ",q[i].id);
	puts("");
	return 0;
}

我钛菜了,菜就多练

标签:CF576C,int,Plane,sqrt,isdigit,Points,区间,莫队,getchar
From: https://www.cnblogs.com/xiaboxin/p/18280505

相关文章

  • [题解]CF988D Points and Powers of Two
    思路首先发现选出的数最多\(3\)个,考虑反证法。假设选出了四个数\(a,b,c,d\),并令:\[|a-b|=2^{x_1},|b-c|=2^{x_2},|c-d|=2^{x_3}\]又因为,\(|a-c|,|b-d|\)也都是\(2\)的次幂,那么有\(x_1=x_2=x_3\)。于是\(|a-d|=3\times2^{x_0}\neq2^k\)。在......
  • CF988D Points and Powers of Two 题解
    题目传送门题目大意题目描述在坐标线上有nnn个不同的点,第iii......
  • kubernetes-外部数据库服务映射至集群内-Service与Endpoints的关系
    创建yaml文件配置数据库信息kind:ServiceapiVersion:v1metadata:name:mysql-svcnamespace:ops-systemspec:type:ClusterIP #Kubernetes将为此服务随机分配一个集群内部的IP地址ClusterIP类型的服务只能在集群内部访问,提供了一个内部访问的固定IP地址,不对......
  • 【VTKExamples::PolyData】第五十四期 SelectVisiblePoints
    很高兴在雪易的CSDN遇见你 VTK技术爱好者QQ:870202403   公众号:VTK忠粉前言本文分享VTK样例SelectVisiblePoints,并解析接口vtkSelectVisiblePoints,希望对各位小伙伴有所帮助!感谢各位小伙伴的点赞+关注,小易会继续努力分享,一起进步!你的点赞就是我的动力(^U^)ノ~YO1. ......
  • 中成科信票务管理系统 ReserveTicketManagerPlane.ashx SQL注入漏洞复现
    0x01产品简介中成科信票务管理系统是专注于演出剧院、体育场馆、旅游景区、游乐园、场地活动的票务管理系统,并为特殊客户量身定制票务应用解决方案,可根据用户的要求采用不同的技术载体实现门票的防伪:二维条码门票防伪技术、RFID电子门票防伪技术、手机二维码门票技术、变温......
  • E.Power of Points
    题目:链接:https://www.luogu.com.cn/problem/CF1857Eorhttps://codeforces.com/problemset/problem/1857/E思路我的思路可能比较复杂:首先由于覆盖的是整点,那么可以想到排序后用前缀和,比如143-->134然后由于区间[a,b]的整点数是b-a+1,那么该点的数量就是注意:这里的......
  • windmill Airplane&Superblocks&Retool&Prefect&Airflow 可选工具
    现在调度工具是越来越多了,而且集成的能力也越来越强大了windmill是一个很不错的workflow调度平台功能很强大特性可扩展的执行runtime,支持跨语言代码执行强大的调度器,支持基于低代码以及yaml模式通过appbuilder使用低代码或者js框架开发面向数据的dashboards智能依赖以......
  • crictl images报错runtime connect using default endpoints: [unix:///var/run/docke
    想试试containerd运行k8s,结果报错还在找dockershim,网上找了解决方法crictl依次查找容器运行时,当查找第一个unix:///var/run/dockershim.sock没有找到,所以报错了,需要你手动指定当前kubernetes的容器运行时,使用什么,例如:kubernetes1.24+之后,dockershim已经变成了cri-docker,所以......
  • P4112DrawingPointsDivOne
    二分具有单调性,考虑二分答案对于\(x\)考虑怎么\(check\),可以暴力的展开\(x\)次,再缩小\(x\)次,如果得到的结果和初始状态相同,那么就合法,否则不合法//Author:xiaruizeconstintN=1e3+10;intn;piia[N];bools[N][N],cur[N][N],mp[N][N];boolcheck(intx)......
  • opencv的projectPoints的使用
    前言今天要用到重投影这块的内容,是想把相机坐标系下的一个点投影到像素坐标系下。原理很简单,其实手搓一个函数也完全可以。但是还是想尝试一下用封装好的库函数,这样比较简洁和优雅。但是使用过程中遇到了一些程序死掉的问题。代码片段std::vector<cv::Point3f>objectPoints......