bzoj4584
2024-09-26 21:16:04
escription
在首尔城中,汉江横贯东西。在汉江的北岸,从西向东星星点点地分布着个划艇学校,编号依次为到。每个学校都
拥有若干艘划艇。同一所学校的所有划艇颜色相同,不同的学校的划艇颜色互不相同。颜色相同的划艇被认为是一
样的。每个学校可以选择派出一些划艇参加节日的庆典,也可以选择不派出任何划艇参加。如果编号为的学校选择
派出划艇参加庆典,那么,派出的划艇数量可以在Ai至Bi之间任意选择(Ai<=Bi)。值得注意的是,编号为i的学
校如果选择派出划艇参加庆典,那么它派出的划艇数量必须大于任意一所编号小于它的学校派出的划艇数量。输入
所有学校的Ai、Bi的值,求出参加庆典的划艇有多少种可能的情况,必须有至少一艘划艇参加庆典。两种情况不同
当且仅当有参加庆典的某种颜色的划艇数量不同
Input
第一行包括一个整数N,表示学校的数量。接下来N行,每行包括两个正整数,用来描述一所学校。其中第行包括的
两个正整数分别表示Ai,Bi(1<=Ai<=Bi<=10^9),N<=500
Output
输出一行,一个整数,表示所有可能的派出划艇的方案数除以1,000,000,007得到的余数
Sample Input
2
1 2
2 3
Sample Output
7
想出来之后不难,挺基础的。
由于AI,BI范围实在太大,所以要考虑离散化,最多一共有2*n-1个可行区间。
用lenj表示区间长度。
然后dp方程就很显然了。
注意,每个学校可以选择不放,所以每次dp方程不用清空,直接累加就好。
思路很简单,写完之后发现一个致命的问题。
唉?TLE了?
怎么办???
卡常,换成register int,加上各种优化。
详细见代码。
#include<bits/stdc++.h>
using namespace std;
const int mod=;
#define ll long long
#ifdef ONLINE_JUDGE
char *TT,*mo,but[(<<)+];
#define getchar() ((TT==mo&&(mo=(TT=but)+fread(but,1,1<<15,stdin)),TT==mo)?0:*TT++)
#endif
inline int read(){
int x=,c=,f=;
for(;c<''||c>'';c=getchar())f=c!='-';
for(;c>=''&&c<='';c=getchar())x=x*+c-'';
return f?x:-x;
}
int dp[][];
int p[];
int len[];
int inv[];
int a[],b[];
int d[];
int cnt;
int ct[];
int n;
int main(){
n=read();
register int i,j,k;
for(i=;i<=n;i++)a[i]=read()-,b[i]=read();
for(i=;i<=n;i++){
d[++cnt]=a[i];
d[++cnt]=b[i];
}
sort(d+,d+cnt+);
cnt=unique(d+,d+cnt+)-d-;
for(i=;i<=cnt;i++){
len[i-]=d[i]-d[i-];
}
inv[]=;
for(i=;i<=n;i++)inv[i]=1ll*inv[mod%i]*(mod-mod/i)%mod;
for(i=;i<=n;i++)a[i]=lower_bound(d+,d+cnt+,a[i])-d,b[i]=lower_bound(d+,d+cnt+,b[i])-d;
for(i=;i<cnt;i++)p[i]=; for(i=;i<=n;++i){
for(j=a[i];j<b[i];++j){
ct[j]++;
for(k=ct[j];k>=;--k){
dp[j][k]=(dp[j][k]+1ll*dp[j][k-]*(len[j]+-k)%mod*inv[k]%mod)%mod;
}
dp[j][]=(dp[j][]+1ll*p[j-]*len[j])%mod;
}
for(j=a[i];j<cnt;++j){
p[j]=p[j-];
for(k=;k<=ct[j];k++)
p[j]=(p[j]+dp[j][k])%mod;
}
}
cout<<p[cnt-]-;
return ;
}
最新文章
- 怎么将java web 项目导入idea 中
- Fragment 代码怎么写
- 获取本地soapUI项目路径
- 【转】What is an entity system framework for game development?
- leetcode 41 First Missing Positive ---java
- java中abstract
- java-swing在组件中显示信息
- Jquery 计算表格某一列的合计
- Springmvc构造RESTful详细讲解
- Js处理json数据
- 【3】创建一个简单的Laravel例子
- deferred initcalls与模块化
- 玩转Bootstarp(连载)
- H5加载优化
- maven之pom
- Sql server DATEADD日期函数的使用
- Python_socket常见的方法、网络编程的安全注意事项、socketsever模块、浏览器中在一段时间记录用户的登录验证机制
- 2015-10-13 jQuery5实例
- 高效的MySQL分页——利用子查询分页
- Okhttp源码简单解析(一)
热门文章
- python5
- 使用Git提交与管理代码
- 亚马逊CEO贝索斯致股东信:阐述公司未来计划
- react native组件的创建
- scrum立会报告+燃尽图(第三周第一次)
- 互评Alpha版本——杨老师粉丝群——Pinball
- 记录 C++ STL 中 一些好用的函数--持续更新 (for_each,transform,count_if,find_if)
- web项目页面加载时,下拉框有值
- 未能加载文件或程序集“log4net, Version=1.2.10.0, Culture=neutral, PublicKeyToken=1b44e1d426115821”或它的某一个依赖项。系统找不到指定的文件。
- 判断字符串中是否存在的几种方案:string.indexof、string.contains、list.contains、list.any几种方式效率对比