题解 - Vijos

2

hpp LV 8 @ 2017-01-18 19:24:18

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
#define ll long long
struct node{
ll a;
ll b;
bool operator < (const node &A) const{
return a < A.a;
}
}d[100001];
ll dp[100001];
int main(){
ll k, m, x, y, l, r, ans = 0;
int i, j, n;
scanf("%lld %lld", &x, &y);
scanf("%d", &n);
for(i = 1; i <= n; i++){
scanf("%lld %lld", &d[i].a, &d[i].b);
dp[i] = 1;
}
sort(d + 1, d + i);
for(i = 1; i <= n; i++)
for(j = 1; j < i; j++){
if(d[i].b > d[j].b)
dp[i] = max(dp[i], dp[j] + 1);
ans = max(ans, dp[i]);
}
printf("%lld",ans);
return 0;
}
n²都能过

1

hahayang LV 10 @ 2017-07-17 13:37:42

n^2

var
  a,b:array[0..500000] of int64;
  f:array[0..500000] of longint;
  x,y:int64;
  n,i,j,s:longint;
function max(x,y:longint):longint;
begin
  if x>y then exit(x)
  else exit(y)
end;
procedure qs(l,r:longint);
var
  i,j,p:longint;
  t:int64;
begin
  i:=l;
  j:=r;
  p:=a[(l+r) div 2];
  repeat
    while a[i]<p do inc(i);
    while a[j]>p do dec(j);
    if i<=j then begin
      t:=a[i];
      a[i]:=a[j];
      a[j]:=t;
      t:=b[i];
      b[i]:=b[j];
      b[j]:=t;
      inc(i);
      dec(j)
    end;
  until i>j;
  if i<r then qs(i,r);
  if l<j then qs(l,j)
end;
begin
  readln(x,y);
  readln(n);
  for i:=1 to n do readln(a[i],b[i]);
  qs(1,n);
  fillchar(f,sizeof(f),0);
  f[1]:=1;
  b[0]:=0;
  for i:=1 to n do
    for j:=0 to i-1 do if b[i]>=b[j] then f[i]:=max(f[j]+1,f[i]);
  s:=0;
  for i:=1 to n do if f[i]>s then s:=f[i];
  write(s)
end.

0

一方T行 LV 10 @ 2014-08-15 22:07:54

program p1638;
var a,b,st:array[0..500000] of int64;
n,i,top:longint;
a1,a2:int64;
//
procedure swap(p1,p2:longint);
var k:longint;
begin
k:=a[p1];a[p1]:=a[p2];a[p2]:=k;
k:=b[p1];b[p1]:=b[p2];b[p2]:=k;
end;
//
procedure fixdui(l,r:longint);
var p1,p2:longint;
begin
p1:=l;p2:=p1 shl 1;
while ((p2+1<=r) and (a[p1]<a[p2+1])) or ((p2<=r) and (a[p1]<a[p2])) do
begin
if (p2+1<=r) and (a[p2]<a[p2+1]) then inc(p2);
swap(p1,p2);p1:=p2;p2:=p2 shl 1;
end;
end;
//
procedure dsort;
var i:longint;
begin
for i:=n div 2 downto 1 do fixdui(i,n);
for i:=1 to n-1 do
begin
swap(1,n-i+1);
fixdui(1,n-i);
end;
end;
//
procedure cmi(p:longint);
var l,r,mid:longint;
begin
l:=1;r:=top;
while (l<=r) do
begin
mid:=(l+r) div 2;
if b[p]>st[mid] then l:=mid+1
else r:=mid-1;
end;
if r=top then begin inc(top);st[top]:=b[p];end
else if b[p]<st[r+1] then st[r+1]:=b[p];
end;
//
begin
readln(a1,a2);
readln(n);
for i:=1 to n do read(a[i],b[i]);
dsort;
for i:=1 to n do cmi(i);
write(top);
end.

0

一方T行 LV 10 @ 2014-08-15 22:07:39

cmi

0

stnttbb LV 9 @ 2014-02-16 20:16:34

var
x,y:int64; a,b,f:array[0..500000] of int64; ans,i,now,n,p:longint; procedure qsort(s,t:longint);
var
i,j:longint; x,y:int64; begin
i:=s;j:=t;x:=a[i];y:=b[i]; while (i<j) do begin while (i<j) and ((a[j]>x) or ((a[j]=x) and (b[j]>=y))) do dec(j); a[i]:=a[j];b[i]:=b[j]; while (i<j) and ((a[i]<x) or ((a[i]=x) and (b[i]<=y))) do inc(i); a[j]:=a[i];b[j]:=b[i]; end; a[i]:=x;b[i]:=y; if s<i-1 then qsort(s,i-1); if j+1<t then qsort(j+1,t); end;
function erfen(l,r:longint):longint;
var
mid:longint; begin
if l=r then exit(l); mid:=(l+r) shr 1; if b[i]<f[mid] then erfen:=erfen(l,mid) else erfen:=erfen(mid+1,r); end;
begin
readln(x,y); readln(n); for i:=1 to n do readln(a[i],b[i]); qsort(1,n); ans:=1;f[1]:=b[1];now:=1; for i:=2 to n do if b[i]>f[now] then begin inc(now); f[now]:=b[i]; if now>ans then ans:=now; end else begin p:=erfen(1,now); f[p]:=b[i]; end; writeln(ans); end.

0

juan1973 LV 10 @ 2014-01-12 13:15:51

var
x,y:int64;
a,b,f:array[0..500000] of int64;
ans,i,now,n,p:longint;
procedure qsort(s,t:longint);
var
i,j:longint;
x,y:int64;
begin
i:=s;j:=t;x:=a[i];y:=b[i];
while (i<j) do
begin
while (i<j) and ((a[j]>x) or ((a[j]=x) and (b[j]>=y))) do dec(j);
a[i]:=a[j];b[i]:=b[j];
while (i<j) and ((a[i]<x) or ((a[i]=x) and (b[i]<=y))) do inc(i);
a[j]:=a[i];b[j]:=b[i];
end;
a[i]:=x;b[i]:=y;
if s<i-1 then qsort(s,i-1);
if j+1<t then qsort(j+1,t);
end;
function erfen(l,r:longint):longint;
var
mid:longint;
begin
if l=r then exit(l);
mid:=(l+r) shr 1;
if b[i]<f[mid] then erfen:=erfen(l,mid)
else erfen:=erfen(mid+1,r);
end;
begin
readln(x,y);
readln(n);
for i:=1 to n do
readln(a[i],b[i]);
qsort(1,n);
ans:=1;f[1]:=b[1];now:=1;
for i:=2 to n do
if b[i]>f[now] then
begin
inc(now);
f[now]:=b[i];
if now>ans then ans:=now;
end
else
begin
p:=erfen(1,now);
f[p]:=b[i];
{now:=p;}刚才花括号忘打了。
end;
writeln(ans);
end.

0

juan1973 LV 10 @ 2014-01-12 13:15:03

var
x,y:int64;
a,b,f:array[0..500000] of int64;
ans,i,now,n,p:longint;
procedure qsort(s,t:longint);
var
i,j:longint;
x,y:int64;
begin
i:=s;j:=t;x:=a[i];y:=b[i];
while (i<j) do
begin
while (i<j) and ((a[j]>x) or ((a[j]=x) and (b[j]>=y))) do dec(j);
a[i]:=a[j];b[i]:=b[j];
while (i<j) and ((a[i]<x) or ((a[i]=x) and (b[i]<=y))) do inc(i);
a[j]:=a[i];b[j]:=b[i];
end;
a[i]:=x;b[i]:=y;
if s<i-1 then qsort(s,i-1);
if j+1<t then qsort(j+1,t);
end;
function erfen(l,r:longint):longint;
var
mid:longint;
begin
if l=r then exit(l);
mid:=(l+r) shr 1;
if b[i]<f[mid] then erfen:=erfen(l,mid)
else erfen:=erfen(mid+1,r);
end;
begin
readln(x,y);
readln(n);
for i:=1 to n do
readln(a[i],b[i]);
qsort(1,n);
ans:=1;f[1]:=b[1];now:=1;
for i:=2 to n do
if b[i]>f[now] then
begin
inc(now);
f[now]:=b[i];
if now>ans then ans:=now;
end
else
begin
p:=erfen(1,now);
f[p]:=b[i];
end;
writeln(ans);
end.

本来题意太烦，想看题解，但是一打开。发现了SYF和RXD大牛的踪迹，于是毅然自己奋斗。
这就是最长上升序列，但第一次交还WA了一次（见程序中花括号，一开始我打了上去）
绍兴一中万岁！
BY JSB

0

S.Y.F LV 10 @ 2013-11-03 12:59:01

擦，本来一次A的；s[i]写成a[i]，数组名打错了。。
DXe

0

renxuandi LV 10 @ 2013-11-03 09:37:12

const oo=1 shl 60;
var Ans,ToT,i,j,k,L,R,Mid,m,n:Longint;
Tmp,A,b:array[1..500001] of Int64;

Procedure Qsort(L,R:Longint);
var Mid,m:Int64;
dl,dr:Longint;
Begin
dl:=l;dr:=r;
Mid:=A[(L+R) shr 1];
Repeat while A[dl]<Mid do Inc(dl);
While A[dr]>Mid do DeC(dr);
If dl<=dr then
Begin
M:=A[Dl];A[Dl]:=A[Dr];A[dr]:=M;
M:=B[Dl];B[Dl]:=B[Dr];B[Dr]:=M;
Inc(Dl);DeC(Dr);
End;
Until dl>dr;
If dl<r then Qsort(Dl,r);
If dr>L then Qsort(L,Dr);
End;

Begin
Readln(N,M);
Readln(N);
For i:=1 to N do Readln(A[i],B[i]);
Qsort(1,N);
Tmp[1]:=B[1];Tmp[2]:=oo;
ToT:=2;
For i:=2 to N do
Begin
L:=1;R:=ToT+1;
While L<=R do
Begin
Mid:=(L+R) shr 1;
If (Tmp[Mid]>=B[i])and(Tmp[Mid-1]<B[i]) then Break
Else If Tmp[Mid]<B[i] then L:=Mid+1
Else R:=Mid-1;
ENd;
Tmp[Mid]:=B[i];
If Mid=ToT then Begin Inc(ToT);Tmp[ToT]:=oo;End;
End;
Writeln(ToT-1);
End.

0

ws_f LV 9 @ 2013-10-31 14:56:37

我不知道是我的理解能力有问题还是那个题目描述有问题，我看了N遍才看明白啊！……

0

H2SO4HCLHNO3 LV 10 @ 2009-10-25 16:16:57

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

nlogn最长不降

0

dg123 LV 8 @ 2009-10-08 15:07:33

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

0

K-Boy LV 10 @ 2009-10-04 21:19:31

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

其实...........单调队列才是王道......

b[i]读入 r[1]=b[1]

for i:=2 to n do

begin

for j:=s+1 downto 1 do

if (b[i]>r[j-1]) and (b[i]

0

逍遥 LV 9 @ 2009-10-01 18:41:05

那x,y似乎没什么用!

0

mintalfance LV 10 @ 2009-09-25 12:35:18

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

program p1638;

var a,b,c,e:array[0..500000] of longint;

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

x,y:int64;

procedure qsort(x,y:longint);

var g,t,s,l,r:longint;

begin

t:=a[(x+y) div 2];s:=b[(x+y) div 2];l:=x;r:=y;

repeat while (a[l]s))do dec(r);

if lr;

if le[l]) then begin

inc(l);c[l]:=a[i];e[l]:=b[i]; end

else begin k:=l;

while (b[i]

0

oimaster LV 10 @ 2009-09-15 16:49:09

描述真让人无语……

0

xuyinuo LV 9 @ 2009-09-10 20:51:05

郁闷，提交了4次同一个程序，三次挂了，最后竟然ac了，并且前三次错的数据竟然不同

0

hxlong LV 10 @ 2009-09-05 18:09:19

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

DP+2分=0MS

0

xjx8599 LV 10 @ 2009-09-04 19:19:06

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

话说所谓的nlogn算法，不用二分也行，我写二分总出错。。。。

0

neaolee LV 8 @ 2009-08-29 18:38:09

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

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

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

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

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

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

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

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

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

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

见鬼哈，改了变量名就A了，vivid认b不认a是咋的

题解

45 条题解

抢救文件

信息

状态

开发

支持

题解

45 条题解

抢救文件

信息

状态

开发

支持

还没有账户？

登录