首页 > 代码库 > upcoj2679 Binary Tree（思路题）
upcoj2679 Binary Tree（思路题）
题意：
给你两个串，每个串有LRU三个操作，L（R）为去左（右）子树，U为回到父亲（根节点不作处理）
然后按这样的规则遍历完第一个串，将现在的位置作为第二个串的起始位置
然后遍历第二个串，第二个串的每个位置都可以执行或者不执行，U操作为将原点倒退（按第一个串行进的过程反向）
问你最多能到多少个节点 ？
思路：
开一个栈将第一个串的每一步的变动压入栈中，第二个串遍历的时候开三个变量l,r,sum
lr分别表示向左（右）走的新节点数量，这样遍历第二个串的时候，
遇到L就让ans和r都加l，意思不好讲啊，就是当前向左走的话就开辟了向右走的新节点。。
遇到R同样，让ans和l都加r
最后就是遇到U的时候，如果第一个串的顶端是L的话表明他是从父亲节点向左走得到的当前的起点
然后U上去就开辟了一个向右走的新节点。。所以ans和r都加1，R的情况同理ans和l都加1
大概就是这样，还是画出图来比较好看，附上我的渣渣代码
/* ***********************************************Author :devil************************************************ */#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#include <vector>#include <queue>#include <set>#include <stack>#include <map>#include <string>#include <cmath>#include <stdlib.h>#define inf 0x3f3f3f3f#define LL long long#define rep(i,a,b) for(int i=a;i<=b;i++)#define dec(i,a,b) for(int i=a;i>=b;i--)#define ou(a) printf("%d\n",a)#define pb push_back#define mkp make_pairtemplate<class T>inline void rd(T &x){char c=getchar();x=0;while(!isdigit(c))c=getchar();while(isdigit(c)){x=x*10+c-‘0‘;c=getchar();}}#define IN freopen("in.txt","r",stdin);#define OUT freopen("out.txt","w",stdout);using namespace std;const int mod=21092013;const int N=1e5+10;int t;char s1[N],s2[N];int main(){ rd(t); rep(y,1,t) { scanf("%s%s",s1,s2); stack<char>q; int len=strlen(s1); rep(i,0,len-1) { if(s1[i]==‘U‘) {if(!q.empty()) q.pop();} else q.push(s1[i]); } int l=1,r=1,ans=1; len=strlen(s2); rep(i,0,len-1) { if(s2[i]==‘U‘&&!q.empty()) { char p=q.top(); q.pop(); ans++; if(p==‘L‘) r++; else l++; } else if(s2[i]==‘L‘) { (ans+=l)%=mod; (r+=l)%=mod; } else if(s2[i]==‘R‘) { (ans+=r)%=mod; (l+=r)%=mod; } } printf("Case %d: %d\n",y,ans%mod); } return 0;}
upcoj2679 Binary Tree（思路题）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。