qq1214917885的博客
qq1214917885 · 共 23 篇文章
[置顶] 经验贴
20.两个分数求最小公倍数:先得到两个最简的分数,然后用这两个分数的分子的最小公倍数 / 这两个分数的分母的最大公约数。即答案 19.用int开的数组MLE的时候可以考虑题目数据是不是在short的范围内改用short可以缓解。 如果不行则考虑滚动数组节约内存。 18.对字符数组的输入还可以控制从某个位置开始读入,例如: char s[22]; scanf("%s", s + 1); //或者 cin >> s + 1; //这样读入的时候第一个字符就在s[1]了 17.在正数范围比long long 还要厉害的有unsigned long long.... 16.递归中要注意剪枝,因为递归…
2014-11-24 17:53 · 评论(0)
HDU1261解题报告
中文题意略。 就是要求排列组合a1Cn * a2C(n-a1) * a3C(n - a1 - a2)………… 不过要高精就是了。 通过这个题学到了高精度排列组合公式的简洁写法。同时掌握了高精乘法和除法。 void bign(int a, int n)//总值乘以n,除以a { int c = 0; int i, j; for (j = 0; j < N; ++j) //高精乘法 { c = sum[j] * n + c; sum[j] = c % 10; c = c / 10; } c = 0; for (j = N - 1; j >= 0; --j) //高精除法 { c = sum[j]…
2015-04-07 17:19 · 评论(0)
一些基础数学平面问题
以下引用自http://blog.csdn.net/lishuhuakai/article/details/8518245 (1) n条直线最多分平面问题 题目大致如:n条直线,最多可以把平面分为多少个区域。 析:可能你以前就见过这题目,这充其量是一道初中的思考题。但一个类型的题目还是从简单的入手,才容易发现规律。当有n-1条直线时,平面最多被分成了f(n-1)个区域。则第n条直线要是切成的区域数最多,就必须与每条直线相交且不能有同一交点。 这样就会得到n-1个交点。这些交点将第n条直线分为2条射线和n-2条线断。而每条射线和线断将以有的区域一分为二。这样就多出了2+(n-2)个区域。 故:…
2015-04-07 11:15 · 评论(0)
KMP
字符串匹配:KMP,就是给出一个长串T,给出一个短串P,求T是否包含子串P,若包含,输出第一个子串的位置。否则输出-1。 首先假定i是T的指针,j是P的指针。 对于传统的匹配模式,每当T* != P时,我们会把j变成0,i跳回到刚才匹配的起始位置的下一个位置重新进行匹配,这样复杂度是O(n*m). 但是对于KMP思想,可以先构造一个next数组,next = k 表示,短串中的子串0 ~ j的串中,以P结尾的后缀串,与该子串中以P开头的前缀串重复时,k的位置。 即有P ~ P = P ~ P. 这样,在匹配过程中当短串匹配到j,长串匹配到了i,然后下一个字符不匹配,那么其实P ~ P 是与 …
2015-03-24 12:10 · 评论(0)
图论之两种最小生成树
第一种,Prim算法. 算法:Prim算法和DIJ类似,整个代码也类似。 过程:假设顶点标号为1 ~ V,第一次先从所有未确定的点中找到距离1(此时只有1是确定的点)最近的点,然后将此点加入到已确定的点,并把该段距离加入总和。然后更新其他的边(这里和DIJ不同),每次更新,都是对已知的点进行选择,选择该点,与哪个已确定的点直接相连最短。然后在下次循环时,找到与确定的点(此时除了1还有另外一个点)最近的点,重复上述过程。 与DIJ的区别就在这里,DIJ的每次循环找的是与源点(一个顶点)最近的点(因为求最短路),而Prim的每次循环找的是与已经确定的点(一个集合)最近的点(但是不用刻意去与集合中…
2015-02-14 10:53 · 评论(0)
图论之三种最短路
第一种,bellman-ford算法; 算法:求单源的两点间最短路。 过程:每次枚举所有已知的边,更新一个点到源点的最短距离,重复V-1次,即可找到各个点离源点的最短距离。 证明:对于从源点出发到任意一点,最差的情况就是算出了前面所有点的最短距离,才能求出该点的最短距离,即把该点看成是V,起点看成是1,那么这两点间最多有V-1条边,对于每条边上的端点,都需要枚举所有的边数E,才能算出该端点距起点1的最短距离。 所以该算法的复杂度为:O(VE). 但是可以用来判断是否存在正环负环,即判断第V次是否还继续更新最短距离。 第二种,DIJ算法. 算法:求单源的两点的最短路。 过程:每次找到最短距离已…
2015-02-13 21:08 · 评论(0)
哈希算法
哈希表(Hashtable,也叫散列表),是根据关键码值(Keyvalue)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。 这个映射函数叫做散列函数,存放记录的数组叫做散列表。 哈希表的做法其实很简单,就是把Key通过一个固定的算法函数既所谓的哈希函数转换成一个整型数字,然后就将该数字对数组长度进行取余,取余结果就当作数组的下标,将value存储在以该数字为下标的数组空间里。 而当使用哈希表进行查询的时候,就是再次使用哈希函数将key转换为对应的数组下标,并定位到该空间获取value,如此一来,就可以充分利用到数组的定位性能进行数据定位。…
2015-01-30 12:56 · 评论(0)
字典序比较类
字典序比较类的常用贪心法:按照字典序比较S和将S反转后的字符串S'; 实例1:每次从一个给定的S字符串的头或者尾取一个字母放入新的字符窜T中,要求得到新的字符窜T为字典序最小。 算法如下:按照字典序比较S和将S反转后的字符串S';如果S较小,就从S的开头取出一个文字,追加到T的末尾;如果S'较小,就从S'的开头取出一个文字,追加到T的末尾;如果相同就随便取。
2015-01-13 23:06 · 评论(0)
暴力算法的优化
对于一些暴力循环嵌套的算法,例如抽签,从n个数里依次取4个数,每次取完皆放回。求取完4次后的数字是否有可能等于某个数。即a* + a + a + a == m; 这样暴力的话就用4个for循环嵌套枚举每一种相加的和的可能性外加判断语句。但是这样复杂度是On^4,明显太大。 初步优化:那么想到,由于n个数是给定的,而且每次取的数字都在这个给定的数组里取,那么我们尝试把n^4给拆分掉,我们可以把求最后一个数的那个循环改写成二分查找,判断的数为m - a* - a - a 与目标区间的a相比较大小,最后判断得到的a是否满足我们的需要。 对于这种优化,因为二分查找的前提是sort排序,故复杂度为: …
2015-01-11 13:29 · 评论(0)
一道概率题
论剑F题。。咋一看各种数据需要处理和判断,好像很麻烦。。但是仔细思考之后。其实可以将问题分解为若干个子问题概率来处理; 对于该概率问题,可以先用一个代表颜色的数组分别遍历一遍男主的衣服和裤子,然后得到各种颜色对应的件数,然后就是重点开始了: 遍历出男主的各种穿衣穿裤情况,对应每种情况下算出当前的概率p,并调用一个函数来计算出全部女生中恰好有x个人穿相同衣服裤子的概率和。然后返回与p相乘,继续累加,最终即可得到结果; 点播: 1.对于求出每种颜色的衣服裤子各有多少件,用一个代表颜色的数组去遍历是比较方便后面的利用的; 2.在函数里求概率的时候,应再分解问题,变成先求出每个女生与男主相同的概率,…
2015-01-01 22:48 · 评论(0)
三分法小结
二分法作为分治中最常见的方法,适用于单调函数,逼近求解某点的值。但当函数是凸性函数时,二分法就无法适用,这时三分法就可以“大显身手”~ 如图,类似二分的定义Left和Right,mid = (Left + Right) / 2,midmid = (mid + Right) / 2; 如果mid靠近极值点,则Right = midmid;否则(即midmid靠近极值点),则Left = mid; 模版如下:例如某函数值在当角度递增的时候呈凸性,那么我们可以对角度进行三分处理。 (注意浮点处理与整型处理的区别) double l = 0, r = pi / 2; while (r - l >= …
2014-12-15 08:37 · 评论(0)
初识树状数组
树状数组:是一个查询和修改复杂度都为log(n)的数据结构,假设数组A,那么查询A+...+A的时,间是log级别的,而且是一个在线的数据结构。 树状数组原理如下:主要是依靠神奇的二进制转换进行保存数据。所以我们需要使用lowbit函数。 const int D = 1000005; int s[d]; inline int lowbit(int x) { return x & (-x); }//用lowbit函数算出该数在二进制下的最后一个1的位置; void add(int x, int w) { while (x < D) { s[x] += w; x += lowbit(x); } …
2014-12-14 23:11 · 评论(0)
小数转分数方法hdu-1717
⑴ 把0.4747……和0.33……化成分数。 想1: 0.4747……×100=47.4747…… 0.4747……×100-0.4747……=47.4747……-0.4747…… (100-1)×0.4747……=47 即99×0.4747…… =47 那么 0.4747……=47/99 想2: 0.33……×10=3.33…… 0.33……×10-0.33……=3.33…-0.33…… (10-1) ×0.33……=3 即9×0.33……=3 那么0.33……=3/9=1/3 由此可见, 纯循环小数化分数,它的小数部分可以写成这样的分数:纯循环小数的循环节最少位数是几,分母就是由几个9…
2014-12-07 22:34 · 评论(0)
排序函数的用法总结
1.qsort 功 能: 使用快速排序例程进行排序 用 法: void qsort(void *base, int nelem, int width, int (*fcmp)(const void *,const void *)); 各参数:1 待排序数组首地址 2 数组中待排序元素数量 3 各元素的占用空间大小 4 指向函数的指针 这个函数还可以对结构体进行二级排序噢 具体案例: struct Q { int li, wi; }haha[n]; int cmp( const void *a , const void *b ) //qsort 的配对配套使用 { struct Q *c = …
2014-11-29 10:42 · 评论(0)
POJ1065贪心
题意:有n条木棒,给出它们每条的l和w,用一台机器对它们进行加工,如果机器正加工的木条,与在它之前加工的木块有关系:l <= l'和w <= w',则机器不用准备时间,否则需准备1分钟。问加工完全部木棒,机器最少需要准备多久。 理解:用贪心要找到一个最优的遍历方案,注意到题目是说与它之前加工的木块的关系。 那么可以认为两个循环,第一个从头开始,第二个循环从第一个循环的变量的下一个开始一直循环到尾部,找出所有满足条件不需要耗时的木块,并对这些木块进行标记,使得在第一个循环里不会再次对他进行计数。 核心代码如下。其中haha数组是以li作为升序排序,并尽量使wi小的在前面。 int icount…
2014-11-29 10:30 · 评论(0)