//pat-143
#include<bits/stdc++.h>
using namespace std;
vector<int> pre;
map<int,int>ex;
void lca(int a,int b){
int i=0;
if(ex[a]==0&&ex[b]==0){
printf("ERROR: %d and %d are not found.\n",a,b);
return;
}
else if(ex[a]==0){
printf("ERROR: %d is not found.\n",a);
return;
}
else if(ex[b]==0){
printf("ERROR: %d is not found.\n",b);
return;
}
while(1){
if((pre[i]>=a&&pre[i]<=b)||(pre[i]<=a&&pre[i]>=b) ){
break;
}
i++;
}//BST给的是结点的值的大小不是序号，所以是双重索引
if((a<pre[i]&&b>pre[i])||(a>pre[i]&&b<pre[i]) ) printf("LCA of %d and %d is %d.\n",a,b,pre[i]);
else if(a==pre[i]) printf("%d is an ancestor of %d.\n",a,b);
else if(b==pre[i]) printf("%d is an ancestor of %d.\n",b,a);
}
int main(){
int m,n;
scanf("%d%d",&m,&n);
for(int i=0;i<n;i++){
int a;
scanf("%d",&a);
pre.push_back(a);
ex[a]=1;
}
for(int i=0;i<m;i++){
int _1,_2;
scanf("%d%d",&_1,&_2);
lca(_1,_2);
}
return 0;
}
//1151
#include<bits/stdc++.h>
using namespace std;
vector<int> in,pre;
map<int,int> ex,pos;
void dfs(int root,int inll,int inrr,int a,int b){
if(inll>inrr) return ;
if(ex[a]==0&&ex[b]==0){
printf("ERROR: %d and %d are not found.\n",a,b);
return;
}else if(ex[a]==0){
printf("ERROR: %d is not found.\n",a);
return ;
}else if(ex[b]==0){
printf("ERROR: %d is not found.\n",b);
return;
}
int i,_1=0,_2=0;
_1=pos[a];
_2=pos[b];
//while(in[i]!=pre[root])i++;
i=pos[pre[root]];//一开始用while找位置总是RE，全部改为键值对对应位置后终于解决掉那个RE点了
if((_1<i&&_2>i)||(_1>i&&_2<i )) {
printf("LCA of %d and %d is %d.\n",a,b,in[i]);
return ;
}
else if(_1<i&&_2<i) dfs(root+1,inll,i-1,a,b);
else if(_1>i&&_2>i) dfs(root+i-inll+1,i+1,inrr,a,b);
else if(_1==i) {
printf("%d is an ancestor of %d.\n",a,b);
return ;
}
else if(_2==i) {
printf("%d is an ancestor of %d.\n",b,a);
return ;}
}
int main(){
int m,n,temp;
scanf("%d%d",&m,&n);
for(int i=0;i<n;i++){
scanf("%d",&temp);
in.push_back(temp);
ex[temp]=1;
pos[temp]=i;
}
for(int i=0;i<n;i++){
scanf("%d",&temp);
pre.push_back(temp);
}
int _3,_4;
for(int i=0;i<m;i++){
scanf("%d%d",&_3,&_4);
dfs(0,0,n-1,_3,_4);
}
return 0;
}
//1004
#include<bits/stdc++.h>
using namespace std;
vector<int> v[110];
int lev[110],maxle=0;
void dfs(int root,int le){
//end
if(le>maxle){
maxle=le;
}
if(v[root].size()==0){
lev[le]++;
return;
}
for(int i=0;i<v[root].size();i++){
dfs(v[root][i],le+1);
}
}
int main(){
int n,m,_1,_2,_3;
scanf("%d%d",&n,&m);
if(n==0) return 0;
for(int i=0;i<m;i++){
scanf("%d%d",&_1,&_2);
for(int j=0;j<_2;j++){
scanf("%d",&_3);
v[_1].push_back(_3);
}
}
dfs(1,0);
printf("%d",lev[0]);
for(int i=1;i<=maxle;i++){
printf(" %d",lev[i]);
}
return 0;
}
#include<bits/stdc++.h>
using namespace std;
vector<int> pos,in;
struct node{
int key;
int index;
};
vector<node> pre;
void dfs(int root,int inll,int inrr,int index){
//end
if(inll>inrr) return;
int i=inll;
while(in[i]!=pos[root]) i++;
pre.push_back({pos[root],index});
dfs(root-(inrr-i)-1,inll,i-1,2*index+1);
dfs(root-1,i+1,inrr,2*index+2);
}
bool cmp(node&a,node&b){
return a.index<b.index;
}
int main(){
int n,temp1;
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d",&temp1);
pos.push_back(temp1);
}
for(int i=0;i<n;i++){
scanf("%d",&temp1);
in.push_back(temp1);
}
dfs(n-1,0,n-1,0);
sort(pre.begin(),pre.end(),cmp);
printf("%d",pre[0]);
for(int i=1;i<pre.size();i++){
printf(" %d",pre[i]);
}
return 0;
}
//1043
#include<bits/stdc++.h>
using namespace std;
vector<int> pre,ans,in;//ans crt
//map<int,int> pos;
int flag=1;
void dfs(int root,int inll,int inrr){
//end
if(inll>inrr) return ;
if(root>pre.size()) return ;
int i=inll;//起点也不是随便设置的
//int i=pos[pre[root]];
if(flag==1)//用原始建树
while(in[i]!=pre[root]&&i<=inrr)i++;//找位置时这个冒是必要的
if(flag==0){
while(in[i]>=pre[root]&&i<=inrr) i++;//镜像中序左大右小 ，i必须是<=
i=i-1;//最后一个相等的位置
}
dfs(root+1,inll,i-1);
dfs(root+i-inll+1,i+1,inrr);
ans.push_back(pre[root]);
/*else{
int i=inll;
while(in[i]!=pre[root]&&i<=inrr)i++;
dfs(root+i-inll+1,i+1,inrr);
dfs(root+1,inll,i-1);
ans.push_back(pre[root]);
}*///先右后左的方式只有知道原前中才能正好得出镜像的后 ,而不是利用镜像的前搭配
}
bool cmp(int a,int b){
return a>b;
}
int main(){
int n,_1;
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d",&_1);
pre.push_back(_1);
}
//debug
/* for(int i=0;i<pre.size();i++){
printf("%d ",pre[i]);
}*/
//printf("\n");
//vector<int>in(pre);
for(int i=0;i<pre.size();i++){
in.push_back(pre[i]);
}
//debug
sort(in.begin(),in.end());
for(int i=0;i<in.size();i++){
printf("%d ",in[i]);
}
dfs(0,0,n-1);
if(ans.size()!=n){
flag=0;
sort(in.begin(),in.end(),cmp);//镜像中序
ans.clear();//crt
dfs(0,0,n-1);
}
if(ans.size()!=n){
printf("NO");
}else{
printf("YES\n");
printf("%d",ans[0]);
for(int i=1;i<ans.size();i++){
printf(" %d",ans[i]);
}
}
return 0;
}
#include<bits/stdc++.h>
using namespace std;
struct node{
int data;
node*lc;
node*rc;
};
void insert(node*&root,int data){//要引地址
if(root==NULL){//null必须大写
root=new node;//因为这有new不能声明就是在原root下
root->data=data;
root->lc=NULL;
root->rc=NULL;
return;
}
if(root->data>data){
insert(root->lc,data);
}else{
insert(root->rc,data);
}
}
void pre(node*root,vector<int>&v){//v为存储值 都是void 数据已经存到里面了
//后面没有new不用&
if(root==NULL){//到达递归边界
return;
}
v.push_back(root->data);
pre(root->lc,v);
pre(root->rc,v);
}
void prem(node*root,vector<int>&v){//v为存储值
//后面没有new不用&
if(root==NULL){//到达递归边界
return;
}
v.push_back(root->data);
prem(root->rc,v);//此时bst已有原树 //prem写成pre
prem(root->lc,v);
}
void post(node*root,vector<int>&v){//v为存储值
//后面没有new不用&
if(root==NULL){//到达递归边界
return;
}
post(root->lc,v);
post(root->rc,v);//此时bst已有原树
v.push_back(root->data);
}
void postm(node*root,vector<int>&v){//v为存储值
//后面没有new不用&
if(root==NULL){//到达递归边界
return;
}
postm(root->rc,v);
postm(root->lc,v);//此时bst已有原树
v.push_back(root->data);
}
vector<int> init,preo,premm,posto,postmm;
int main(){
int n,_1;
scanf("%d",&n);
node*root=NULL;
for(int i=0;i<n;i++){//二叉树插入
scanf("%d",&_1);
insert(root,_1);
init.push_back(_1);
}
//vector 数组之间的比较不需要循环
pre(root,preo);
prem(root,premm);
//debug
for(int i=0;i<n;i++){
printf("%d ",preo[i]);
}
printf("\n");
for(int i=0;i<n;i++){
printf("%d ",premm[i]);
}
if(preo==init){
printf("YES\n");
post(root,posto);
printf("%d",posto[0]);
for(int i=1;i<posto.size();i++){
printf(" %d",posto[i]);
}
}else if(premm==init){
printf("YES\n");
postm(root,postmm);
printf("%d",postmm[0]);
for(int i=1;i<postmm.size();i++){
printf(" %d",postmm[i]);
}
}else {
printf("NO");
}
return 0;
}
//1053
#include<bits/stdc++.h>
using namespace std;
struct node{
int id,we;
};
int wei[110],cnt=0;
vector<node> v[110];
vector<int> ans[110],temp;
void dfs(int root,int k){
temp.push_back(wei[root]);
//end
if(v[root].size()==0){
int sum=0;
for(int i=0;i<temp.size();i++){
sum+=temp[i];
}
if(sum==k){
ans[cnt++]=temp;
}
temp.pop_back();
return;
}
for(int i=0;i<v[root].size();i++){
dfs(v[root][i].id,k);
}
temp.pop_back();
}
bool cmp(node &a,node&b){
return a.we>b.we;
}
int main(){
int n,m,s,_1,_2,_3;
scanf("%d%d%d",&n,&m,&s);
for(int i=0;i<n;i++){
scanf("%d",&wei[i]);
}
for(int i=0;i<m;i++){
scanf("%d%d",&_1,&_2);
for(int j=0;j<_2;j++){
scanf("%d",&_3);
v[_1].push_back({_3,wei[_3]});
}
sort(v[_1].begin(),v[_1].end(),cmp);
}
dfs(0,s);
for(int i=0;i<cnt;i++){
printf("%d",ans[i][0]);
for(int j=1;j<ans[i].size();j++){
printf(" %d",ans[i][j]);
}
printf("\n");
}
return 0;
}
//1064
#include<bits/stdc++.h>
using namespace std;
struct node{
int index,data;
};
vector<int> in;
vector<node> ans;
int cnt=0;
void dfs(int index,int n){
//end
if(index>n-1){//注意一下，这里的终止条件，一开始没弄对
return;
}
dfs(2*index+1,n);
ans.push_back(node{index,in[cnt++]});
dfs(2*index+2,n);
}
bool cmp(node&a,node&b){
return a.index<b.index;
}
int main(){
int n,_1;
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d",&_1);
in.push_back(_1);
}
sort(in.begin(),in.end());
dfs(0,n);
sort(ans.begin(),ans.end(),cmp);
printf("%d",ans[0].data);
for(int i=1;i<ans.size();i++){
printf(" %d",ans[i].data);
}
return 0;
}
#include<bits/stdc++.h>
using namespace std;
vector<int> v[100010];
int amount[100010];
double p,r;
double sum=0;//double 比flost精度要高，要尽量用double
void dfs(int root,int le){
//end
if(v[root].size()==0){
sum+=amount[root]*p*pow(1+double(r/100),le);
return;
}
for(int i=0;i<v[root].size();i++){
dfs(v[root][i],le+1);
}
}
int main(){
int n,_1,_2;
scanf("%d%lf%lf",&n,&p,&r);
for(int i=0;i<n;i++){
scanf("%d",&_1);
if(_1==0){
scanf("%d",&_2);
amount[i]=_2;
}
else{
for(int j=0;j<_1;j++){
scanf("%d",&_2);
v[i].push_back(_2);
}
}
}
dfs(0,0);
printf("%.1lf",sum);
return 0;
}
//1086
#include<bits/stdc++.h>
using namespace std;
map<int,int>pos;//in
vector<int> pre,in,post;
void dfs(int root,int inll,int inrr){
//end
if(inll>inrr) return;
int i=pos[pre[root]];
dfs(root+1,inll,i-1);
dfs(root+i-inll+1,i+1,inrr);
post.push_back(pre[root]);
}
int main(){
int n,_1;
scanf("%d",&n);
stack<int> mo;
for(int i=0;i<2*n;i++){
char a[6];
scanf("%s",&a);//未必一定带着后面的1
if(strlen(a)==4){
scanf("%d",&_1);
mo.push(_1);
pre.push_back(_1);
}else{
int temp=mo.top();//stack 是top
mo.pop();
in.push_back(temp);
}
}
for(int i=0;i<in.size();i++){
pos[in[i]]=i;//pos忘弄
}
dfs(0,0,n-1);
printf("%d",post[0]);
for(int i=1;i<post.size();i++){
printf(" %d",post[i]);
}
return 0;
}
//1090
#include<bits/stdc++.h>
using namespace std;
vector<int> v[100010];
double p,r,ans=0;
int cnt=0;
void dfs(int root,int le){
//end
if(v[root].size()==0){
double temp=p*pow(1+r/100,le-1);//root suplly就是指的4,4就是根不是它上面还有个根节点 for the root supplier is defined to be ?1.
if(temp==ans){//逻辑上错误，上面赋完值已经相同再与相同的作比较肯定成立啊 注意上面的赋值会不会影响下面的判断
cnt++;
}
if(temp>ans){
ans=temp;
cnt=1;
}
/*if(temp==ans){
cnt++;
}*/
}
for(int i=0;i<v[root].size();i++){
dfs(v[root][i],le+1);
}
}
int main(){
int n,_1,root;
scanf("%d%lf%lf",&n,&p,&r);
root=n;
for(int i=0;i<n;i++){
scanf("%d",&_1);
if(_1==-1){
v[root].push_back(i);
}else{
v[_1].push_back(i);
}
}
dfs(root,0);
printf("%.2lf %d",ans,cnt);
return 0;
}
//pat-143
#include<bits/stdc++.h>
using namespa
阅读背景：
pat 二刷树部分-01_江船夜雨听笛的博客
来源：互联网
分享到：
