Shiroha白羽的博客
·
Educational Codeforces Round 161 (Rated for Div. 2)
💡
原文中文，约4200字，阅读约需10分钟。
📝
内容提要
给定三个字符串，确定是否存在一个模式，可以匹配前两个字符串但不匹配第三个字符串。给定一组边长为2的幂的边，计算可以形成的不同三角形的数量。给定一行具有坐标的城市，计算任意两个城市之间的距离。给定一行具有攻击和防御值的怪物，计算每轮死亡的怪物数量。构造一个具有恰好n个递增子序列的字符串。
🎯
关键要点
- 设定一种模式串，匹配前两个字符串但不匹配第三个字符串。
- 只需确保前两个字符串在某个位置不同于第三个字符串。
- 计算使用不同边的三角形数量，边长为2的幂。
- 讨论两条边相同和三条边相同的情况。
- 计算任意两个城市之间的距离，使用前缀和方法。
- 城市之间的移动成本为1，其他城市的成本为距离。
- 怪物的攻击力和防御力决定其生死，计算每轮死亡的怪物数量。
- 只需考虑死亡怪物附近的怪物，不需考虑全部。
- 构造一个字符串，使其内部的递增子序列数量恰好为n。
❓
延伸问答
如何确定一个模式串可以匹配前两个字符串但不匹配第三个字符串？
只需确保前两个字符串在某个位置不同于第三个字符串，并且该位置的模式串是大写的第三个字符串的字符。
如何计算使用不同边的三角形数量？
需要讨论两条边相同和三条边相同的情况，利用边长为2的幂的特性进行计算。
如何计算任意两个城市之间的距离？
使用前缀和方法计算，移动成本为1，其他城市的成本为实际距离。
怪物的攻击力和防御力如何影响其生死？
当一个怪物受到的攻击大于其防御力时，它将死亡，每轮只需考虑死亡怪物附近的怪物。
如何构造一个具有恰好n个递增子序列的字符串？
可以通过添加数值x到已有的递增序列中，利用2的幂关系增加递增子序列的数量。
在计算三角形数量时，为什么需要考虑边的相同情况？
因为边长为2的幂的特性使得至少有两条边相同时才能形成三角形。
➡️
