首先设当前总分为sum

sum一开始=1(根)

分情况讨论：

当输入一个'L':sum=sum*2

当输入'P'：sum不变

当输入'R':sum=sum*2+3^k （k为目前为止'*'的个数）

当输入一个'*' ：sum=(sum*2)+(sum)+(sum*2+3^k) (三种情况加起来)

　　　　　　　　 =5*sum+3^k

阶段划分：

if str='L' then f:=f*2;

if str='R' then f:=f*2+1;

if str='P' then f:=f;

但由于'*' 的介入，使这题有多种解，于是要加起来

if str='L' or str='*' then f:=f+f*2;

if str='R' or str='*' then f:=f+f*2+1;

if str='P' or str='*' then f:=f+f;

可以看出，这种方法对于‘L’和‘P’来说是可行的，但对于'R’（f*2+1)来说就不行了，

应该是f*2+num（num为现在分支的个数）

压8位，一遍AC，第二遍超时了。。。

很显然，由于*的存在，每次出现一个*，R中的常数项会发生改变。易得常数s=3^p,p为已出现的*的个数。所以3个状态（p就直接忽略吧- -）的转移如下：

L: ans:=ans shl 1;

R: ans:=ans shl 1+3^p;

*: ans:=5*ans+3^p;

剩下的就水了。。

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 41ms

├ 测试数据 10：答案正确... 166ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：207ms

位压8位

PASCAL的数组开大了要超时。。

压5位 开10000的就够了

Accepted 有效得分：100 有效耗时：284ms

郁闷，第一次忘记把调试时的“｝”去掉了....

注意：数组范围不要吝啬....开大点不会大影响速度.....

cgy4ever的方法MS有错？我编了一个，L*R输出就不对了。

时间太诡异了：

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 119ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 166ms

├ 测试数据 10：答案正确... 322ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：607ms

如果没学过数据结构，就用数学方法做这道题，那高精度用C语言要怎么写？

高精度，数组10000，残啊，wa了那么多次！！

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 9ms

├ 测试数据 10：答案正确... 134ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：143ms

对高精度越来越拿手了。。。

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 41ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：41ms

同意唐钰小宝的意见……同时……注意用高精度的时候要压位……7位足够……

然后Orz一下yxy同学的题解位置……华丽丽的飘过……

怪了，在老师那测都好得很，在这交两次都running。。

编译通过...

to 楼下:

Orz...这题解的位置...

简单题，但是……

第一次提交：居然没写高精度。

第二次提交：写了高精度，还压位了，但是数组只开了1000，80分……

第三次提交：数组开到了2000，AC……

可以发现

操作列中没有'*'的话,最终只有一种状态

每多一个'*',可能的状态就要乘3(因为'*'可以置换成'L','R','P'中的任何一种);

并且从当前的和可以推出下一个操作符后的和

因为对于当前的每种状态,操作都是相同的

设当前和为Ans,状态数为Sum

初始Ans=1,Sum=1;

对于'L':ANS:=ANS*2;

'R':ANS:=ANS*2+SUM;

'*':ANS:=ANS('*'换成'P')+ANS*2('*'换成'L')+ANS*2+SUM('*'换成'R')

=ANS*5+SUM;

并且Sum:=Sum*3;

找规律（这么简单！考试时竟然没有想到！！） + 高精度

首先设当前总分为sum

sum一开始=1(根)

分情况讨论：

当输入一个'L':sum=sum*2

当输入'P'：sum不变

当输入'R':sum=sum*2+3^k （k为目前为止'*'的个数）

当输入一个'*' ：sum=(sum*2)+(sum)+(sum*2+3^k) (三种情况加起来)

=5*sum+3^k

就这么简单！

10000位！！！吐血！！！

Accepted 有效得分：100 有效耗时：0ms

终于写出个不错的高精度

Hint:

设原向量M=(1,0)

那么L,R,P,*就是对向量的线性操作

L(a,b)=(2a,b)

R(a,b)=(2a,a+b)

P(a,b)=(a,b)

*(a,b)=(5a,a+3b)

从后往前依次进行操作

那么最后得到向量(a,b),答案就是a+b了.

地板，递推+高精度