philos

题解

未归档(12)

/ 注册

全部文章 / 题解（共63篇）

整除问题来自专栏

思路首先暴力求出来 n 的阶乘肯定不行，那么我们可以把 a 给拆分成若干个质因子之积，然后看下 2 ~ n 中包含多少个对应的质因子，就能得出来最多可以整除 a 的多少次方。比如 a 中有质因子、、，2 ~ n 中有对应的质因子、... 个，那 k 的最大值也就是若干个 num 的最小值。 ...

2021-03-03

32 1742

鸡兔同笼来自专栏

思路六年级记忆，但是这道题更简单一些，动物越多也就是鸡尽量多就好了，动物越少也就是兔子尽量多就好了。但是总脚数肯定是偶数。 #include <iostream> #include <vector> using namespace std; int main(){ ...

2021-03-03

0 494

八皇后来自专栏

思路八皇后问题是很经典的递归回溯问题，就是在每一行尝试放置皇后，观察是否会冲突，这里就最简单粗暴的写出来解法吧。 #include <iostream> #include <vector> using namespace std; /* 检查是否冲突 */ bool i...

2021-03-02

0 584

拦截导弹来自专栏

思路首先先捋清一下题意：有若干发炮弹，拦截系统拦截的导弹的高度必须是递减的，那这道题就变成了最长下降子序列了，和下面一道题类似，用动态规划求解。用 dp[i] 表示以 i 结尾的子序列的最长长度，那么状态转移方程为： #include<iostream> #include<v...

2021-03-02

0 669

字符串排序来自专栏

思路我们一条条规则进行分析，首先看前两条，不区分大小写字母以及按照输入顺序排序，这就很简单了，我们构造一个数据结构，给相同的字母赋相同的值，因为要按照输入顺序进行排序，可以使用 stable_sort 或者再向数据结构中添加下标字段，排序的时候值相同比较下标（这里采用第二种做法）。这里也牵扯到自...

2021-03-02

2 787

采药来自专栏

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

2021-03-02

0 631

求平均年龄来自专栏

练习一下C++精度设置 #include<iostream> #include<iomanip> using namespace std; int main() { int n, num; while (cin >> n) { ...

2021-03-02

1 867

点菜问题来自专栏

思路很经典的 0-1 背包问题，不太熟悉的可以去看一下背包九讲，报销经费的总额就是背包的容量，其实背包问题也是动态规划，我们用 dp[i][j] 表示前 i 种菜报销经费为 j 时的最大总评价分数，那么最后结果就是dp[N][C] 我们再来看看状态转移方程怎么写，对于第 i 种菜，我们可以选择也可...

2021-03-02

0 656

打印极值点下标来自专栏

思路遍历比较一遍就好了 #include<iostream> #include<vector> using namespace std; int main(){ int n; while(cin >> n){ vector&l...

2021-02-08

0 478

中位数来自专栏

思路使用快排思路就可以了，首先我们来回顾一下快速排序，这是一个典型的分治算法。我们对数组做快速排序的过程是：分解：将数组「划分」成两个子数组、，使得中的每个元素小于等于，且小于等于中的每个元素。其中，计算下标 q 也是「划分」过程的一部分。解决：通过递归调用快速排序...

2021-02-07

2 639