[vijos NOIP模拟题]天神下凡 贪心+搜索
2024-10-12 21:40:22
样例:
考试的时候没时间打了,随便敲了敲就交上去了,没想到竟然编译错误,忘定义n了23333
自己测了测能骗20分hhhh
考虑每个圆对答案的贡献,当一个圆被小圆内切的时候,分成了两半,对答案的贡献就是2。其余情况是1。
按左端点从小到大排序,左端点相同则按右端点由大到小。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define pos(i,a,b) for(int i=(a);i<=(b);i++) #define N 301000 int n; struct haha{ int l,r,o; }cun[N]; int ans[N]; bool aaa(const haha &a,const haha &b){ if(a.l==b.l) return a.r>b.r; return a.l<b.l; } int cnt; void dfs(int now){ cnt=now+1;int maxr=cun[now].l; int flag=0; while(cnt<=n&&maxr<cun[now].r){ if(cun[cnt].r>cun[now].r) break; if(!flag&&cun[cnt].l==maxr){ maxr=max(maxr,cun[cnt].r); } else flag=1; dfs(cnt); } if(maxr==cun[now].r){ ans[now]=2; } else ans[now]=1; } int sum; int main(){ scanf("%d",&n); pos(i,1,n){ int x,y; scanf("%d%d",&x,&y); cun[i].o=x;cun[i].l=x-y;cun[i].r=x+y; } sort(cun+1,cun+n+1,aaa); pos(i,1,n){ if(!ans[i]) dfs(i); sum+=ans[i]; } cout<<sum+1; return 0; }
最新文章
- [django]windows下用Django,静态文件请求失败,出现UnicodeDecodeError
- SQL Server使用文件组备份降低备份文件占用的存储空间
- Canvas 教程
- Django学习笔记——安装(linux环境)
- PQ分区魔术师v9.0 中文版
- Ubuntu + Django + Nginx + uwsgi
- JavaScript(四)---- 函数
- 【多线程】-ThreadPool线程池
- 题解 P1496 【火烧赤壁】
- javascript基础 之 jQuery教程
- 测者的测试技术手册:自动的自动化框架EvoSuite集成Cobertura得到可视化的代码覆盖报告
- VSCode插件开发全攻略(二)HelloWord
- linux学习第十二天 (Linux就该这么学)找到一本不错的Linux电子书,附《Linux就该这么学》章节目录
- 【第196期】Drupal7 Features模块与 Drupal8 Configuration Management 模块对比
- github链接地址及
- springmvc返回中文乱码问题
- Qt实在太漂亮了
- LOADRUNNER重装经验
- 单线程和多线程处理1W条数据对比代码
- 关于BFS和dijkstra(2019.04.20)
热门文章
- [leetcode-599-Minimum Index Sum of Two Lists]
- MacTex XeLaTex xdvipdfmx:fatal: pdf_ref_obj(): passed invalid object. 报错的解决方法
- es6的一些知识点
- JavaWeb 后端 <;十四>; 文件上传下载
- 一颗简单的JDBC栗子
- 剥析surging的架构思想
- Centos7 安装keepalived实现高可用
- spring 页面跳转
- (转)Spring定时任务的几种实现
- Spring源码情操陶冶-AbstractApplicationContext#initApplicationEventMulticaster