四. 时间与空间

0. 数学符号扫盲

• $\left \lfloor x \right \rfloor$ ：向下取整
• $\left \lceil x \right \rceil$ ：向上取整
• $\left [ x \right ]$ ：向下取整
• $\sum_{i=1}^{n} i$ ：$i$ 从 $1$ 开始增长到 $n$ ，然后都给加起来
• $\sum_{i=l}^{r} i^3$ ：$i$ 从 $l$ 开始增长到 $r$ ，然后把三次方都给加起来
• $\sum_{i=l}^{r} 2i+3$ ：相当于 $(2l+3) + (2(l+1)+3) + (2(l+2)+3)+...+(2(r-1)+3)+(2r+3)$
• $\prod_{i=1}^{n}i$ ：相加改为相乘

1. 数据类型的范围

• 数据类型存在取值范围
• int
  • 最大存储 $2^{31}-1$
  • 最小存储 $-2^{31}$
• long long
  • 最大存储 $2^{63}-1$
  • 最小存储 $-2^{63}$
• 数字还大？视为字符串存储，计算使用高精度算法

2. 取模的性质

由于某些题目的计算结果可能超出了long long的范围，而且高精度算法很难写，所以很多题目要求我们将计算结果取模后再输出。

• $a\% b$ 的结果取值范围为 $0$ 到 $b-1$
  • 因此我们可以通过取模把所有的整数不重不漏分类
  • 一个数取模之后可以保证结果不会比模数还要大
• $(a+b)\%p=(a\%p+b\%p)\%p$
• $(a*b)\%p=a\%p*b\%p$
• $(a-b)\%p=(a\%p-b\%p+p)\%p$
  • 为什么要加p模p？因为我们防止出现负数
    • 如 $(7-5)\%3$ 显然是 $2$
    • 而 $7\%3=1$ ，$5\%3=2$
    • 你可以考虑一下 $(a+b)\%b$
• 除法？没有类似的，需要逆元

3. 空间限制

• 你开的所有变量都是占用内存的
• 使用sizeof函数可以查看占用内存情况
• 语法：sizeof(a) 可以看到变量 $a$ 占用内存。函数返回一个int，表示变量占用内存，单位字节
  • sizeof(a)/1024 单位kb
  • sizeof(a)/1024/1024 单位mb

来个题目

T217223 https://www.luogu.com.cn/problem/T217223

• oi中的科学计数法：$1e9=10^9$ , $2e10=2\times 10^9$，你可以在c++中直接这么表示

  • 注意c++中的 10^9 不代表 $10^9$ 而是表示 $10$ 与 $9$ 进行异或运算

• 运算过程中很有可能超出了int的范围，即使取模能让你的中间运算结果位于 $1e9+9$ 以内，但你发现两个 $1e9$ 的数字相乘会超出int范围，考虑使用long long

• 把哪个变量变成long long？我建议你把所有变量都变成long long

  1. 加入 #define int long long 代码
  2. 把main函数的返回值数据类型改为 signed
  3. 以后做题最好是都 #define int long long 确保万无一失

• 但long long类型的内存占用大，你需要注意一点题目的空间限制

• 注意，这种取模的题，每次运算都要取模！一个地方没取模就有可能寄

• mle了？考虑是不是数组有点多余了

4. 前缀和

解锁我们的第二个算法

（不带修改的区间询问）https://www.luogu.com.cn/problem/U156243

• 直接暴力

  • 处理单次询问时间复杂度 $O(n)$
  • 共 $m$ 次询问，总的时间复杂度为 $O(mn)$ ，无法通过

• 令 $sum[i]=sum[i-1]+a[i]$ ，对于 $[l,r]$ 的询问，直接输出 $sum[r]-sum[l-1]$ 即可

  • 预处理时间复杂度 $O(n)$
  • 处理单次询问时间复杂度 $O(1)$
  • 共 $m$ 次询问，总的时间复杂度为 $O(m+n)$ ，跑的飞快！

• 类似前缀和的思想

  • 从 $1$ 到 $n$ 加起来，公式为 $\frac{n(n+1)}{2}$
  • 从 $l$ 加到 $r$ 呢？

5. 语法扫尾

• if、while、for语句在花括号中仅有一行代码时可以简写，省略花括号
• c++中，0 就代表false，除 0 以外的数字都代表 true，可用于简化条件

cpp
1
2
3
if(a!=0){
	x++;
}

cpp
1
if(a) x++;

• 常量：在定义变的时候加 const ，如 const int mod=1e9+9 即可定义一个常量。常量不能被改变
  • 一般开成全局变量
  • #define mod 1000000009 也有类似效果，但这里就不建议使用 $1e9+9$ 了
  • 准确来说不建议使用 $1e9+9$ 这种形式，因为有学长因为这个爆零过...
  • 一般来说，数组长度和模数都定义成常量，这样我更改一处，所有地方都能跟着改变

cpp
1
2
#define _ 1000006
int arr[_];

• 一些数学函数
  • sqrt(a) ：开方，返回double类型数据
  • abs(a)：给整数取绝对值
  • fabs(a)：给浮点数取绝对值
• 如何比较两个double类型相等？

cpp
1
2
3
4
5
6
7
const double eps=1e-9;//给一个非常小的误差常数

if(fabs(a-b)<=eps){
    //a==b
}else{
    //a!=b
}

• 正无穷

  • 对于 int 类型，可以赋值为 0x3f3f3f3f 来将该变量的值变成正无穷，加一个负号就是负无穷
  • 对于 long long 类型，可以赋值为 0x3f3f3f3f3f3f3f3f

• memset(arr,0,sizeof(arr)) memset可以批量给一个数组赋值，但只能赋值为一些简单值，比如1和0，2貌似就不太行了，如果你不太懂建议开for循环，或者写个代码测试一下能不能正确赋值

  • memset(arr,0x3f,sizeof(arr)) 可批量赋值为正无穷
  • memset(arr,-0x3f,sizeof(arr)) 可批量复制为负无穷

• 潜在的致命错误：.size()的返回的无符号整数类型。无符号类型和有符号整数类型比较会出问题

  cpp
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  #include<bits/stdc++.h>
  using namespace std;
  
  int main(){
  	string a="";
  	if(-1<a.size()){
  		cout<<"a";
  	}else{
  		cout<<"b";
  	}
  	return 0;
  }
  

  cpp
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  //正确的处理方案
  #include<bits/stdc++.h>
  using namespace std;
  
  int main(){
  	string a="";
  	int len=a.size();
  	if(-1<len){
  		cout<<"a";
  	}else{
  		cout<<"b";
  	}
  	return 0;
  }
  

• 关于头文件

  • #include<iostream> 中包含 cout/cin/endl 等
  • #include<string> 中包含 string 类型等
  • #include<cstring> 中包含 strlen/memset 等
  • #include<algorithm> 中包含 sort 等
  • #include<cmath> 中包含 abs/fabs/sqrt 等
  • 你以后学习新东西之后可能都要记忆在哪个头文件中
  • #include<bits/stdc++.h> 万能头，包含所有头文件

大谈输入输出

信竞中的输入是门学问

• 方案一：cin/cout

  • 优点就是简单

  • 缺点就是有很多问题

  • 速度比较慢，容易超时，虽然可以使用 ios::sync_with_stdio(false); 解决

  • 出乎意料的输出

  • cpp
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    //类型一：整数位很多
    double x=12345678;
    //类型二：小数位很多，有效小数位少
    double y=0.00001234;
    //类型三：小数位很多，有效小数位也多
    double z=3.1415926;
    
    cout<<x<<endl;
    cout<<y<<endl;
    cout<<z<<endl;
    
    /*
    输出结果
    1.23457e+07
    1.234e-05
    3.14159
    */
    

• 方案二：scanf/printf

  • 优点：速度很快，而且可以自由控制输出

  • 缺点：你可能要多学点东西

  • 占位符：

    • %d：int类型
    • %lf：double类型
    • %s：char数组类型
    • %c：char类型
    • %.nlf：保留 $n$ 位小数
    • %lld：long long类型

  • printf

    • printf("number:%d",123)
    • 输出时，占位符位置会变成你传递的内容
    • 有几个占位符就要额外传递几个参数
    • 占位符和传递的参数的数据类型要匹配

  • 就想输出百分号？%%

  • 换行符 \n

  • 就想输出斜杠 \\

  • scanf

    • scanf("%d",&n)
    • 输入一个指定的内容，存到给定的变量中
    • 变量前需要加 &
    • 占位符和传递的参数的数据类型要匹配
    • 读入字符串有点不同

    cpp
    1
    2
    3
    4
    //不要加 `&` 且 str 变量需要是一个char数组
    char str[1003];
    scanf("%s",str);
    printf("you input: %s", str);
    

  • 你要是 #define int long long 之后直接 printf("%d", a) 就寄啦！

• 注意！

  • 使用 ios::sync_with_stdio(false); 后，就不能再使用 scanf/printf 了，否则就寄啦！

• 一个可能更好的方案

  • 一般题目，只需要 ios::sync_with_stdio(false); + cin/cout 即可
  • 如果遇到需要保留的小数的问题，cin/cout + printf 即可
  • 不过建议有能力的同学可以考虑从现在开始就养成只用 scanf/printf 的习惯

吾生也有涯，而知也无涯。 —— 庄子·内篇·养生主第三

还有更多知识有待大家学习！

6. 练习

套题：CZOI Online #1 https://www.luogu.com.cn/contest/185344

本次练习题按比赛的形式进行，各位可以提前看看洛谷的比赛功能怎么操作

一定要交一下自己的名字！代码写完交完之后就不用再发到群里了

额外附赠的几道题

（练习取模）T217224 [CZOI2022]没有用的前缀和 https://www.luogu.com.cn/problem/T217224

（练习前缀和）P8218 【深进1.例1】求区间和 https://www.luogu.com.cn/problem/P8218

（练习前缀和）P5638 【CSGRound2】光骓者的荣耀 https://www.luogu.com.cn/problem/P5638

一些适合初学者的近年真题

P9752 [CSP-S 2023] 密码锁 https://www.luogu.com.cn/problem/P9752

P9117 [春季测试 2023] 涂色游戏 https://www.luogu.com.cn/problem/P9117

P7960 [NOIP2021] 报数 https://www.luogu.com.cn/problem/P7960

P9868 [NOIP2023] 词典 https://www.luogu.com.cn/problem/P9868

去年选拔赛的题目

CZSC 2023（第一次）https://www.luogu.com.cn/training/359855

CZSC 2023（第二次）https://www.luogu.com.cn/training/364201

以下题目有难度（甚至适合给高二的学生练），仅供大佬研究（至少我们的选拔赛出不了这么难的题）

（化简求和符号，当时作为21级模拟赛题目，仅一人做出）T269292 「FAOI-R1」A Simple Math Problem (D) https://www.luogu.com.cn/problem/T269292

（推式子）P5686 [CSP-S2019 江西] 和积和 https://www.luogu.com.cn/problem/P5686

（观察性质+前后缀和+考虑贡献）T351561 [CZOI Online #4] 序列 https://www.luogu.com.cn/problem/T351561 （这个题就看看吧，这题当时连轩神和金神都没搞出来）

7. 关于选拔赛

CZSC 2024 （第一次）https://www.luogu.com.cn/contest/188106