36 条题解
-
2852741 LV 10 @ 2018-08-16 17:51:17
本题考查很全面 线段树(单点修改+区间查询+区间最大值)+离散化+DP+二分查找
线段树方面:对于每一个在s[i]+t与s[i]-t之间的高度(离散化)进行累加 最大值与sum值分开计算
离散化:用了Rank来记录第1个元素的编号(从小到大)
DP: 对于i 最大的方案长度={距离不超过t的所有人中最大的方案长度}+1 i的方案={i之前不超过t的所有人的总方案}+1
这题BT...狂打120ROW
话不多说,代码上:
#include<cstdio>
#include<algorithm>
const int MAXN=100100;
const int MOD=198964;
using namespace std;
struct Tree {
int l,r,maxv,sum,add;
#define l(x) tree[x].l
#define r(x) tree[x].r
#define maxv(x) tree[x].maxv
#define sum(x) tree[x].sum
#define add(x) tree[x].add
#define lch (o<<1)
#define rch (o<<1|1)
} tree[MAXN<<2];
inline int max(int a,int b) {
return a>b?a:b;
}
inline int read(){
int x=0;
char ch=getchar(),w=1;
while(ch<'0'||ch>'9'){
if(ch=='-')w=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+ch-'0';
ch=getchar();
}
return x*w;
}
void build(int o,int l,int r) {
l(o)=l,r(o)=r,maxv(o)=sum(o)=add(o)=0;
if(l==r)return;
int mid=(l+r)>>1;
if(l<=mid)build(lch,l,mid);
if(r>mid)build(rch,mid+1,r);
return;
}
int ask_max(int o,int l,int r) {
if(l(o)>=l&&r(o)<=r)return maxv(o);
if(l(o)==r(o))return maxv(o);
int mid=(l(o)+r(o))>>1,val=0;
if(l<=mid)val=ask_max(lch,l,r)%MOD;
if(r>mid)val=max(val,ask_max(rch,l,r))%MOD;
return val;
}
int ask_sum(int o,int l,int r) {
if(l(o)>=l&&r(o)<=r)return sum(o);
int mid=(l(o)+r(o))>>1,val=0;
if(l<=mid)val=ask_sum(lch,l,r)%MOD;
if(r>mid)val=(val+ask_sum(rch,l,r))%MOD;
return val;
}
int wl,wr;
void change(int o,int pos,int v) {
if(l(o)==r(o)) {
add(o)=(add(o)+v)%MOD;
sum(o)=(sum(o)+v)%MOD;
maxv(o)=ask_max(1,wl,wr)+1;
return;
}
int mid=(l(o)+r(o))>>1;
if(pos<=mid)change(lch,pos,v);
if(pos>mid)change(rch,pos,v);
sum(o)=(sum(o)+v)%MOD;
maxv(o)=max(maxv(lch),maxv(rch));
}
int Rank[MAXN],s[MAXN],a[MAXN],m=0,h[MAXN],n,t,tot=0;
bool cmp(int x,int y) {
return s[x]<s[y];
}
int findl(int x) {
int l=0,r=n;
while(r-l>1) {
int mid=(l+r)>>1;
if(a[mid]>=x)r=mid;
else l=mid;
}
return h[Rank[r]];
}
int findr(int x) {
int l=1,r=n+1;
while(r-l>1) {
int mid=(l+r)>>1;
if(a[mid]<=x)l=mid;
else r=mid;
}
return h[Rank[l]];
}
int main() {n=read();t=read();
for(int i=1; i<=n; i++) {
s[i]=read();
a[i]=s[i];
Rank[i]=i;
}
sort(Rank+1,Rank+1+n,cmp);
sort(a+1,a+1+n);
a[0]=-1;
for(int i=1; i<=n; i++) {
if(a[i]!=a[i-1])m++;
h[Rank[i]]=m;
}
build(1,1,m);
for(int i=1; i<=n; i++) {
wl=findl(s[i]-t);
wr=findr(s[i]+t);
int ret=ask_sum(1,wl,wr);
tot=(tot+ret)%MOD;
change(1,h[i],ret+1);
}
printf("%d\n",tot);
if(maxv(1)!=1)printf("%d\n",maxv(1));
else puts("0");
return 0;
}
注意,已经AC了 -
02017-04-28 07:10:31@
DP的时候f[i]最开始设计成1~i中最长序列,但是转移的时候f[i]=max(f[i-1],pre[i]?(f[pre[i]]+1):0);
pre[i]为i之前第一个与其相邻差小于等于h的数的位置。
这样的话因为第i个数可以不取的(决策1)所以决策2中的f[pre[i]]也可能是从i之前与其差大于h的数开始取的。。就出现了问题。
所以要改成固定序列最后一位取什么的状态。 -
02016-05-07 11:21:01@
用treap写的,比较慢。。。。
话说为啥要模198964。。。。测试数据 #0: Accepted, time = 15 ms, mem = 15440 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 15444 KiB, score = 10
测试数据 #2: Accepted, time = 15 ms, mem = 15444 KiB, score = 10
测试数据 #3: Accepted, time = 46 ms, mem = 15444 KiB, score = 10
测试数据 #4: Accepted, time = 93 ms, mem = 15444 KiB, score = 10
测试数据 #5: Accepted, time = 109 ms, mem = 15440 KiB, score = 10
测试数据 #6: Accepted, time = 171 ms, mem = 15444 KiB, score = 10
测试数据 #7: Accepted, time = 359 ms, mem = 15444 KiB, score = 10
测试数据 #8: Accepted, time = 421 ms, mem = 15448 KiB, score = 10
测试数据 #9: Accepted, time = 406 ms, mem = 15444 KiB, score = 10
Accepted, time = 1635 ms, mem = 15448 KiB, score = 100 -
02014-04-17 19:42:12@
千万记住最大的方案也要模……
-
02012-09-15 16:10:43@
编译通过...
├ 测试数据 01:答案正确... (3ms, 8400KB)
├ 测试数据 02:答案正确... (0ms, 8400KB)
├ 测试数据 03:答案正确... (0ms, 8400KB)
├ 测试数据 04:答案正确... (0ms, 8400KB)
├ 测试数据 05:答案正确... (14ms, 8400KB)
├ 测试数据 06:答案正确... (18ms, 8400KB)
├ 测试数据 07:答案正确... (10ms, 8400KB)
├ 测试数据 08:答案正确... (190ms, 8400KB)
├ 测试数据 09:答案正确... (175ms, 8400KB)
├ 测试数据 10:答案正确... (175ms, 8400KB)---|---|---|---|---|---|---|---|-
Accepted / 100 / 588ms / 8400KB真是辛苦,前面百度博客的题解全挂了,费了好多功夫才自己想出来,另外此题细节非常恶心!
我们很容易写出两个简单的DP方程,然后用线段树维护最值,和。
一个关键的问题就是离散化,但是有h太大,使得离散化受到了约束。
方法如下:
离散化之后,因为每个数扫描的范围就不是a[i]正负H了,
所以我们可以把每个数的扫描范围重新更新(关键)
范围的确定,可以预处理出来,把离散化后的排序再二分查找。
把上下边界算出来后,在DP中加入线段树的查找即可
下面是注意的细节:
1.题意,长度为1的情况输出0,模198964(这个数字很和谐。。)
2.二分查找下边界是大于或等于v的数,上边界是小于或等于v的数
3.线段树的每个节点的sum值都要取模! -
02010-07-03 18:18:05@
第100人通过- -
-
02010-03-03 22:41:57@
Accepted 有效得分:100 有效耗时:372ms
蛮好玩的题啊``不过我比较悲剧,第一次提交没取模,第二次每输出无解.....第三次才过.....线段树乱搞啦,,,不用二分吧...
写了点题解额,,
http://hi.baidu.com/darin7/blog/item/578592af6a3fa8024a36d634.html -
02009-11-01 22:57:04@
198964
看成了198946
难道我真的跟一次AC线段树无缘? -
02009-11-01 21:58:04@
评测机太神奇了
自己机子上将近2S的
交上来只用了400MS
AC了就好
AC经典题了
强大的离散线段树
兴奋把 -
02009-10-22 19:52:21@
少有的一遍AC
我的blog有代码和稍微的提示;(copy无意义)
http://hi.baidu.com/think%5Fexist/blog/item/6308a9d4e3c5f22506088b2f.html -
02009-10-01 17:07:00@
编译通过...
├ 测试数据 01:答案正确... 0ms
├ 测试数据 02:答案正确... 0ms
├ 测试数据 03:答案正确... 0ms
├ 测试数据 04:答案正确... 0ms
├ 测试数据 05:答案正确... 72ms
├ 测试数据 06:答案正确... 103ms
├ 测试数据 07:答案正确... 181ms
├ 测试数据 08:答案正确... 524ms
├ 测试数据 09:答案正确... 586ms
├ 测试数据 10:答案正确... 571ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分:100 有效耗时:2037ms哇蛤蛤 竟然一次AC 太神奇啦!!!!!!!!
-
02009-09-27 14:05:34@
要判断 长度为 0 的情况的说...
-
02009-09-19 15:40:22@
线段树+离散化
-
02009-08-05 14:43:24@
1A,线段树啊,中间用了很多二分查找,速度慢到867MS dragon;607ms puppy
-
02009-07-31 13:08:12@
-
02009-07-26 19:00:43@
编译通过...
├ 测试数据 01:答案正确... 0ms
├ 测试数据 02:答案正确... 0ms
├ 测试数据 03:答案正确... 0ms
├ 测试数据 04:答案正确... 0ms
├ 测试数据 05:答案正确... 0ms
├ 测试数据 06:答案正确... 9ms
├ 测试数据 07:答案正确... 41ms
├ 测试数据 08:答案正确... 338ms
├ 测试数据 09:答案正确... 338ms
├ 测试数据 10:答案正确... 275ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分:100 有效耗时:1001ms
把Splay注释掉...
boyzkk...你失算了
哈哈哈哈哈哈... -
02009-07-26 18:46:36@
编译通过...
├ 测试数据 01:答案正确... 0ms
├ 测试数据 02:答案正确... 0ms
├ 测试数据 03:答案正确... 0ms
├ 测试数据 04:答案正确... 0ms
├ 测试数据 05:答案正确... 41ms
├ 测试数据 06:答案正确... 119ms
├ 测试数据 07:答案正确... 212ms
├ 测试数据 08:答案正确... 666ms
├ 测试数据 09:答案正确... 697ms
├ 测试数据 10:答案正确... 588ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分:100 有效耗时:2323ms
Orz fengdieqiao!!!
Splay 太慢了,有空写线段树。
注意在旋转的时候也要mod。 -
02009-07-08 13:47:55@
Accepted 有效得分:100 有效耗时:1866ms
话说我写的线段树从来就比大家的慢半拍,估计是用了结构体的缘故吧.注意那个mod..
如果出个数据,方案数正好是那个不和谐的数的倍数的话,还得判断是真的零还是假的零了.. -
02009-06-18 14:42:08@
编译通过...
├ 测试数据 01:答案正确... 0ms
├ 测试数据 02:答案正确... 0ms
├ 测试数据 03:答案正确... 0ms
├ 测试数据 04:答案正确... 0ms
├ 测试数据 05:答案正确... 0ms
├ 测试数据 06:答案正确... 9ms
├ 测试数据 07:答案正确... 41ms
├ 测试数据 08:答案正确... 244ms
├ 测试数据 09:答案正确... 259ms
├ 测试数据 10:答案正确... 259ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分:100 有效耗时:812ms对与第三次写线段树的我来说,能一次AC简直是奇迹!
-
02009-05-25 10:39:05@
终于AC了,提醒一句:
线段树插入点的时候要从上往下,不能从下往上,不然mod就是不对,至于为什么我也不知道……囧……
Orz...