2018-03-27 PAT补题练习题
2018-09-25 本文已影响11人
_弓长_大人
L2-004. 这是二叉搜索树吗？
代码当然是越短越好了
我的代码写的有点丑
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int num[1001];
int ans[1001];
int cn=0;
int f=0;
void dfs(int l,int r){
if(l>r)
return;
if(f==0){
int ll,rr;ll=l,rr=l;
int i=l+1;
for(i;i<=r;i++){
if(num[i]<num[l]){
ll++;
}else{
break;
}
}
rr=ll;
for(i;i<=r;i++){
if(num[i]>=num[l]){
rr++;
}else{
break;
}
}
if(rr!=r){
f=1;//no
}
//cout<<ll<<" dd "<<rr<<endl;
if(f==0){
//左子树
dfs(l+1,ll);
// 右子树
dfs(ll+1,r);
ans[cn++]=num[l];
}
}
}
int ff=0;
void dfs2(int l,int r){
if(l>r)
return;
// cout<<ff<<endl;
if(ff==0){
int ll,rr;ll=l,rr=l;
int i=l+1;
for(i;i<=r;i++){
if(num[i]>=num[l]){
ll++;
}else{
break;
}
}
rr=ll;
for(i;i<=r;i++){
if(num[i]<num[l]){
rr++;
}else{
break;
}
}
if(rr!=r){
ff=1;//no
}
//cout<<ll<<" dd "<<rr<<endl;
if(ff==0){
//左子树
dfs2(l+1,ll);
// 右子树
dfs2(ll+1,r);
ans[cn++]=num[l];
}
}
}
int main()
{
int n;
cin>>n;
for(int i=0;i<n;i++){
cin>>num[i];
}
dfs(0,n-1);
if(f==0){
printf("YES\n");
cout<<ans[0];
for(int i=1;i<n;i++){
cout<<" "<<ans[i];
}
cout<<endl;
}else{
dfs2(0,n-1);
if(ff)
printf("NO\n");
else{
printf("YES\n");
cout<<ans[0];
for(int i=1;i<n;i++){
cout<<" "<<ans[i];
}
cout<<endl;
}
}
return 0;
}
利用 stl set相关函数，
之前我同时用了 并交 集合，超时，其实只用一个交集合就可以求出并集合~~~
#include <algorithm>
#include <iostream>
#include <set>
#include<cstdio>
using namespace std;
set<int>s[51];
int main()
{
int n;
scanf("%d",&n);
// cin>>n;
int t;
int a,b;
set<int>ss;
set<int>st;
set<int>::iterator it;
for(int i=1;i<=n;i++){
scanf("%d",&t);
//cin>>t;
for(int j=0;j<t;j++)
{
scanf("%d",&a);
//cin>>a;
s[i].insert(a);
}
}
cin>>t;
for(int i=0;i<t;i++){
ss.clear();
st.clear();
cin>>a>>b;
set_intersection(s[a].begin(),s[a].end(),s[b].begin(),s[b].end(),inserter(ss,ss.begin()));
// set_union(s[a].begin(),s[a].end(),s[b].begin(),s[b].end(),inserter(st,st.begin()));
double ans=100*ss.size();
ans=ans/((s[a].size()+s[b].size())-ss.size());
printf("%.2lf%%\n",ans);
}
return 0;
}
#include <bits/stdc++.h>
using namespace std;
int tree[100000];
void build(int rt,vector<int>a,vector<int>b)
{
if(a.size()==0||b.size()==0)
return;
int p=0;
for(int i=0;i<b.size();i++){
if(b[i]==a[b.size()-1]){
p=i;
break;//根节点
}
}
vector<int>al,ar,bl,br;
for(int i=0;i<p;i++){
al.push_back(a[i]);
}
for(int i=p;i<a.size()-1;i++){
ar.push_back(a[i]);
}
for(int i=0;i<p;i++){
bl.push_back(b[i]);
}
for(int i=p+1;i<b.size();i++){
br.push_back(b[i]);
}
tree[rt]=a[a.size()-1];
build(rt<<1,al,bl);
build(rt<<1^1,ar,br);
return;
}
void bfs()
{
queue<int>q;
q.push(1);
int f=0;
while(q.size()){
int p=q.front();
q.pop();
if(f++){
cout<<" ";
}cout<<tree[p];
if(tree[p<<1]!=-1){
q.push(p<<1);
}
if(tree[p<<1^1]!=-1){
q.push(p<<1^1);
}
}
cout<<endl;
}
int main()
{
memset(tree,-1,sizeof(tree));
int n;
cin>>n;
int t;
vector<int>a,b;
for(int i=0;i<n;i++){
cin>>t;
a.push_back(t);
}
for(int i=0;i<n;i++){
cin>>t;
b.push_back(t);
}
build(1,a,b);
bfs();
return 0;
}
// 其实不用vecotr 也可以的 直接传下标就可以了 ！
#include <bits/stdc++.h>
using namespace std;
int tree[100000];
int a[100];int b[100];
void build(int rt,int x,int xx,int y,int yy)
{
if(xx<=x||yy<=y)
return;
int p=0;
for(int i=y;i<yy;i++){
if(b[i]==a[xx-1]){
p=i;
break;//根节点
}
}
int cn=p-y;
tree[rt]=a[xx-1];
build(rt<<1,x,x+cn,y,y+cn);
build(rt<<1^1,x+cn,xx-1,p+1,yy);
return;
}
void bfs()
{
queue<int>q;
q.push(1);
int f=0;
while(q.size()){
int p=q.front();
q.pop();
if(f++)
cout<<" ";
cout<<tree[p];
if(tree[p<<1]!=-1)
q.push(p<<1);
if(tree[p<<1^1]!=-1)
q.push(p<<1^1);
}
cout<<endl;
}
int main()
{
memset(tree,-1,sizeof(tree));
int n;
cin>>n;
int t;
for(int i=0;i<n;i++)
cin>>a[i];
for(int i=0;i<n;i++)
cin>>b[i];
build(1,0,n,0,n);
bfs();
return 0;
}
#include <bits/stdc++.h>
using namespace std;
int tree[100000];
void build(int rt,vector<int>a,vector<int>b)
{
if(a.size()==0||b.size()==0)
return;
int p=0;
for(int i=0;i<a.size();i++){
if(a[i]==b[0]){
p=i;
break;//根节点
}
}
vector<int>al,ar,bl,br;
for(int i=0;i<p;i++){
al.push_back(a[i]);
}
for(int i=p+1;i<a.size();i++){
ar.push_back(a[i]);
}
for(int i=1;i<p+1;i++){
bl.push_back(b[i]);
}
for(int i=p+1;i<b.size();i++){
br.push_back(b[i]);
}
tree[rt]=b[0];
build(rt<<1,al,bl);
build(rt<<1^1,ar,br);
return;
}
void bfs()
{
queue<int>q;
q.push(1);
int f=0;
while(q.size()){
int p=q.front();
q.pop();
if(f++){
cout<<" ";
}cout<<tree[p];
if(tree[p<<1^1]!=-1){
q.push(p<<1^1);
}
if(tree[p<<1]!=-1){
q.push(p<<1);
}
}
cout<<endl;
}
int main()
{
memset(tree,-1,sizeof(tree));
int n;
cin>>n;
int t;
vector<int>a,b;
for(int i=0;i<n;i++){
cin>>t;
a.push_back(t);
}
for(int i=0;i<n;i++){
cin>>t;
b.push_back(t);
}
build(1,a,b);
bfs();
return 0;
}
题很简单，但是信息比较多容易搞错，并查集好久没写了，忘了写合并了 GG
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct Node
{
bool f=false;
int mo=-1;int fa=-1;
bool bm=false;
int cn=0;
double area=0;
int peo=1;
int pre=0;
int mid=0;
}node[10005];
int n,t,a,b,s,tt;
int c;
int ch;
double area;
int pa,pb;
int findpre(int x)
{
if(node[x].pre!=x){
node[x].pre=findpre(node[x].pre);
}
return node[x].pre;
}
struct no2{
int id;
double area;
int cn;
int peo;
}node2[10000];
bool vis[10000];
bool cmp(struct no2 a,struct no2 b)//人均面积降序输出，成员编号升序输出
{
if(a.area*b.peo==b.area*a.peo){
return a.id<b.id;
}
return a.area*b.peo>b.area*a.peo;
}
int main()
{
cin>>n;
for(int i=0;i<10000;i++){
node[i].pre=i;
node[i].mid=i;
}
for(int i=0;i<n;i++){
cin>>s;
cin>>a>>b;
node[s].f=true;
node[s].fa=a;node[s].mo=b;
t=findpre(s);
if(a!=-1){
node[a].f=true;
tt=findpre(a);
node[tt].pre=t;
}
if(b!=-1){
node[b].f=true;
tt=findpre(b);
node[tt].pre=t;
}
cin>>ch;
for(int j=0;j<ch;j++){
cin>>a;
node[a].f=true;
tt=findpre(a);
node[tt].pre=t;
}
cin>>c>>area;
node[s].area=area;
node[s].cn+=c;
}
int cc=0;
for(int i=0000;i<10000;i++){
if(node[i].f){
t=findpre(i);
if(t!=i){
node[t].peo+=node[i].peo;
node[t].area+=node[i].area;
node[t].cn+=node[i].cn;
node[t].mid=min(node[t].mid,node[i].mid);
}
}
}
for(int i=0000;i<10000;i++){
if(node[i].f){
t=findpre(i);
if(vis[t]==0){
vis[t]=1;
node2[cc].area=node[t].area;
node2[cc].id=node[t].mid;
node2[cc].cn=node[t].cn;
node2[cc].peo=node[t].peo;
cc++;
}
}
}
sort(node2,node2+cc,cmp);
cout<<cc<<endl;
for(int i=0;i<cc;i++){
// cout<<node2[i].peo<<" "<<node2[i].area<<endl;
printf("%04d %d %.3lf %.3lf\n",node2[i].id,node2[i].peo,(double)node2[i].cn/(double)node2[i].peo,node2[i].area/node2[i].peo);
}
return 0;
}
之前 用的三层循环 也有一个样例超时了
改成两层循环过了，分为 奇数与偶数对称即可
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
string s;
// 12345678910019
bool check(int i,int j){
for(int k=i,m=1;k<i+j/2;k++,m++){
if(s[k]!=s[i+j-m]) // 1 11
return false;
}
return true;
}
int main()
{
getline(cin,s);
int ans=1;
for(int i=0;i<s.size();i++){
int l,r;
l=r=i;
r=i+1;
int cn=0;
while(l>=0&&r<s.size()&&s[l]==s[r]){
cn++;
l--;r++;
}
ans=max(cn*2,ans);
cn=0;
l=i-1;
r=i+1;
while(l>=0&&r<s.size()&&s[l]==s[r]){
cn++;
l--;r++;
}
ans=max(cn*2+1,ans);
}
cout<<ans<<endl;
return 0;
}
