22.4.5 – 小飞侠

1，省赛练习，2，二叉树模板复习；3，二叉树高度（不限制根节点）

1，省赛练习题；

①peak

判断一个序列数组是否为驼峰，并且严格满足；

#include<bits/stdc++.h>
#define rep1(i,a,n) for(register int i=a;i<n;i++) 
#define rep2(i,a,n) for(register int i=a;i<=n;i++) 
#define per1(i,n,a) for(register int i=n;i>a;i--) 
#define per2(i,n,a) for(register int i=n;i>=a;i--)
#define quick_cin() cin.tie(0),cout.tie(0),ios::sync_with_stdio(false)
#define INF 0x3f3f3f3f
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
typedef double db;
const int N=1e5+10;
int a[N];
void solve()
{
	int n;
	cin>>n;
	int maxx=0;
	bool flag1=0,flag2=0,flag3=0;
	rep2(i,1,n)cin>>a[i];
	rep2(i,1,n)
	{
		if(a[1]>a[2])
		{
			flag3=1;
			break;
		}
		if(a[i]>maxx&&flag1==0)maxx=a[i];
		else 
		{
			if(!flag1)
			{
				flag1=1;
			}
		}
		if(flag1)
		{
			if(a[i]>=maxx)
			{
				flag2=1;
				break;
			}
			if(a[i]<maxx)maxx=a[i];
		}
	}
	if(flag2||flag3)printf("No\n");
	else if(flag1)printf("Yes\n");
	else printf("No\n");
}
signed main()
{
	quick_cin();
	int t;
	cin>>t;
	while(t--)
	{
		solve();
	}
	return 0;
}

②king of karaoke

找差值的最大个数；

#include<bits/stdc++.h>
#define rep1(i,a,n) for(register int i=a;i<n;i++) 
#define rep2(i,a,n) for(register int i=a;i<=n;i++) 
#define per1(i,n,a) for(register int i=n;i>a;i--) 
#define per2(i,n,a) for(register int i=n;i>=a;i--)
#define quick_cin() cin.tie(0),cout.tie(0),ios::sync_with_stdio(false)
#define INF 0x3f3f3f3f
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
typedef double db;
const int N=1e5+10;
int a[N];
int b[N];
void solve()
{
	int n;
	cin>>n;
	unordered_map<int,int>hs;
	rep2(i,1,n)cin>>a[i];
	int maxx=0;
	rep2(i,1,n)
	{
		int x;
		cin>>x;
		int t=a[i]-x;
		hs[t]++;
		if(hs[t]>maxx)maxx=hs[t];
	}
	printf("%d\n",maxx);
}
signed main()
{
	quick_cin();
	int t;
	cin>>t;
	while(t--)
	{
		solve();
	}
	return 0;
}

③continue..?

多罗列几个数找到了规律；

能够完成分组的只有3，4；7，8；11，12；15，16；这类数；

并且恰好每次都是有规律的安排；

以11和12为例看：

11分成两组和一样的，一组3，4，5，6，7，8 共6个数；一组1，2，9，10，11 共5个数；

12分成两组和一样的，一组4，5，6，7，8，9 共6个数；一组1，2，3，10，11，12共6个数；

可以发现，n为奇数，则有一组从（n+1）/4开始，到（n+1）/4 + n/2 -1；再把1~n中剩下的分给另一组即可；

n为偶数，则为一组从（n+1）/4 +1开始，到（n+1）/4 + n/2 ；再把1~n中剩下的分给另一组即可；

这里注意要关闭quick_cin()；不知道为什么输出会错行，用了quick_cin()；

这两个-1是上面两组数据的答案，但是都跑到第三组这里输出了，很奇怪，关了quick_cin()即正常；

#include<bits/stdc++.h>
#define rep1(i,a,n) for(register int i=a;i<n;i++) 
#define rep2(i,a,n) for(register int i=a;i<=n;i++) 
#define per1(i,n,a) for(register int i=n;i>a;i--) 
#define per2(i,n,a) for(register int i=n;i>=a;i--)
#define quick_cin() cin.tie(0),cout.tie(0),ios::sync_with_stdio(false)
#define INF 0x3f3f3f3f
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
typedef double db;
const int N=1e6+10;
char s[N];
int t;
void solve()
{
	int n,nb=0,ng=0;
	cin>>n;
	cin>>s+1;
	int sum=n*(1+n)/2;
	if(sum%2!=0)cout<<"-1\n";
	else
	{
			int t=(n+1)/4;
			if(n%2==1)
			{
				rep2(i,t,t+((n+1)>>1)-1)
				{
					if(s[i]=='0')s[i]='1';
					else s[i]='3';
				}
				rep2(i,1,t-1)
				{
					if(s[i]=='0')s[i]='2';
					else s[i]='4';				
				}
				rep2(i,t+((n+1)>>1),n)
				{
					if(s[i]=='0')s[i]='2';
					else s[i]='4';			
				}
			}
			else
			{
				rep2(i,t+1,t+((n+1)>>1))
				{
					if(s[i]=='0')s[i]='1';
					else s[i]='3';
				}
				rep2(i,1,t)
				{
					if(s[i]=='0')s[i]='2';
					else s[i]='4';				
				}
				rep2(i,t+((n+1)>>1)+1,n)
				{
					if(s[i]=='0')s[i]='2';
					else s[i]='4';			
				}			
			}
		rep2(i,1,n)cout<<s[i];
		cout<<endl;
	}
}
signed main()
{
//	quick_cin();
	cin>>t;	
	while(t--)solve();
	return 0;
}

④ Doki Doki Literature Club

结构体排序，比较字典序可以直接return a.s<b.s;

但是这里也有坑点，printf(“%lld”,ans)会wa，不知道为啥，除非关了quick_cin();

用了quick_cin()只能用cout输出；注意下也要，碰到lld的输出该用cout！；

#include<bits/stdc++.h>
#define rep1(i,a,n) for(register int i=a;i<n;i++) 
#define rep2(i,a,n) for(register int i=a;i<=n;i++) 
#define per1(i,n,a) for(register int i=n;i>a;i--) 
#define per2(i,n,a) for(register int i=n;i>=a;i--)
#define quick_cin() cin.tie(0),cout.tie(0),ios::sync_with_stdio(false)
#define INF 0x3f3f3f3f
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
typedef double db;
const int N=1e5+10;
int t;
struct ji
{
	string s;
	ll f;
}a[110];
bool cmp(ji a,ji b)
{
	if(a.f!=b.f)return a.f>b.f;
	else return a.s<b.s;
}
void solve()
{
	int n,m;
	cin>>n>>m;
	rep2(i,1,n)cin>>a[i].s>>a[i].f;
	sort(a+1,a+n+1,cmp);
	ll ans=0;
	rep2(i,1,m)
	{
		ans+=(m-i+1)*a[i].f;
	}
	cout<<ans;
	rep2(i,1,m)cout<<" "<<a[i].s;
	cout<<endl;
}
signed main()
{
	quick_cin();
	cin>>t;	
	while(t--)solve();
	return 0;
}

2，二叉树模板，记住细节，尤其是结构体开头那里；

#include<bits/stdc++.h>
#define rep1(i,a,n) for(register int i=a;i<n;i++) 
#define rep2(i,a,n) for(register int i=a;i<=n;i++) 
#define per1(i,n,a) for(register int i=n;i>a;i--) 
#define per2(i,n,a) for(register int i=n;i>=a;i--)
#define quick_cin() cin.tie(0),cout.tie(0),ios::sync_with_stdio(false)
#define INF 0x3f3f3f3f
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
typedef double db;
const int N=1e5+10;
int t;
typedef struct BTnode
{
	char data;
	struct BTnode *Lchild,*Rchild;
}*BinTree;
void creatBT(BinTree &BT)
{
	char c;
	cin>>c;
	if(c=='#')return;
	if(BT==NULL)
	{
		BT=(BTnode*)malloc(sizeof(BTnode));
		BT->data=c;
		BT->Lchild=NULL;
		BT->Rchild=NULL;
	}
	creatBT(BT->Lchild);
	creatBT(BT->Rchild);
}
void frontorder(BinTree &BT)
{
	if(BT==NULL)return;
	cout<<BT->data;
	frontorder(BT->Lchild);
	frontorder(BT->Rchild);
}
void midorder(BinTree &BT)
{
	if(BT==NULL)return;
	midorder(BT->Lchild);
	cout<<BT->data;
	midorder(BT->Rchild);
}
void backorder(BinTree &BT)
{
	if(BT==NULL)return;
	backorder(BT->Lchild);
	backorder(BT->Rchild);
	cout<<BT->data;
}
signed main()
{
	quick_cin();
	BTnode *BT=NULL;
	creatBT(BT);
	frontorder(BT);
	cout<<endl;
	midorder(BT);
	cout<<endl;
	backorder(BT);
	return 0;
}

3，求二叉树高度，

用PII数组，first当左儿子，second当右儿子；

找根节点用到了并查集的代码；

主要还是height（）函数，多记多理解；

#include<bits/stdc++.h>
#define rep1(i,a,n) for(register int i=a;i<n;i++) 
#define rep2(i,a,n) for(register int i=a;i<=n;i++) 
#define per1(i,n,a) for(register int i=n;i>a;i--) 
#define per2(i,n,a) for(register int i=n;i>=a;i--)
#define quick_cin() cin.tie(0),cout.tie(0),ios::sync_with_stdio(false)
#define INF 0x3f3f3f3f
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
typedef double db;
PII p[1100];
int n;
int height(int x)
{
	int hl,hr;
	if(!x)return 0;
	hl=height(p[x].first);
	hr=height(p[x].second);
	return max(hl,hr)+1;
}
int pp[1100];
int find(int x)
{
	return pp[x]==x?x:pp[x]=find(pp[x]);
}
signed main()
{
	quick_cin();
	cin>>n;
	int root;
	rep2(i,1,n)pp[i]=i;
	rep2(i,1,n)
	{
		int x,l,r;
		cin>>x>>l>>r;
		p[i].first=l;
		p[i].second=r;
		pp[l]=find(i);
		pp[r]=find(i);
	}
	rep2(i,1,n)
	if(pp[i]==i)
	{
		root=i;
		break;
	}
	if(!root)cout<<0;
	cout<<height(root);
	return 0;
}

原文链接：https://blog.csdn.net/aidaqiudeaichao/article/details/123975568

你可能也喜欢