15011418730 LV 7 @ 2025-8-24 22:20:40

自动搬运

来自洛谷，原作者为

	wuyonghuming **

搬运于2025-08-24 22:20:40，当前版本为作者最后更新于2020-07-18 12:24:15，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

错误：

这道题目我一开始模拟二叉树，结果 $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;//别忘了
}

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

ID

5439

时间

1000ms

内存

32MiB

难度

标签

递交数

已通过

上传者

Hydro

1 条题解

自动搬运

以下是正文

错误：

思路：

规律：

规律一：

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

规律二：

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

规律三：

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

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

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

代码：

[COCI 2008/2009 #2] SETNJA

信息

1 条题解

自动搬运

以下是正文

错误：

思路：

规律：

规律一：

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

规律二：

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

规律三：

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

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

ansi=2(ansi−1)+3xans_i = 2(ans_{i-1}) + 3^xansi​=2(ansi−1​)+3x

代码：

[COCI 2008/2009 #2] SETNJA

信息

还没有账户？

登录

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

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

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

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

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