王清楚

分类

ACM(1) PAT(3) uva(1) 未归档(9) 题解(95)

/ 注册

TA的专栏 59篇文章 1人订阅

牛客题霸题解

59篇文章 2787人学习

全部文章（共110篇）

【题解】子数组的最大异或和

记表示数组前个数的异或和，就是区间的异或和那如果想知道以位置结尾的子数组的最大异或和，只需要知道和中的数异或的最大值就可以了。（即这些区间异或和的最大值）那怎么样快速地知道和中的数异或和的最大值呢?我们利用前缀树的结构，对每一个，从最高位到最低位判断。这里需要注意一下，因为我们想...

2020-10-15

4 1297

【题解】换钱的最少货币数

表示组成价值需要的最少的货币数如果目前情况下价值目前最少能由个货币组成，那么加了一个价值的商品，就可以由个货币组成对于每一个物品，从循环一遍，更新dp的值。所有的物品都加入完毕以后，就是结果。 #include<iostream> using namespace std; co...

2020-10-10

6 894

【题解】比大小

利用栈来操作，如果当前入栈的元素比栈顶元素大，那这个元素就是栈顶元素右边第一个比栈顶元素大的元素。如果当前元素比栈顶元素小。或者栈为空，那当前元素入栈。 #include<iostream> #include<stack> #include<vector> usi...

2020-09-23

4 820

【题解】遍历二叉树

这道题一开始看到的时候想先把二叉树剪出来，然后再找出叶子节点做一个动态规划，然后仔细一想发现，对于满二叉树来说，中序遍历的第1，3，5，7.。。项就是叶子节点。那我们就可以直接获得叶子节点了，然后用表示前个节点可以获得的最大粮食数，可以从(偷当前节点的粮食)和(不偷当前节点的粮食)转移而来...

2020-09-22

8 744

【题解】矩阵中的路径

比较裸的搜索题，从矩阵的每一个位置开始搜索，看能不能达成一个成功的字符串这道题给出的矩阵是按一维字符串给的。所以(x,y)应该是x*cols+y #include<iostream> #include<cstring> using namespace std; class S...

2020-09-22

4 713

【题解】矿泉水问题

先判断一下买大瓶水划算还是买小瓶水划算，如果小瓶水划算，那么就全买小瓶水，如果大瓶水划算的话，看一下全买大桶水价钱低还是尽量多的买大桶水，剩下不满1500ml的部分买小瓶水价钱低。 #include<iostream> #include<cmath> #include<...

2020-09-18

7 611

【题解】代金券组合

表示实现凑价格最少需要几张优惠券，那么就是要求的结果。对于每张优惠券。都遍历一遍。看一下加上这张优惠券能不能有更好的效果。 #include<iostream> using namespace std; const int INF = 0x3f3f3f3f; int mai...

2020-09-18

6 928

【题解】括号字符串的最长有效长度

动态规划解法，dp[i]表示以i为开始的最长有效括号字符串的长度，只有以'('开始有可能出现有效括号串，对于每一个'('来说，要凑出一个有效的括号字符串肯定是'('+一段有效的括号字符串+')' +一段有效的括号字符串 #include<iostream> using namespa...

2020-09-18

6 989

【题解】合并区间

先把区间按区间的起始位置从小到大排序，然后从前往后看一遍，如果下一个区间的开始比前一个区间的末尾要小。那么这两个区间就可以合并。 #include<iostream> #include<algorithm> using namespace std; const int M...

2020-09-18

2 782

【题解】生产机器

第n个月的兔子可以分成4类，一类是成熟的兔子f(n-3)，第二类是刚出生的兔子f(n-3)，第三类是出生了一个月的兔子f(n-4)，第四类是出生了两个月的兔子f(n-5) #include<iostream> using namespace std; const int MAXN =...

2020-09-17

2 776