练习5-1 求m到n之和 int sum( int m, int n ){ int temp=0; for(int i=m;i<=n;i++){ temp +=i; } return temp; } 练习5-2 找两个数中最大者 int max( int a, int b ){ return a>b?a:b; } 练习5-3 字符金字塔 void CharPyramid( int n, char ch){ for(int i=0;i<n;i++){ for(int j=0;j<n-1-i;j++){ printf(" "); } for(int j=...

当k不大时可以直接模拟，时间复杂度为O(k）： #include<stdio.h> #include<vector> using namespace std; int main() { int a0, a1, p, q,k; scanf("%d%d%d%d%d", &a0, &a1, &p, &q, &k); vector<int> a(k+1); a[0] = a0; a[1] = a1; for (int i = 2; i <= k; i++) { a[i] = (p * a[i - 1]...

题目链接埃氏筛法：高效找出自然数范围内所有素数。用埃氏筛法打表出2-10000范围内的所有素数，x后面添加的数不能有前导0（仅输出最小那个）：判断x加1位，x1-x9中是否有质数；判断x加2位，x10-x99中是否有质数； #include<stdio.h> #include<vector> using namespace std; vector<int> num(10001);//0-10000全标记为质数 vector<int> prime; //埃氏筛法 void is_prime() { //0和1标记为不是质数 num[0] = 1; ...

题目链接把输入的无符号整数转化为二进制形式输出 #include <stdio.h> #include<vector> using namespace std; //除2取余，商0停止，逆序排列 int main() { unsigned int n; while (scanf("%u", &n) != EOF) { vector <int> bin; //特殊处理 if (n == 0) { printf("0\n"); continue; } else { while (n != 0) { bin.push...

0-1背包问题：背包：有一定体积/重量限制物品：只能选择一次，放入背包/不放入背包；物品有双重属性：比如体积/重量和价值目标函数：在满足容量约束的前提下，使得背包内物品的总价值最大化动态规划解题：最优解：大背包的最优解包含了小背包的最优解子问题有重叠：（用递归会冗余）记录状态避免重复递归计算 #include <stdio.h> #include <algorithm> #include <vector> #include<cstring> using namespace std; int main() { int C, N;//C总额，N种菜 ...

题目链接思路：用动态规划，dp[i]表示前i个元素的最大序列和，如果前面累加的和为负数或0，则不计入当前元素前缀最大和；否则加入； #include<stdio.h> #include<algorithm> using namespace std; long long s[1000001];//存含n个元素的序列 long long dp[1000002];//元素的取值范围 [−10^9,10^9],设成全局变量 int main() { int n;//范围1<=n<=10^6 scanf("%d", &n); for (in...

题目链接注意：公共子串是要求连续的，公共子序列可以不连续 #include<stdio.h> #include<algorithm> #include<string> using namespace std; short dp[10002][10002]; int main(){ char s1[10001], s2[10001]; scanf("%s%s", s1, s2); int m = strlen(s1); int n = strlen(s2); short maxcnt = 0; for (int i = 0; i <=...

练习动态规划，思路：dp[i][j]:表示是s1的前缀长度为i，s2的前缀长度为j时的最长公共子序列长度（不要求连续）1.边界初始化：s1的前缀长度为0，或s2的前缀长度为0时,最长公共子序列长度是02.小问题向大问题转移：若s1和s2的上一次对比元素相等，则在这次的dp值+1；若不等，则取两者相比较的最大值（最长的公共前缀值）为这次的dp值。注意点：即使当前字符并不相等，也要看看保留哪个字符，可以使得当前两个字符串（其实是长度为0到i前缀子串）公共子序列更长。 #include<stdio.h> #include<algorithm> #include<stri...

动态规划的入门练习 #include<stdio.h> #include<vector> using namespace std; int main() { int m, n; while (scanf("%d%d", &m, &n) != EOF) { //初始化dp vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0)); //0个苹果，n个盘子，只有1种分法 for (int i = 0; i <= n; i++) { dp[0][i] ...

题目链接思路：考察单源最短路径，用Dijkstra算法：BFS遍历+贪心算法1.先定义距离数组，记录所有点到起点的距离，初始正无穷2.BFS：取出起点，（如果更小）更新邻居到起点的距离(利用小根堆--优先队列结构实现）3.贪心：取出离结点最近的点，设为新起点，执行2 #include<stdio.h> #include<vector> #include<queue> using namespace std; struct Edge { int u; int v; int w; Edge(int u_, int v_, int w_) { u = u_; v ...

思路：构造最小生成树，即保证所有顶点连通（间接也可以）+边的权值最小。可用克鲁斯克拉算法求生成树：每次选权值最小的边，判断若边所在的两个顶点不连通则加入树中，否则跳过该边，一直到树构建完成（特征是边数=顶点个数-1）。 #include <cstring> #include<stdio.h> #include<vector> #include<algorithm> using namespace std; int father[1010]; //初始化 void Initfun(int n) { for (int i = 1; i < n;...

题目链接思路：依次把输入结点-结点加入集合中（形成1棵树），判断是否标记false：（注意是仅标记，非立即终止树的构造）1.有环不行：用并查集判断，在已连通的2顶点（处于同一集合，根一样），加入一条边则成环2.多个入边不行：用一个数组记录各个顶点入度3.不相连不行：无环的连通性：边数=结点个数-1ps：呜呜呜呜呜呜我以后一定认真写if-else，搞了半天没accepted，逻辑检查了几遍发现是main里面第二个if后面没写else，导致本来else中的代码也默认执行了！ #include<stdio.h> #include<vector> #include<alg...

思路：考察并查集的基本操作，根据题目要求构建并查集，初始化并查集个数为城镇个数，依次输入道路合并，最后需要建设的道路数目为并查集个数-1：合并到最后只有1个并查集，则说明集合内结点相互连通，不用建路；合并到最后只有2个并查集，之间要建1条路才连通；合并到最后只有3个并查集，之间要建2条路才连通； #include <cstring> #include<stdio.h> #include<vector> #include<algorithm> using namespace std; int father[1010]; int setCnt;//记...

题目链接题目:把含若干数字的数组任意划分成两个子数组，使得两个子数组的和相差最小。本题采用3种解法，最后一种ac。解法一：动态规划（数组和不大时可以采用，否则容易超时）思路：设数组总和为sum，目标是找到一个子数组使得子数组和尽可能<=sum/2，这样两个数组和若相等，则和相差最小是0。对于每一个数组中数字，都要更新dp数组：如果之前能凑出vec[i](数组元素），那么现在有了j，你就能凑出vev[i]+j了（前提是 vev[i]+j 不超过 target） #include<stdio.h> #include<vector> #include<algori...