philos

分类

未归档(12) 题解(63)

/ 注册

TA的专栏 75篇文章 0人订阅

64篇文章 1825人学习

复旦历年机考题解

11篇文章 643人学习

全部文章（共75篇）

字母统计来自专栏

简单地开辟一个大小为26的数组存储一下每个字母的个数就好了 #include<iostream> using namespace std; int main(){ string s; while(cin >> s){ int chars[2...

2021-03-05

0 731

最小面积矩阵来自专栏

思路这一题还是有些复杂的，先说一下大致思路：任选两列，把这两列间的元素相加成一列，即一维数组，实际宽度为 j - i + 1 遍历一维数组，找到和大于等于 K 的最短连续子序列，长度为 len 那么上面对应的子矩阵的面积为 (j - i + 1) * len 重复上述过程找到最小值我们先来...

2021-03-03

1 1184

整除问题来自专栏

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

2021-03-03

27 1712

鸡兔同笼来自专栏

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

2021-03-03

0 482

八皇后来自专栏

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

2021-03-02

0 571

拦截导弹来自专栏

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

2021-03-02

0 652

字符串排序来自专栏

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

2021-03-02

2 771

采药来自专栏

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

2021-03-02

0 605

求平均年龄来自专栏

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

2021-03-02

1 857

点菜问题来自专栏

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

2021-03-02

0 643