• C++的#include<cstdio> 等价于 C语言的#include<stdio.h> 其他c语言的库文件也是这么变换
  • 题目要求$10^9$以内或者32位整数,用int,$10^{18}$内或64位整数用long long
1
2
long long b = 123456789012345LL;
//long long 赋大于int的初值,要在后面加LL,否则编译错误
  • 涉及到浮点数,全用double,因为精度高
  • 小写字母比大写字母的ASCII码值大32
1
2
\n换行
\0代表空字符NULL,其ASCII码值为0,\0不是空格
  • 字符串常量可以作为初值赋给字符数组
1
char s[10] = "1234444";
  • 整型常量在赋值给布尔变量会自动转换为bool变量,在C语言中使用bool,要加stdbool.h
  • 宏定义#define语句无分号,宏定义是简单替换,容易出错,定义常量推荐用const
  • 条件运算符a>b?a:b;
1
#define MAX(a,b) ((a)>(b)?(a):(b))
  • 位运算符
1
2
3
4
5
INF本来等于2^31-1,用位运算表示为(因为位运算优先级低于算术,要加括号)
(1<<31)-1
但是为了避免相加超过int,故一般定义INF为
const int INF = (1<<30)-1;
const int INF = 0X3fffffff;
1
2
3
a<<x;//a左移x位等价于a*(2^x)
a>>x;//a右移x位等价于a/(2^x)
&|^~ //按位与,或,异或(不等为1),按位取反
  • 输入输出
1
2
3
4
5
6
7
8
9
10
scanf("%d",&intn);
scanf("%lld",&longn);
scanf("%f",&floatn);
scanf("%lf",&doublen);
scanf("%c",&charc);
scanf("%s",str);//注意不加&
scanf("%d:%d:%d",&hh,&mm,&ss); //特殊格式输入
//printf中,double和float的占位符都是%f
//输出% 或者\,需要再加一个%或者\
printf("%%"); printf("\\");
  • !!!scanf除了%c以外,对其他格式符的输入是以空白符(空格TAB)作为结束标志

    • 因此除非%c把空格按字符读入,其他情况会跳过空格

    • 1
      scanf("%d%d",&a,&b); //输入格式为 “3 4”时可以不加空格
  • 字符数组使用%s读入时,是以空格和换行作为读入结束标志

  • scanf的%c是会读入空格和换行的!!!!!!

    • eg.例子 20页
  • 实用输出格式

    • 1
      2
      //%md  超过或等于m位保持原样,不足m位,高位用空格补齐
      printf("%5d");
    • 1
      2
      //%0md  超过或等于m位保持原样,不足m位,高位用0补齐!!!!!!非常好用
      printf("%05d");
    • 1
      2
      //%.mf  保留m位小数输出
      printf("%.5f");
  • 使用getchar,putchar输入输出单个字符

    • 1
      2
      char ch = getchar();
      putchar(ch);
    • getchar可以识别换行符,所以敲回车的时候如果后面有getchar就会被存进去

  • 常用math函数

    • fabs(double x); //对double变量取绝对值
    • floor(double x), ceil(double x); //向下取整 和 向上取整 返回值仍是double
    • pow(double r, double p); //$r^p$
    • sqrt(double x);
    • log(double x);//返回double型以自然对数为底的对数
      • 换底公式 $log_ab=log_eb/log_ea$
    • sin(x),cos(x),tan(x); 弧度制!!!!
    • acos(x), asin(x), atan(x);
      • const double pi = acos(-1.0);
    • round(double x); //四舍五入取整!!!
  • case语句不用加大括号

    • 1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      switch(a+b){
      case 1:
      break;//必须加,否则会直接向下执行
      case 2:
      int c= 1;
      int d=0;//多条语句不用加大括号的!!
      break;
      default:
      break;
      }
  • do{}while(condition); //do-while 记得加分号

  • 数组大小必须是整数常量,不可以是变量

  • 数组初始化

1
2
3
int a[] = {5,3,2};
int a[10] = {}; //没被初始化的默认为0,这句话就起了把数组全体赋值为0的效果
int a[10] = {0}; //没被初始化的默认为0,效果同上
  • 冒泡排序

    • 本质在于交换,每趟都通过比较,把剩余元素中最大的元素交换到另一端

    • 1552998067043

    • 一共进行n-1趟,每一趟,比较相邻元素,将大的通过交换放在右边,再比较下一对相邻元素

    • 有一个关系式:第$i$趟,剩余元素待排序序列长度为$n-i+1$,元素下标范围$0$到$n-i$,所以循环的范围是$0\leq j<n-i$

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      #include<cstdio>
      using namespace std;

      int a[10] = {3,4,2,6,1,5}

      void bubbleSort(int a[], int n){
      for(int i=1;i<n;i++){
      for(int j=0; j<n-i; j++){
      if(a[j] > a[j+1]){
      int tmp = a[j];
      a[j] = a[j+1];
      a[j+1] = tmp;
      }
      }
      }
      }
  • 二维数组初始化

    • 1
      int a[5][6] = {{3,1,2}, {8,4},{},{1,2,3,4,5}}; //中间没赋值的必须加{},否则编译错误
  • memset

    • memset(数组名,值,sizeof(数组名));
    • memset按字节赋值,对每个字节赋相同的值,如果是int4个字节,每个字节都被赋值成一样的,所以只能给它赋0,1,因为0的补码为全0,-1的补码为全1,不会错
    • 如果要对数组赋其他数字,要用STL的fill函数
  • 字符数组仅允许在初始化时直接赋值字符串

  • 二维数组开大了,必须要在main函数外面定义,大概$10^6$级别!!!

  • 字符数组输入输出

    • scanf,printf

    • 1
      2
      scanf("%s",str);//不加取地址&
      printf("%s",str);
    • %c可以识别空格和换行并将其输入,而%s通过空格和换行来标识一个字符串输入结束,不会将其输进去

    • getchar,putchar

    • 1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      char str[5][5];//字符串数组
      for(int i=0; i<3;i++){
      for(int j=0;j<3;j++){
      str[i][j] = getchar();
      }
      getchar();//为了吸收每个字符串输入时的换行符,因为getchar会输入空格和换行
      }
      for(int i=0; i<3;i++){
      for(int j=0;j<3;j++){
      putchar(str[i][j]);
      }
      putchar('\n');//换行!!
      }
    • gets,puts

      • gets用于输入一行字符串,puts用于输出字符串,并外加了一个换行

      • gets函数识别换行为结束标志,当前面scanf输入后,回车符需要!!!!用getchar吸收!!!否则gets会读到换行,以为输入结束!出现问题!!!!!!!!!!!!!!!!!

      • 1
        2
        3
        4
        5
        6
        7
        8
        9
        10
        11
        12
        #include<cstdio>
        #include<cstring>
        using namespace std;

        int main(){
        int a;
        char chr[25];
        scanf("%d",&a);
        getchar();
        gets(chr);
        printf("chr = %s",chr);
        }
  • 字符串末尾有一个’\0’作为字符串结束标志,在计算字符串所需空间时需要算上这个位

    • 在输入字符串时,scanf和gets会自动在后面加一个\0并占一个字符位
    • 输出时,printf和puts识别到这个表示字符串达到结尾
    • 在使用getchar循环输入字符串时(一般也不会),记得要手动加’\0’
  • string.h

    • strlen(str);
    • strcmp(str1,str2);
      • 按位比较字典序,小于返回负整数,等于返回0,大于返回正整数
    • strcpy(str1,str2);
      • 将字符数组2复制给数组1,包括复制’\0’
    • strcat(str1,str2);
      • 将数组2接到1后面
  • sprintf,sscanf!!!!!字符串利器!!!!

    • sscanf(str, “%d”, &n); 将str的内容以%d的格式写到n中

    • sprintf(str, “%d”, n); 将n的内容以%d的格式写到str中

    • sscanf(screen, “%d”, &n); 等价于 scanf(“%d”,&n);

    • 1
      2
      char str[100] = "2048:3.14,hello", str2[100];
      sscanf(str, "%d:%lf,%s",&n,&db,str2);
    • 1
      2
      3
      4
      char str[100], str2[100] = "good";
      int n = 12;
      double db = 3.1415;
      sprintf(str, "%d:%.2f,%s",n,db,str1);
  • int变量占用4个字节,long long变量占8个字节,每个字节是一个房间,有个房间号,变量地址是首字节地址,指针变量是用来保存地址的变量

  • 注意:同时定义多个指针变量时,*要挨着变量,且每个变量前都要有,不同时的话则随意,C++喜欢挨着类型

    • 1
      int *p1, *p2, *p3;
  • 指针加1,跨越的是一整个int型,即4字节。

  • 数组a的首地址=&a[0]=a (数组名称可以当作数组首地址)

  • *(a+i) == a[i]

    • 1
      2
      3
      4
      scanf("%d",a+i);
      for(int*p=a;p<a+10;p++){
      vis(*p);
      }
  • p=2688708 q=2688688 q-p输出的是5不是20

    • 本来是20,但是指针相减,减的单位是int(假设是int指针),所以要20/4=5
  • 1
    2
    3
    4
    5
    void swap(int *a, int *b){
    int temp = *a;
    *a=*b;
    *b=temp;
    }//正确写法
  • 1
    2
    3
    4
    5
    6
    7
    void swap(int *a,int*b){
    int *temp;
    *temp = *a;
    *a=*b;
    *b = *temp;
    //因为temp指针未初始化,不能直接对所指的空间赋值
    }//错误
  • 1
    2
    3
    4
    5
    6
    void swap(int *a,int*b){
    int *temp = a;
    a = b;
    b = temp;
    //虽然函数里面的a,b确实交换了地址,但是传入的a,b实际是指针的拷贝,不会影响外面a,b的存放的地址值
    }//错误
  • 1
    2
    3
    4
    5
    6
    void swap(int* &a,int* &b){
    int *temp = a;
    a = b;
    b = temp;
    //传入的是引用!!!!是指针的别名!
    }//正确!!!
  • 结构体里虽然不能定义自己本身,但是可以定义自身类型的指针

    • 1
      2
      3
      4
      struct node {
      node n;
      node *next;
      }
  • 结构体里有隐式的默认构造函数,有个技巧是重写这个

1
2
3
4
5
6
struct point{
int x,y;
point(){} //用于不经初始化地定义结构体变量pt[10]
point(int _x, int_y):x(_x),y(_y){} //用于提供对x和y的初始化
}pt[10];
point(3,5);//定义且初始化了!
  • cin,cout

    • 1
      2
      3
      4
      cin>>n>>db>>C>>str;
      cout<<n<<db<<c<<"\n"<<str<<endl;
      #include<iomanip> //控制时要加入这个头文件
      cout << setiosflags(ios::fixed)<<setprecision(2)<<123.4567<<endl;//控制输出位数
  • getline

    • 1
      2
      char str[100];
      cin.getline(str,100);
    • 1
      2
      string str;
      getline(cin, str);
  • 事实上必要时才用 cin,cout(如string str时),否则性能糟糕

  • 浮点数比较

    • eps一般取$10^{-8}$

    • 当变量经过误差较大的计算后再比较,就需要考虑精度的问题,比如0,有时候经过计算后的0实际是很小的负数,如果开根就会出错,需要用eps来修正

    • 就要重写比较函数

    • 对于a,如果落到区间$[b-eps,b+eps]$ 就应该判断a==b成立,所以相等的条件是$|a-b|<eps$

    • 对于a要大于b,因为b在$[b-eps,b+eps]$都被认为等于b,所以大于的话,必须$a>b+eps=>a-b>eps$

    • 小于$aa-b<-eps$

    • 大于等于的话,就是大于和等于都要,则$a>b-eps=>a-b>-eps$

    • 小于等于,就是小于和等于都要,则$aa-b<eps$

    • 1
      2
      3
      4
      5
      6
      7
      const double eps = 1e-8;
      const double Pi = acos(-1.0);
      #define equ(a,b) ( (fabs((a)-(b))) < (eps) )
      #define more(a,b) (((a)-(b)) > (eps))
      #define less(a,b) (((a)-(b)) < (-eps))
      #define geq(a,b) (((a)-(b)) > (-eps))
      #define leq(a,b) (((a)-(b)) < (eps))
  • 复杂度

    • $O(1)<O(logN)<O(N)<O(NlogN)<O(N^2)$
    • 估计运行时间
      • $O(N^2)$ 规模1e3的话,运算次数1e6,规模1e5的话,运算次数1e10
      • 一般OJ,一秒能承受的运算为1e7~1e8
  • 多点测试——程序一次能运行所有数据,且输出结果都要正确

    • 1
      2
      3
      4
      //循环输入多组数据
      while(scanf("%d%d",&a,&b) != EOF){

      }
    • 1
      2
      3
      4
      5
      6
      7
      8
      //循环输入多组数据,当输入为xxx时停止输入
      while(scanf("%d%d",&a,&b) != EOF){
      if(a==0 && b==0) break;
      }
      //等价
      while(scanf("%d%d",&a,&b), a||b){

      }
    • 1
      2
      3
      4
      5
      //给定测试数据组数
      scanf("%d",&t);
      while(t--){

      }
    • 1
      //三种输出,书上有。。。
  • 多点测试,每一次while(EOF)循环都要重置下变量和数组,用memset或者fill