/ Vijos / 题库 / /

题解

25 条题解

  • 1
    @ 2009-10-22 21:47:20

    首先设当前总分为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

  • 1
    @ 2009-05-24 10:10:00

    阶段划分:

    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为现在分支的个数)

  • 0
    @ 2009-10-22 21:33:59

    压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;

    剩下的就水了。。

  • 0
    @ 2009-10-13 19:39:51

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    位压8位

  • 0
    @ 2009-09-20 23:09:41

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

    压5位 开10000的就够了

  • 0
    @ 2009-09-12 19:54:16

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

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

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

  • 0
    @ 2009-07-16 17:14:41

    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

  • 0
    @ 2009-07-14 10:10:25

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

  • 0
    @ 2009-07-14 09:03:12

    高精度,数组10000,残啊,wa了那么多次!!

  • 0
    @ 2009-05-08 19:41:39

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

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

  • 0
    @ 2009-04-20 13:20:06

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

  • 0
    @ 2009-04-13 12:07:59

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

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

  • 0
    @ 2009-04-13 23:12:32

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

    编译通过...

  • 0
    @ 2009-04-01 19:15:19

    to 楼下:

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

  • 0
    @ 2009-03-29 16:52:42

    简单题,但是……

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

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

    第三次提交:数组开到了2000,AC……

  • 0
    @ 2009-03-29 14:54:47

    可以发现

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

    每多一个'*',可能的状态就要乘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;

  • 0
    @ 2009-03-28 22:32:09

    找规律(这么简单!考试时竟然没有想到!!) + 高精度

    首先设当前总分为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

    就这么简单!

  • 0
    @ 2009-03-28 20:40:34

    10000位!!!吐血!!!

  • 0
    @ 2009-03-28 19:28:02

    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了.

  • 0
    @ 2009-03-28 18:01:05

    地板,递推+高精度

信息

ID
1522
难度
7
分类
动态规划 | 高精度 点击显示
标签
(无)
递交数
571
已通过
107
通过率
19%
被复制
2
上传者