算法入门笔记：背包dp //01背包 void ZeroOnePack(int v, int w, int m) { //v为当前物品的容量 m为给定最大的容量 w为当前物品的价值for (int i = m; i >= v; i--) {dp[i] = max(dp[i], dp[i - v] + w);} }//完全背包 void CompletePack(int v, int w, int m) { //v为当前物品的容量 m为给定最大的容量 w为当前物品的价值for (int i = v; i <= m; i++) {dp[i] = max(dp[i], dp[i - v] + w);} }//多重背包 void MultiPac...
一、 算法入门博主在市面上发现了很多，很多有关书算法的书籍，但是真正能够让初学者易懂的算法书籍，只是一点点，以下我讲以 Aditya Bhargava写的一本关于算法的入门书籍，为参考，这本书非常的优秀，浅显易懂，图文并茂！带你走进算法的世界，要知道，作为一名优秀的程序员，不会算法是不行滴。 书籍的地址，可以给博主留言，也可以加我QQ或者微信，欢迎你和我一起来探讨，编程世界的秘密二、 算法简介所谓的算法是一组完成任务的...
DFS入门例题 棋盘问题 问题描述： 在一个给定形状的棋盘（形状可能是不规则的）上面摆放棋子，棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列，请编程求解对于给定形状和大小的棋盘，摆放k个棋子的所有可行的摆放方案C。 Input: 输入含有多组测试数据。 每组数据的第一行是两个正整数，n k，用一个空格隔开，表示了将在一个n*n的矩阵内描述棋盘，以及摆放棋子的数目。 n <= 8 , k <= n 当为-1 -1时表示输...
【Notes】WA 题目描述Sample Input 3 1 2 3 2 3 4 9223372036854775807 -9223372036854775808 0Sample Output Case #1: false Case #2: true Case #3: false问题代码 【Notes】想得也太简单了= - = #include<cstdio>int main() {long long int a,b,c;int n; scanf("%d",&n);for(int i=0;i<n;i++){scanf("%lld%lld%lld",&a,&b,&c);if((a+b)>c) printf("Case #%d: true\n",i+1);else printf("Case #%d: false\n",i+1);} return 0; }...
尺取算法 入门+模板+例题 博客推荐 尺取法原理及模板 https://blog.csdn.net/doubleguy/article/details/81265327 一些入门例题 https://blog.csdn.net/lxt_Lucia/article/details/81091597 模板 这里根据题目POJ 3061来具体实现。 题意是说给你一个有数字组成的序列，找出最短的子串（注意：子串是连续的，子序列可以不连续）,使得这个子串的和大于等于S,求子串的长度。 思路：使用尺取法来解决。 #include<cmath> #include<cstdi...
习题1-1 平均数（average） 输入3个整数，输出它们的平均值，保留3位小数。 #include<stdio.h> int main() {int a,b,c;double ave;scanf("%d%d%d",&a,&b,&c);ave = (a+b+c)/3.0;printf("%.3f\n",ave);return 0; }习题1-2 温度（temperature） 输入华氏温度f，输出对应的摄氏温度c，保留3位小数。 提示：c＝5（f－32）/9。 #include<stdio.h> int main() {double f,c;scanf("%lf",&f);c= 5*(f-32)/9.0;printf("%.3f\n",c);return 0;...
输入两个整数a和b，交换二者的值，然后输出。 样例输入： 824 16 样例输出： 16 824 #include<stdio.h> int main() {int a,b;scanf("%d %d",&a,&b);printf("%d %d\n",b,a);return 0; }#include<stdio.h> int main() {int a,b,c;scanf("%d %d",&a,&b);c = a;a = b;b = c;printf("%d %d\n",a,b);return 0; }#include<stdio.h> int main() {int a,b;scanf("%d %d",&a,&b);a = a+b;b = a-b;a = a-b;printf("%d %d\n",a,b);return 0; }点...
Manacher 算法 回文串专用算法manacher 人名，该算法的发明者。palindrome名词：回文。博客推荐 https://www.cnblogs.com/lykkk/p/10460087.html，比较简洁，代码清晰。 https://www.cnblogs.com/cloudplankroader/p/10988844.html， 一些细节的东西比较讲解比较细。 模板 //预处理函数，使得处理后的字符串长度为奇数，并且有一些比较好的性质 int init(char* s, char* ss) {int len=strlen(s);ss[0]='@'; ss[1]='#';int j=2;for(...
拓展KMP算法入门 博客推荐 扩展KMP算法, 图很形象，代码写的也很清晰，下面的模板就是出自该博客文章。 拓展KMP是求母串S长度为n和子串T长度为m,求S的每一个后缀子串与T的前缀子串匹配的最长长度。 代码实现 //求解模式串T的next数组，这个函数和下面的函数几乎相同 void getnext(string &T, int m, int[] next) {int a = 0, p = 0;next[0] = m; //T字符串自身和自身匹配for(int i=1; i<m; i++){if(i >= p || i + next[i - a] >= p...
4.1 排序 4.1.1 选择排序 简单选择排序是指，对一个序列A中的元素A[1] ~ A[n],令i从1到n枚举，进行n趟操作，每趟从待排序部分[i,n]中选择最小的元素，令其与待排序部分的第一个元素A[i]进行交换，这样元素A[i]就会与当前有序区间[1,i-1]形成新的有序区间[1,i]。 4.1.2 插入排序 直接插入排序是指，对序列A的n个元素A[1] ~ A[n],令i从2到n枚举，进行n-1趟操作。假设某一趟时，序列A的前i-1个元素A[1] ~ A[i-1]已经有序，而范围[i,n]...
小编今天学习了一下 分治策略（参考 算法导论），并用python代码实现了一下 实例中的 方法。大家一起相互学习啦。首先是 插入排序的方法： 时间复杂度为 (n^2)。 代码实现如下：# 插入排序法 a = [2,1,6,5,4,8,9] for i in range(int(len(a))):for j in range(int(len(a))-1):if a[j] > a[j+1]:b = a[j]a[j] = a[j+1]a[j+1] = b print("增序列表" + str(a))然后就是： 归并排序法，时间复杂度为 nlog(n)：# 归并排序法 a = [2,1,...
PAT B1036?跟奥巴马一起编程?(15分)美国总统奥巴马不仅呼吁所有人都学习编程，甚至以身作则编写代码，成为美国历史上首位编写计算机代码的总统。2014 年底，为庆祝“计算机科学教育周”正式启动，奥巴马编写了很简单的计算机代码：在屏幕上画一个正方形。现在你也跟他一起画吧！ 输入格式： 输入在一行中给出正方形边长 N（3）和组成正方形边的某种字符 C，间隔一个空格。 输出格式： 输出由给定字符 C 画出的正方形。但是注意到行...
算法竞赛入门经典——数组和字符串 注意点： 1.比较大的数组应尽量声明在main函数外，否则程序可能无法运行。 2.C语言的数组并不是“一等公民”，而是“受歧视”的。例如，数组不能够进行赋值操作，如果声明“int a[maxn],b[maxn]”，是不能赋值b=a的。如果要从数组a复制k个元素到数组b，可以这样做：memcpy(b,a,sizeof(int)*k)。当然，如果数组a和b都是浮点型的，复制时要写成“memcpy(b,a,sizeof(double)*k)”，另外需要注意的是...
12道java经典入门算法题！ 【程序1】 题目：将一个数组逆序输出。 程序分析：用第一个与最后一个交换。 其实，用循环控制变量更简单： for(int k=11;k>=1;k--) System.out.print(myarr[k]+","); 【程序2】 题目：取一个整数a从右端开始的4～7位。 程序分析：可以这样考虑： (1)先使a右移4位。 (2)设置一个低4位全为1,其余全为0的数。可用~(~0 < <4) (3)将上面二者进行&运算。 public class Ex32 {...
【程序1】 题目：求1+2!+3!+...+20!的和 1.程序分析：此程序只是把累加变成了累乘。 public class Ex21 { static long sum = 0; static long fac = 0; public static void main(String[] args) { long sum = 0; long fac = 1; for(int i=1; i<=10; i++) { fac = fac * i; sum += fac; } System.out.println(sum); } } 【程序2】 题目：利用递归方法求5!。 1.程序分析：递归公式：fn=fn_1*4! ...