思路 这个和 点菜问题 一样，也是 0-1 背包问题，这里就不进行赘述了，用 dp[i][j] 表示限时 j 采前 i 种药的最大总价值，那最后求出来 dp[M][T] 就好了 不采第 i 种药： 采第 i 种药： 因为前面已经说过如果进行空间复杂度的优化，这里我就直接写出优化后的版本了。 #include<iostream> #include<vector> using namespace std; int main(){ int T, M; while(cin >> T >> M){ vector&lt...

练习一下C++精度设置 #include<iostream> #include<iomanip> using namespace std; int main() { int n, num; while (cin >> n) { float sum = 0; for(int i = 0; i < n; i ++){ cin >> num; sum += num; } cout << fixed &lt...

思路 很经典的 0-1 背包问题，不太熟悉的可以去看一下背包九讲，报销经费的总额就是背包的容量，其实背包问题也是动态规划，我们用 dp[i][j] 表示前 i 种菜报销经费为 j 时的最大总评价分数，那么最后结果就是dp[N][C] 我们再来看看状态转移方程怎么写，对于第 i 种菜，我们可以选择也可以不选择 如果不选择的话： 如果选择的话： 则 #include<iostream> #include<vector> using namespace std; int main(){ int C, N; while(cin >> C &...

思路 遍历比较一遍就好了 #include<iostream> #include<vector> using namespace std; int main(){ int n; while(cin >> n){ vector<int> nums(n, 0); for(int i = 0; i < n; i ++) cin >> nums[i]; if(nums[0] != nums[1]) cout << 0 <<...

思路 使用快排思路就可以了，首先我们来回顾一下快速排序，这是一个典型的分治算法。我们对数组 做快速排序的过程是： 分解： 将数组 「划分」成两个子数组 、，使得 中的每个元素小于等于 ，且 小于等于 中的每个元素。其中，计算下标 q 也是「划分」过程的一部分。 解决： 通过递归调用快速排序，对子数组 和 进行排序。 合并： 因为子数组都是原址排序的，所以不需要进行合并操作， 已经有序。 由此可以发现每次经过「划分」操作后，我们一定可以确定一个元素的最终位置，即 x 的最终位置为 q，并且保证 a[l⋯q−1] 中的每个元素小于等于 a[q]，且 a[q] 小于等于 a[q+1⋯...

思路 重载一下运算符使得可以从大到小排序就好了 #include<iostream> #include<vector> #include<algorithm> using namespace std; struct Rat{ int weight; string color; Rat(int w, string c) : weight(w), color(c){} bool operator < (const Rat& rat) const { return weight > rat....

思路 递归回溯问题，例如 abc，我们可以在每一次递归的时候把某一个字母放到最前面，就是 swap 一下，就变成了分别从 abc、bac、cba 开始的字符串，然后后面的两个字母也可以选择任意一个放到“开头”，以此类推 #include<iostream> #include<vector> #include<algorithm> using namespace std; void backtrace(vector<string>& ans, string s, int start, int len){ if(start == ...

思路 因为直接使用 find 的话不是单词也可能匹配到，所以在 a，b 前面加了空格，主要使用了 C++ 库函数的 erase(pos, len)，清楚 pos 开始的长度为 len 的子串，insert(pos, b) 在 pos 位置插入字符串 b #include <iostream> #include <string> using namespace std; int main(){ string s,a,b; getline(cin,s); getline(cin,a); getline(cin,b); s = " "...

思路 如果是普通的二叉树，求公共父节点的话，就是遍历某个根节点的左右子树，看看这两个节点是否在一棵子树上，在的话就继续遍历子树，不在的话就直接返回根节点。 而这道题，很容易看出来一个节点 i 的父节点就是 i/2，那就很简单了，不断除以 2 直到相等就好了。 #include<iostream> using namespace std; int main(){ int x, y; while(cin >> x >> y){ while(x != y){ if(x > y) x /= 2; ...

思路 其实就是走楼梯问题，设 dp[n] 为吃 n 块巧克力的方案，那要么最后剩两块一口气吃完或者最后剩一块一口气吃完，也就是 dp[n] = dp[n - 1] + dp[n - 2]，初始值 dp[1] = 1，dp[2] = 2，因为太简单我就直接写 O(1) 空间复杂度的解法了。 #include<iostream> using namespace std; int main(){ int n; while(cin >> n){ int dp1 = 1, dp2 = 2; if(n <= 2) cout ...

思路 最简单的方法就是一个个地进行判断是否与 7 有关 #include<iostream> using namespace std; bool isRelative(int num){ if(num % 7 == 0) return false; while(num){ if(num % 10 == 7) return false; num /= 10; } return true; } int main(){ int n; while(cin >> n){ int s...

思路 题干无力吐槽，借用一下讨论中的更正： 在 skew binary 表示中，第 k 位的值 x[k] 表示 x[k]×(2^(k+1)-1)。每个位上的可能数字是 0 或 1，最后面一个非零位可以是 2，例如，10120(skew) = 1×(2^5-1) + 0×(2^4-1) + 1×(2^3-1) + 2×(2^2-1) + 0×(2^1-1) = 31 + 0 + 7 + 6 + 0 = 44。前十个 skew 数是 0、1、2、10、11、12、20、100、101、以及 102。 那就很简单了。 #include<iostream> #include<cmat...