P1924 层次遍历答疑提问：_复旦大学2023年机试题

windflew

TA的个人主页 >

文章

粉丝

获赞

访问

154

P1924 层次遍历答疑提问：

windflew

P1924 复旦大学2023年机试题

发布于2025年12月27日 11:04

阅读数 109

为什么WA?只有80分，递归建树后BFS

#include<bits/stdc++.h>
#define ll long long

#define endl "\n"
#define mod 998244353
const int N = 1e6+5;
using namespace std;
int n;
int a[N];
int p[N];
int h[N][2];
map<int,int> mp,nmp;
int fun(int l,int r,int ql,int qr)//中序 先序
{
	//cout<<"*"<<l<<" "<<r<<" "<<ql<<" "<<qr<<endl;
	if(l==r)
	{
		return a[ql];
	}
	int root=a[ql];
	
	int cnt0 = 0;
	if((root-1  - l +1)>0)cnt0 = (root-1  - l +1);
	int cnt1 = 0;
	if(r- (root+1) + 1 >0)cnt1 = (r- (root+1) + 1);
	if(cnt0)
	{
		int a= fun(l,root-1,ql+1,ql+cnt0);
		h[root][0] = a;
	}
	if(cnt1)
	{
		int b= fun(root+1,r,qr+1-cnt1,qr);
		h[root][1] = b;
	}
	return root;
}
bool vis[N];
void sol()
{
	/**/
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		h[i][0]=h[i][1]=-1;
	}
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		p[i]=a[i];
	}
	int idx=0;
	//离散化
	
	sort(p+1,p+n+1);
	for(int i=1;i<=n;i...

登录查看完整内容