【NOIP2018提高组模拟9.20】 有所失

2024-05-29 02:48

本文主要是介绍【NOIP2018提高组模拟9.20】 有所失,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

文章目录

  • Description
  • Input
  • Output
  • Sample Input
  • Sample Output
    • 样例输出1
    • 样例输出2
  • Data Constraint
  • Solution
  • Code

Description

在这里插入图片描述

Input

在这里插入图片描述

Output

若干行,对每个1操作,输出到这个点最多经过多少点。

Sample Input

样例输入1
3 5
1 0 0 1
0 0
1 0
0 1
5
1 3
2 1 1
1 4
2 2 2
1 5

样例输入2
3 5
2 1 1 2
0 0
1 0
0 1
5
1 3
2 1 1
1 4
2 2 2
1 5

Sample Output

样例输出1

2
3
4

样例输出2

1
2
3

Data Constraint

n , m &lt; = 100000 , k &lt; = 20 n,m&lt;=100000,k&lt;=20 n,m<=100000k<=20

Solution

首先我们想办法把坐标系弄一下变成直角坐标系。
对于每个点,求出它到给定两个边界的三角形的有向面积,以面积的大小为新的下标,并离散化。
可以发现,这样之后,每个点依然满足没有重合而且边界就变成了一个直角的边界。
因为k比较小,考虑从k入手。
把最右边和最上面的k个点分别放到两个队列里,其他不在队列里的点的答案是不会变的,将这些点放到数据结构里。
提前预处理好每个点的答案,然后考虑加入。
预处理相当于二维偏序问题,扫描线加树状数组。
加入时,取出最右和最上的共2k个点,直接暴力转移得到这2k个点的新答案,随后求出新的最右和最上的k个点,多余出的那个点加入数据结构。
发现数据结构的功能只是前缀取max和单点修改,用树状数组即可。
这样有个800的常数,不过不会超时。
时间复杂度 O ( m l o g n ) O(mlogn) O(mlogn)

Code

#include<cstdio>
#include<cstring>
#include<algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
#define N 201000
#define ll long long
using namespace std;
int n,K,m,ni;
struct P{ll x,y,z;
}a[N],X,Y,c[N];
int q[N][2],f[N],t[2][N],b[2][N],bz[N];
ll abx(ll x){return x>0?x:-x;}
ll cross(P a,P b){return a.x*b.y-a.y*b.x;}
bool cnt1(P a,P b){return cross(a,Y)<cross(b,Y);}
bool cnt2(P a,P b){return cross(X,a)<cross(X,b);}
bool cmt1(P a,P b){return (a.x<b.x)||(a.x==b.x&&a.y<b.y);}
bool cmt2(P a,P b){return (a.y<b.y)||(a.y==b.y&&a.x<b.x);}
bool cid(P a,P b){return a.z<b.z;}
int lowbit(int x){return x&(-x);}
void lsh()
{fo(i,1,ni) c[i]=a[i];sort(c+1,c+ni+1,cnt1);int k=0;fo(i,1,ni){if(i==1||cnt1(c[i-1],c[i])) k++;a[c[i].z].x=k;}sort(c+1,c+ni+1,cnt2);k=0;fo(i,1,ni){if(i==1||cnt2(c[i-1],c[i])) k++;a[c[i].z].y=k;}
}
void ins(int q,int x,int z)
{for(;x<=ni;x+=lowbit(x)) t[q][x]=max(t[q][x],z);
}
int get(int q,int x)
{int ans=0;for(;x;x-=lowbit(x)) ans=max(ans,t[q][x]);return ans;
}
void pre()
{sort(a+1,a+ni+1,cmt1);fo(i,1,ni)if(a[i].z<=n){int j=a[i].z;f[j]=get(0,a[i].y)+1;ins(0,a[i].y,f[j]);}memset(t[0],0,sizeof(t[0]));int jy=0;fd(i,ni,1)if(a[i].z<=n){if(jy>=K) ins(0,a[i].y,f[a[i].z]);else b[0][++jy]=a[i].z;}sort(a+1,a+ni+1,cmt2);jy=0;fd(i,ni,1)if(a[i].z<=n){if(jy>=K) ins(1,a[i].x,f[a[i].z]);else b[1][++jy]=a[i].z;}sort(a+1,a+ni+1,cid);
}
int main()
{freopen("travel.in","r",stdin);freopen("travel.out","w",stdout);scanf("%d%d",&n,&K);ni=n;scanf("%lld%lld%lld%lld",&X.x,&X.y,&Y.x,&Y.y);fo(i,1,n) scanf("%lld%lld",&a[i].x,&a[i].y),a[i].z=i;scanf("%d",&m);fo(i,1,m){scanf("%d",&q[i][0]);if(q[i][0]==2||q[i][0]==3){q[i][1]=++ni;scanf("%lld%lld",&a[ni].x,&a[ni].y),a[ni].z=ni;}else scanf("%d",&q[i][1]);}lsh();pre();int numb=0;memset(c,0,sizeof(c));fo(i,1,m){int x=q[i][1];if(q[i][0]==1){numb++;printf("%d\n",f[x]);}else{if(q[i][0]==2) f[x]=get(1,a[x].x)+1;else f[x]=get(0,a[x].y)+1;fo(j,1,K) c[j+j-1]=a[b[0][j]],c[j+j]=a[b[1][j]];c[K+K+1]=a[x];sort(c+1,c+K+K+2,cmt1);fo(j,1,K+K+1) if(c[j].z!=0) fo(k,j+1,K+K+1) if(c[j].z!=c[k].z&&c[k].z!=0&&c[j].x<=c[k].x&&c[j].y<=c[k].y) f[c[k].z]=max(f[c[k].z],f[c[j].z]+1);int jy=0;fd(j,K+K+1,1)if(!bz[c[j].z]){bz[c[j].z]=1;if(jy>=K) ins(0,c[j].y,f[c[j].z]);else b[0][++jy]=c[j].z;}fo(j,1,K+K+1) bz[c[j].z]=0;jy=0;sort(c+1,c+K+K+2,cmt2);fd(j,K+K+1,1)if(!bz[c[j].z]){bz[c[j].z]=1;if(jy>=K) ins(1,c[j].x,f[c[j].z]);else b[1][++jy]=c[j].z;}fo(j,1,K+K+1) bz[c[j].z]=0;}}
}

这篇关于【NOIP2018提高组模拟9.20】 有所失的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1012436

相关文章

CSS模拟 html 的 title 属性(鼠标悬浮显示提示文字效果)

《CSS模拟html的title属性(鼠标悬浮显示提示文字效果)》:本文主要介绍了如何使用CSS模拟HTML的title属性,通过鼠标悬浮显示提示文字效果,通过设置`.tipBox`和`.tipBox.tipContent`的样式,实现了提示内容的隐藏和显示,详细内容请阅读本文,希望能对你有所帮助... 效

如何提高Redis服务器的最大打开文件数限制

《如何提高Redis服务器的最大打开文件数限制》文章讨论了如何提高Redis服务器的最大打开文件数限制,以支持高并发服务,本文给大家介绍的非常详细,感兴趣的朋友跟随小编一起看看吧... 目录如何提高Redis服务器的最大打开文件数限制问题诊断解决步骤1. 修改系统级别的限制2. 为Redis进程特别设置限制

【C++】_list常用方法解析及模拟实现

相信自己的力量,只要对自己始终保持信心,尽自己最大努力去完成任何事,就算事情最终结果是失败了,努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一:什么是list? •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二:list常用接口 •🌰1.默认成员函数 🔥构造函数(⭐) 🔥析构函数 •🌰2.list对象

usaco 1.2 Transformations(模拟)

我的做法就是一个一个情况枚举出来 注意计算公式: ( 变换后的矩阵记为C) 顺时针旋转90°:C[i] [j]=A[n-j-1] [i] (旋转180°和270° 可以多转几个九十度来推) 对称:C[i] [n-j-1]=A[i] [j] 代码有点长 。。。 /*ID: who jayLANG: C++TASK: transform*/#include<

hdu4431麻将模拟

给13张牌。问增加哪些牌可以胡牌。 胡牌有以下几种情况: 1、一个对子 + 4组 3个相同的牌或者顺子。 2、7个不同的对子。 3、13幺 贪心的思想: 对于某张牌>=3个,先减去3个相同,再组合顺子。 import java.io.BufferedInputStream;import java.io.BufferedReader;import java.io.IOExcepti

键盘快捷键:提高工作效率与电脑操作的利器

键盘快捷键:提高工作效率与电脑操作的利器 在数字化时代,键盘快捷键成为了提高工作效率和优化电脑操作的重要工具。无论是日常办公、图像编辑、编程开发,还是游戏娱乐,掌握键盘快捷键都能带来极大的便利。本文将详细介绍键盘快捷键的概念、重要性、以及在不同应用场景中的具体应用。 什么是键盘快捷键? 键盘快捷键,也称为热键或快捷键,是指通过按下键盘上的一组键来完成特定命令或操作的方式。这些快捷键通常涉及同

CSP 2023 提高级第一轮 CSP-S 2023初试题 完善程序第二题解析 未完

一、题目阅读 (最大值之和)给定整数序列 a0,⋯,an−1,求该序列所有非空连续子序列的最大值之和。上述参数满足 1≤n≤105 和 1≤ai≤108。 一个序列的非空连续子序列可以用两个下标 ll 和 rr(其中0≤l≤r<n0≤l≤r<n)表示,对应的序列为 al,al+1,⋯,ar​。两个非空连续子序列不同,当且仅当下标不同。 例如,当原序列为 [1,2,1,2] 时,要计算子序列 [

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟)

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟) 题目描述 给定一个链表,链表中的每个节点代表一个整数。链表中的整数由 0 分隔开,表示不同的区间。链表的开始和结束节点的值都为 0。任务是将每两个相邻的 0 之间的所有节点合并成一个节点,新节点的值为原区间内所有节点值的和。合并后,需要移除所有的 0,并返回修改后的链表头节点。 思路分析 初始化:创建一个虚拟头节点

如何提高 GitHub 的下载速度

如何提高 GitHub 的下载速度 文章目录 如何提高 GitHub 的下载速度1. 注册账号2. 准备好链接3. 创建仓库4. 在码云上下载代码5. 仓库更新了怎么办 一般来说,国内的朋友从 GitHub 上面下载代码,速度最大是 20KB/s,这种龟速,谁能忍受呢? 本文介绍一种方法——利用“码云”,可以大大提高下载速度,亲测有效。 1. 注册账号 去“码云”注册一

每日一题|牛客竞赛|四舍五入|字符串+贪心+模拟

每日一题|四舍五入 四舍五入 心有猛虎,细嗅蔷薇。你好朋友,这里是锅巴的C\C++学习笔记,常言道,不积跬步无以至千里,希望有朝一日我们积累的滴水可以击穿顽石。 四舍五入 题目: 牛牛发明了一种新的四舍五入应用于整数,对个位四舍五入,规则如下 12345->12350 12399->12400 输入描述: 输入一个整数n(0<=n<=109 ) 输出描述: 输出一个整数