第三部分 编程题第一题《寻找神奇的平方宝石》 第一幕平方王国的藏宝图1、很久很久以前有一个叫做平方王国的地方。国王收藏着许多神奇宝石。但是并不是所有宝石都有资格进入宝库。只有一种特殊的宝石才能进去。它们叫做完全平方数2、国王告诉同学给你两个数字 L 和 R。请你帮我数一数在这两个数字之间一共有多少颗平方宝石1例如L 1 R 20哪些是平方宝石呢2我们一个一个找。1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 203其中1 1×1 4 2×2 9 3×3 16 4×4一共4个3、 完全平方数的性质完全平方数就是某个整数自己乘自己。例如1 1² 4 2² 9 3² 16 4² 25 5²第二幕最容易想到的方法1我把 L 到 R 全部暴力检查一遍例如100 101 102 …… 100000每个数字都判断是不是平方数。枚举数字。2接下来怎么判断一个数是不是平方数例如49可以不停试1² 2² 3² ... 7²找到7²49成功3可是……如果L1 R100000000怎么办太慢了第三幕我们发现了规律1、平方数到底有哪些1²1 2²4 3²9 4²16 5²25 6²36 7²49 8²64 9²81 10²1002、我们可以不断制造平方数这样速度就是超级快。第四幕制造平方宝石1、现在我们制造1² 2² 3² 4² ……2、如果平方数R继续。3、如果平方数L就开始计数。4、例如L5 R301制造1²1 太小 × 2²4 太小 × 3²9 √ 4²16 √ 5²25 √ 6²36 已经超过30 停止3、最后答案3是不是挺快的。第五幕怎样写循环呢1、代码for(int i1;i*ir;i)2、假设R100那么1² 2² …… 10²就够了。因为11²121已经超过100。3、所以循环条件就是i*iR意思只要平方没有超过R就继续。第六幕什么时候计数呢1、制造出来以后1例如i5得到252判断25L如果成立。说明25就在区间里面。于是ans;3如果16比L小。说明不在藏宝区。不能计数。第七幕参考代码#include iostream using namespace std; int main() { int l, r; cin l r; int ans 0; // 不断制造平方数 for (int i 1; i * i r; i) { // 平方数进入区间 if (i * i l) ans; } cout ans; return 0; }第八幕逆向枚举1、我们学会了一种编程思想。以前枚举每一个数字后来枚举答案的来源这是逆向枚举反向思考2、很多算法竞赛题都可以这样优化。例如以前检查队伍里面每个人是不是冠军。后来直接找到冠军。 再看冠军在不在这个队伍里面。 本题知识树完全平方数 │ ├── 什么是平方数 │ ├── 暴力枚举数字太慢 │ ├── 枚举平方数优化 │ ├── i*iR 为什么 │ ├── i*iL 为什么 │ └── 逆向思维记忆口诀判断平方数数字全走完自己来造平方数找到边界就停下。枚举来源比枚举值程序又快又简单