B 减成一 题目地址： https://ac.nowcoder.com/acm/contest/5758/B 基本思路： 我们求出差分数组，可以发现题意就是让我们每次将差分数组-1，+1，最后将差分数组变为第一个数为1其他数都为0的最小次数，因此实际答案就是差分数组中的正数之和减一。 参考代码： #pragma GCC optimize(2) #pragma GCC optimize(3) #include <bits/stdc++.h> using namespace std; #define IO std::ios::sync_with_stdio(false) #...

E 赛马 题目地址： https://ac.nowcoder.com/acm/contest/5758/E 基本思路： 我们考虑贪心，也就是说对于对方的每匹马，我们找比他大但是最小的那匹马去和他打。那么由于数据量很小，所以我们可以暴力实现这个过程，但是更优的，我们可以将双方的马放在一起排序，然后从前往后对于对方的每匹马，我们用小明的马和他匹配，然后最大的匹配数就是答案了，但是我们要注意相等的情况，所以相等的时候我们应该让小明的马在前面。 参考代码： #pragma GCC optimize(2) #pragma GCC optimize(3) #include <bits/s...

J 最大值 题目地址： https://ac.nowcoder.com/acm/contest/5758/J 基本思路： 我们观察题目的意思，然后我们联想一下KMP中的next数组的定义，next数组是在当前位置前后缀相等的长度，其实和题目中要找的AC串是一个意思，因此在next数组中找最大就行了。 参考代码： #pragma GCC optimize(2) #pragma GCC optimize(3) #include <bits/stdc++.h> using namespace std; #define IO std::ios::sync_with_stdio(...

H 直线 题目地址： https://ac.nowcoder.com/acm/contest/5758/H 基本思路： 容易推得结论条直线在平面上最多的交点数为，由于数据比较大，所以我们开就行了。 参考代码： #pragma GCC optimize(2) #pragma GCC optimize(3) #include <bits/stdc++.h> using namespace std; #define IO std::ios::sync_with_stdio(false) #define int __int128 #define rep(i, l, r) for...

C 面积 题目地址： https://ac.nowcoder.com/acm/contest/5758/C、 基本思路： 签到题，两个圆的面积加中间的正方形，注意输出换行。 参考代码： #pragma GCC optimize(2) #pragma GCC optimize(3) #include <bits/stdc++.h> using namespace std; #define IO std::ios::sync_with_stdio(false) #define ll long long #define rep(i, l, r) for (int i = l;...

NC15748 旅游 题目地址： https://ac.nowcoder.com/acm/problem/15748 基本思路： 考虑树形，对于每个节点我们考虑两个状态，住或者不住。我们让表示当前节点住的情况下这棵子树的最长旅行时间，同理令表示在当前节点不住的情况下这颗子树的最长旅行时间。我们根据题意容易分析到，如果当前位置住，那么它的子节点只能选择不住，否者可以选择住或者不住。因此我们应该很容易推断出以下的转移方程: ; ;然后我们以s为根跑一遍就能发现就是答案。 参考代码： #pragma GCC optimize(2) #pragma GCC optimize(3) #inc...

NC25043 Protecting the Flower 题目地址： https://ac.nowcoder.com/acm/problem/25043 基本思路： 又是这种改排序贪心，我们先只考虑两只牛谁先更优，假如先再那么损耗的花为，假如先再那么损耗的花为，那么我们可以知道只要根据和的大小排序，就能决定这两只牛谁先谁后，那么实际上容易证这个对于更多牛的情况也是普遍成立的，因此根据此规则排序然后直接模拟一遍题意统计答案就行了。 参考代码： #pragma GCC optimize(2) #pragma GCC optimize(3) #include <bits/stdc...

NC21228 货币系统 题目地址： https://ac.nowcoder.com/acm/problem/21228 基本思路： 这题的关键在于我们要清楚面值大的金币只会被面值小的金币组成，因此我们只要将金币的面值进行一个排序，就能发现这个问题直接转换为了一个存在性的完全背包问题。我们将之前面值小的硬币跑完全背包，就能确定当前的面值是否是必需的(能否被组成)，如果必需那么我们加入答案并且再用该面值更新我们的完全背包就行了。 参考代码： #pragma GCC optimize(2) #pragma GCC optimize(3) #include <bits/stdc++...

NC20154 [JSOI2007]建筑抢修 题目地址： https://ac.nowcoder.com/acm/problem/20154 基本思路： 考虑贪心，我们先将建筑队列按照截止时间排序，然后我们依次选择，但是这个时候我们发现可能会出现一个事件持续时间过长而占用过多时间的情况，所以我们考虑一种能将之前耗时最长的工作进行替换的操作，而这个操作我们可以使用优先队列实现。我们使用优先队列维护队列中工作的耗时，在无法添加工作的情况下我们将队列中的最大值替换以减少时间消耗，这样我们在不改变之前结果的情况下给了之后任务更大的空闲时间，这样贪心我们就能得到最优解。 参考代码： #pra...

NC14414 小AA的数列 题目地址： https://ac.nowcoder.com/acm/problem/14414 基本思路： 首先我们发现这是一个区间位运算的题，所以依照惯有套路，我们对于每一个二进制位分位考虑，我们发现每一位的贡献次数应该等于异或值为1且符合条件的区间的数目，然后因为对于每一位我们要找区间异或值，所以这一部分可以再使用区间异或前缀和来搞一下，然后我们还发现要考虑奇偶的情况，所以我们再对奇偶位置分别考虑分开计算就是了。 参考代码： #pragma GCC optimize(2) #pragma GCC optimize(3) #include <...

NC19913 [CQOI2009]中位数图 题目地址： https://ac.nowcoder.com/acm/problem/19913 基本思路： 最近几天都没写题解，感冒了难受QAQ。这题比较经典的套路了，我们观察这是1~n的排列，也就是说只在数组中出现一次，知道了这个我们想假如令小于的数为，大于的数为，等于的数为，那么要找到题目要求的连续子序列，我们只要在的位置左右找到两个位置使其满足加上的和为，这部分我们可以根据前缀和先算一边的情况，然后用map储存每个数的出现次数，然后再算另一边的时候加上map里储存的次数就是了。 参考代码： #pragma GCC optimize...

NC14734 比赛 题目地址： https://ac.nowcoder.com/acm/problem/14734 基本思路： 这道题的思路比较明了，我们先通过题目说的三种情况算出每道题的真正通过率：；然后我们可以使用状态枚举等方法计算出答案，但是我们发现因为每道题只有对错两种可能，而且只有12题，所以我们直接状压枚举出所有可能状态，然后对于每个状态里正确题目的数量分别统计答案就是了。 参考代码： #pragma GCC optimize(2) #pragma GCC optimize(3) #include <bits/stdc++.h> using namespa...

NC53676「土」秘法地震 题目地址： https://ac.nowcoder.com/acm/problem/53676 基本思路： 非常裸的一道二维前缀和，我们做出这个矩阵的二维前缀和，每次判断是否会停止施法就是了。关于二维前缀和的求法为递推式：，我们可以大脑中想象一下，应该很容易想到这个递推式是合理的，然后二维前缀和的查询方式，假设我们要找,,到,这部分子矩阵的和那么答案就是 这个大家可以自己画图辅助理解。(我拿鼠标画图疯狂手抖，就不画了OAO) 参考代码: #pragma GCC optimize(2) #pragma GCC optimize(3) #include &...

NC14683 储物点的距离 题目地址： https://ac.nowcoder.com/acm/problem/14683 基本思路： 比较经典的前缀和应用，我们先将输入中前后两个储物点的距离，转化一次前缀和存在数组a中，这时候既可以将储物点定位在数轴中，然后 , 两点间的运送代价即为：那么区间内的东西转移到的的代价和即为，也就是 前半部分我们求一下的前缀和就能每次O(1)求到，同理后半部分我们求的前缀和也能每次O(1)求到，因此我们只要讨论一下这个绝对值的情况就是了，这部分可以画个数轴辅助一下理解，应该不难，然后就是注意取模有负数。 参考代码： #pragma GCC op...