-
[综合] 如何实现O(n)的2-sum
2-sum问题实现找数组中的二元数组(a,b)(a+b=0) 方法一: 循环O(n2) 方法二:二分查找: for(inti=0;i<n;i++){ Binary_Search(-a[i]); } 结果O(nlogn) 方法三:牺牲空间换取时间基数排序算法 比如10^8内的整数 a[10^8]...
67
热度 -
[综合] Find local minima in an array
YouaregivenanarrayArr[1..n]withthespecialpropertythatArr[1]≥Arr[2]andArr[n?1]≤Arr[n].WesaythatanelementArr[x]isalocalminimumifitislessthanorequaltobot...
18
热度 -
87
热度 -
46
热度 -
[综合] scanf的使用注意
格式字符串 格式字符串的一般形式为: %[*][输入数据宽度][长度]类型 其中有方括号[]的项为任选项。各项的意义如下。 %x和%X都能读16进制,并且他们不区分A和a 2)“*”符用以表示该输入项,读入后不赋予相应的变量,即跳过该输入值。如: scanf("%d%*d%d",&...
32
热度 -
[综合] c++ string reverse 用法
reverse() std::voidreverse(s.begin(),s.end()); 上面是原地反转的方法,如果需要反转到别的string里面,一样简单: s1.assign(s.rbegin(),s.rend()); 效率也相当理想。
58
热度 -
[综合] memset calloc malloc
calloc虽然把内存都初始化了,但是会降低效率,相当于Malloc完了在进行一个memset: 1.分配内存空间函数malloc调用形式:(类型说明符*)malloc(size)功能:在内存的动态存储区中分配一块长度为"size"字节的连续区域。函数的返回值为该区域的首地址。“类型说明符”表示把...
35
热度 -
9
热度 -
[综合] 弗洛伊德算法 路径还原
用DP来解决,在只使用顶点0~k和i,j的情况下(i,j作为起点和重点,0~k个点作为中间点),记i到j的最短长度为dp[k][i][j],k=-1表示只是用i和j两个点,此时dp[0][i][j]=cost[i][j] 接下来,我们分i到j的最短路恰好经过k和不经过k两种,如果不经过k点 那么就是...
3
热度 -
[综合] 0-1背包问题:输出最小背包
如何输出最小背包? 0-1背包 #include<iostream> usingnamespacestd; constintmaxn=1005; intdp[maxn][maxn]; intweight[maxn]; intvalue[maxn]; intn,v; intmax(int...
7
热度 -
[综合] 部分和问题-dfs穷举
给定整数a1,a2,..am判断是否可以从中选出若干个数字,使得他们的和恰好为n 我们要判断每个数字选或者不选 #include<iostream> usingnamespacestd; constintmaxn=10005; inta[maxn]; intn; intsum; boo...
19
热度 -
82
热度 -
83
热度 -
90
热度 -
91
热度 -
[综合] 尺取法 poj3061
尺取法:就是两个指针表示区间[l,r]的开始与结束然后根据题目来将端点移动,是一种十分有效的做法。适合连续区间的问题 1poj3061 给定长度为n的数列整数a0,a1,a2,a3.....an-1以及整数S。求出和不小于S的连续子序列的长度的最小值。如果解不存在,则输出0。 方法1;暴力:O(n^...
34
热度 -
[综合] dp-挑战程序设计竞赛-状态的选择 多重部分和 LIS
DP的核心是状态的定义,状态的巧妙定义。 多重部分和 题目:给定整数a1、a2、.......an,每种数各mi个,判断是否可以从中选出若干数,使它们的和恰好为K。 分析:这是一个完全背包恰好装满的问题,当然可以用O(NKmi) 但通过把状态dp[i][j]定义成第i个数字使得和为j剩下的个数 这样...
61
热度 -
[综合] 大一下一点小小的总结
1.对于学校的课,想要拿高绩点,上课的ppt是很主要的。读透课本倒不是那么必要。 2.正如李笑来所说,很多时候犹豫要不要去做这件事情的成本比深入了解的时间花的还多。很多事情可以先先做一下再判断可不可做。
12
热度 -
[综合] pair (c++)
pair的类型: pair实质上是一个结构体 pair是一种模版类型。每个pair可以存储两个值。这两种值无限制。也可以将自己写的struct的对象放进去。。 pair<string,int>p; pair<int,int>p; pair<double,int>p...
82
热度 -
28
热度