$AT2292\ Division\ into\ Two$ $dp$
2024-09-03 13:39:37
正解:$dp$
解题报告:
不妨令$A\geq B$,于是先$sort$然后预处理判下如果有三个元素两两差都小于$B$的就直接$GG$了.
然后考虑对集合$X$进行$dp$,剩下的数放到$Y$就成.设$f_i$表示集合$X$最后一个选择的是$i$时的方案数,就有$f_i=\sum f_j,a_i-a_j\geq A$.
嗷然后因为我很呆所以我开始想的时候漏了个条件把代码打完才发现样例都过不去,,,就还需要$[j+1,i-1]$中任意两个数的差大于等于$B$.显然$j$就一段区间,前缀和优化一波就完事$QwQ$
#include<bits/stdc++.h>
using namespace std;
#define il inline
#define int long long
#define gc getchar()
#define t(i) edge[i].to
#define w(i) edge[i].wei
#define ri register int
#define rc register char
#define rb register bool
#define rp(i,x,y) for(ri i=x;i<=y;++i)
#define my(i,x,y) for(ri i=x;i>=y;--i) const int N=1e5+,mod=1e9+;
int n,a[N],A,B,f[N],sum[N],pos1,pos2,as; il int read()
{
rc ch=gc;ri x=;rb y=;
while(ch!='-' && (ch>'' || ch<''))ch=gc;
if(ch=='-')ch=gc,y=;
while(ch>='' && ch<='')x=(x<<)+(x<<)+(ch^''),ch=gc;
return y?x:-x;
}
il int dec(ri x,ri y){x-=y;if(x<)x+=mod;return x;}
il int ad(ri x,ri y){x+=y;if(x>=mod)x-=mod;return x;} signed main()
{
//freopen("2292.in","r",stdin);freopen("2292.out","w",stdout);
n=read();A=read();B=read();rp(i,,n)a[i]=read();sort(a+,a++n);if(A<B)swap(A,B);
rp(i,,n)if(a[i]-a[i-]<B)return printf("0\n"),;;f[]=sum[]=;
rp(i,,n)
{
while(a[i]-a[pos1+]>=A)++pos1;;if(pos2<=pos1)f[i]=dec(sum[pos1],pos2?sum[pos2-]:);
sum[i]=ad(sum[i-],f[i]);if(a[i]-a[i-]<B && i>)pos2=i-;
}
my(i,n,){as=ad(as,f[i]);if(i<n && a[i+]-a[i]<B)break;}printf("%lld\n", as);
return ;
}
最新文章
- 【原】理解javascript中的闭包
- Windows下安装Scala
- 电梯多媒体WinForm项目Q&;A总结
- Java中数据类型及其之间的转换
- iOS开发之 在release版本禁止输出NSLog内容
- CodeForces Round #287 Div.2
- linux系统时间同步更新
- 关于C51的中断函数要注意的几个问题
- [React] React Router: setRouteWillLeaveHook
- 再谈Java方法传参那些事
- 康复计划#4 快速构造支配树的Lengauer-Tarjan算法
- 【Alpha】Daily Scrum Meeting——Day5
- Python爬虫之模拟登录微信wechat
- requests库入门05-参数类型
- C# 注册机功能开发,机器码设计
- Maven私服(Nexus)启动创建Windows服务
- SLES12SP2使用总结
- c++ opencv 3.2 +Mfc VS2015窗体显示图片方法
- oracle 查出一个表中字段值出现次数大于2的所有记录
- [置顶] js 实现 <;input type=";file"; />; 文件上传
热门文章
- @bzoj - 2388@ 旅行规划
- Android 性感美图在线浏览APP
- 严重: Servlet.service() for servlet [jsp] threw exception java.lang.NullPointerException
- Nginx 日志记录post数据,并使用goaccess进行日志分析
- C# 递归、try
- poj 3181 Dollar Dayz(完全背包)
- Lua环境搭建之使用EditPlus搭建Lua开发环境
- .NET 创建 WebService
- Vue 获取DOM元素ref
- CodeForces 1204E";Natasha, Sasha and the Prefix Sums";(动态规划 or 组合数学--卡特兰数的应用)