算法竞赛入门经典(刘汝佳)——基础篇心得_算法竞赛入门经典》-刘汝佳

1、基础篇
1.1 输出格式与变量类型的关系

• 对于如下程序

#include<stdio.h>
using namespace std;
int main()
{
    printf("%f\n",8/5);
    return 0;
}
1
2
3
4
5
6
7

函数不会进行任何类型转换，它只是从内存中读出你所提供的元素的值（按照%d，%f等控制字符提示的格式）。printf("%c\n",48);会输出0C语言设计中，int类型一般是32bit或者16bit，而float一般是64bit，并且有可能使用科学计数保存。例如，5在内存中为00000000,00000101。而且5一般都在静态区，程序的静态存储区默认是0，那么当用%f来读时，就会读64bit，也就是会读之前的很多位0，最后按照（有效数字）×（基数2)pow(指数）的方式来取数，自然结果是0。尽量用const关键字声明常数。

1.2 关于整数与浮点数范围：c++有如下基本数据类型

bool 布尔型 － true,false
(signed) int 有符号整型 4 -（2的31次方）～2的31次方-1
(signed)long (int) 有符号长整型 4 -（2的31次方）～(2的31次方-1)
float 实型 4 -（10的38次方）～10的38次方
double 双精度型 8 （-10的308次方）～10的308次方
long double 长双精度型* 8 -（10的308次方）～10的308次方
longlong能支持十进制下大约19位数 8字节 （-2的63）~（2的36次方-1）
1
2
3
4
5
6
7

1.3 数学基本问题：

• 不要出现1/0的错误，编译无法发现。

    printf("sqrt(-10)d: %d\n",sqrt(-10));
    printf("sqrt(-10)f: %f\n",sqrt(-10));
    printf("1.0/0.0d: %d\n",1.0/0.0);
    printf("1.0/0.0f: %f\n",1.0/0.0);
    printf("0.0/0.0d: %d\n",0.0/0.0);
    printf("0.0/0.0f: %f\n",0.0/0.0);
1
2
3
4
5
6

• 如何判断一个数是整数？

//使用floor函数
floor(n)返回不大于n的一个最大整数
if(n==floor(n))
then n是一个整数

//另外，由于浮点数运算存在误差，最后可能导致n从1变为0.9999，n==floor(n)不成立。
//使用四舍五入的方法：
floor(n+0.5)
1
2
3
4
5
6
7
8

• 如何判断一个数是素数？

int is_prime(int n)
{
    for(int i=2;i*i<=n;i++)//两个因子不可能同时大于sqrt(n),一个大于sqrt(n)另一个必小于sqrt(n)，所以只需要比较到sqrt(i)
        if(n%i==0)
            return 0;
    return 1;
}
1
2
3
4
5
6
7

• 关于阶乘

如果计算只包含加法、减法和乘法的整数表达式除以正整数m的余数，可以在每步计算后对n取余，结果不变。

/*******************************
计算1-n的阶乘之和，并取后六位
**************************/

int main()
{
    const int mod = 100000;
    int n,result=0;
    scanf("%d",&n);


    if(n>25)
        n=25; //多次测试可以发现25！后六位均为0，所以25以后的阶乘结果不影响最终的result，这种方法适用于最后取余保留最后6位以内的问题
    for(int i=1;i<=n;i++)
    {
        int factorial=1;
        for(int j=1;j<=i;j++)
        {
            factorial = factorial*j%mod;
        }
        result=(result+factorial)%mod;
    }


    printf("%d\n",result);
    printf("used time %.2lf\n",(double)clock()/CLOCKS_PER_SEC);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

1.4 关于调试：
”中间变量输出法“

printf("used time %.2lf\n",(double)clock()/CLOCKS_PER_SEC);

//返回程序从开始运行到这一步的时间
//头文件<time.h>
//若有键盘输入，搭配windows命令行下的echo|program使用
1
2
3
4
5

1.5 针对数组/字符数组的一些常用函数

int a[maxn]
int b[maxn]
//如果需要将a复制k个元素到b
memcpy(b,a,sizeof(int)*k)

memset(a,0,sizeof(a))//把数组a清零   与memcpy一起第三个参数都需要提供操作的地址大小

strchr(s,buf[i])//判断字符数组（字符串）s中是否有buf[i]
//没有返回NULL 有的话返回buf[i]的下标

strlen(a)//获得字符数组（字符串）的实际长度，即"\0"之前字符的个数

sprintf(buf,"%d%d%d%d%d",i,j,a,b,c);
//将输出输入到字符串buf
1
2
3
4
5
6
7
8
9
10
11
12
13
14

    char test[5]="abcd";
    char test2[100]={};
    memcpy(test2,test,sizeof(char)*3); //内存复制
    printf("%s\n",test2);
    printf("%d",strlen(test2));
    return 0;

注意使用memcpy(test2,test,sizeof(char)*3)函数时，如果没有复制到test的终结符，且test2没有初始化，
test2是不会有终止符的。
1
2
3
4
5
6
7
8
9

因此在使用字符数组时一定要考虑是否初始化的问题。

1.6 关于输入输出的一些问题

1. while( c= getchar() &&c!=’\n’)为什么错误？

其等价于c=(getchar() &&c!=’\n’)与运算符的先后顺序有关， 正确应写为（c=getchar()）!=’\n’)

2. scanf("%c",&c)和getchar()均会读取缓冲区中的字符，包括回车和空格！

int main()
{
    int c;
    int i=0;
    c=getchar();
    //scanf("%c",&c);
    printf("test\n");
    printf("%c",c);
    printf("test");
}
1
2
3
4
5
6
7
8
9
10

经过测试，scanf和getchar()的结果基本相同。
二者的区别在于返回值不同，scanf返回的是输入的个数， getchar()从标准输入里读取下一个字符。返回类型为int型，返回值为用户输入的ASCⅡ码，出错返回-1。

3. scanf与cin的区别

scanf("%c",&c)和cin>>c的区别在于cin遇到缓冲区中的[enter],[space],[tab]会结束当前输入，并舍弃[enter],[space],[tab]，继续下一项输入，当有连续[space],[enter,[tab]会全部舍弃。

cin的输入很简单，整体的看输入，遇到[enter],[space],[tab]表示当前输入结束，下一个输入从非[enter],[sapce],[tab]开始，两输入间无线多个[space][]enter[tab]都是无效的,但会把[enter]留在缓冲区，会被其他能够接收[enter]的输入符接收。

4. 读取带空格和tab的字符串可以考虑getchar和scanf和cin.getline(),前两者会读取回车，cin.getline()不会，且会将缓冲区回车删除。

while(scanf("%c",&c)!=EOF&&c!='\n')
while((c=getchar())!=EOF)
1
2

5. 如何输出’‘和’%’?**

printf("\\n");printf("%%d\n");

6. 特殊输出格式

printf("%03d"，a):表示输出3位整数a，不够在前面补0

printf("%5d"，a):表示输出5位整数a，不够在前面补空格
1
2
3

1.9 题目中的某些细节

1、注意getchar()函数运用时对于缓冲区剩余字符的处理（回车 tab 由于循环跳出未被接受的字符）
如果需要在读到某个字符就跳出读入，但该字符后面还有输入时，最好是先将所有字符保存下来，再进行循环判断

2、scanf()对二维字符数组赋值时，scanf("%s",test[i])不用写&号

3、注意题目对输出的要求，如果是两个输出结果间有一个空行，则不能在程序的最后输出多于空行。如下所示：

1.10 底层存储对于程序的影响
在可执行文件中，正文段用于存储指令，数据段用于存储已初始化的的全局变量，BSS段用于存储未赋值的全局变量所需的空间。在程序运行时，会动态创建一个堆栈段，里面存放着调用栈，因此保存着函数的调用关系和局部变量。

1.11 模拟类ACM题解（本心得篇的题解将会通过外链的形式呈现）
uva_1589象棋模拟题.
UVa220黑白棋问题.
IP地址转化（uva1590）.

1.12 常用STL数据结构总结
算法竞赛入门经典(刘汝佳)——常用STL数据结构总结
试题：
UVA1592 数据库 Database 题解

1.13 大整数运算总结
高精度数运算加法乘除阶乘c++的实现总结