考试常用语法点整理合集

ShiRoZeTsu · 2023-09-25 23:16:49 · 个人记录

本文是笔者 2023 CSP-S 复习写的博客，主要是总结知识点用，如有遗漏或不准确，还请海涵。

Part1 输入与输出

1.1 cin /cout 和 scanf/ printf

C++ 标准的输入输出是 cin 与 cout，它们可以输入/输出绝大部分常用的数据类型，以下给出一些常见数据类型。

整型：int / long long / unsigned int / unsigned long long

int a;
long long b;
unsigned int c;
unsigned long long d;
cin >> a >> b >> c >> d;
cout << a << b << c >> d;

浮点型：float / double

float a;
double b;
cin >> a >> b;
cout << a << b;

字符/字符串型：char / char* / string

char a;
char b[maxn];
string c;
cin >> a >> b+1 >> c;
cout << a << b+1 << c;

但是，有些题目对于输入/输出有格式上的要求，而 cin 和 cout 在格式上很难操控，因此我们常用 scanf 和 printf 来代替。

整型：int / long long / unsigned int / unsigned long long

int a;
long long b;
unsigned int c;
unsigned long long d;
scanf("%d %lld %u %llu", &a, &b, &c, &d);
printf("%d %lld %u %llu", a, b, c, d);

浮点型：float / double

float a;
double b;
scanf("%f %lf", &a, &b);
printf("%f %lf", &a, &b);

字符/字符串型：**char / char***

char a;
char b[maxn];
scanf("%c %s", &a, b+1);
printf("%c %s", a, b+1);

• 注意，scanf 和 printf 不能输入/输出 string 类型。

对于输入/输出 8 进制或 16 进制的数字，scanf 与 printf 的操作非常简便。

int a;
scanf("%o", &a);
printf("%o", a);
//%o 是八进制 （o 即为 octal 八进制的缩写）
scanf("%x", &a);
printf("%x", a);
//%x 是十六进制 （x 即为 hex 八进制的缩写）
//当然，%d 是十进制 （d 即为 decimal 八进制的缩写）

• scanf 还可以限定输入长度。

比如有一个数字 114514，如果只想读入前 4 位：

int a;
scanf("%4d", &a);

• scanf 还可进行一些格式化的输入。

比如要输入 2023-9-25 22:39:10 这个时间，那么可以用 scanf 很方便地读入。

int year, month, day, hour, minute, second;
scanf("%d-%d-%d %d:%d:%d", &year, &month, &day, &hour, &minute, &second);

当然，这样限定长度也是可以的。

比如输入 11 45 14，但我只想要两边的数字，不要中间的 45，可以这么写：

int a, b;
scanf("%d 45 %d", &a, &b);

这样 a = 11，b = 14。

• printf 可以控制浮点数的保留小数位数。

比如 114.514，我只想保留一位小数：

double a = 114.514;
printf("%.1lf", a);

注意四舍五入。

1.2 换行

在输出一行文本时，常用的换行符有两种。

• 第一种是 cout 使用的 endl：

cout << a << endl;

• 第二种是 printf 使用的 '\n'：

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

但是实际上，cout 也是可以使用 '\n' 的。

cout << a << '\n';

注意这里是单引号，也就是说 '\n' 整体是一个字符。

在这里阐述一下我只使用 '\n' 而从来不用 endl 的原因：因为 endl 比 '\n' 更慢，据说是要刷新一些东西（这个不是很懂），而且我主要使用的是 scanf 和 printf，所以 endl 很少碰。

在一些输入输出数据非常大的题目中，如果你使用 endl 可能会喜提 TLE，但是用 '\n' 就能 AC。

还有一些输出换行符的方式：

• putchar：

putchar('\n');

实际上就是单独输出一个 '\n' 字符嘛。

• puts：

puts("");

虽说写起来比较短，但是尽量我很少使用。

1.3 读入字符

单独把读入字符列出来的原因是，scanf("%c", &c) 这玩意儿会读入空格，有的时候会很麻烦。

怎么解决？

用cin读入字符串即可。

scanf("%s", s+1);

用这个东西代替你读入单个字符，然后你要的那个字符就是 s[1]。

因为读入字符串会自动过滤空格，所以这样是没问题的。

当然，狠人可以使用 getchar （也就是和 putchar 对应的，输入/输出单个字符），然后不断过滤空格。

char c = getchar();
while(c == ' ' || c == '\n') c = getchar();

1.4 读入整行

也就是说，一行中有若干个字符串（之间有空格），现在要把它们全部输入进一个字符串里。

当然，scanf 是可以做到这个操作的，但是这里也可以使用 cin。

形式类似于这样：

string s;
getline(cin, s);

就可以了。

1.5 IO优化

IO 优化，也就是针对所谓的输入/输出效率优化，这里介绍三种常用方法。

第一种 关闭同步

这个主要针对 cin 与 cout 来使用，它们的代码长这样：

ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);

牢记这三行。

这个优化可以让 cin 和 cout 的效率和 scanf 与 printf 接近（虽说还是差了一丁点）。

但是有一个大忌：由于关闭了同步，在写了上面的三行代码之后，绝对不要使用任何 scanf 和 printf！

如果你使用了，这样做的后果就是输出紊乱。

切记，切记！

第二种 使用 scanf 和 printf

既然关闭同步的效率和 scanf 和 printf 差不多，那我为什么不直接使用 scanf 和 printf 呢（）。

第三种 手写输入输出

这个是三种方法中速度最快的方法了。当然，这么快的代价就是要写很长一段，不过比赛前十分钟，你应该可以抽出空写。

这里给出输入/输出 int 的快读模板：

int read() {
    int res = 0, flag = 1; char c = getchar();
    while(c < '0' || c > '9') { if(c == '-') flag = -1; c = getchar(); }
    while(c >= '0' && c <= '9') { res = res*10 + c-'0'; c = getchar(); }
    return res*flag;
}

void print(int x) {
    if(x > 9) print(x/10);
    putchar(x%10 + '0');
}

1.6 一些例外

• 大数字 -- __int128

  总有数据范围开到很大，甚至超过 unsigned long long 的时候。这个时候你会选择使用高精度吗？

  能不用就不用，因为写起来太麻烦了。

  这里推荐一个科技：使用 __int128。

  当然，使用 __int128 是不适配 cin cout 或 scanf printf 的，所以只能手写输入/输出。

  __int128 read() {
    __int128 res = 0, flag = 1; char c = getchar();
    while(c < '0' || c > '9') { if(c == '-') flag = -1; c = getchar(); }
    while(c >= '0' && c <= '9') { res = res*10 + c-'0'; c = getchar(); }
    return res*flag;
  }
  
  void print(__int128 x) {
    if(x > 9) print(x/10);
    putchar(x%10 + '0');
  }

• 不断读入，直到输入为 0

  这个还是有一定技巧的。

  我个人比较推荐，将输入放在循环内部的写法，因为这样就可以避免一些奇奇怪怪的返回值。

  scanf("%d", &n);
  while(n) {
    //这里是程序主体
    scanf("%d", &n);
  }

Part2 数组及相关内容

1.1 定义

数组，也就是一组数，用来开辟若干大小的空间，开辟若干个变量。

正常数组的定义方式有三种。

• 声明长度和元素

  也就是说，一开始定义就直接告诉程序，这个数组的长度，以及其中的元素。

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

  \

• 声明长度

  一开始只告诉程序，你的数组大小。

  int a[5];

  注意，此时如果你的数组不是全局变量，那么你的数组在实际使用时需要初始化。

  \

• 声明元素（并声明长度）

  一开始只告诉程序，你的数组元素。而程序会记录你输入的元素个数，构成数组长度。

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

  其实也就是，不那么直接地声明长度。

• 如果你的数组是全局变量，而且你没有进行初始化，那么它们默认都是 0；

• 如果题目中给定 n （即数组长度）的范围，在实际开数组时，请务必开得比 n 大一些（一般是大 5 或者 10），因为程序中数组的第一个元素是 a[0]。

• 在题目给定了内存限制时，请计算自己所使用的空间是否超出范围。

  比如一道题内存限制时 128 MiB，你开了一个大小为 10^8 的 int 数组。现在来看看你的空间是否超出了限制：

  • 先将 10^8 \times 4 变成 4 \times 10^8（乘 4 是因为，一个 int 占 4 个字节）；

  • 再将 4 \times 10^8 用计算器连续除以两次 1024，也就是：

    \frac{4 \times 10^8}{1024 \times 1024} \approx 381

  因此你的数组占用空间约为 381 MiB，超过了 128 MiB，于是爆掉了。

  当然，其它数据类型也是可以计算的。不过如果你不清楚一个数据类型的占用空间大小，可以使用 sizeof 关键字。

  • int

  printf("%d\n", sizeof(int));

  这一行的输出结果是 4。

  • long long

  printf("%d\n", sizeof(long long));

  这一行的输出结果是 8。

  • char

  printf("%d\n", sizeof(char));

  这一行的输出结果是 1。

  • __int128

  printf("%d\n", sizeof(__int128));

  这一行的输出结果是 16。

1.2 遍历

一般使用 for 循环遍历所有元素。当然，不遍历所有元素也是可以的。

for(int i = 1; i <= n; i++) {
    a[i] += 2;
    //程序内容
}

二维数组也是一样。

for(int i = 1; i <= n; i++)
    for(int j = 1; j <= m; j++) {

    }

1.3 传参

对于一个数组 a[n]，a 代表的是这个数组的首地址，也就是第一个元素的地址。

• 在将整个数组作为函数的参数时，可以选择两种写法。

第一种

void f(int* a) {
    //程序内容
}

第二种

void f(int a[]) {
    //程序内容
}

• 此外，由于 a 代表首元素地址，因此在输入数组时，也有两种写法。

第一种

for(int i = 1; i <= n; i++)
    scanf("%d", &a[i]);

第二种

for(int i = 1; i <= n; i++)
    scanf("%d", a+i);

注意下面是 a+i，因为 a 是地址，不需要再写取地址符 &。

• 也可以将数组只传一半。

  int a[] = {0, 2, 4, 6, 8, 10};
  f(a);

  然后在 f 函数里这么写：

  void f(int* a) {
    for(int i = 1; i <= 5; i++)
        printf("%d ", a[i]);
  }

  输出结果自然是 2 4 6 8 10。

  但是如果只想要 6 8 10 呢？

  int a[] = {0, 2, 4, 6, 8, 10};
  f(a+2); //注意这里

  然后在 f 函数里这么写：

  void f(int* a) {
    for(int i = 1; i <= 3; i++)
        printf("%d ", a[i]);
  }

  输出结果就变成了 6 8 10。

  可以单纯理解为，原来是从 2 开始输出，现在后移了 2 位，从 6 开始输出。

1.4 初始化/覆盖

假如有一个数组 a，想要把里面都清空成 0，怎么做？

• 当然可以使用 for 循环。

  for(int i = 1; i <= n; i++)
    a[i] = 0;

• 或者使用 <cstring> 里面的 memset 函数。

  memset(a, 0, sizeof(a));

那如果都清空成 1 呢？

请注意，此时不能使用 memset，只能使用 for 循环。

for(int i = 1; i <= n; i++)
    a[i] = 1;

不难发现，memset 虽然好用，但是是有局限性的。

一般来讲，memset 里可以传入的数字有 0，-1。这些修改都是成功的。

比较特殊地，如果要将数组都变成一个很大的数字，一般来说是 0x3f3f3f3f，那么也可以这么写：

memset(a, 0x3f, sizeof(a));

如果要将数组都变成一个很大的数字，那么也可以这么写：

memset(a, 0xc0, sizeof(a));

当然，在数组第一次使用时，只要你声明的是全局变量，那么不清零也是可以的，因为默认是 0。

1.5 常用函数

排序函数

比较常见的就是将数字元素排序。

在默认情况下，sort 函数是从小到大排序的。

sort(a+1, a+1+n);

请注意，这里面 a+1 是第一个元素的指针，a+1+n 是最后一个元素的后一个指针。（也就是说，a+1+n 这个地址是没有数字的。）

至于从大到小排序，以及其它更复杂的排序，我会在后面的内容讲到。

去重函数

也就是 unique 函数，它和 sort 函数的参数一样。

但是，它的返回值是去重后最后一个元素的后一个指针，因此如果想记录数组中不同元素的个数，可以这么写：

sort(a+1, a+1+n);
//不要忘记，使用 unique 函数之前，一定要保证数组已经排好序
int m = unique(a+1, a+1+n) - a - 1;

牢记。

二分查找

手写的二分查找当然没问题，不过这里主要说的是 lower_bound 和 upper_bound。

它们的写法和 sort，unique 也是一样的，同样也返回的是指针。

在确定一个元素的位置，常见写法是这样的：

int pos = lower_bound(a+1, a+1+n, x) - a;

先总结到这，如有遗漏，欢迎提出！