#include <stdio.h>

int n, order, a[1001];

char isHeap(int p)
{
    char is_heap = 1;
    if (p * 2 <= n)
    {
        if (a[p] * order < a[p * 2] * order) return 0;
        is_heap = isHeap(p * 2);
    }
    if (p * 2  + 1 <= n)
    {
        if (a[p] * order < a[p * 2 + 1] * order) return 0;
        is_heap = is_heap && isHeap(p * 2 + 1);
    }
    return is_heap;
}

char isBST(int p)
{
    char is_BST = 1;
    if (p * 2 <= n)
    {
        if (a[p] * order < a[p * 2] * order) return 0;
        is_BST = isBST(p * 2);
    }
    if (p * 2  + 1 <= n)
    {
        if (a[p] * order > a[p * 2 + 1] * order) return 0;
        is_BST = is_BST && isBST(p * 2 + 1);
    }
    return is_BST;
}

int main()
{
    int q;
    scanf("%d", &q);
    for (int i = 1; i <= q; i++)
    {
        scanf("%d", &n);
        for (int j = 1; j <= n; j++)
            scanf("%d", &a[j]);
        order = 1;
        char is_heap = isHeap(1), is_BST = isBST(1);
        order = -1;
        is_heap = is_heap || isHeap(1);
        is_BST = is_BST || isBST(1);
        if (is_heap && is_BST)
            printf("Case #%d: Both\n", i);
        else if (is_heap)
            printf("Case #%d: Heap\n", i);
        else if (is_BST)
            printf("Case #%d: BST\n", i);
        else
            printf("Case #%d: Neither\n", i);
    }
}

我一直以为的堆的定义居然是错的....微醉

40+行的代码默默的看着你们
递归即可
#include<cstdio>
#include<cstring>
using namespace std;

const int maxn=3000;
bool heap1[maxn],heap2[maxn],bst1[maxn],bst2[maxn];
int a[maxn],n;

void solve(int root) {
int l=root*2,r=root*2+1;
bool c1=1,c2=1;
if (a[l]==-1) {
heap1[l]=heap2[l]=bst1[l]=bst2[l]=1;
c1=0;
} else solve(l);
if (a[r]==-1) {
heap1[r]=heap2[r]=bst1[r]=bst2[r]=1;
c2=0;
} else solve(r);
heap1[root]=heap1[l]&&heap1[r]&&(c1?a[l]<a[root]:1)&&(c2?a[r]<a[root]:1);
heap2[root]=heap2[l]&&heap2[r]&&(c1?a[l]>a[root]:1)&&(c2?a[r]>a[root]:1);
bst1[root]=bst1[l]&&bst1[r]&&(c1?a[l]<a[root]:1)&&(c2?a[r]>a[root]:1);
bst2[root]=bst2[l]&&bst2[r]&&(c1?a[l]>a[root]:1)&&(c2?a[r]<a[root]:1);
}

int main() {
int t; scanf("%d",&t);
for (int T=1;T<=t;++T) {
scanf("%d",&n);
memset(heap1,0,sizeof(heap1));
memset(heap2,0,sizeof(heap2));
memset(bst1,0,sizeof(bst1));
memset(bst2,0,sizeof(bst2));
memset(a,-1,sizeof(a));
for (int i=1;i<=n;++i) scanf("%d",&a[i]);
solve(1);
bool heap=heap1[1]||heap2[1];
bool bst=bst1[1]||bst2[1];
if (heap&&bst)
printf("Case #%d: Both\n",T);
else if (heap)
printf("Case #%d: Heap\n",T);
else if (bst)
printf("Case #%d: BST\n",T);
else
printf("Case #%d: Neither\n",T);
}
return 0;
}

C++11有一个is_heap函数....
但是VJ不支持C++11 TAT

#include<stdio.h>

int main()
{int n,i,j;
scanf("%d",&n);
int a[n+1][1001],p[n+1];//a[]里面是权值，p[]里面是节点数
for(i=1;i<=n;i++)
{
scanf("%d",&p[i]);
for(j=1;j<=p[i];j++)
scanf("%d",&a[i][j]);
}

int big,small,up,down,sum;

int q=0;

for(i=1;i<=n;i++)
{
sum=0;up=0;down=0;small=0;big=0;
if(p[i]%2==0)
p[i]=p[i]+1;

for(j=1;j<=(p[i]-1)/2;j++)
{
if(a[i][j]>=a[i][j*2]&&a[i][j]>=a[i][j*2+1])
q++;
}
if(q==(p[i]-1)/2)
big=2;
else
big=0;
q=0; //大根堆

for(j=1;j<=(p[i]-1)/2;j++)
{
if(a[i][j]<=a[i][j*2]&&a[i][j]<=a[i][j*2+1])
q++;
}
if(q==(p[i]-1)/2)
small=2;
else
small=0;
q=0; //小根堆

for(j=1;j<=(p[i]-1)/2;j++)
{
if((a[i][j]>a[i][j+j+1])&&(a[i][j]<a[i][j+j]))
{q=q+1;}
}
if(q==(p[i]-1)/2)
down=10;
else
down=0;
q=0; //降序树

for(j=1;j<=(p[i]-1)/2;j++)
{
if(a[i][j]<a[i][j+j+1]&&a[i][j]>a[i][j+j])
q++;
}
if(q==(p[i]-1)/2)
up=11;
else
up=0;

q=0; //升序树

sum=big+small+up+down;

printf("Case #%d:",i);

switch(sum){
case 0:printf("Neither");break;
case 2:
case 4:printf("Heap");break;
case 10:
case 11:printf("BST");break;
case 12:
case 13:
case 14:
case 15:printf("Both");break;

default:printf("Both");
}
printf("\n");

}

return 0;

}

题解:
第一题,只要按照题目要求去检查一下就可以了,没有什么可以多说的.

我第一次交了个错误的程序居然A了--
#include<cstdio>
#include<algorithm>
using namespace std;
#define maxn 1001
int a[maxn],n,T,ls,rs;
bool heapl,heapg,bstu,bstd;
inline void case_init()
{
scanf("%d",&n);
for(int i=1;i<=n;++i) scanf("%d",&a[i]);
}
inline void case_solve(int kase)
{
heapl=heapg=bstu=bstd=true;
for(int i=1;i<=n;++i)
{
ls=i<<1; rs=(i<<1)+1;
if(ls>n) continue;
if(a[i]>a[ls]) bstd=heapl=false;
else bstu=heapg=false;
if(rs>n) continue;
if(a[i]>a[rs]) bstu=heapl=false;
else bstd=heapg=false;

}
printf("Case #%d: ",kase);
bool heap=heapg||heapl;
bool bst=bstu||bstd;
if(heap&&bst) puts("Both");
else if(heap) puts("Heap");
else if(bst) puts("BST");
else puts("Neither");
}
int main()
{
scanf("%d",&T);
for(int i=1;i<=T;++i)
{
case_init();
case_solve(i);
}
return 0;
}

比赛的时候看到这题以为很简单 没想到我居然爆0了 →→ 其实还是概念弄不清楚 把堆和大根小根的集合关系弄混了
Heap：包括大根堆和小根堆 一个堆不一定只是大根堆或只是小根堆 可能有些大根有些小根
BST：升序：左<根<右 降序：左>根>右 并且只能满足一个顺序
我会说我比赛的时候输出没有冒号么 →→

需要更丰富的内容输出？编辑器快速入门 | Markdown详细帮助

企鹅今日沪上的发生大发阿萨德撒 的

编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 856 KiB, score = 10

测试数据 #1: Accepted, time = 0 ms, mem = 856 KiB, score = 10

测试数据 #2: Accepted, time = 0 ms, mem = 852 KiB, score = 10

测试数据 #3: Accepted, time = 15 ms, mem = 868 KiB, score = 10

测试数据 #4: Accepted, time = 15 ms, mem = 872 KiB, score = 10

测试数据 #5: Accepted, time = 15 ms, mem = 868 KiB, score = 10

测试数据 #6: Accepted, time = 15 ms, mem = 868 KiB, score = 10

测试数据 #7: Accepted, time = 15 ms, mem = 872 KiB, score = 10

测试数据 #8: Accepted, time = 15 ms, mem = 872 KiB, score = 10

测试数据 #9: Accepted, time = 0 ms, mem = 856 KiB, score = 10

Accepted, time = 90 ms, mem = 872 KiB, score = 100

改了又改。起先没弄清楚堆得定义。
type
arr=array[1..2002]of integer;
var
t:arr;
d,z,i,j:integer;
c:array[1..100]of string;
k:array[1..1000]of integer;
procedure treet(i,g:integer);
var
a:integer;
begin
if i<=g then
begin
read(a);
t[i]:=a;
treet(i+1,g);
end;
end;

procedure b(p,q:integer);
begin
if p<=q then
begin
b(p*2,q);
k[d]:=t[p];
inc(d);
b(p*2+1,q);
end;
end;

function sj(n:integer):boolean;
var
i:integer;
begin
sj:=true;
if k[1]<=k[2] then
begin
for i:=2 to n-1 do
if k[i]>k[i+1] then exit(false);
end
else if k[1]>=k[2] then
begin
for i:=2 to n-1 do
if k[i]<k[i+1] then exit(false);
end;
end;

function panheap(n:integer):boolean;
var
i,j:integer;
begin
panheap:=true;
for i:=1 to n do
if t[i*2]<>1000 then
if (t[i]>=t[i*2]) then
begin
if t[i*2+1]=1000 then t[i*2+1]:=0;
if (t[i]<t[i*2+1]) then exit(false);
end
else
if (t[i]<=t[i*2]) then
if (t[i]<t[i*2])and(t[i]>t[i*2+1]) then exit(false);
end;

function panbst(n:integer):boolean;
var
j:integer;
begin
d:=1;
panbst:=false;
b(1,n);
if sj(n) then exit(true);
for j:=1 to 1000 do k[j]:=0;
end;

procedure p(m:integer);
var
n:integer;
begin
read(n);
treet(1,n);
if panheap(n)and panbst(n) then
begin
c[m]:='Both';
end
else
begin
if panbst(n)then c[m]:='BST'
else
if panheap(n)then c[m]:='Heap' else
c[m]:='Neither';
end;
end;

begin
for i:=1 to 1002 do t[i]:=1000;
read(z);
for i:=1 to z do
begin
p(i);
for j:=1 to 1002 do t[j]:=1000;
end;
for i:=1 to z do
writeln('Case #',i,': ',c[i]);
end.

测试数据 #0: Accepted, time = 0 ms, mem = 1600 KiB, score = 10

测试数据 #1: Accepted, time = 0 ms, mem = 1600 KiB, score = 10

测试数据 #2: Accepted, time = 0 ms, mem = 1608 KiB, score = 10

测试数据 #3: Accepted, time = 0 ms, mem = 1604 KiB, score = 10

测试数据 #4: Accepted, time = 0 ms, mem = 1604 KiB, score = 10

测试数据 #5: Accepted, time = 0 ms, mem = 1608 KiB, score = 10

测试数据 #6: Accepted, time = 0 ms, mem = 1604 KiB, score = 10

测试数据 #7: Accepted, time = 0 ms, mem = 1604 KiB, score = 10

测试数据 #8: Accepted, time = 0 ms, mem = 1604 KiB, score = 10

测试数据 #9: Accepted, time = 0 ms, mem = 1604 KiB, score = 10

Accepted, time = 0 ms, mem = 1608 KiB, score = 100

代码
var
i,j,n,t,l:longint;f1,f2,f3:boolean;
a:array[1..200000]of longint;
begin
read(t);
for l:=1 to t do begin
f1:=true;f2:=true;f3:=true;read(n);a[n+1]:=maxlongint;
for i:=1 to n do read(a[i]);
for i:=1 to n shr 1 do
if (a[2*i]<=a[i])and(a[i]<=a[2*i+1])then continue
else begin f1:=false;break;end;
for i:=1 to n shr 1 do
if (a[2*i]>=a[i])and(a[i]>=a[2*i+1])then continue
else begin f3:=false;break;end;
f1:=f1 or f3;
for i:=1 to n shr 1-1 do
if (a[2*i]>=a[i])and(a[i]<=a[2*i+1])or
(a[2*i]<=a[i])and(a[i]>=a[2*i+1])
then continue
else begin f2:=false;break;end;i:=n shr 1;
if n and 1=1 then if not((a[2*i]>=a[i])and(a[i]<=a[2*i+1])or
(a[2*i]<=a[i])and(a[i]>=a[2*i+1]))
then f2:=false;
if f1 and f2 then writeln('Case #',l,': Both');
if f1 and not f2 then writeln('Case #',l,': BST');
if f2 and not f1 then writeln('Case #',l,': Heap');
if not f1 and not f2 then writeln('Case #',l,': Neither');
end;
end.
比赛第一次ac

#include <stdio.h>

using namespace std;
const int MAXN=1000;
const int INF=1<<30;
bool judge1(int l[MAXN+1],int n){
bool flag=true;
int t;
int i;
if(n==0){
return true;
}
if(n%2==0){
flag=false;
}
t=n/2;
if(l[1]<l[2]){ //左子树,右子树<根
if(flag==false){
l[n+1]=INF;
}
for(i=1;i<=t;i++){
if(l[i]<l[i*2]&&l[i]<l[i*2+1]){
}
else{return false;}
}
return true;
}
else{
if(flag==false){
l[n+1]=-INF;
}
for(i=1;i<=n/2;i++){
if(l[i]>l[i*2]&&l[i]>l[i*2+1]){
}
else{return false;}
}
return true;

}
}

bool judge2(int l[MAXN+1],int n){
int i;
bool flag=true;
if(n==0){
return true;
}
if(n%2==0){
flag=false;
}

if(l[1]>l[2]){//左子树<根<右子树
if(flag==false){l[n+1]=INF;}
for(i=1;i<=n/2;i++){
if(l[i]>l[i*2]&&l[i]<l[i*2+1]){
}
else{return false;}
}
return true;
}else{
if(flag==false){l[n+1]=-INF;}
for(i=1;i<=n/2;i++){
if(l[i]<l[i*2]&&l[i]>l[i*2+1]){
}
else{return false;}
}
return true;
}

}
int main(){
int t,n;
int l[MAXN+1];
int i,j;
bool flag1,flag2;
scanf("%d",&t);
for(i=1;i<=t;i++){
scanf("%d",&n);
for(j=1;j<=n;j++){
scanf("%d",&l[j]);
}
flag1=judge1(l,n);
flag2=judge2(l,n);
if(flag1==true&&flag2==true){
printf("Case #%d: Both\n",i);
}
if(flag1==true&&flag2==false){
printf("Case #%d: Heap\n",i);
}
if(flag1==false&&flag2==true){
printf("Case #%d: BST\n",i);
}
if(flag1==false&&flag2==false){
printf("Case #%d: Neither\n",i);
}
}
return 0;
}

#include <iostream>
#include <cstdio>
using namespace std;
int main()
{
int t;
cin>>t;
for(int q=1;q<=t;q++)
{
int n,tree[1010];
cin>>n;
int i,j;
for(i=1;i<=n;i++)
scanf("%d",&tree[i]);
//for(i=1;i<=n;i++)
// cout<<tree[i]<<" ";
//cout<<endl;
int heap=1,bst=1;
//大根堆
int f1=1;
for(i=1;i<=n;i++)
{
if(i*2+1<=n)
if(tree[i]<tree[2*i+1] || tree[i]<tree[2*i])
{
f1=0;
break;
}
if(i*2==n)
if(tree[i]<tree[2*i])
{
f1=0;
break;
}
}
//cout<<"f1="<<f1<<endl;
//小根堆
int f2=1;
for(i=1;i<=n;i++)
{
if(i*2+1<=n)
if(tree[i]>tree[2*i+1] || tree[i]>tree[2*i])
{
f2=0;
break;
}
if(i*2==n)
if(tree[i]>tree[2*i])
{
f2=0;
break;
}
}
//cout<<"f2="<<f2<<endl;
if(f1==0 && f2==0) heap=0;

//降序排序树
f1=1;
for(i=1;i<=n;i++)
{
int k=0;
if(i*2+1<=n)
{
if(tree[2*i]<tree[i] && tree[i]<tree[2*i+1])
k=1;
if(!k)
{
f1=0;
break;
}
}
k=0;
if(i*2==n)
{
if(tree[2*i]<tree[i])
k=1;
if(!k)
{
f1=0;
break;
}
}
}
//cout<<"f3="<<f1<<endl;
//升序排序树
f2=1;
for(i=1;i<=n;i++)
{
int k=0;
if(i*2+1<=n)
{
if(tree[2*i]>tree[i] && tree[i]>tree[2*i+1])
k=1;
if(!k)
{
f2=0;
break;
}
}
k=0;
if(i*2==n)
{
if(tree[2*i]>tree[i])
k=1;
if(!k)
{
f2=0;
break;
}
}
}
//cout<<"f4="<<f2<<endl;

if(f1==0 && f2==0) bst=0;
if(bst==1 && heap==1) cout<<"Case #"<<q<<": Both"<<endl;
if(bst==1 && heap==0) cout<<"Case #"<<q<<": BST"<<endl;
if(bst==0 && heap==1) cout<<"Case #"<<q<<": Heap"<<endl;
if(bst==0 && heap==0) cout<<"Case #"<<q<<": Neither"<<endl;
}
//while(1);
return 0;
}

program exam;
uses dos;
var a:array[0..10000000] of longint;
num,i:longint;
procedure add(no,l,r:longint);
var t:longint;
begin
if no>8 then exit;
t:=random(r-l)+l;
a[no]:=t;
add(no shl 1,t,r);
add(no shl 1+1,l,t);
end;
begin
randomize;
assign(output,'a.in');
rewrite(output);

add(1,0,1000);
writeln('1');
writeln('8');
for i:=1 to 8 do
write(a[i],' ');
close(output);
end.
怎么测都是BST，都没错，为什么还是0分………………

今晚电脑8点多才修好，不知道自己自动在更新什么，开不了机。我用标准文件做的。
type
arr=array[1..2000]of integer;
var
t:arr;
z,i,j:integer;
procedure treet(i,g:integer);
var
a:integer;
begin
if i<=g then
begin
read(a);
t[i]:=a;
treet(i+1,g);
end;
end;

function panheap(n:integer):boolean;
var
i:integer;
begin
panheap:=true;
for i:=1 to n do
if (t[i]>t[i*2]) or (t[i]>t[i*2+1]) then exit(false);
end;

function panbst(n:integer):boolean;
var
j:integer;
begin
panbst:=true;
for j:=1 to n do
if (t[j*2]<>1000) then
if (t[j]<t[j*2]) or (t[j]>t[j*2+1]) then exit(false);
end;

procedure p(m:integer);
var
n:integer;
begin
readln(n);
treet(1,n);
if panheap(n)and panbst(n) then
begin
writeln('Case #',m,': ','Both') ;
end
else
begin
if panbst(n)then writeln('Case #',m,': ','BST')
else
if panheap(n)then writeln('Case #',m,': ','Heap') else
writeln('Case #',m,': ','Neither');
end;
end;

begin
assign(input,'c:\pascalceshi\chiniupai.txt');
assign(output,'c:\pascalceshi\chiniupaoshuchu.txt') ;
reset(input);
rewrite(output);
for i:=1 to 1000 do t[i]:=1000;
readln(z);
for i:=1 to z do
begin
p(z);
for j:=1 to 1000 do t[j]:=1000;
end;
close(input);
close(output);
end.

...

浙江 周李轩武 提前签到