编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

SBT is a kind of BT.

Maybe is also a kind of SB...

是左上角，不是左下角，敬请注意。本人为此思考了1S

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

快排再搜索，秒杀。

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

#include "stdio.h"

int main()

{

int zhan[15001][3];

int flag[15001]={0};

int i,j,n,s;

scanf("%d",&n);

for(i=1;i

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

直接枚举都过了...

用标准的树状数组写的。。。

#include

using namespace std;

const int MaxN = 15010;

struct Star {

int x, y;

} S[MaxN];

int N;

int c[MaxN];

int Ans[MaxN];

int cmp(const void *a, const void b) {

if (((Star ) a).x != ((Star ) b).x) return ((Star ) a).x - ((Star ) b).x;

else return ((Star ) a).y - ((Star *) b).y;

}

int L_Bit(int k) {

return k & (k ^ (k - 1));

}

void Update(int k) {

while (k 0) {

Res += c[k];

k -= L_Bit(k);

}

return Res;

}

int main() {

int i;

scanf("%d", &N);

for (i = 0; i < N; i++) scanf("%d%d", &S[i].x, &S[i].y);

qsort(S, N, sizeof (Star), cmp);

for (i = 0; i < N; i++) S[i].x = S[i].y, S[i].y = i + 1;

qsort(S, N, sizeof (Star), cmp);

for (i = 0; i < N; i++) {

Ans[G_Sum(S[i].y)]++;

Update(S[i].y);

}

for (i = 0; i < N; i++)

printf("%d\n", Ans[i]);

return 0;

}

有人说这道题用动态规划，我觉得这样叫不妥。

动态规划是要满足其一条性质的——最优子结构，所以这道题是不能叫做动态规划的。

叫做递推还差不多。当然，用树状数组或者线段树一样可以解决。

用快排=秒杀

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

数据范围看成15W，居然上了AVL。。。

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

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

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

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

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

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

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

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

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

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

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

完全裸搜

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

用Treap做的，练习一下，效果不错

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

先对X坐标进行排序，问题转化为在Y序列中求满足

YJ的方案

可以用动态规划实现

用F表示前I个数不大于J的个数

可以用滚动数组实现,时间复杂度为O(N^2)

如果只求AC此题,到这里就足够了,因为此题数据实在太弱,15000的平方随便

过.

但如果要0ms通过,可以用线段树或是树状数组优化到NlogN.

我用的是树状数组,关键代码如下.

For I:=1 to N do

Begin

J:=Y;

T:=0;

While(J>0)Do

Begin

Inc(T,F[J]);

J:=J Xor LowBit(J);//lowbit有多种求法,如 Not(X-1) And X

End;

Inc(Ans[T]);//T为前I个数中小于Y的个数

J:=Y;

While(J

在我没学动归之前

我研究这道题研究了一个多小时都没做出来

在我学了动归之后

我慢慢吞吞地10分钟就AC了

啊，学习带给人们智慧

秒杀！！

建议大家还是虚二叉树做吧。

枚举也显得我们oiers太没水平了是不？

编译通过...

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

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

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

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

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

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

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

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

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

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

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

郁闷……以为能全0呢……

是用升级版导弹拦截做的~~二维最长不下降子序列……

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

晕~~

枚举也可以如此爽快的过！！！

9ms啊~~！！！

var

a:array[1..15000]of record

x,y:longint;

end;

b:array[0..14999]of longint;

n,i,j,t:longint;

begin

readln(n);

for i:=1 to n do begin read(a[i].x);read(a[i].y);end;

for i:=1 to n do

begin

t:=0;

for j:=1 to n do

if (ji)and(a[i].x>=a[j].x)and(a[i].y>=a[j].y) then t:=t+1;

b[t]:=b[t]+1;

end;

for i:=0 to n-1 do writeln(b[i]);

end.

如果你想学东西那么此题可以用 线段树 树状数组 虚二叉树.(可以交到ural1028)

如果你只想+ac数 请用枚举 ._.