为什么答案对了却通过不了，在dev c++上答案是对的，在oj上却0%？求解_P1924

倪克斯

TA的个人主页 >

文章

粉丝

获赞

访问

713

为什么答案对了却通过不了，在dev c++上答案是对的，在oj上却0%？求解

倪克斯

P1924 复旦大学2023年机试题

发布于2025年3月19日 08:50

阅读数 305

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

const int N=100010;

int pre[N],ind[N];
int tree[N*2];
int n;

void build(int root,int p_l,int p_r,int i_l,int i_r)
{
	if(p_l<=p_r && i_l<=i_r)
	{
		tree[root]=pre[p_l];
		int i;
		for(i=i_l;i<=i_r;i++)
			if(ind[i]==pre[p_l]) break;
		
		if(root*2<=2*n) build(root*2,p_l+1,i-i_l+p_l,i_l,i-1);
		if(root*2+1<=2*n) build(root*2+1,i-i_l+p_l+1,p_r,i+1,i_r);
	}
}

void bfs()
{
	queue<int> q;
	q.push(1);
	
	while(q.size())
	{
		auto t=q.front();
		q.pop();
		cout<<tree[t]<<' ';
		if(t*2<=2*n && tree[t*2]) q.push(t*2);
		if(t*2+1<=2*n && tree[t*2+1]) q.push(t*2+1);
	}
}

int main()
{
	cin>>n;
	for(int i=0;i<n;i++) cin>>pre[i];
	for(int i=0;i<n;i++) ind[i]=pre[i];
	
	sort(ind,ind+n);
	
	build(1,0,n-1,0,n-1);
	
	bfs();
	
	return 0;
}

...

登录查看完整内容

登录后发布评论

4 条评论

admin SVIP

2025年3月19日 18:34

得0分得原因是后台10组测试数据中没有样例的小数据，这道题的数据是当时23年上岸复旦的同学贡献的。

代码错误在于用数组存储树结构，导致可能数组越界，二叉搜索树不平衡，可能层数会很深，比如退化为链状。

大部分同学都是用链式结构存储，数组写法可以参考这个代码：https://noobdream.com/DreamJudge/Issue/code/807376/

倪克斯 : 回复 admin： if(p_l<=p_r && i_l<=i_r) =有这个判断应该不会越界吧

2025年3月19日 20:53

快乐小土狗

2025年3月19日 11:11

在二叉搜索树里，中序遍历的结果是有序的。你通过对先序遍历数组进行排序得到了中序遍历数组 ind，不过你使用数组 ind 来存储中序遍历元素时，未对元素和其索引的映射关系进行正确处理。在 build 函数里，ind[i] 代表的是中序遍历的元素，而非元素对应的索引。你需要构建一个映射来记录每个元素在中序遍历里的位置。

倪克斯 : 回复快乐小土狗： i就是中序数组ind中的下标索引，ind[i]是根节点在中序数组中的元素值

2025年3月19日 17:20