算法竞赛入门经典 摘要 语言篇

it2023-09-12  78

此摘要纯属个人笔记,大佬自行跳过。 1.1

const double pi=acos(-1.0);

const 关键字表示pi的值不可改变。 2.1

printf("%03d\n",m);

%3d–可以指定宽度,不足的左边补空格 %-3d–左对齐 %03d—一种左边补0 的等宽格式,比如数字12,%03d出来就是: 012

3.1

#include<stdio.h> int main() { int a,b; scanf("%d%d",&a,&b); printf("%d %d\n",b,a); return 0; }

算法竞赛采用黑盒测试,即只考查程序解决问题的能力,而不关心采用的什么方法 所以算法竞赛的一些奇淫之技皆出于此~~(个人猜测 )~~ 划重点 算法竞赛是比谁能更好地解决问题,而不是比谁写的程序看上去更高级,所以我立志做一个蒟蒻,不愿成为牛犇 4.1

while(scanf("%d",&x)==1){}

scanf函数也有返回值,它返回的是成功输入的变量个数。 5.1

while(scanf("%d",&x)==1&&n){}

这样操作可以使程序以n=0未结束标记,书上提到这样做是为了鲁棒性。具体的真实性我也不是很确定,因为我是初学者 6.1 在多组数据的题目中,一个常见的错误是:在计算完一组数据后某些变量没有重置,影响到下一组数据的求解。 因为这一点,吃亏甚多。 6.2 当嵌套的两个代码块中又同名变量时,内层的变量会屏蔽外层变量,有时会引起十分隐蔽的错误。 7.1 从数组a复制k个元素到数组b,可以这样做:memcpy(b,a,sizeof(int)*k) 这里就要引出strcpy() 将数组s2赋值到s1中去,可以这样做:strcpy(s1,s2)

strcpy和memcpy主要有以下3方面的区别。 1、复制的内容不同。 strcpy只能复制 字符串,而memcpy可以复制任意内容,例如 字符数组、整型、 结构体、类等。 2、复制的方法不同。strcpy不需要指定长度,它遇到被复制字符的串结束符"\0"才结束,所以容易溢出。memcpy则是根据其第3个参数决定复制的长度。 3、用途不同。通常在复制字符串时用strcpy,而需要复制其他类型数据时则一般用memcpy

这里引出一个思考,怎么将二维数组s1复制到s2当中去呢?本蒟蒻现在还不知道,如果知道了会进行补充,知道的可以在评论中补充。 这一个点其实还有很多东西可以补充,但是本蒟蒻不会,所以等我刷够了题,看够了书,自己搞清楚了再回来修改。 8.1

scanf("%s",s); scanf("%d",&n);

两者其实在一定程度上是等价的。 它会读入一个不含空格,TAB和回车符的字符串,存入数组s 这句话对我来说真TM的是神仙语 本蒟蒻在之前遇到输入类似"asd 135 548 888888"的题的时候,我一直用的是一个个输入再一个个判断是否为空格:

char ch; scanf("%c",&ch); if(ch==' ') ......

这样做不仅繁琐还容易出错,以下是测试+改良版:

#include<stdio.h> #include<string.h> #define N 100 char s1[N],s2[N],s3[N]; int main() { scanf("%s",s1); scanf("%s",s2); scanf("%s",s3); int len1=strlen(s1); int len2=strlen(s2); int len3=strlen(s3); for(int i=0;i<len1;i++) printf("%c ",s1[i]); printf("\n"); for(int i=0;i<len2;i++) printf("%c ",s2[i]); printf("\n"); for(int i=0;i<len3;i++) printf("%c ",s3[i]); printf("\n"); return 0; }

不难发现当输入空格的时候自动结束对字符串的输入,且不会输入到下一个数组中去。 现在感觉以前就是个沙雕,再一次新生比赛中出现类似的水题,其他人马上AC了,可我还在一个个输入,真的心态无了 再就是一个小点:可以用"scanf("%s",s[i])"读取第i个字符。 9.1 关于sscanf函数和ssprintf函数的用法。 这里我就不多打字了 直接看我前几天写的一篇博文就可以基础运用sscanf函数和ssprintf函数了 地址如下,名为:洛谷P1957做题笔记

https://blog.csdn.net/weixin_50547586/article/details/109167399

10.1 对strcpy函数,strcmp函数,strcat函数的使用。 10.1.1

strcpy(s1,s2)

相当于int 类型中的赋值。 s1=s2; 10.1.2

strcmp(s1,s2);

其主要用途就是比较char 类型数组是否相同 相同则返回0;s1>s2则返回正数;s1<s2则返回负数 注意:这里的比较是从左到右的ASCLL值比较 10.1.3

strcat(s1,s2);

其主要用于连接,即将s2的头部接到s1的尾部,使用这个函数要注意数组溢出的问题。 11.1 列题3-5:最小生成元问题

#include<stdio.h> #include<string.h> #define N 100005 int s1[N],s2[N]; int main() { int n,sub; scanf("%d",&n); memset(s1,0,sizeof(s1)); for(int i=0;i<n;i++) { scanf("%d",&sub); s1[sub]++; } for(int i=1;i<N;i++) { int x=i,y=i; while(x>0) { y+=x%10; x=x/10; } if(s1[y]!=0) printf("%d\n",i); } return 0; }

这是我在看完思路后自己写的代码,可以参考。题目我不便多少,靠自己感悟。 12.1 例题3-6:环状序列 所有的理解都在代码里

#include<stdio.h> #include<string.h> #define maxn 105 char s[maxn]; int less(int l,int r) { int len=strlen(s); for(int i=0;i<len;i++) { if(s[(l+i)%len]!=s[(r+i)%len])//此处的%是精华,这样写可以完美的将数组从头开始 return s[(l+i)%len]<s[(r+i)%len];//如果s1<s2则返回1,否则返回0 } return 0; } int main() { int T; scanf("%d",&T);//此处的T是代表测多少组数据 while(T--) { int ans=0;//ans的用处就是作为一个标志 getchar(); //取消上次scanf的换行符 gets(s);//输入初始数组 int len=strlen(s); for(int i=1;i<len;i++)//此处循环的意思就是从第二项开始对比 ,i的意义就在于从何开始 { if(less(i,ans))//less函数的用处就是用于对比 ans=i;//如果找到比当前数组更小的,则标记那个点 } for(int i=0;i<len;i++) putchar(s[(i+ans)%len]);//此处使用putchar比使用sacnf好用,但在一些oj上getchar和putchar使用会出问题,所以最好还是写成sacnf printf("\n"); } return 0; }

13.1 进制转换 这里主聊二进制和十进制之间的转换(因为我只会这一点皮毛 ) 这是我刚刚看书学会的十进制转为二进制

#include<stdio.h> int s[100],s1[100]; int main() { int n,step=0; scanf("%d",&n); for(int i=0;;i++) { s[i]=n%2; n=n-s[i]; step++; if(n/2==0) break; n=n/2; } for(int i=step-1;i>=0;i--) { s1[step-i-1]=s[i]; } for(int i=0;i<=step-1;i++) { printf("%d",s1[i]); } printf("\n"); return 0; }

十转二的精髓就是运用‘/’和‘%’,每次取余就是一个二进制位,因为二进制中只有0和1。 进制转化与位移运算符:这下面的我是真的不懂,以后懂了再补充。 14.1 为了使用方便,往往用“typedef struct{ 域定义 ;}类型名;”的凡是定义一个新类型名。这样,就可以像原生数据类型一样使用这个自定义类型。 这个的具体用法现在还不太会,等我 变强了 再来解释。 15.1 即使最终答案再所选择的数据类型范围内,计算的中间结果仍然可能溢出。 16.1 素数判定中的有意思的点: 代码如下

int is_prime(int n) { for(int i=2;i*i<=n;i++) { if(n%i==0) return 0; } return 1; }

这段代码中的 i*i<=n 用的很好,这样写可以极高程度的减少循环次数和运行时间。 再者就是建议把谓词(用于判断某事物是否具有某种性质的函数)命名成“is_xxx”的形式,返回int值,非0表示真,0表示假。 之后对这段代码的修改也是比较好的思想:

int is_prime(int n) { if(n<=1) return 0; int m=floor(sqrt(n)+0.5)//一定要加0.5,这样做才能做到4舍5入 for(int i=2;i*i<=n;i++) { if(n%i==0) return 0; } return 1; }

如果直接写成 m=sqrt(n),"x.9999"中的 .999会被截掉。 总结一波,一般来说,c语言中的强制类型转化就是直接截掉超出的部分。 就像m=sqrt(n);一样,它的运算过程实际上是将浮点型转为int类型。 而保留小数位则会进行4舍5入的操作

#include<stdio.h> int main() { double a=1.99999; printf("%.2f\n",a); return 0; }

输出结果是2.00 从素数判定中还可以学到一个关于floor函数的使用,这个函数很好理解,就直接引用大佬的文章了

floor(x),也写做Floor(x),其功能是“向下取整”,或者说“向下舍入”,即取不大于x的最大整数(与“四舍五入”不同,下取整是直接取按照数轴上最接近要求值的左边值,即不大于要求值的最大的那个整数值)。   头文件:#include   实例:     floor(3.14) = 3.0     floor(9.999999) = 9.0     floor(-3.14) = -4.0     floor(-9.999999) = -10      与floor函数对应的是ceil 函数,即上取整函数。   有趣的是,floor在英文中是地板的意思,而ceil是天花板的意思,很形象地描述了下取整和上取整的数学运算。 转载于:https://www.cnblogs.com/astonc/p/10846595.html

17.1 看到这里就到了指针了,指针博大精深,欲练此功,先看基础。 先前写的一篇关于指针的入门篇 17.2 指针的基础东西看完了后,就要学习数组作为参数和返回值。 很碰巧,书上写的错误代码就是我以前写的样子,我还更差,没有sizeof()计算范围。

#int sum(int a[]) { int ans=0; for(int i=0;i<sizeof(a);i++) ans+=a[i]; return 0; }

首先应该明白:**把数组作为参数传递给函数时,实际上只有数组的首地址作为指针传递给函数。**所以定义中的int a[]相当于int *a。 下面的三组时正确操作,按照剧本来讲,最后两种解法十分关键。

int sum(int *a,int n) { int ans=0; for(int i=0;i<n;i++) { ans+=a[i]; } return ans; } int sum(int *begin,int *end) { int n=end-begin; int ans=0; for(int i=0;i<n;i++) { ans+=begin[i]; } return ans; } int sum(int *begin,int *end) { int *p=begin; int ans=0; for(int *p=begin;p!=end;p++) ans+=*p; return ans; }

还有一种需要补充的:

int main() { int a[]={1,2,3,4}; printf("%d\n",sum(a+1,3)); return 0; }

注意,a+1意思是a[1]。a+k就相当于a后面的第k个元素。 其实关于数组做参数可以联想到strcpy函数,具体说明名可以看我以前写的一篇笔记: 关于strcpy一类的函数使用

语言篇我就先写道这里吧,后面的c++和STL我会再开一章。本文很水,如果你看到了这里,我表示感谢,同时希望此文对你有所帮助。若有不足之处,也请指出,谢谢 2020 10 23

最新回复(0)