直接裸奔……

编译通过...

├ 测试数据 01：运行超时...

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 41ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 25ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：运行超时...

├ 测试数据 09：运行超时...

├ 测试数据 10：运行超时...

---|---|---|---|---|---|---|---|-

Unaccepted 有效得分：60 有效耗时：66ms

看题解…队列维护+二分+边界注意…

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

-.-

NlgN导弹拦截

（队列，二分）

为什么我没有秒杀！！！！！

哈哈 第一次编对二分查找了！！！！

庆祝一下!!!

另：只用单调队列优化会超时！！！！

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

---|---|---|---|---|---|---|晒程序啊---|---|---|---|---|---|-

var

a,s:array[0..300001] of longint;

f:array[0..300001] of boolean;

n,k,i,j,t:longint;

function find(l,r,x:longint):longint;

var y:longint;

begin

if r-l=1 then exit(l);

y:=(l+r) div 2;

if x=s[y] then exit(y);

if x>s[y] then find:=find(y,r,x)

else find:=find(l,y,x);

end;

begin

readln(n,k);

for i:=1 to n do

read(a[i]);

for i:=1 to k-1 do

if a[i]

一般化方法：

在第k个前面且大于第k个数字的设为-inf,

在第k个后面且小于第k个数字的设为+inf.

注意要用大于int 类型。

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 9ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：9ms

编译通过...

├ 测试数据 01：答案错误...　├ 标准行输出

　├ 错误行输出

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 9ms

---|---|---|---|---|---|---|---|-

Unaccepted 有效得分：90 有效耗时：9ms

不明真相...cheat

60 70分的看过来

如果二分是 l+1《r的

注意更新队列是1的特殊性 还有一定不能 r=mid-1 要r=mid 因为r=mid-1有可能变成0

不明白的用这组数据看看 不要看答案 看队列的更新 我在这里挂了1个小时

14 3

0 0 0 6 8 4 5 6 7 9 8 9 5

在第6个地方 注意队列的第一位更新情况

找了一篇讲 LIS的文章，看了好久才懂....

关于二分查找怎么写的问题：这个写的不错 最后的 p 是 接上去之后的长度；

for(int i = 1;i

这是教主出的题，该题就是最长上升序列的优化版，分前后两段考虑前一段的最大值不能大于a[k]，后一段的最小值不能小于a[k]，动归：b[i]为长度为i的最长上升序列的最后一个数的最小值，用二分查找，可以达到nlogn的复杂度。

注意！！最后要打的东西是长度，不是序列！！！！

左右分开处理

左边加上一个条件即可:

if(l>0 || i==k)

s[l+1]=max(s[l+1],x[i]);

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

写了 个极猥琐 的 二分 ， 结果竟然 秒杀 了……

function xx(x:longint):longint;

var

i,j:longint;

begin

if x>b[num] then

begin

inc(num);

b[num]:=x;

exit(num);

end;

i:=1;j:=num;

repeat

while (b[(i+j)shr 1]=x)and(j(i+j)shr 1) do

j:=(i+j)shr 1;

until i+1>=j;

if b[i]>=x then begin b[i]:=x;exit(i);end

else begin b:=x;exit(i+1);end;

end;

f[i]:=xx(a[i]);

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 25ms

program haoshui;

var

a,b,c,d,e,f,g:longint;

m,n,k:longint;

arr,brr,crr:array[0..300000] of longint;

function main(a,n:longint):longint;

var

i,x,l,r,mid:longint;

begin

if a>n then exit(0);

m:=1;

crr[1]:=brr[a];

for i:=a+1 to n do begin

x:=brr[i];

if x>crr[m] then begin inc(m); crr[m]:=x; end;

l:=1; r:=m;

while l

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－

var

i,j,k,n,m:longint;

a,f,g:array[0..300000]of longint;

procedure li(x,l,r:longint);

var

i,j,mid:longint;

begin

if a[x]g[mid]

then run(x,mid,r)

else run(x,l,mid);

end;

begin

read(n,m);

for i:=1 to n do

read(a[i]);

f[0]:=a[m];

k:=0;

for i:=m downto 1 do

if a[i]g[0]

then run(i,0,k);

write(k+j+1);

end.

就是以m为起点　分别做一次m downto 1 的最长递减，与m to n 的最长上升．

注意点m为起点不可更新，判断一下即可AC.

90分，干了见降rp的事，cheat了~~~~

我的方法是把k前面小于k的放到另一数组，k后面大于k的也放过去，然后LIS，但为什么第一个点标准输出事601，而我的是603，我的算法错了么？

首先数据范围肯定得用O(nlogn)算法

在1~k时候常规做法

在k+1~n的时候把前面的数组清零，并把b[0]设为a[k]

而且必须要mid!=0时才更新，这样后面就是第一项是a[k]的最长上升子序列长度

最后在d[k+1]~d[n]找出最大的，输出max+d[k]即可

虽然没全0不过一共72ms~~很有成就感的说

program p1369;

var i,j,k,mid,l,r,n:longint;

max,js:int64;

a,d:array [0..300010] of longint;

begin

read(n,k);

for i:=1 to n do begin read(a[i]);d[i]:=maxlongint;end;

for i:=1 to k-1 do

begin

if a[i]1 do

begin

mid:=(r+l)div 2;

if d[mid]>a[i] then r:=mid else l:=mid;

end;

if d[r]a[k] then

begin

l:=0;r:=max;

while r-l>1 do

begin

mid:=(r+l)div 2;

if a[i]

编译通过...

├ 测试数据 01：运行超时...

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 88ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 41ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：运行超时...

├ 测试数据 09：运行超时...

├ 测试数据 10：运行超时...

---|---|---|---|---|---|---|---|-

Unaccepted 有效得分：100有效耗时：129ms

编译通过...

├ 测试数据 01：答案错误...　├ 标准行输出

　├ 错误行输出

├ 测试数据 02：答案错误...　├ 标准行输出

　├ 错误行输出

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案错误...程序输出比正确答案长

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案错误...　├ 标准行输出

　├ 错误行输出

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案错误...　├ 标准行输出

　├ 错误行输出

---|---|---|---|---|---|---|---|-

Unaccepted 有效得分：50 有效耗时：0ms

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

难得一次A