536 条题解
-
0
453844077 LV 10 @ 2009-08-19 16:36:47
...无聊的要死。。拿来练手了。。。
Treap：
#include
#include
using namespace std;
const bool Right=true,Left=false;
const int inf=~0U>>1;
struct Node
{
int x,pri,num;
Node* C[2];
Node(int t,int p,int n,Node* c0,Node* c1)
:x(t),pri(p),num(n){C[0]=c0;C[1]=c1;}
}TNull(-1,inf,0,NULL,NULL);
typedef Node* Tree;
Tree Null=&TNull;
struct Treap
{
Tree root;
void init()
{
root= new Node(inf,-1,1,Null,Null);
}
Tree Ratote(Tree& a,bool Direct)
{
Tree x=a->C[Direct];
a->C[Direct]=x->C[!Direct];
x->C[!Direct]=a;
a=x;
}
void Insert(int x,Tree& a)
{
if(a==Null)
{
a=new Node(x,rand(),1,Null,Null);
return;
}
if(x==a->x)
{a->num++;return;};
bool Direct=x > a->x;
Insert(x,a->C[Direct]);
if (a->pri > a->C[Direct]->pri)
Ratote(a,Direct);
}
Tree& Search(int x,Tree a)
{
if(a->x==x||a==Null) return a;
return Search(x,a->C[x > a->x]);
}
bool Exist(int x,Tree a)
{
if(a->x==x||a==Null) return a->x==x;
return Exist(x,a->C[x > a->x]);
}
void Del(int x,Tree& t)
{
if(t!=Null)
{
if(t->x!=x) Del(x,t->C[x > t->x]);
else
if(t->num>1) {t->num--;return;}
else
if(t->C[Left]==Null&&t->C[Right]==Null)
{
delete t;
t=Null;
return;
}
else
{
bool direct = t->C[Right]->pri < t->C[Left]->pri;
Ratote(t,direct);
Del(x,t->C[!direct]);
}
}
}
int DelMin()
{
Tree t=root;
while(t->C[Left]!=Null)
t=t->C[Left];
int x=t->x;
Del(x,root);
return x;
}
};
int main()
{
srand(199581);
Treap T;
T.init();
int n,k;
cin>>n;
for(int i=0;i>k;
T.Insert(k,T.root);
}
int a,b;
long long sum=0;
for(int i=1;ivalnext;
else
{
Last[lv--]=p;
p=p->down;
}
};
return Last[1]->val;
}
void insert(int v)
{
if (v==search(v))
{
Last[1]->num++;return;
}
int h=Lev();
node* p,* q;
q=NULL;
for(int i=1;inext,q);
Last[i]->next->pre=p;
Last[i]->next=p;
q=p;
}
}
void Delete(int v)
{
if (v!=search(v))
{cout1)
{Last[1]->num--;return;};
for(int i=1;ival!=v) break;
Last[i]->pre->next=Last[i]->next;
Last[i]->next->pre=Last[i]->pre;
delete Last[i];
}
}
int GetMin()
{
int t=Head[1]->next->val;
Delete(t);
return t;
}
int N=0;
int main()
{
srand(199581);
init();
int n,k;cin>>n;
for(int i=0;i>k;
insert(k);
}
int a,b;
long long sum=0;
for(int i=1;i -
0
太坚强了
快排5点超时
├ 测试数据 01：运行超时...
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 353ms
├ 测试数据 06：答案正确... 697ms
├ 测试数据 07：运行超时...
├ 测试数据 08：运行超时...
├ 测试数据 09：运行超时...
├ 测试数据 10：运行超时...
插排1点超时
├ 测试数据 01：运行超时...
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 56ms
├ 测试数据 06：答案正确... 119ms
├ 测试数据 07：答案正确... 744ms
├ 测试数据 08：答案正确... 806ms
├ 测试数据 09：答案正确... 697ms
├ 测试数据 10：答案正确... 806ms
快排+插排终于搞定了！
├ 测试数据 01：答案正确... 634ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 9ms
├ 测试数据 06：答案正确... 88ms
├ 测试数据 07：答案正确... 572ms
├ 测试数据 08：答案正确... 728ms
├ 测试数据 09：答案正确... 572ms
├ 测试数据 10：答案正确... 681ms -
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms
终于秒了！
秒杀好爽！
搞懂堆排了！
此题还是堆排好！ -
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms -
0
双队列
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms
秒了 -
0
yangfudong27 LV 8 @ 2009-08-10 14:27:41
这题用贪心就可解决。每次选最小的两堆合并。不用任何优化都可过。
......我打错一个变量，交了4次才过......
只能说我太水
-
0
handsomedon LV 7 @ 2009-08-08 11:21:13
var
n,i:longint;
sum:qword;
a:array[-1..10001] of qword;
procedure sqort(x,y:longint);
var
i,j,k:longint;
begin
i:=x;
j:=y;
k:=a[(i+j) div 2];
repeat
while a[i]k do dec(j);
if ij;
if ix then sqort(x,j);
end;
begin
readln(n);
for i:=1 to n do read(a[i]);
sqort(1,n);
for i:=2 to n-1 do begin
a[i]:=a+a[i];
inc(sum,a[i]);
end;
inc(a[n],a[n-1]);
writeln(a[n]+sum);
end.各位大牛，帮我检查一下哪里错了？？？
-
0
编译通过...
├ 测试数据 01：答案正确... 166ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 166ms
├ 测试数据 08：答案正确... 150ms
├ 测试数据 09：答案正确... 150ms
├ 测试数据 10：答案正确... 166ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：798msprogram su_he(input,output);
var
s,n,i:longint;
a:array[1..100000]of longint;
max1,max2:longint;
procedure hebing(n:longint);
var
i,j,k:longint;
begin
if n=1 then exit else
begin
max1:=maxlongint;max2:=maxlongint;
for i:=1 to n do
if a[i] -
0
var
a :array[0..20000]of longint;
i :longint;
n,ans :longint;procedure qsort(l,r:longint);
var
i,j,x,y :longint;
begin
i:=l;j:=r;
x:=a[(i+j)div 2];
repeat
while a[i]>x do inc(i);
while x>a[j] do dec(j);
if not(i>j) then begin
y:=a[i];a[i]:=a[j];a[j]:=y;
inc(i);
dec(j);
end;
until i>j;
if l -
0
秒杀~~~~~ 我是沙茶~~~~ 此代码谨献给研究者 抄袭者自助~~
var a,b:array[0..30000] of longint;
n,i,j,k,l,m,ans,min:longint;
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
procedure qsort(l,r:longint);
var i,j,mid,temp:longint;
begin
i:=l;j:=r;
mid:=a[(i+j) shr 1];
repeat
while a[i]mid do dec(j);
if ij;
if ia[i]+b[j]) then
begin
min:=a[i]+b[j];k:=3;
end;
if k=1 then inc(i,2);
if k=2 then inc(j,2);
if k=3 then begin
inc(i);inc(j);
end;
inc(m);
b[m]:=min;
dec(ans,min);
end;
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
begin
readln(n);
for i:=1 to n do
read(a[i]);qsort(1,n);
ans:=0; i:=1; j:=1; k:=0;
for l:=1 to n-1 do
begin
min:=maxlongint;
minx;
end;
writeln(ans);
end. -
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms
用堆优化的结果
453844077
LV 10
@ 2009-08-19 16:36:47
