题解 P6424 【[COCI2008-2009#2] SETNJA】

· · 题解

错误：

这道题目我一开始模拟二叉树，结果 TLE MLE RE ， 原因是 * 太多了，需要很多数组，每次来一个就要多两个树枝，如果全部都是 * 时间复杂度极高。

代码：

#include <bits/stdc++.h>
using namespace std;
string gaojingdujiafa(string a,string b)
{
    string d,i="",j;
    char f;
    int g=0,h,bb=0;
    if(a.size()<b.size())
    {
        swap(a,b);
    }
    if(a.size()!=b.size())
    {
        for(register int c=b.size()-1;c>=0;c--)
        {
            i+=b[c];
        }
        while(a.size()>i.size())
        {
            i+='0';
        }
        b="";
        for(register int c=i.size()-1;c>=0;c--)
        {
            b+=i[c];
        }
    }
    for(register int c=a.size()-1;c>=0;c--)
    {   
        h=a[c]+b[c]-'0'-'0'+g;
        if(h>=10)
        {
            g=1;
            f=h-10+'0';
        }
        else
        {
            f=h+'0';
            g=0;
        }
        d+=f;                                       
    }
    if(g==1)
    {
        d+='1';
    }
    i="";
    for(register int c=d.size()-1;c>=0;c--)
    {
        if(bb==0)
        {
            if(d[c]=='0')
            {
                continue;
            }
            else
            {
                bb=1;
            }
        }
        i+=d[c];
    }
    return i;
}
int main()
{
    string s[2001],str,ans="0";
    int g=1;
    s[1]="1";
    cin>>str;
    for(register int i=0;i<str.size();i++)
    {
        if(str[i]=='L')
        {
            for(register int j=1;j<=g;j++)
            {
                s[j]=gaojingdujiafa(s[j],s[j]);
            }
        }
        else if(str[i]=='R')
        {
            for(register int j=1;j<=g;j++)
            {
                s[j]=gaojingdujiafa(gaojingdujiafa(s[j],s[j]),"1");
            }
        }
        else if(str[i]=='*')
        {
            int l=g;
            for(register int j=1;j<=l;j++)
            {
                g++;
                s[g]=gaojingdujiafa(s[j],s[j]);
                g++;
                s[g]=gaojingdujiafa(gaojingdujiafa(s[j],s[j]),"1");
            }
        }
    }
    for(register int i=1;i<=g;i++)
    {
        ans=gaojingdujiafa(ans,s[i]);
    }
    cout<<ans;
    return 0;
}

思路：

需要找规律，最后按照规律就可以把答案算出来了。

规律：

规律一：

我们先假设全部都是 * ，设 * 的个数是 x 。

当 x= 1 答案为 6

当 x= 2 答案为 33

当 x= 3 答案为 174

当 x= 4 答案为 897

当 x= 5 答案为 4566

我们用 ans_i 表示 x_i 的答案。

我们发现 ans_i = 5(ans_{i-1})+3^{x-1}

还可以发现，这个规律在加入其他操作的时候依旧成立。

例子：

LRLR = 21 , LRLR* =106 LRLR* = 106 , LRLR** =533

规律二：

我们先假设全部都是 L ，设 L 的个数是 x 。

当 x= 1 答案为 2

当 x= 2 答案为 4

当 x= 3 答案为 8

当 x= 4 答案为 16

当 x= 5 答案为 32

我们用 ans_i 表示 x_i 的答案。

我们发现 ans_i = 2(ans_{i-1})

还可以发现，这个规律在加入其他操作的时候依旧成立。

例子

R*R* = 178 , R*R*L =356 R*R*L = 356 , R*R*LL =712

规律三：

我们先假设全部都是 R ，设 R 的个数是 x 。

当 x= 1 答案为 3

当 x= 2 答案为 7

当 x= 3 答案为 15

当 x= 4 答案为 31

当 x= 5 答案为 63

我们用 ans_i 表示 x_i 的答案。

我们发现 ans_i = 2(ans_{i-1}) + 1

*但是我们发现，这个规律在前面加入 $ $ 的时候就不成立了。**

例子

L*L* = 113 , L*L*R = 235 L*L*R = 235 , L*L*R = 479

*我们又发现，前面加入 $$ 就有了新规律**

我们设前面 * 的个数是 x ，用 ans_i 表示答案。

ans_i = 2(ans_{i-1}) + 3^x

发现了这些规律，就可以打代码了。

代码：

#include <bits/stdc++.h>//头文件
using namespace std;
int ans[10001],s[10001];//答案，和三的幂
void LLLLL()//这个是处理L的函数
{
    int z=ans[0],f=0;//ans[0]保存这个数的长度进位可能改变ans[0]所以就用了个z保存，f是判断进位的
    for(int k=z;k>=1;k--)//从低位往高位算
    {
        ans[k]=ans[k]+ans[k]+f;//乘二再加上进位
        f=ans[k]/10;//更新是否需要进位
        ans[k]%=10;//更新这一位的值
    }
    if(f==1)//如果最后还需要进位 
    {
        for(int k=z;k>=1;k--)//从低位到高位
        {
            ans[k+1]=ans[k];//往右移动，因为前面产生了新的一位
        }
        ans[1]=1;//新的那一位一定是1
        ans[0]=z+1;//长度又变长了
    }
    return;//别忘了
}
void RRRRR()//这个是处理R的函数
{
    int z=ans[0],f=0,l=s[0];//ans[0]保存这个数的长度进位可能改变ans[0]所以就用了个z保存，f是判断进位的，l是记录现在三的幂的位置，否则无法和ans对齐
    for(int k=z;k>=1;k--)//从低位往高位算
    {
        ans[k]=ans[k]+ans[k]+f;//乘二再加上进位
        if(l>0)//如果需要继续加
        {
            ans[k]+=s[l];//加上去
        }
        f=ans[k]/10;//更新是否需要进位
        ans[k]%=10;//更新这一位的值
        l--;//往前
    }
    if(f==1)//如果最后还需要进位     
    {
        for(int k=z;k>=1;k--)//从低位到高位
        {
            ans[k+1]=ans[k];//往右移动，因为前面产生了新的一位
        }
        ans[1]=1;//新的那一位一定是1
        ans[0]=z+1;//长度又变长了
    }
    return;//别忘了
}
void LRLRLRLRLR()//这个是处理*的函数
{
    int z=ans[0],f=0,l=s[0];//ans[0]保存这个数的长度进位可能改变ans[0]所以就用了个z保存，f是判断进位的，l是记录现在三的幂的位置，否则无法和ans对齐
    for(int k=z;k>=1;k--)//从低位往高位算
    {
        ans[k]=ans[k]*5+f;//乘五再加上进位
        if(l>0)//如果需要继续加
        {
            ans[k]+=s[l];//加上去
        }
        f=ans[k]/10;//更新是否需要进位
        ans[k]%=10;//更新这一位的值
        l--;//往前
    }
    if(f!=0)//如果最后还需要进位
    {
        for(int k=z;k>=1;k--)//从低位到高位
        {
            ans[k+1]=ans[k];//往右移动，因为前面产生了新的一位
        }
        ans[1]=f;//新的那一位是f
        ans[0]=z+1;//长度又变长了
    }
    return;//别忘了
}
void sssss()//这个是处理三的幂的函数
{
    int z=s[0],f=0;//s[0]保存这个数的长度进位可能改变s[0]所以就用了个z保存，f是判断进位的
    for(int k=z;k>=1;k--)//从低位往高位算
    {
        s[k]=s[k]*3+f;//乘三再加上进位
        f=s[k]/10;//更新是否需要进位
        s[k]%=10;//更新这一位的值
    }
    if(f!=0)//如果最后还需要进位 
    {
        for(int k=z;k>=1;k--)//从低位到高位
        {
            s[k+1]=s[k];//往右移动，因为前面产生了新的一位
        }
        s[1]=f;//新的那一位是f
        s[0]=z+1;//长度又变长了
    }
    return;//别忘了
}
int main()
{
    string c;//存输入
    ans[1]=ans[0]=s[1]=s[0]=1;//赋初值
    cin>>c;//输入
    for(int i=0;i<c.size();i++)//循环来根据指令操作
    {
        if(c[i]=='L')//如果是左
        {
            LLLLL();//左边函数
        }
        else if(c[i]=='R')//如果是右
        {
            RRRRR();//右边函数
        }
        else if(c[i]=='*')//如果是左右停
        {
            LRLRLRLRLR();//左右停函数
            sssss();//需要再乘三
        }
    }
    for(int i=1;i<=ans[0];i++)//循环输出答案
    {
        printf("%d",ans[i]);//输出
    }
    return 0;//别忘了
}

谢谢管理审核和大家观赏!