[jzoj 6073] 河 解题报告 (DP)
2024-08-30 21:20:42
interlinkage:
https://jzoj.net/senior/#main/show/6073
description:
solution:
- 考虑一条河$x$被染的效果
- 显然对于一条河$i$来说,若$k_i>k_x,b_i<b_x$,那么$i$会被$x$直接染
- 这实际上启示我们可以把直线按$k$为第一关键字,$b$为第二关键字升序排序
- 又发现若$k_i>k_x,b_i>b_x$,这条河会被$x$染色的充要条件是存在$k_y>k_i>k_x,b_y<b_x$
- 这样就易得一个结论,按上述方法将直线排序,一条直线能染得部分是向右最后一个$b$比它小的和向左最后一个$b$比它大的
- 问题转化为了有$n$个区间,询问覆盖总长的方案数,注意到这些区间不存在完全包含关系,$DP$即可
- $f(n)$为染色到$n$的方案数,把这些区间按右端点排序再枚举右端点转移即可。这个可以前缀和优化
code:
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<iostream>
using namespace std;
typedef long long ll; const int N=5e5+;
const ll mo=1e9+;
int n;
struct node
{
int k,b;
int id;
}p[N];
bool cmpk(node a,node b) {return a.k==b.k?a.b<b.b:a.k<b.k;}
bool cmpb(node a,node b) {return a.b<b.b;}
struct seg
{
int l,r;
}c[N];
bool operator < (seg a,seg b) {return a.r==b.r?a.l<b.l:a.r<b.r;}
inline int read()
{
char ch=getchar();int s=,f=;
while (ch<''||ch>'') {if (ch=='-') f=-;ch=getchar();}
while (ch>=''&&ch<='') {s=(s<<)+(s<<)+ch-'';ch=getchar();}
return s*f;
}
ll f[N],s[N];
int main()
{
freopen("river.in","r",stdin);
freopen("river.out","w",stdout);
n=read();
for (int i=;i<=n;i++) p[i].b=read(),p[i].k=read();
sort(p+,p++n,cmpk);
for (int i=;i<=n;i++) p[i].id=i;
sort(p+,p++n,cmpb);
int mi=n;
for (int i=n;i>=;i--) mi=min(mi,p[i].id),c[p[i].id].l=mi;
int mx=;
for (int i=;i<=n;i++) mx=max(mx,p[i].id),c[p[i].id].r=mx;
sort(c+,c++n);
int pos=;
for (int i=;i<=n;i++)
{
while (pos<c[i].r-)
{
++pos;
s[pos]=(s[pos-]+f[pos])%mo;
}
(f[c[i].r]*=)%=mo;//这个区间可以选,也可以不选
(f[c[i].r]+=s[c[i].r-]-(c[i].l>=?s[c[i].l-]:)+mo)%=mo;
if (c[i].l==) (f[c[i].r]+=)%=mo;
}
printf("%lld\n",f[n]%mo);
return ;
}
最新文章
- app使用微信支付成功后,点击返回到该app却跳到另外一个app去了
- 错误代码:ERR_UNSAFE_PORT
- Gauss elimination Template
- Spring相框
- 使用adb shell启动特定activity
- 深入了解Android蓝牙Bluetooth——《基础篇》
- 安装 cgilib 0.5
- es6学习笔记--新数据结构Set,Map以及WeakSet,WeakMap
- erlang进程概述
- C#线程安全使用(三)
- vue的事件处理梳理
- zabbix通过自动发现tomcat应用端口监控连接数
- NFS服务配置
- 牛客多校10 D Rikka with Prefix Sum 不是数据结构
- sql 循环语句几种方式(变量循环,游标循环,事务)
- mySQL 教程 第2章 安装和介绍mySQL
- Unity学习笔记(3):一些常用API和应用场景
- OK6410 rmmod卸载模块失败:No such file or directory -- 转
- [转载]Java抽象类和接口的学习
- 彻底解密C++宽字符(一)