[关闭]
@P2Oileen 2017-04-10T12:27:00.000000Z 字数 7384 阅读 1736

寒假吓人集训日记

集训日记

小迪大佬太强啦！

字符串函数

strstr
strstr(p,c) 查找字符；
strstr(p,p1) 查找字符串；
strcpy
strcpy(p1,p) 复制字符串 把p复制给p1
strncpy
strncpy(p1,p,n) 指定长度复制
strcmp
strcmp(m,n) 比较字符串大小 自左向右ASCⅡ码值对比，返回m-n；
atoi atof
cstdlib里面的函数，atoi(p)将字符串转换为整型，atof(p)将字符串转换为实型。
double m=atof(p1); printf("%lf",m);
可以直接输出，atof()返回的就是double。

高精度系列

我感觉下面的代码有点不太对，等我过两天po个正确的上来

高精度加法：

步骤：
1.存到一个字符串里面
2.把它逆序放到一个数组里面
3.把两个数组加起来
4.把加和数组里面的每一位判断是否大于零（进位）
5.输出

  1. #include <cstdio>
  2. #include <iostream>
  3. #include <algorithm>
  4. #include <cmath>
  5. #include <cstring>
  6. using namespace std;
  8. char ch1[2005],ch2[2005];
  9. int in1[2005],in2[2005],len1,len2;
  11. void csh()
  12. {
  13.     len1=strlen(ch1);
  14.     int k=0;
  15.     for(int i=len1-1;i>=0;i--)
  16.     {
  17.         in1[k++]=ch1[i]-'0';
  18.     }
  19.     len2=strlen(ch2);
  20.     k=0;
  21.     for(int i=len2-1;i>=0;i--)
  22.     {
  23.         in2[k++]=ch2[i]-'0';
  24.     }
  25. }
  27. void plusa()
  28. {
  29.     for(int i=0;i<max(len1,len2);i++)
  30.     {
  31.         in1[i]+=in2[i];
  32.         if(in1[i]>=10)
  33.         {
  34.             in1[i+1]+=1;
  35.             in1[i]-=10;
  36.         }
  37.     }
  38. }
  40. int main()
  41. {
  42.     scanf("%s %s",ch1,ch2);
  43.     csh();
  44.     plusa();
  45.     bool first=1;
  46.     for(int i=max(len1,len2)-1;i>=0;i--)
  47.     {
  48.         if(first && in1[i]==0) continue;
  49.         first=0;
  50.         printf("%d",in1[i]);
  51.     }
  52.     if(len1==1 && len2==1 && in1[0]==0) printf("0");
  53. }

高精度减法：

注意
1.两个数大小判断要先判断长度，后用strcmp
2.相减后可能出现‘039’的情况
3.可能会有符号'(a 

  1. #include <stdio.h>
  2. #include <string.h>
  3. int main()
  4. {
  5.     char m[555],n[555];
  6.     int i,len_m,len_n;
  7.     int a[555]={0},b[555]={0};
  8.     scanf("%s",m);scanf("%s",n);
  9.     if   ( (strlen(m)<strlen(n)) ||
  10.                 ( (strlen(m)==strlen(n)) &&
  11.                 ( strcmp(m,n)<0 ) ) )
  12.     {
  13.         char mm[555];
  14.                     strcpy(mm,m); 
  15.                     strcpy(m,n);   
  16.                     strcpy(n,mm);
  17.         printf("-");
  18.     }
  19.     len_m =strlen(m);len_n=strlen(n);
  20.     for(i=0;i<len_m;i++)
  21.         a[i]=m[len_m -1 -i]-'0';
  22.     for(i=0;i<len_n;i++)
  23.         b[i]=n[len_n -1 -i]-'0';
  24.             for(i=0;i<len_m;i++)
  25.     {
  26.         a[i]-=b[i];
  27.         if(a[i]<0)
  28.         {
  29.             a[i]+=10;
  30.             a[i+1]--;
  31.         }
  32.     }
  33.     i=len_m-1;
  34.     while(a[i]==0 && i>0)  i--;
  35.     for( ; i>=0 ; i--)
  36.         printf ("%d", a[i]);
  38.     return 0;
  39. }

高精度乘法：

意料之外的简单，不过也要注意进位的问题，把高精度加法的拿来用就好了= =
还有就是有个公式miao[i+j]+=ch1[i]*ch2[j];
qwq我就是喜欢喵（谁让蛤蛤不让用呢）
乘0怎么办？

  1. #include <cstdio>
  2. #include <iostream>
  3. #include <algorithm>
  4. #include <cmath>
  5. #include <cstring>
  6. using namespace std;
  8. char ch1[2005],ch2[2005];
  9. int in1[2005],in2[2005],len1,len2;
  10. int miao[20005];
  12. void csh()
  13. {
  14.     len1=strlen(ch1);
  15.     int k=0;
  16.     for(int i=len1-1;i>=0;i--)
  17.     {
  18.         in1[k++]=ch1[i]-'0';
  19.     }
  20.     len2=strlen(ch2);
  21.     k=0;
  22.     for(int i=len2-1;i>=0;i--)
  23.     {
  24.         in2[k++]=ch2[i]-'0';
  25.     }
  26. }
  28. void cheng()
  29. {
  30.     for(int i=0;i<len1;i++)
  31.     {
  32.         for(int j=0;j<len2;j++)
  33.         {
  34.             miao[i+j]+=in1[i]*in2[j];
  35.         }
  36.     }
  37.     for(int i=0;i<len1+len2;i++)
  38.     {
  39.         if(miao[i]>=10)
  40.         {
  41.             miao[i+1]+=miao[i]/10;
  42.             miao[i]=miao[i] % 10;
  43.         }
  44.     }
  45. }
  47. int main()
  48. {
  49.     scanf("%s %s",ch1,ch2);
  50.     csh();
  51.     cheng();
  52.     bool first=1;
  53.     for(int i=len1+len2;i>=0;i--)
  54.     {
  55.         if(first && miao[i]==0) continue;
  56.         first=0;
  57.         printf("%d",miao[i]);
  58.     }
  59.     if((len1==1 && in1[1]==0) || (len2==1 && in2[1]==0)) printf("0");
  60. }

多用函数！！！！！！！！！

高精度除法

1.高精度/低精度 也是小学算法- =

  1. #include <cstdio>
  2. #include <cstring>
  3. int main()
  4. {
  5.     char a[2005];
  6.     int ans[2005]={0};
  7.     int b;
  8.     scanf("%s",a);
  9.     scanf("%d",&b);
  10.     int qwq=0;
  11.     int len=strlen(a);
  12.     for(int i=0;i<=2000;i++)
  13.     {
  14.         qwq=qwq*10+a[i]-'0';
  15.         if(qwq>=b)
  16.         {
  17.             ans[i]=qwq/b;
  18.             qwq=qwq % b;
  19.         }
  20.         else ans[i]=0;
  21.     }
  22.     bool first=true;
  23.     for(int i=0;i<=2000;i++)
  24.     {
  25.         if(first && ans[i]==0) continue;
  26.         if(first && ans[i]!=0)
  27.         {
  28.             first=false;
  29.             printf("%d",ans[i]);
  30.             continue;
  31.         }
  32.         printf("%d",ans[i]);
  33.     }
  34.     return 0;
  35. }

2.高精度/高精度
    1)高精度/相差不大的高精度 暴力枚举
    2)高精度/相差巨大的高精度 烦人qwqqq

关于高精度
后来我越想越觉得高精度这个东西很妙啊。某天GG问我，你觉得最开始那个创造出高精度的人是怎么发现它的，我说可能是因为他long long写挂了（……）GG表示无法苟同……
我想了一下，觉得现在的

我感觉上面的代码有点不太对，等我过两天po个正确的上来

时间复杂度分析

一般来说，影响时间复杂度的是循环的层数，每层循环次数和执行语句数，但是在分析复杂度的时候我们往往可以忽略常数，比如O(n)=O(6n)=O(n/3)。当有多项式时，一般来说取最高次项（影响程度最深），例如O(n^3+n^2+n)=O(n^3)。
计算机一秒能够执行的操作为10^8~10^9次，那么在复杂度不同的时候，n的取值如下：

O() 对应n取值
O(n) 10^8
O(nlogn) 10^5
O(n^2) 10^4*5
O(n^3) 100~500

有时通过n的取值，我们可以通过看题目中的数据范围倒推算法。如果n取值到了10^8，则算法复杂度为O(n)。特殊的，sqrt(n)的算法一般为分块算法，把长度为n的数组分为sqrt(n)份，每份含sqrt(n)个数据，【似乎这样能提高某些算法的效率】

枚举和贪心策略

“是否存在”“有多少种可能”这类的问题，通常会使用枚举的方法来实现。
在某些情况下，可以将一个问题分成不同情况，针对某些情况可以使用枚举策略从而获得解。
贪心指的是取局部最优解，可以将拥有多个对象的一个问题变成只有两个对象的问题，从而获得贪心策略。贪心策略适用于：求最值，最优解，最大或最小和等问题，与动态规划的求解量类似。但是数据量不适用于dp，如数据量为几万或者更多的问题。

数据结构

链表

链表的好处在于其插入和删除操作非常简便。
插入就把这个要进去的元素接进去……就像接电路一样~
删除同理~
结构图示：
环形链表

双向链表 

  1. //链表的实现
  2. //先来个结构体存一下
  3. struct name
  4. {
  5. int text;//存当前目标的文本值
  6. int next;//存当前目标连的下一个目标的位置（例如连到a[5],存5）
  7. }a[2005];
  8. //这样就能愉快的存进去元素啦

经典的题目：约瑟夫环

队列

队列是先进后出表。
C++里面有专门的库函数<queue>用来执行队列操作。【学长说这个有点慢……】
队列也可以通过数组实现，但是为了节约空间，可以将它变成一个循环队列~但是还是会有覆盖之前的内容的风险。
【所以为什么不用queue呢……queue大法好】
举个栗子！

  1. #include <iostream>
  2. #include <stack>//这个要有啊qwq
  3. using namespace std;
  4. //省略
  5. queue <int> q;//声明队列
  6. q.push(1);//把1推入队列
  7. printf("%d",q.front());//q.front()返回1
  8. printf("%d",q.size());//q.size()返回q的大小（元素个数）
  9. q.pop();//队列首元素弹出
  10. if(q.empty()) printf("yes");//q.empty()返回真代表队列为空

在用数组实现置空队列的时候，直接把首尾指针捏一起就行啦。
队列的应用：队列在宽度优先搜索，图的单源最短路（spfa算法）中均有应用，是noip考场的常客，与图的最短路结合的题目考察的比较多

栈

与队列相反，栈是先进先出表。
C++里面也有个库函数<stack>用来执行栈操作。
栈也可以用数组实现，但是这个显然还是stack方便啦。
栈在一些关于逆序的问题上有着相当优良的表现，而且简便易懂~
如果用数组模拟只需要一个指针保持不变，top指针上下移动……
元素多了就把top往上面挪。如图所示~ 

  1. //其实和queue差不多啦……
  2. #include <stack>
  3. //省略
  4. stack <int> q;//声明栈
  5. q.push(1);//把1推入栈
  6. q.push(2);
  7. printf("%d",q.top());//q.top()返回栈顶元素：2
  8. printf("%d",q.size());//q.size()返回q的大小（元素个数）
  9. q.pop();//队列首元素弹出
  10. if(q.empty()) printf("yes");//q.empty()返回真代表栈为空

栈在判断匹配的方面有特技- -
还有神奇的计算表达式的值！

小专题：计算表达式的值

现在有一个表达式：12+(2+5*4)/2-5，需要你算出表达式的值ovo

首先回顾小学知识：【四则混合运算规则】
（1） 先算括号内，再算括号外；
（2） 在无括号或同层括号的情况下，先做乘除运算，后做加减运算，即乘除运算的优先级高于加减运算的优先级；
（3） 同一优先级运算，从左向右依次进行。

然后介绍一个新的概念：后缀表达式
在平时人类的运算中，我们习惯的是中缀表达式，即运算符在两个操作数中间的表达式，举个例子：12+(2+5*4)/2-5，但是这个方式有个弊端：既要考虑括号的作用，又要考虑运算符的优先级，还要考虑运算符出现的先后次序。
然而为了方便计算机的运算，我们要用后缀表达式：运算符在两个操作数后面的表达式。
那么上面的式子就会变成：12 2 5 4*+2/+5-，计算机只需要过一遍就可以完成运算啦。它的好处在于：不存在括号，也不存在运算符的优先级，计算过程完全按照运算符出现的先后次序进行。

怎么把一个中缀表达式变成后缀表达式呢？还是要用栈。。。
原理：把每个运算符都移到它的两个运算数的后面，然后删除所有的括号即可。

每次的计算取出栈里面的两个数，取出另一个栈里的一个运算符，然后将这两个数通过该运算符计算出来的结果放入原来的栈内，直至栈中元素只有一个，就是最终的解。

基础算法

深度优先搜索

首先要说一下‘搜索’这个东西www
搜索其实就是枚举法的应用，【因此我们也叫暴力搜索】，它的作用就是将所有可能的情况都枚举一遍，从中找出最优解亦或正解。显而易见的是，这么做的复杂度一定会很高，如果把所有的情况看做一棵树，那么可以通过某些限制条件确定一些情况是不可能的，就可以不再向下搜索。这个方式叫做“剪枝”【生动形象】，是提高效率的好方式ovo

关于深度优先搜索先讲个小故事（？）
有一天艾琳饿了，就种了一棵二叉树。
二叉树上结了一些月玄丹。
现在艾琳要把月玄丹全都摘下来。
艾琳正在学习新的算法，其中有一个就叫做深度优先搜索，她决定使用这个方式来摘月玄丹。
深度优先搜索的意思是：她要从这棵树的根节点开始，每次访问当前结点的左儿子，再访问它的右儿子。如果走不通了就掉头。
那么如下图所示，月玄丹被摘下来的顺序就是：
A(begin)(left son)
-->B(left son)
-->D(left son)
-->F(back to D)(right son)
-->G(left son)
-->H(back to G)(right son)
-->I(back to G)(back to D)(back to B)(right son)
-->E(back to B)(back to A)(right son)
-->C(end)
图片挂了,这里本来应该有一棵二叉树，如果挂了请联系我QAQ

好了不闹了，谈谈深度优先搜索的代码实现问题吧。
显然我们要一直往下搜寻，这就意味着需要不断地循环。可以用递归的思路，终止条件是“走不通”，将每个结点的左右儿子遍历，每次将左/右儿子又当做下一层递归的结点再遍历左/右儿子的左右儿子（递归果然不能想得太多qwqqqqq脑子真的会乱的）
可以说深度优先搜索就是建立在递归的基础之上的~
伪代码如下~以艾琳摘月玄丹举例www

  1. dfs(状态) 
  2. {
  3.     if(状态 是 目标状态)//如果艾琳往前走找不到月玄丹了 
  4.     {
  5.         do something;//艾琳回到她上次摘月玄丹的地方，看看可以再往哪儿走
  6.     }
  7.     else//如果艾琳往前走还能找到月玄丹
  8.     for(每个新状态)//前面有n条路，全都看一遍
  9.     {
  10.         if (新状态合法) dfs(新状态)//如果这条路上有月玄丹，就走这条路摘月玄丹
  11.     }
  12. }
  13. .
  14. .
  15. .
  16. int main()
  17. {
  18. dfs(初始状态);//艾琳从根节点开始走
  19. }

深度优先搜索就是一头倔强的驴，一直在往前走，不撞南墙不回头，但是也要注意不能撞死呀qwq要记得回头qwq（回溯）

宽度优先搜索

如果说深度优先搜索是一头驴，不撞南墙不回头，那么宽度优先搜索就像一滴墨，缓缓地荡漾开来，逐渐染黑了整杯墨水。宽度优先搜索是指从根节点开始，逐层往下搜索，直至搜索出所有的点。
那么这次幽灵要来抓研究员了，幽灵有着影分身之术，一旦遇到岔路就可以分出两个影子，每个影子都可以抓研究员~（请研究员不要打我，家里的事儿自己解决哈哈哈哈）
假设如图所示A~G每个点上面都站着一个研究员，幽灵从A点开始要捕食研究员，那么研究员被捕食的顺序是：
A
（A分身！下一层）B C被捕食
（B分身！下一层）D E被捕食
（D分身！下一层）F G被捕食
（G分身！下一层）H I被捕食
图片挂了,这里本来应该有一棵二叉树，如果挂了请联系我QAQ

可以看出遍历的顺序是ABCDEFGHI，那么怎么实现呢？
每次我们遍历了当前点的所有儿子，再遍历所有儿子的所有儿子……
这样一排一排的，可以用神奇的队列来实现~
首先把根节点丢进队列，再把根节点的所有儿子丢进队列……
根节点已经被遍历完了，现在把它吐出来……pop
再把当前队首的结点的所有儿子丢进队列……依此类推，直至队列没有元素~
代码我就不写啦www用while循环就可以轻松完成了~

宽度优先搜索在有关于图（迷宫！），计算步数之类的题中有很好的用途！

关于搜索算法的小小总结：搜索是信息学竞赛中的骗分好方法，玩的好就可以超神啦QAQ
但是由于思想还是枚举，如果能有确定的正解方法，还是选择正解吧qwq
（我只会暴力啊怎么办qwqqqqqqq我太弱了qwqqqqqq）
请叫我天南星科天南星目魔芋属蒟蒻谢谢（doge脸）

哈希！（我特别喜欢这个名字只是因为我是hath它是hash）

（我也不知道哈希为什么要放在这里不过我真的懒得动了）
哈希是是一类算法的统称，一般来说满足这样的关系：f(data)=key，输入任意长度的data数据，经过哈希算法处理后输出一个定长的数据key。同时这个过程是不可逆的，无法由key逆推出data。

如果是一个data数据集，经过哈希算法处理后得到key的数据集，然后将keys与原始数据进行一一映射就得到了一个哈希表。一般来说哈希表M符合M[key]=data这种形式。

哈希表的好处是当原始数据较大时，我们可以用哈希算法处理得到定长的哈希值key，那么这个key相对原始数据要小得多。我们就可以用这个较小的数据集来做索引，达到快速查找的目的。

举个栗子！比如这里有一万首歌，要求按照某种方式保存好。到时候给你一首新的歌（命名为X），要求你确认新的这首歌是否在那一万首歌之内。

无疑，将一万首歌一个一个比对非常慢。但如果存在一种方式，能将一万首歌的每一首的数据浓缩到一个数字（称为哈希码）中，于是得到一万个数字，那么用同样的算法计算新的歌X的编码，看看歌X的编码是否在之前那一万个数字中，就能知道歌X是否在那一万首歌中。

显然，由于信息量的丢失，有可能多首歌的哈希码是同一个。好的哈希算法会尽量减少这种冲突，让不同的歌有不同的哈希码。最差的哈希算法自然就是所有的歌用那个算法算出来的都是同一个哈希码。

哈希表在查表运算中非常重要，搜索字符串比搜索大量信息快速得多。

图片挂了,这里本来应该有一个哈希表，如果挂了请联系我QAQ

以上内容基本都来自于什么是哈希表和哈希算法？,如有侵权请联系我删除qwq

↑返回顶部

添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注