CSP 2019-J2信息学奥赛题解：数字游戏与交通换乘

"这份资料是关于2019年信息学奥赛入门组复赛CSP 2019-J2题目的详细解答，主要涵盖了NOIP（全国青少年信息学奥林匹克联赛）的相关竞赛内容，适合对信息学奥赛感兴趣的学生和教练参考。" 在信息学奥赛中，CSP（非专业级软件能力认证）是一项重要的竞赛，分为入门组（CSP-J）和提高组（CSP-S），旨在检验参赛者的计算机编程能力。2019年的CSP-J2复赛中包含了一些典型的问题，如数字游戏、交通换乘和纪念品等。 首先，我们来看T1数字游戏。这是一个字符串处理问题，要求读入一个字符串并统计其中数字“1”的个数。程序中通过遍历字符串，检查每个字符是否等于'1'，如果等于，则将答案累加。示例代码简洁明了，使用了标准库`bits/stdc++.h`，并用`scanf`和`printf`进行输入输出，同时用一个循环来遍历字符串，计算'1'的数量。 接下来是T2交通换乘。这道题涉及到动态规划和数据结构的应用。问题可能是关于如何在有限的预算内，通过使用不同价格的公交优惠券进行最经济的乘车。关键策略是维护一个针对每个价格的向量，存储相应价格优惠券的获取时间，并用一个数组记录已使用的优惠券。每次乘车时，选择当前最高价格的优惠券中最早的一张使用，并更新记录。如果没有任何优惠券可用，则需要付费。这里的解决方案需要理解动态规划的原理，以及如何有效地利用数据结构优化查找过程。 最后是T3纪念品问题，它可能是一个股票交易或商品买卖的问题。题目可能要求参赛者找出在一段时间内，如何通过买入和卖出纪念品来最大化利润，而买入和卖出可以连续进行。此题的关键在于，问题可以转化为考虑在连续的两天之间进行操作，从而简化问题的解决。 这些题目展示了信息学奥赛中常见的问题类型，包括基本的字符串处理、动态规划和贪心策略。通过解决这些问题，学生可以提升自己的编程思维和算法设计能力，为参加更高层次的信息学竞赛做好准备。