安德球查看:0 回复:2 评论:0 创建时间:2019-02-28T23:23:42用户:
小伙伴早上好鸭, 咱一边说着忙的要喵其实是咕咕咕掉更文跑去Codeforces刷题
刷题一段时间之后也找到了一些有趣的题, 普遍特点是难度不高, 但很有意思
于是, 咱就整个新栏目出来, 拿来放点题解
预备知识: 在查阅本文之前, 我会假定读者已经具备了基础的程序开发技能, 附加的程序会使用GNU C++ 8.1.0提供, 即对应C++的2a版本, 原题网站将会在文章结束时给出, 有兴趣的看官可以自行提交代码测试.
题目的翻译由安德球提供, 不保证正确性也不保证信达雅, 随缘看听个响就成.
Codeforces Round #479 (Div. 3)
A. 错误削减 - 时间限制: 1s, 内存限制: 256MB, 输入: 标准输入, 输出: 标准输出
小女孩Tanya正在学习减一运算, 但遇到两位或以上的数字她就会歇菜. 具体是这么整的:
1. 如果数字的最后一位不是零, 那么她可以正确地将其减一;
2. 如果数字的最后一位是零, 她会将数字除以十(也就是将末尾的零删掉).
你会获得一个数字n, 而Tanya会将其减一k次. 你的任务是输出k次削减后的数字, 结果保证为一个正整数.
数据输入:
输入的第一行包含两个整数n和k(2 <= n <= 10^9, 1 <= k <= 50) - 也就是Tanya会操作的被减数和减一运算的次数.
数据输出:
输出仅包含一个整数 - n进行k次减法运算后的结果, 结果保证为一个正整数.
测试样例:
input
512 4
output
50
input
1000000000 9
output
1
注解:
第一个测试样例中, 对应的运算为: 512 → 511 → 510 → 51 → 50.
这里先提及一点点算法相关的知识, 关于题目名称后面的时间限制一类的意味. 对于算法而言, 在相对可以接受的时间内, 使用可接受的内存空间解决问题, 大概是定义一类的了.
也就是说算法不仅仅只是保证正确就足够了的, 一个点一下跑一年的算法是要出事的, 比如动态交通状况评估, 咱整了个贼好用但是螺旋慢的算法, 喀拉点了一下, 然后跑到了三月份, 没用的. 另一个要素就是内存限制, 比如开了个1000*10000的二维数组, 用来存道路千万条, 然后算了算得花三四个TB的内存, 嗯, 受到这个喵落后的计算机工业, 我天才的算法用不了.
通常而言, 算法对于时间的要求都是1s, 对于java语言, 会额外赠送2s, 嗯我不是说java慢还是怎样, 只是举个例子. 通常, 1s时间内对于千万级运算以下通常都能料理得来, 如果算了算要上亿次运算, 恭喜, TLE.
而内存限制要少得多, 256MB的内存基本上都足够用, 换算一下用来存int数字, 足够开喵,000,000个数字了, 基本上不作都是用不完哒. 当然, 对于java语言, 会额外赠送512MB, 我也没有说java内存占用大, 嗯.
而最后的输入输出, 都是标准输入/输出, 意思是可以直接从控制喵取输入, 并将结果直接输出到控制台即可, 对于有文件I/O需求的题目, 以后遇到了再说, 这里只需要知道cin读取和cout输出就成了.
扯完了没啥用的背景知识, 咱终于可以做题了. 该题目作为某轮比赛的A题, 自然也是最简单的签到题了, 在这种数据规模下, 小于50次运算, 直接把每次运算模拟出来也不会超时, 比如, 上个while, 最后一位是不是零? 不是就减一, 是就去了零. 但是, 有没有办法让它稍微快一丢丢呢, 咱魔鬼安德就来玩一波了.
话不多说, 先上代码, 从代码开始讲解.
第一行我不打算多做介绍, 大致就看成包含了所有常用头的头文件就行, 懒人必备技能.
第二三行是基本的指定命名空间和声明几个需要用到的变量, 以后的代码都会保持这种风格, 前三行也不会再多做介绍了.
第六行中使用的ios::sync_with_stdio(false)将cin/cout与scanf/printf的同步关闭, 将会让流I/O的效率比scanf/printf更快, 但缺点是注意不要将cin与scanf混合使用, 否则会造成读入数据混乱.
第九行中语句与int t = n % 10等价, 但同样的, 这样的写喵更快, 这一步将数字n的末尾数字取出.
后面就很简单啦, 判断末尾数字是否是零, 这里额外加了一步, 判断末尾数字大于等于k, 等于k-1, 或是更小的情况, 这样可以将几步操作和为一步, 无论末尾数字是几, 均会到达三种状态之一: k归零削减结束, 末尾数字丢弃削减结束, 削减未结束去掉末尾位继续进行下一次循环. 效率比单步判定开支提高了数倍.
总体来说, 就是通过三步加速, 将算法效率提高, 喵模拟也是要注意效率的哦. 本题最终在int喵_t的范围内都可以在2ms内解决, 可以说是很良心了.
那么有看官可能要问了, 这个算法的时间复杂度是多少吖? 答案是O(logN), 在评论区给出证明的小伙伴将获得柠檬一个.
本次题解到此为止啦, 如果还有更多问题的话, 欢迎在评论区留下问题, 咱看到后会提交回复.
