洛谷P3353 【在你窗外闪耀的星星】
2024-10-06 21:40:18
题目真的好甜呢QwQ
冲着这题面也要来做
满分解法:线段树
我们暴力地把所有点建成一颗线段数
接着在从1到maxx里每个长度为 w的区间中执行区间求和
其实单点修改都不需要,可以在输入的时候统计出每个点上星星的亮度和
另:同一点上可能有多个星星
#include<bits/stdc++.h>
#define inf 0x7fffffff
#define ll long long
using namespace std;
#define maxn 100009
struct node{
int l,r,val;
}tr[maxn*];
int n;
int a[maxn];
void Buildtree(int x,int l,int r)
{
tr[x].l=l;
tr[x].r=r;
if(l==r)
{
tr[x].val=a[l];
return;
}
int mid=(l+r)>>;
Buildtree(x*,l,mid);
Buildtree(x*+,mid+,r);
tr[x].val=tr[x*].val+tr[x*+].val;
}
int Query(int x,int l,int r)
{
if(l<=tr[x].l&&tr[x].r<=r)
{
return tr[x].val;
}
int mid=(tr[x].l+tr[x].r)/;
int ans=;
if(l<=mid) ans+=Query(x*,l,r);
if(r>mid) ans+=Query(x*+,l,r);
return ans;
}
int main()
{
int maxx=;
int w;
scanf("%d%d",&n,&w);
for(int i=;i<=n;i++)
{
int x,y;
scanf("%d%d",&x,&y);
a[x]+=y;
maxx=max(maxx,x);
}
Buildtree(,,maxx);
//建树的范围是所有点,从1到最大点的位置 int ans=;
for(int i=;i<=maxx;i++)
{
ans=max(ans,Query(,i,i+w-));//记得w-1
/*
窗框算在W之内
W=3
框 星 框
| * |
------------------------
*/
}
printf("%d\n",ans);
return ;
}
最新文章
- VS2015 Git 源码管理工具简单入门
- 启动Tomcat报异常host-manager does not exist or is not a readable directory
- 【总结】总结写了3个React页面后遇到的各种坑
- CVTE实习面经
- codeforces 725D . Contest Balloons(贪心+优先队列)
- C/C++中函数参数传递详解(二)
- 敏捷开发之道(二)极限编程XP
- 远程控制篇:在DELPHI程序中拨号上网
- dtrace4linux
- Java中x+=y和x=x+y两种实现的区别
- 验证浏览器是否安装已flash插件的js脚本
- dva + antd + mockjs 实现基础用户管理
- studio中碰到的jni问题:java.lang.UnsatisfiedLinkError
- egret 添加帧动画
- vue监听滚动事件-元素固定位置显示
- Python对elasticsearch的CRUD
- faster rcnn 做识别
- MySQL5.7 虚拟列实现表达式或函数索引
- oj错误之char型超出范围
- 20155204 王昊《网络对抗技术》EXP2 后门原理与实践