前言本篇文章着重介绍CSP认证第二题常见考点，以【202012-202206】6次真题的第二题为例，旨在帮助你我从70分（暴力模拟，运行超时）到100分（利用特定技巧，降低时间复杂度）。此文参考了众多大佬的优秀文章和视频，感恩你们的分享。考点202009：常规模拟，不卡时间202012：前缀和&后缀和202104：二维前缀和202109：一维差分202112：分段&差值202203：一维差分202206：稀疏数组前置知识学习前缀和与差分图文并茂超详细整理（全网最通俗易懂）林小鹿@的博客-CSDN博客_前缀和差分【小白学算法】2.稀疏数组-知乎(zhihu.com)真题一、前缀和&后缀和题干20
前言本篇文章着重介绍CSP认证第二题常见考点，以【202012-202206】6次真题的第二题为例，旨在帮助你我从70分（暴力模拟，运行超时）到100分（利用特定技巧，降低时间复杂度）。此文参考了众多大佬的优秀文章和视频，感恩你们的分享。考点202009：常规模拟，不卡时间202012：前缀和&后缀和202104：二维前缀和202109：一维差分202112：分段&差值202203：一维差分202206：稀疏数组前置知识学习前缀和与差分图文并茂超详细整理（全网最通俗易懂）林小鹿@的博客-CSDN博客_前缀和差分【小白学算法】2.稀疏数组-知乎(zhihu.com)真题一、前缀和&后缀和题干20
想查看其他题的真题及题解的同学可以前往查看：CCF-CSP真题附题解大全试题编号：202212-2试题名称：训练计划时间限制：1.0s内存限制：512.0MB问题描述：问题背景西西艾弗岛荒野求生大赛还有 n 天开幕！问题描述为了在大赛中取得好成绩，顿顿准备在 n 天时间内完成“短跑”、“高中物理”以及“核裂变技术”等总共 m 项科目的加强训练。其中第 i 项（1≤i≤m）科目编号为 i，也可简称为科目 i。已知科目 i 耗时 ti 天，即如果从第 a 天开始训练科目 i，那么第 a+ti−1 天就是该项训练的最后一天。大部分科目的训练可以同时进行，即顿顿在同一天内可以同时进行多项科目的训练，但
想查看其他题的真题及题解的同学可以前往查看：CCF-CSP真题附题解大全试题编号：202212-2试题名称：训练计划时间限制：1.0s内存限制：512.0MB问题描述：问题背景西西艾弗岛荒野求生大赛还有 n 天开幕！问题描述为了在大赛中取得好成绩，顿顿准备在 n 天时间内完成“短跑”、“高中物理”以及“核裂变技术”等总共 m 项科目的加强训练。其中第 i 项（1≤i≤m）科目编号为 i，也可简称为科目 i。已知科目 i 耗时 ti 天，即如果从第 a 天开始训练科目 i，那么第 a+ti−1 天就是该项训练的最后一天。大部分科目的训练可以同时进行，即顿顿在同一天内可以同时进行多项科目的训练，但
题目描述新学期伊始，适逢顿顿书城有购书满 x 元包邮的活动，小P同学欣然前往准备买些参考书。一番浏览后，小P初步筛选出 n 本书加入购物车中，其中第 i 本（1≤i≤n）的价格为 ai 元。考虑到预算有限，在最终付款前小P决定再从购物车中删去几本书（也可以不删），使得剩余图书的价格总和 m 在满足包邮条件（m≥x）的前提下最小。试帮助小P计算，最终选购哪些书可以在凑够 x 元包邮的前提下花费最小？输入格式从标准输入读入数据。输入的第一行包含空格分隔的两个正整数 n 和 x，分别表示购物车中图书数量和包邮条件。接下来输入 n 行，其中第 i 行（1≤i≤n）仅包含一个正整数 ai，表示购物车中第
题目描述新学期伊始，适逢顿顿书城有购书满 x 元包邮的活动，小P同学欣然前往准备买些参考书。一番浏览后，小P初步筛选出 n 本书加入购物车中，其中第 i 本（1≤i≤n）的价格为 ai 元。考虑到预算有限，在最终付款前小P决定再从购物车中删去几本书（也可以不删），使得剩余图书的价格总和 m 在满足包邮条件（m≥x）的前提下最小。试帮助小P计算，最终选购哪些书可以在凑够 x 元包邮的前提下花费最小？输入格式从标准输入读入数据。输入的第一行包含空格分隔的两个正整数 n 和 x，分别表示购物车中图书数量和包邮条件。接下来输入 n 行，其中第 i 行（1≤i≤n）仅包含一个正整数 ai，表示购物车中第
原题链接前言： 几个月前去的这场，只打了240分，t3做乱了，转到t4看完题目直接就开始写pushup和pushdown了，把线段树板子敲完才发现线段树没法做。。。最后连暴力都没写出来。老早就看了t4的官方题解，今天才想起来补，然后这题操作1属实有点难写，又因为两个bug调了两个小时。过两天就去下一场了，希望能>300分。思路： 我是看官方题解做出来的，所以思路和题解一样。 操作1：总体是要维护1~n这些人的投票情况，最大1e9的n用数组维护无论从时间还是空间来看都不可能。所以考虑把连续的投票意愿相同的人看作一个块，用结构体表示，放到set里维护。structseg
原题链接前言： 几个月前去的这场，只打了240分，t3做乱了，转到t4看完题目直接就开始写pushup和pushdown了，把线段树板子敲完才发现线段树没法做。。。最后连暴力都没写出来。老早就看了t4的官方题解，今天才想起来补，然后这题操作1属实有点难写，又因为两个bug调了两个小时。过两天就去下一场了，希望能>300分。思路： 我是看官方题解做出来的，所以思路和题解一样。 操作1：总体是要维护1~n这些人的投票情况，最大1e9的n用数组维护无论从时间还是空间来看都不可能。所以考虑把连续的投票意愿相同的人看作一个块，用结构体表示，放到set里维护。structseg
想查看其他题的真题及题解的同学可以前往查看：CCF-CSP真题附题解大全试题编号：202212-1试题名称：现值计算时间限制：1.0s内存限制：512.0MB问题描述：问题描述评估一个长期项目的投资收益，资金的时间价值是一个必须要考虑到的因素。简单来说，假设银行的年利率为 5，那么当前的 100 元一年后就会变成 105 元，两年后变成 110.25 元。因此，现在收到 100 元比两年后收到 100 元收益更多，两年后再支出 100 元会比立刻支出 100 元更加划算。基于上述分析，我们使用如下的模型来衡量时间价值：假设银行的年利率为 i，当前（第 0 年）的 x 元就等价于第 k 年的 x
想查看其他题的真题及题解的同学可以前往查看：CCF-CSP真题附题解大全试题编号：202212-1试题名称：现值计算时间限制：1.0s内存限制：512.0MB问题描述：问题描述评估一个长期项目的投资收益，资金的时间价值是一个必须要考虑到的因素。简单来说，假设银行的年利率为 5，那么当前的 100 元一年后就会变成 105 元，两年后变成 110.25 元。因此，现在收到 100 元比两年后收到 100 元收益更多，两年后再支出 100 元会比立刻支出 100 元更加划算。基于上述分析，我们使用如下的模型来衡量时间价值：假设银行的年利率为 i，当前（第 0 年）的 x 元就等价于第 k 年的 x
