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

题号 NC112558名称 List Of Integers 来源 CF920G 戳我进入往期每日一题汇总贴~往期每日一题二期题单 如果你在题库做题时遇到了喜欢的题目，欢迎推荐给邓老师~ 点击查看详情每日一题QQ群:659028468 题解 作者：@。。。201910131627798  分析 求第 大的大于等于 且与 互质的数，那么我们先考虑如果我们枚举第 大是谁，其实并不好做。这样时间复杂度的的下限至少为 。那么我们考虑二分一个值 ， 与 互质的数的总个数求出来，这样二分的值就具有单调性了，也可以很好的处理大于等于 这个条件，做一次差分就好了。那么现在算法的主要问题就是如何求出 有几个数与...

利用栈来操作，如果当前入栈的元素比栈顶元素大，那这个元素就是栈顶元素右边第一个比栈顶元素大的元素。如果当前元素比栈顶元素小。或者栈为空，那当前元素入栈。 #include<iostream> #include<stack> #include<vector> using namespace std; const int MAXN = 1e6+10; int arr[MAXN]; int ans[MAXN]; int main() { int N; cin >> N; for(int i = 0 ; i < N ; i++) { cin &gt...

题号 NC19974名称 [HAOI2008]硬币购物 来源 [HAOI2008] 戳我进入往期每日一题汇总贴~往期每日一题二期题单 如果你在题库做题时遇到了喜欢的题目，欢迎推荐给邓老师~ 点击查看详情每日一题QQ群:659028468 题解 直接背包会T，考虑容斥首先算出当硬币无限的时候情况——跑一个完全背包。然后我们容斥一下即可，也就是减掉每一种硬币有限制的方案数的和加上某两种硬币有限制的方案数的和……那么问题变成了：当完全背包的数组出来以后，我们能算出第一种硬币的限制为d[1]的情况的方案数么？显然它等于总数减一种硬币超过 个的方法数，即其中其实是我先选上个第一种，然后剩下背包随便装，这...

这道题一开始看到的时候想先把二叉树剪出来，然后再找出叶子节点做一个动态规划，然后仔细一想发现，对于满二叉树来说，中序遍历的第1，3，5，7.。。项就是叶子节点。那我们就可以直接获得叶子节点了， 然后用 表示前 个节点可以获得的最大粮食数，可以从(偷当前节点的粮食)和(不偷当前节点的粮食)转移而来。 #include<iostream> using namespace std; const int MAXN = 1e5+10; int main() { int n; cin >> n; int t; for(int i = 0 ; i < n ; i++){cin ...

比较裸的搜索题，从矩阵的每一个位置开始搜索，看能不能达成一个成功的字符串这道题给出的矩阵是按一维字符串给的。所以(x,y)应该是x*cols+y #include<iostream> #include<cstring> using namespace std; class Solution { public: bool hasPath(char* matrix, int rows, int cols, char* str) { for(int i = 0 ; i < rows ; i++) { for(int j = 0 ; j < cols ; j++)/...

题号 NC19857名称 最后的晚餐(dinner) 来源 牛客OI周赛4-提高组 戳我进入往期每日一题汇总贴~往期每日一题二期题单 如果你在题库做题时遇到了喜欢的题目，欢迎推荐给邓老师~ 点击查看详情每日一题QQ群:659028468 题解 基本容斥，根据正难则反的方式我们考虑用全部的方案-不合法的方案；全部方案：(2n-1)!减去：(注意:严格的说，这个并不是至少有一队相邻的方案数，因为诸如第1对和第3对都相邻的情况在这里面被算了两次——组合数选到第1对的时候算了一次，组合数算到第3对的时候也算了一次，这也就是为什么要容斥的原因。)所以他还有重新加上这个又有算重的……以此类推：  另外：@...

题单链接：https://ac.nowcoder.com/acm/problem/collection/910BZOJ41 排队 https://ac.nowcoder.com/acm/problem/211255BZOJ229 向量 https://ac.nowcoder.com/acm/problem/19985BZOJ1001 狼抓兔子 https://ac.nowcoder.com/acm/problem/209695BZOJ1002 轮状病毒 https://ac.nowcoder.com/acm/problem/19951BZOJ1003 物流运输trans https://ac....

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

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

先判断一下买大瓶水划算还是买小瓶水划算，如果小瓶水划算，那么就全买小瓶水，如果大瓶水划算的话，看一下全买大桶水价钱低还是尽量多的买大桶水，剩下不满1500ml的部分买小瓶水价钱低。 #include<iostream> #include<cmath> #include<cstdio> using namespace std; int main() { int T; cin >> T; while(T--) { int x,a,b; cin >> x >> a >> b; if(b/3<a) { cout&...

表示实现凑价格 最少需要几张优惠券，那么 就是要求的结果。对于每张优惠券。都遍历一遍 。看一下加上这张优惠券能不能有更好的效果。 #include<iostream> using namespace std; const int INF = 0x3f3f3f3f; int main() { int P; int dp[10010]={0}; while(cin >> P && P!=0) { int N; cin >> N; int v; for(int i = 0 ; i <= P ; i++) { dp[i]=INF; } for(...

动态规划解法，dp[i]表示以i为开始的最长有效括号字符串的长度，只有以'('开始有可能出现有效括号串，对于每一个'('来说，要凑出一个有效的括号字符串 肯定是'('+一段有效的括号字符串+')' +一段有效的括号字符串 #include<iostream> using namespace std; const int MAXN = 1e5+10; int main() { string s; cin >> s; int ans = 0; int dp[MAXN]={0}; for(int i = s.length()-2 ; i >= 0 ; i--) { if...

题号 NC20271名称 [SCOI2009]游戏 来源 [SCOI2009]戳我进入往期每日一题汇总贴~往期每日一题二期题单 如果你在题库做题时遇到了喜欢的题目，欢迎推荐给邓老师~ 点击查看详情每日一题QQ群:659028468 题解 首先，对于任何的一组置换我们都可以把它换成若干的轮换（即A->B,B->C,C->D,D->A这样子转一圈），因为如果a变成b,b变成c……之后没有一个数变回a的话，在变化之后的数列里面a就没有了，所以一定会形成一个圈。那么对于一个有x个元素的轮换，显然换X次才能换回原样，那么对于所有的轮换，他们的LCM就是答案。于是问题就变成了：把n...