• 如果您想对本站表示支持,请随手点击一下广告即可~
  • 本站致力于提供原创、优秀的技术文章~
  • 有任何疑问或建议 均可以在站点右侧栏处 通过各种方式联系站长哦~
  • POJ1472 – Instant Complexity

    ACM-POJ EXP 120阅读 0评论

    全解题报告索引目录 -> 【北大ACM – POJ试题分类


    大致题意

    给出一段Pascial程序,计算其时间复杂度(能计算的项则计算,不能计算则化到最简的关于n的表达式O(n),并把各项根据n的指数从高到低排列),输出时,系数为0的项不输出,系数为1的项不输出系数,指数为1的项不输出指数。

    一段程序只有唯一一个BEGIN,代表程序的开始。与其对应的为最后的END,代表程序的结束。

    一段程序最多只有10层循环嵌套,循环的入口为LOOP,一个LOOP对应一个END,代表该层循环的结束。

    一段程序中OP的个数不限。

    LOOP是循环的入口,其后面的数据可能是常量(非负整数),也可能是变量n,代表循环体执行的次数。

    OP是语句,其后面的数据只能为常量(非负整数),代表该语句执行的次数。

    解题思路

    此题就是一条表达式化简的模拟题,用递归直接模拟(也可用状态机做)。

    以第一个样例说明处理方法:

    从该例子我们可以得到一条关于n的最初表达式:

    n*(4+3*(n*1+2)+1)+17

    稍微化简一下,合并同一层的OP值,得到了

    n*(3*(n*1+2)+5)+17

    不难看出每一个循环体都能写成k*n+i形式的子表达式,其中loop是*关系,op是+关系

    由于最大循环次数为10,那么我们用exp[11]存储多项式的每一项的指数i和系数k=exp[i],其中exp[0]其实就是常数项,由OP语句产生

    注意LOOP后面可能输入字符n,也可能输入数字,处理方法:用字符串输入s,若为s[0]==n,则直接作字符处理;若s[0]!=n,则认为是数字串,把它转换为int再处理。

    Source修正

    Southwestern European Regional Contest 1997

    测试数据

    本文第二页附带测试数据

    测试数据下载


    转载请注明:EXP 技术分享博客 » POJ1472 – Instant Complexity

    喜欢 (0) 分享 (0)
    发表我的评论
    取消评论

    表情

    Hi,您需要填写昵称和邮箱!

    • 昵称 (必填)
    • 邮箱 (必填)
    • 网址