当前位置:网站首页>CSP认证 202203-2 出行计划(多种解法)
CSP认证 202203-2 出行计划(多种解法)
2022-04-23 09:52:00 【不考浙大不改名】
解法一前置知识:差分数组
解法二前置知识:线段树
试题编号: | 202203-2 |
试题名称: | 出行计划 |
时间限制: | 1.5s |
内存限制: | 512.0MB |
问题描述: | 问题描述最近西西艾弗岛上出入各个场所都要持有一定时限内的核酸检测阴性证明。 具体来时,如果在 t 时刻做了核酸检测,则经过一段时间后可以得到核酸检测阴性证明。这里我们假定等待核酸检测结果需要 k 个单位时间,即在 t+k 时刻可以获得结果。如果一个场所要求持 24 个单位时间内核酸检测结果入内,那么凭上述的核酸检测结果,可以在第 t+k 时刻到第 t+k+23 时刻进入该场所。 小 C 按时间顺序列出接下来的 n 项出行计划,其中第 i 项(1≤i≤n)可以概括为: 为了合理安排核酸检测时间,试根据小 C 的出行计划,回答如下查询:
这样的查询共有 m 个,分别为 q1,q2,⋯,qm;查询之间互不影响。 输入格式输入的第一行包含空格分隔的三个正整数 n、m 和 k,分别表示出行计划数目、查询个数以及等待核酸检测结果所需时间。 接下来输入 n 行,其中每行包含用空格分隔的两个正整数 ti、ci,表示一项出行计划;出行计划按时间顺序给出,满足 0<t1≤t2≤⋯≤tn≤2×105。 最后输入 m 行,每行仅包含一个正整数 qi,表示一个查询。m 个查询亦按照时间顺序给出,满足 0<q1<q2<⋯<qm≤2×105。 输出格式输出共 m 行,每行一个整数,表示对应查询的答案。 样例输入 Data 样例输出 Data 样例解释时刻 1 做检测,可以满足第三、四、六项出行计划; 时刻 2 做检测,可以满足第四、五、六项出行计划。 子任务40% 的测试数据满足 0<n,k≤1000、m=1; 70% 的测试数据满足 0<n,m,k≤1000; 全部的测试数据满足 0<n,m,k≤105。 |
题目本质:每个出行计划都代表一个区间。每次查询就是查询当前时间x在k时间后(即x+k)被多少个区间包含。
解法一:差分数组(最好想、码量最少的解法)
差分数组适合于多次区间修改,极少区间查询或者先区间修改再区间查询,不是边修改边查询的情况。本题使用差分数组,每个出行计划就是对有效区间的操作。最后前缀和统计一下,随后查询即可。
/*
差分数组版本,五分钟就AC,比线段树好太多了
*/
#include <cstdio>
#define fi(i,l,r) for(int i=(l);i<=(r);++i)
#define fd(i,r,l) for(int i=(r);i>=(l);--i)
using namespace std;
int n,m,t;
int x,y;
int a[300005];
template<typename T>void Read(T &x)
{
x=0;T k=1;char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-') k=-1;ch=getchar();}
while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
x*=k;
}
template<typename T>void Print(T x)
{
if(x<0){putchar('-');Print(-x);return;}//这个return很重要,某些情况可能出错
if(x>9) Print(x/10);
putchar((x%10)^48);
}
int main (void)
{
Read(n);
Read(m);
Read(t);
while(n--)
{
Read(x);
Read(y);
a[x-y<0?1:x-y+1]++;
a[x+1]--;
}
fi(i,1,300004)
a[i]+=a[i-1];
while(m--)
{
Read(x);
Print(a[x+t]);
putchar('\n');
}
return 0;
}
解法二:线段树(码量较多)
线段树区间修改和区间查询都在log级别,也是符合要求的。本题只需要写单点查询就行,所以和一般的线段树模板有一定的区别。
#include <cstdio>
#define fi(i,l,r) for(int i=(l);i<=(r);++i)
#define fd(i,r,l) for(int i=(r);i>=(l);--i)
#define lc (rt<<1)
#define rc ((rt<<1)|1)
#define mid ((R+L)>>1)
using namespace std;
const int N=300005;
int n,m,t;
int x,y;
struct arr{
int add,val;
}str[N<<2];//线段树一般要开到四倍大
template<typename T>void Read(T &x)
{
x=0;T k=1;char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-') k=-1;ch=getchar();}
while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
x*=k;
}
template<typename T>void Print(T x)
{
if(x<0){putchar('-');Print(-x);return;}//这个return很重要,某些情况可能出错
if(x>9) Print(x/10);
putchar((x%10)^48);
}
void pushUp(int rt)
{
str[rt].val=str[lc].val+str[rc].val;
}
void pushDown(int rt,int L,int R)
{
str[lc].val+=str[rt].add*(mid-L+1);
str[rc].val+=str[rt].add*(R-mid);
str[lc].add+=str[rt].add;
str[rc].add+=str[rt].add;
str[rt].add=0;
}
void Upd(int rt,int L,int R,int ul,int ur,int addVal)
{
if(L>ur||R<ul) return;
if(ul<=L&&ur>=R)
{
str[rt].add+=addVal;
str[rt].val+=addVal*(R-L+1);
return;
}
if(str[rt].add!=0) pushDown(rt,L,R);
if(ul<=mid) Upd(lc,L,mid,ul,ur,addVal);
if(ur>mid) Upd(rc,mid+1,R,ul,ur,addVal);
pushUp(rt);
}
int Query(int rt,int L,int R,int x)
{
if(L==x&&R==x) return str[rt].val;
if(str[rt].add!=0) {pushDown(rt,L,R);pushUp(rt);}
if(x<=mid) return Query(lc,L,mid,x);
else return Query(rc,mid+1,R,x);
}
int main (void)
{
Read(n);
Read(m);
Read(t);
while(n--)
{
Read(x);
Read(y);
Upd(1,1,300000,x-y<0?1:x-y+1,x,1);
}
while(m--)
{
Read(x);
Print(Query(1,1,300000,x+t));
putchar(10);
}
return 0;
}
版权声明
本文为[不考浙大不改名]所创,转载请带上原文链接,感谢
https://blog.csdn.net/qq_45351611/article/details/124240116
边栏推荐
- P1446 [hnoi2008] cards (Burnside theorem + DP count)
- Redis 异常 read error on connection 解决方案
- 面试官:说几个PHP常用函数,幸好我面试之前看到了这篇文章
- 2022年制冷与空调设备运行操作考试练习题及模拟考试
- 论文阅读《Integrity Monitoring Techniques for Vision Navigation Systems》——4视觉系统中的多故障
- PHP笔记(一):开发环境配置
- C language: expression evaluation (integer promotion, arithmetic conversion...)
- Formattime timestamp format conversion
- 杰理之通常程序异常情况有哪些?【篇】
- formatTime时间戳格式转换
猜你喜欢
ABAP CDs view with association example
SAP pi / PO function operation status monitoring and inspection
Three challenges that a successful Devops leader should be aware of
《谷雨系列》空投
Comparison of overloading, rewriting and hiding
Cloud identity is too loose, opening the door for attackers
SAP ECC connecting SAP pi system configuration
AI上推荐 之 MMOE(多任务yyds)
计算机网络安全实验二|DNS协议漏洞利用实验
《Redis设计与实现》
随机推荐
Kernel PWN learning (3) -- ret2user & kernel ROP & qwb2018 core
Cloud identity is too loose, opening the door for attackers
Go语言实践模式 - 函数选项模式(Functional Options Pattern)
NEC红外遥控编码说明
GCD of p2257 YY (Mobius inversion)
Redis expired key cleaning and deletion policy summary
2022茶艺师(初级)考试试题模拟考试平台操作
亚马逊云科技入门资源中心,从0到1轻松上云
Leetcode0587. Install fence
Kernel PWN learning (4) -- double fetch & 0ctf2018 baby
论文阅读《Integrity Monitoring Techniques for Vision Navigation Systems》——3背景
打印页面的功能实现
如何实现根据照片获取地理位置及如何防御照片泄漏地理位置
Three ways to create objects in JS
Flutter's loading animation is more interesting
Nine abilities of agile manufacturing in the era of meta universe
Construire neuf capacités de fabrication agile à l'ère métacosmique
Yarn资源调度器
Leetcode question bank 78 Subset (recursive C implementation)
Alibaba cloud architects interpret the four mainstream game architectures