程序能力实训(BY) test 1 题解

cww970329 edited 4 年，7 月前

A

注意一下可能有空格（ASCII码是32），行读入以及取模的时候注意结果可能是负数（注意k的范围）就行了。

不做过多的解释，说一下要注意的点吧。

1. 题意：题目给的是加密规则，询问的是解密，所以是减k不是加k。
2. 字符串存在空格，所以不能直接cin或者scanf，要行读入，用gets或者getline。
3. 循环位移k次实际上对于字母来说就是位移k%26次，对于数字来说就是位移k%10次。
4. 因为是减k，所以可能会减成负数，而负数取模还是负数，所以记得取正。

B

写错的犬决

C

按题意模拟即可，题目中连伪代码都给出来了。

D

只需读取所有的字符，统计B的个数就可以了。

E

贪心。只需按照$\frac{a_i}{b_i}$为第一关键字，编号为第二关键字，从小到大排序即可。注意不能用double比较，这样精度会出问题。直接通分就可以在整数范围内完成比较了。

struct St{
    long long a, b, c, id;
    bool operator <(const St &r) const{
        if (a*r.b != r.a*b) return a*r.b < r.a*b;
        return id < r.id;
    }
}

思考2（难度：1）：这个贪心算法的正确性证明。可以参考1998年NOIp提高组的”拼数”一题。

思考3（难度：5）：如果存在一些”要击败第$i$个怪物，必须先击败第$j(j<i)$个怪物 “这样的限制呢？（小声bb：其实这才是原本想出的题目）

F

首先在双方的生命/攻击/防御都确定的情况下，康康是否可以击败怪物和剩余多少生命值都是可以O(1)计算的。

只需枚举加多少次攻击，然后根据康康受到攻击的次数计算剩下的强化次数是加防御合算还是加生命合算。如果怪物每次对康康的伤害大于等于$4$，那么加防的收益就固定是受到攻击的次数$\times 4$，而加血的收益固定是$800$。如果怪物已经不能对康康造成伤害，那么加防的收益是$0$，加血的收益仍然是$800$。因此只有3种情况：

1.全都加生命

2.先加防御，如果怪物对康康的伤害变成0之后仍有剩余强化次数，剩下的次数加生命

3.先加防御，如果怪物对康康的伤害小于4之后仍有剩余强化次数，剩下的次数加生命

三种情况都$O(1)$计算出来，比较一下取最大值即可。这样对于每组数据，复杂度为$O(K)$。

注意：康康最多剩下$0$血时，应输出$-1$。

思考1（难度：3）：是否有时间复杂度更低的做法？

Comments