Shiroha白羽的博客
·
Codeforces Round 913 (Div. 3)
💡
原文中文，约6500字，阅读约需16分钟。
📝
内容提要
Codeforces 第913轮（Div. 3）包含多个编程题目，涉及城堡移动、字符处理、删除字符对、线段跳跃、好三元组组合、数组变换和灯的开关状态等。每个题目都有特定的解法，运用枚举、遍历和二分查找等算法技巧。
🎯
关键要点
- A. Rook：题目涉及棋盘上城堡的移动，解法为枚举横向和纵向的可达格子。
- B. YetnotherbrokenKeyboard：题目要求根据输入的字母删除特定的大写或小写字母，解法为从后向前遍历输入字符串。
- C. Removal of Unattractive Pairs：题目要求删除相邻不同字符，最后求剩余字符的最小数量，解法为统计字符数量。
- D. Jumping Through Segments：题目要求在给定线段上从0点开始移动，求最小步数k，解法为二分查找k的值。
- E. Good Triples：题目要求找到满足特定条件的三元组组合，解法为从十进制角度逐位枚举。
- F. Shift and Reverse：题目要求通过特定操作使数组变得非递减，解法为分析数组的基本有序性。
- G. Lights：题目要求通过开关操作使所有灯关闭，解法为构建图并进行拓扑排序，分析环的性质。
❓
延伸问答
Codeforces 第913轮的主要题目有哪些？
主要题目包括城堡移动、字符处理、删除字符对、线段跳跃、好三元组组合、数组变换和灯的开关状态等。
如何解决城堡移动的问题？
通过枚举城堡在棋盘上横向和纵向的可达格子来解决。
YetnotherbrokenKeyboard题目的解法是什么？
从后向前遍历输入字符串，删除特定的大写或小写字母。
Removal of Unattractive Pairs题目的核心思路是什么？
统计字符数量，判断是否有字符数量超过一半，以此求出剩余字符的最小数量。
Jumping Through Segments题目如何求解最小步数？
通过二分查找k的值来求解最小步数。
如何判断数组是否可以通过操作变得非递减？
分析数组的基本有序性，判断是否可以通过允许的操作实现非递减。
➡️
