题号 NC113786名称 Topforces Strikes Back 来源 CF1183F 戳我进入往期每日一题汇总贴~往期每日一题二期题单 如果你在题库做题时遇到了喜欢的题目，欢迎推荐给邓老师~ 点击查看详情每日一题QQ群:659028468 题解 作者：YangYL° 前言 这道题目是一道非常巧妙的贪心。 难度：4星 简略题意： 给定一个长度为 的序列,在序列中取至多三个数，使得这取的数互不为倍数关系。 ， 具体做法： 因为是最多取 3 个数，不妨按取的数的个数进行分类讨论。   ： 取一个数  这样的话当然是取最大的那个数最优，Pass。  ：取两个数  通过手玩几组样例后，我们发现...

题号 NC110736名称 Special Matrices 来源 CF489F 戳我进入往期每日一题汇总贴~往期每日一题二期题单 如果你在题库做题时遇到了喜欢的题目，欢迎推荐给邓老师~ 点击查看详情每日一题QQ群:659028468 题解 作者：YangYL°  前言 难度:3星 做法:dp + 滚动数组优化 题目翻译（摘选自luogu（我翻译的，引用应该没有问题吧.....））： 简化题意： 给定一个的矩阵的前行，求满足每行以及每列的和为2的01矩阵的数量 思路 (这里提供的是 O()) 的做法。 观察到数据范围，发现不大像数学题，但是貌似也不是模拟题，看到方案数，就想到了 。 考虑怎么去...

题号 NC112136名称 Hacker, pack your bags! 来源 CF822C 戳我进入往期每日一题汇总贴~往期每日一题二期题单 感谢 YangYL° 推荐题目，100牛币奖励已发放~如果你在题库做题时遇到了喜欢的题目，欢迎推荐给邓老师~ 点击查看详情每日一题QQ群:659028468 题解 前言 这是一道很棒的思维题/数据结构！ 难度：2星做法：二分，排序 线段树 题意： 给定 以及 个区间，区间 有左端点 和 右端点 以及 花费 ,要求你选出两个区间,满足下面两个条件:  两个区间没有交集 两个区间的长度和等于 (这里的长度为 )  现在要求你选出的这两个区间的权值和最小，...

题号 NC20391名称 [SDOI2017]数字表格 来源 [SDOI2017] 戳我进入往期每日一题汇总贴~往期每日一题二期题单 如果你在题库做题时遇到了喜欢的题目，欢迎推荐给邓老师~ 点击查看详情每日一题QQ群:659028468 题解 #include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 1e6 + 10, mod = 1e9 + 7, Mod = mod - 1; ll prime[N], mu[N], fib[N], phi[N], inv_fib[N], f[...

这就是传说中的牛币吧，i了i了

题号 NC26255名称 小阳的贝壳 来源 牛客小白月赛16 戳我进入往期每日一题汇总贴~往期每日一题二期题单 如果你在题库做题时遇到了喜欢的题目，欢迎推荐给邓老师~ 点击查看详情每日一题QQ群:659028468 题解 前置知识:差分数组、线段树 差分数组 设原数组为 , 令 , 称 为 的差分数组。差分数组有什么好处呢?首先不难得到 另外，对原数组 进行区间加 的操作时只需要令: ，。这样做的目的是为了让我们每次查询 的时候都能保证 的结果都是比原来多 的，从而实现了区间加法操作。 线段树 线段树是一种能够支持 复杂度进行区间查询，区间修改的数据结构。  题目是经典区间修改及查询问题，需要...

比赛名称：牛客练习赛74   活动具体内容   12月20日22:00-1月20日18:00，写牛客练习赛74题目的题解，即可获得牛币~   发放牛币的数量取决于题目难度，题目数量，题解质量   比赛结束之后点击每题后的进入题解->写题解，博客会被收录在每道题目之下   活动奖励：    在牛客博客中写题解，并回复地址，如果写了多篇题解，请在回复中说明~ 我们将在1月20日下午审核，并给每篇题解发放5-60牛币    PS:    如果题解写的非常好，会增加其获得的牛币   如果题解写的非常水，会减少获得其获得的牛币   如果题解有抄袭行为，会取消其获得牛币的资格

没有环的链表尾节点会指向空有环的链表会有一个节点指向链表中以存在的节点链表如果没有环的话，我们顺着链表的节点一直走下去，一定会遇到空节点。但是如果有环的话，我们一直顺着链表的节点走下去，就会造成死循环，那我们如何判断链表中是否有环呢？设置两个指针，一个指针一次走一步，另一个指针一次走两步,如果两个指针相遇的话，那这个链表就是有环的，这个解法时间复杂度,额外空间复杂度。表示链表中节点个数下面来证明一下为什么有环的话两个指针一定会相遇，以及一定可以在n次操作之内相遇当慢指针进入环的入口节点的时候，快指针一定在环内的某个位置，假设快慢指针这时的距离为t。如下图快指针和慢指针之间的距离就是8然后每一次...

题号 NC111227名称 Necklace 来源 CF613C 戳我进入往期每日一题汇总贴~往期每日一题二期题单 如果你在题库做题时遇到了喜欢的题目，欢迎推荐给邓老师~ 点击查看详情每日一题QQ群:659028468 题解 知识点：构造算法题意：已知每个字母的出现次数，让你构造一个环，使得存在尽可能多的切法保证切开后为一个回文串。思路：  对于所有的字母的次数而言，如果存在不小于两个奇数，那么显然无论如何也不可能构成回文串。因此输出0即可。 如果奇数只有1个或者全部是偶数，那么可以构造出回文串。怎样构造让断点尽可能多呢？可以这样思考：若存在至少两个断点，即对于回文串仍有断点，不妨设回文串中的...

题号 NC50444名称 老瞎眼 pk 小鲜肉 来源 牛客练习赛53 戳我进入往期每日一题汇总贴~往期每日一题二期题单 如果你在题库做题时遇到了喜欢的题目，欢迎推荐给邓老师~ 点击查看详情每日一题QQ群:659028468 题解 作者：nagisa_菜鸡看到题目，我想大家第一个想到的就是前缀异或和，因为这种询问一整段的异或和的一半都需要这样处理，不然复杂度太高。之后，题目要询问的就是找到在区间[L,R]中的存在的点sum[l]==sum[r],使得r-l+1最小。若是考虑直接让值对应整个[l,r]区间则会很麻烦，所以，考虑转化为单点维护。考虑单点维护，则有两个选择：要么放在l，要么放在r。那么...

设表示走到位置需要的最小路径和那首先，第一行和第一列是确定的，其余位置但是可以发现，其实不用新开辟一个dp数组，直接在原数组上更新也可以c++ class Solution { public: int minPathSum(vector<vector<int> >& matrix) { int n = matrix.size(); int m = matrix[0].size(); for(int i = 1 ; i < n ; i++){matrix[i][0] = matrix[i-1][0]+ matrix[i][0];} for(int j = 1...

回文串定义：“回文串”是一个正读和反读都一样的字符串所以，长度为1的字符串是回文串，例： “a” 进行𝑙𝑒𝑛/2次判断， 如果出现一次 𝑠𝑡𝑟[𝑖] != 𝑠𝑡𝑟[𝑙𝑒𝑛−1−𝑖] 那就不是回文，𝑙𝑒𝑛/2次判断全都相等，那么就是回文串 c++ class Solution { public: bool judge(string str) { int len = str.length(); for(int i = 0 ; i < len/2 ;i++) { if(str[i]!=str[len-1-i]) return false; } return t...

例 ：1 5 8 4 2 3 6 4 10 7 3 2 1 6对于这个样例来说，最优的交易应该是：第1天买，第3天卖第5天买，第7天卖第8天买，第10天卖第13天买，第14天卖我们再观察可以发现，其实可以简化成，只要是两天之间是上涨的，那我们就要这一段的收益。 c++ class Solution { public: int maxProfit(vector<int>& prices) { int ans = 0; for(int i = 1 ; i < prices.size() ; i++) { if(prices[i]>prices[i-1]) { ans...

题号 NC113566名称 Superhero Battle 来源 CF1141E 戳我进入往期每日一题汇总贴~往期每日一题二期题单 如果你在题库做题时遇到了喜欢的题目，欢迎推荐给邓老师~ 点击查看详情每日一题QQ群:659028468 题解 知识点：数学定义每n天为一个“周目”。那么本题应该是样思考：  如果第一周目就可以结束，那么 模拟即可。 如果第一周目无法结束，且（ 为每周目的伤害总和），那么输出-1（因为每周目后初始血量都会提升）。 如果第一周目无法结束，且，那么每周目血量会减少 这么多。这时可以记录一下所有前缀和的最小值（显然是个负数），记为min。那么，当进行了 个周目后，下两个...