首页 > 代码库 > UVALive 6577 Binary Tree 二叉树的LRU串

UVALive 6577 Binary Tree 二叉树的LRU串

2024-07-02 02:24:49   228人阅读

今天继续攒人品。。。真开心啊O(∩_∩)O~~各种身体不舒服~~

https://icpcarchive.ecs.baylor.edu/external/65/6577.pdf

题意是这样的，现在有一个向下无限延伸的二叉树。然后输入起点（通过只含LRU的字符串S，从根结点开始执行）。LRU分别表示往左儿子走，往右儿子走，往爹娘处走（根结点的爹娘是自己，估计他是石头里蹦出来的）。

然后输入一个可选步骤串T。可以选择T中的子序，从起点开始走。然后问可以走到多少个不同的结点。

 

比赛的时候不会做啊╮(╯▽╰)╭。赛后好像有题解不过看不懂。。。。英语渣的缘故吧，我猜。。。然后看LC他们的代码，研究下终于搞懂的样子

我们可以先考虑，只有LR的情况，初始化，ans=1,L=1,R=1 。LR分别表示往左（右）走的新结点数量。然后遍历T字符串，然后如果有L则ans+=L,R+=L；其实就是往左走为往右走开辟了往右走的新结点。。。好别扭，不知道怎么解释。。建议画图模拟。。。然后如果有R则ans+=R,L+=R。。。。这个好像是做过的某一题

好了，只有LR的情况解决了=。=

然后如果是现在要up，如果是up到从根执行S串的路途中，那如果up到的结点最后一次往下走是left，那现在up上去必然的结果就是，开辟了一个往右的新结点，反过来是right也一样=。=同时答案+1

 

有可以参考的人（代码）真好啊~~~好像太依赖参考了。。。

复杂度就O（n）

以上都是在晕晕的状态写的=。=所以有那啥的求评论。。。

 

Note: 好像忘memset也AC。。。。还是不需要memset？

P.S.边吃饭边发现，那个dir是可以不用memset的~~~看来要多吃饭~~~

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <iostream>
 4 #include <algorithm>
 5 #include <cmath>
 6 #include <string>
 7 #include <vector>
 8 #include <queue>
 9 #include <set>
10 using namespace std;
11 
12 #define ll long long
13 #define inf 0x3f3f3f3f
14 #define eps 1e-8
15 #define maxn 100010
16 #define mod 21092013
17 
18 char a[maxn],b[maxn];
19 char dir[maxn];
20 int main(){
21     int t,ca=0;
22     scanf("%d",&t);
23     while(t--){
24         scanf("%s%s",a,b);
25         //memset(dir,0,sizeof(dir));// 可以不用memset
26         int dep=0;
27         int la=strlen(a),lb=strlen(b);
28         for(int i=0;i<la;++i){
29             if(a[i]==‘U‘)dep=max(dep-1,0);
30             else dir[dep++]=a[i];
31         }
32         int ans=1,l=1,r=1;
33         for(int i=0;i<lb;++i){
34             if(b[i]==‘U‘){
35                 if(--dep<0){
36                     dep=0;
37                     continue;
38                 }
39                 ans=(ans+1)%mod;
40                 if(dir[dep]==‘L‘)r=(r+1)%mod;
41                 else if(dir[dep]==‘R‘)l=(l+1)%mod;
42             }
43             else if(b[i]==‘L‘){
44                 ans=(ans+l)%mod;
45                 r=(r+l)%mod;
46             }
47             else if(b[i]==‘R‘){
48                 ans=(ans+r)%mod;
49                 l=(l+r)%mod;
50             }
51         }
52         printf("Case %d: %d\n",++ca,ans);
53     }
54     return 0;
55 }
View Code


联系
我们