2021第十二届蓝桥杯大赛软件赛省赛C/C++ 大学 B 组

记录刷题的过程、感悟、题解。 希望能帮到，那些与我一同前行的，来自远方的朋友😉

大纲：

1、空间-（题解）-字节单位转换

2、卡片-（题解）-可以不用当组合来写，思维题

3、直线-（题解）-数学知识y=ax+b、+模拟

4、货物摆放-（题解）-锻炼巧妙预处理的方式

5、路径-（题解）-披着图论的，dp🥲，怪吓人、其实跟图论没啥关系

6、时间显示-（题解）-时间转换与printf格式输出

7、砝码称重-（题解）-一道线性dp

8、杨辉三角形-（题解）-组合数+观察模拟

9、双向排序-（题解）-真 · 靠观察，天才门，脑洞大开吧

（已重刷：3 遍）

题目：

1、空间

本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。 小蓝准备用 256MB 的内存空间开一个数组，数组的每个元素都是 32 位 二进制整数，如果不考虑程序占用的空间和维护内存需要的辅助空间，请问 256MB 的空间可以存储多少个 32 位二进制整数？ 运行限制

• 最大运行时间：1s
• 最大运行内存: 128M

/* 基础知识 1TB=1024GB 1GB=1024MB 1MB=1024KB 1KB=1024B(字节) 1B=8b(bit) */ // int 32位，4字节B 在作本题的时候，一定要注意一个抽象的问题：越界 （256*1024*1024*8/32，这样会越界😥）

#include <bits/stdc++.h>
using namespace std;

int main(){
	 cout<<256*1024*1024/4<<endl;
	return 0;
}

2、卡片

问题描述

小蓝有 k 种卡片, 一个班有 n 位同学, 小蓝给每位同学发了两张卡片, 一 位同学的两张卡片可能是同一种, 也可能是不同种, 两张卡片没有顺序。没有 两位同学的卡片都是一样的。

给定 n, 请问小蓝的卡片至少有多少种?

输入格式

输入一行包含一个正整数表示 n 。

输出格式

输出一行包含一个整数, 表示答案。

样例输入

6

样例输出

3

样例说明

小朋友们手中的卡片可能是: (1,1),(1,2),(1,3),(2,2),(2,3),(3,3)。

评测用例规模与约定

对于 50 的评测用例, 1≤n≤104。

对于所有评测用例, 1≤n≤109。

运行限制

• 最大运行时间：1s
• 最大运行内存: 256M

其实这题，是可以不用动态规划。

简单的推导就行，简答的考察了一下思维。

​

大家看到了什么

第一个3个、2个、1个...倒序，对吧！就是根据这个，

你能简单的计算一下区间数量。（1、3、6...）从而逆向求出需要几张卡片。

举例：有5个小朋友，2张卡片，只能区分3个。而3张卡片能区分6个。所以，需要3张卡片。

#include <bits/stdc++.h>
#define int long long
using namespace std;

signed main(){
	int n;
	cin>>n;
	int cnt = 1;
	int sum = 1; // 能够表示的个数 
	while(true){
		if(sum>=n) break;
		cnt++;
		sum+=cnt;
	} 
	cout<<cnt<<endl;
	return 0;
} 

3、直线

题目描述 本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。 在平面直角坐标系中，两点可以确定一条直线。如果有多点在一条直线上， 那么这些点中任意两点确定的直线是同一条。 给定平面上 2 × 3 个整点(x,y)∣0≤x<2,0≤y<3,x∈Z,y∈Z，即横坐标 是 0 到 1 (包含 0 和 1) 之间的整数、纵坐标是 0 到 2 (包含 0 和 2) 之间的整数 的点。这些点一共确定了 11 条不同的直线。 给定平面上 20×21 个整点 (x,y)∣0≤x<20,0≤y<21,x∈Z,y∈Z，即横 坐标是 0 到 19 (包含 0 和 19) 之间的整数、纵坐标是 0 到 20 (包含 0 和 20​) 之 间的整数的点。 请问这些点一共确定了多少条不同的直线。 运行限制

• 最大运行时间：1s
• 最大运行内存: 128M

// 其实本题，能转化成简单的数学问题，也就是 是不是一条线的问题 // 咱们这道题： /* 既然要找线段，首先就要确定两个点，从而确定一条线 但是有一种情况是，线段可能重复计算 排除重复的前提是，首先需要确定这条线： 这时，我们可以根据公式 y=kx+b; 我们可以根据 k 、b两个值，确定这条直线 （a1、b1）（a2、b2） : b1 = ka1 + b : b2 = kb2 + b k = (b1-b2)/(a1-a2); b = (a1*b2-a2*b1)/(a1-a2) -- 切记，这是化简之后的。 如果不化简，可能导致，精度损失过大，导致误判！！！ 当然，在计算过程中，要排除一种情况，就是k无限大的可能。90°时，无限大。 但只有20个，直接跳过，可以在结尾上加入。 但是，前提要用set这个函数。 因为红黑树重载了pair，能用 < 比较 但是unordered_set，没有重载pair的哈希 */

#include <bits/stdc++.h>
using namespace std;

int main(){
 
	set<pair<double,double>> set; 
	for(int a1=0; a1<20; ++a1){
		for(int b1=0; b1<21; ++b1){
      // 位置第一个(i，j)位置
      for(int a2=0; a2<20; ++a2){
        for(int b2=0; b2<21; ++b2){
          // 位置第二个(x，y)位置，现在，咱们知道了，两个位置，也可以开始计算了
          // 这个时候，要排除两个点：
          if(a1==a2) continue; // 当a1==a2的情况时 b1==b2重叠，b1!=b2 垂直
		  double k =  (double)(b1-b2)/(a1-a2);
		  double b = (double)(a1*b2-a2*b1)/(a1-a2);
		  set.emplace(k,b);
        }
      }
			
	 }
	}
	cout<<set.size()+20<<endl;
	return 0;
}

4、货物摆放

题目描述 小蓝有一个超大的仓库，可以摆放很多货物。 现在，小蓝有 n 箱货物要摆放在仓库，每箱货物都是规则的正方体。小蓝规定了长、宽、高三个互相垂直的方向，每箱货物的边都必须严格平行于长、宽、高。 小蓝希望所有的货物最终摆成一个大的长方体。即在长、宽、高的方向上分别堆 L、W、H 的货物,满足 n=L×W×H。 给定 n，请问有多少种堆放货物的方案满足要求。 例如，当 n=4 时，有以下 6 种方案：1×1×4、1×2×2、1×4×1、2×1×2、2×2×1、4×1×1。 请问，当 n=2021041820210418（注意有 16 位数字）时，总共有多少种方案？ 提示：建议使用计算机编程解决问题。 答案提交 这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

/* 讲一个冷知识，普遍大家的编辑器，1s空转大概也就1e8次~1e9次之间 而本题大概有1e16次方这么大，所有就不要有不切实际的幻想啦！ 所以做这种题目，不要怀疑！直接对数据提前处理。 就算预处理，依然要考虑一件事情，就是怎么处理16位数据。 对题目分解，你或许会发现，其实本题参与运算的，其实都是质因数。

当然，这里有一个冷知识，注意开辟数组的大小。int类型数组，开到1e8大概400MB，long long为800MB（都会内存越界），所以开到1e7最为合适。 */

#include <bits/stdc++.h>
#define int long long
const int N = 1e7;
int arr[N];
using namespace std;

signed main(){
 	int sum = 2021041820210418;
	int cnt = 0;
	// 通过巧妙的数学思维，转换高纬度运算。并且求值 
	for(int i=1; i*i<=sum; ++i){ 
		if(sum%i==0) arr[cnt++]=i;
		if(sum%i==0&&sum/i!=i) arr[cnt++]=sum/i; // 切记，千万别忘加sum%i，否则会导致误判很多 
	}  
	int res = 0;
	for(int i=0; i<cnt; ++i)
		for(int j=0; j<cnt; ++j)
			for(int k=0; k<cnt; ++k)
				if(arr[i]*arr[j]*arr[k]==sum) res++;
				
	cout<<res<<endl;
	return 0;
} 

5、路径

本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。 小蓝学习了最短路径之后特别高兴，他定义了一个特别的图，希望找到图 中的最短路径。 小蓝的图由 2021 个结点组成，依次编号 1 至 2021。 对于两个不同的结点 a, b，如果 a 和 b 的差的绝对值大于 21，则两个结点 之间没有边相连；如果 a 和 b 的差的绝对值小于等于 21，则两个点之间有一条 长度为 a 和 b 的最小公倍数的无向边相连。 例如：结点 1 和结点 23 之间没有边相连；结点 3 和结点 24 之间有一条无 向边，长度为 24；结点 15 和结点 25 之间有一条无向边，长度为 75。 请计算，结点 1 和结点 2021 之间的最短路径长度是多少。 提示：建议使用计算机编程解决问题。 运行限制

• 最大运行时间：1s
• 最大运行内存: 128M

/* 如果，真的把这道题目当作图论来写，那就真是小可爱。 怎么说呢，就是一道，血脉纯正的dp，与图真的，不太沾边 但是，写这道题目的前提是， 你要会求解 lcm，而求解lcm的前提是，你会求解 gcd。 当这一切搞定，那就理所应当的开始dp之旅吧 dp[i]的，定义可以看作是 到达i 所走的距离 */

#include <bits/stdc++.h>
using namespace std;

int dp[2070]; // 稍稍开大一点 
int gcd(int a, int b){
	return a%b==0?b:gcd(b,a%b); 
}
int main(){
	// dp[i]代表，到达i所走的距离 
	for(int i=1; i<=2021; ++i){
		for(int j=i+1; j<=i+21; ++j){ // 当然是算21的差距啦 
			if(dp[j]==0) dp[j]=dp[i]+i*j/gcd(i,j);
			else dp[j]=min(dp[j],dp[i]+i*j/gcd(i,j)); 
		}
	}
	cout<<dp[2021]<<endl;
	return 0;
} 

6、时间显示

题目描述

小蓝要和朋友合作开发一个时间显示的网站。

在服务器上，朋友已经获取了当前的时间，用一个整数表示，值为从 1970 年 11 月 11 日 00:00:00 到当前时刻经过的毫秒数。

现在，小蓝要在客户端显示出这个时间。小蓝不用显示出年月日，只需要显示出时分秒即可，毫秒也不用显示，直接舍去即可。

给定一个用整数表示的时间，请将这个时间对应的时分秒输出。

输入描述

输入一行包含一个整数，表示时间。

输出描述

输出时分秒表示的当前时间，格式形如 HH:MM:SS，其中 HH 表示时，值为 0​​​​ 到 23​​​​，MM 表示分，值为 00​​​ 到 59​​​，SS 表示秒，值为 0​​ 到 59​。时、分、秒 不足两位时补前导 0。

输入输出样例

示例 1

输入

46800999

输出

13:00:00

示例 2

输入

1618708103123

输出

01:08:23

评测用例规模与约定

对于所有评测用例，给定的时间为不超过 10^18 的正整数。

// 毫秒的计算单位

// 当时的思考过程：先求出，有多少秒，在求出，有多少分，最后在求出，有多少小时，本题跟年、月无关 // 炸了，无论怎么写，好像都不对 // printf . 的位置，哪里错了？？！！！ /*

其实这里有两点需要注意：1s=1000ms； 1ms=1000ns

第二点，就是printf()的格式说明。 （%[标志][宽度][.精度][长度]转换说明符）--- 这个小玩意都玩不明白，就完了 · 1、整数补零格式：printf("%02lld",a)；补成3的格式：printf("%32lld",a);不足两位的补成3 2、精度（四舍五入）的格式 printf("%.4lf",a)；小数点后4位

*/

#include <bits/stdc++.h>
#define int long long
using namespace std;
// 毫秒的计算单位

signed main(){
    int sum;
    cin>>sum;
    int ss = (sum/1000)%60; // 有多少秒
    int mm = (sum/1000/60)%60; // 有多少分
    int hh = (sum/1000/60/60)%24; // 求有多少小时
    printf("%02lld:%02lld:%02lld",hh,mm,ss);
    return 0;
}

7、砝码称重

问题描述

你有一架天平和 N 个砝码，这 N 个砝码重量依次是 W1,W2,⋅⋅⋅,WN​。

请你计算一共可以称出多少种不同的重量？ 注意砝码可以放在天平两边。

输入格式

输入的第一行包含一个整数 N。

第二行包含 NN 个整数：W1,W2,W3,⋅⋅⋅,WN​。

输出格式

输出一个整数代表答案。

样例输入

3
1 4 6

样例输出

10

样例说明

能称出的 10 种重量是：1、2、3、4、5、6、7、9、10、11。

1=1；

2=6−4(天平一边放 6，另一边放 4)；​

3=4−1；

4=4；

5=6−1；

6=6；

7=1+6；

9=4+6−1；

10=4+6；

11=1+4+6。

评测用例规模与约定

对于 50的评测用例，1≤N≤15。

对于所有评测用例，1≤N≤100,N​个砝码总重不超过 100000。

运行限制

• 最大运行时间：1s
• 最大运行内存: 256M

// 要给出暴力解法

/* 怎么说呢，这道题目，都暗示的这么明显了。 其实多少有点背包问题的味道。 但，他可比背包问题，多了不同的情况 （背包问题考虑的是，放还是不放 （砝码问题，考虑的是，放的时候，放左边，还是放右边，或者不放 所以大胆的设dp值：dp[i][j] 含义是第i个砝码，能够称出的重量为j 递推公式，更易推导出来 咱们这里先举出所有递推公式： ( dp[i-1][j]; ( dp[i-1][abs(j-w)] ( dp[i-1][j+w] 放入第i个砝码时，判断能否称出重量k 是由上一个砝码决定的。 如本题：1 4 6 dp[i-1][j] 当轮到砝码6时，判断是否能称出1时，dp[i][k]=dp[i-1][k]，直接判断之前是否出现这种情况。 dp[i-1][j+w] 大家可以找一个，他的作用是，放在天平两侧 1、4、6无法举出好例子，当如果i-1时，能称出，12这个重量，那么dp[i-1][12-6]就相当于称出了6这个重量。 dp[i-1][abs(j-w)]，公式推导，天平放在同一侧。 当轮到砝码6时，判断能否称出2这个重量时，2-6;-->看的就是 是否存在 dp[i-1][abs(2-6)]--dp[i-1][abs(i-j)]; 判断是否能称出砝码10时，10-6；--> 看的就是 是否存在 dp[i-1][abs(10-6)]--dp[i-1][abs(i-j)]; 注：其实，j-w<0时，就相当于，放在了天平两侧 */

我知道，你曾经对dp[i-1][abs(j-w)]，有天大的疑惑，现在我来告诉你，他就是j与w位置互换。（第三遍复习留白）

#include<bits/stdc++.h>
using namespace std;
const int N = 1e2+5;
const int W = 2e5+5; 

int dp[N][W]; 
int weight[N];
int main(){
	memset(dp,0,sizeof dp);
	int n; // 表示有几个砝码
	cin>>n; 
	for(int i=1; i<=n; ++i) cin>>weight[i]; // 天呐，简直了
	 
 	dp[0][0]=1;
	for(int i=1; i<=n; ++i){
		int w = weight[i]; // 原来是这样子的呢。
		for(int k=0; k<100001; ++k){ // 原来是这样子的呢。的呢。 
			if(dp[i-1][k]) dp[i][k]=dp[i-1][k];
			else {
				dp[i][k]=max(dp[i-1][abs(k-w)],dp[i-1][k+w]); 
			}
		} 
	} 
	int cnt = 0;
	for(int i=1; i<100001; ++i) if(dp[n][i]) cnt++;
	cout<<cnt;
	return 0;
}

8、杨辉三角形

题目描述

下面的图形是著名的杨辉三角形：

​

如果我们按从上到下、从左到右的顺序把所有数排成一列，可以得到如下数列： 1,1,1,1,2,1,1,3,3,1,1,4,6,4,1,⋯

给定一个正整数 N，请你输出数列中第一次出现 NN 是在第几个数？

输入描述

输入一个整数 N。

输出描述

输出一个整数代表答案。

输入输出样例

示例 1

输入

6

输出

13

评测用例规模与约定

对于 20​​ 的评测用例，1≤N≤10​； 对于所有评测用例，1≤N≤1000000000。

/* 能完成这道题目，观察思维都是次要的，因为，你要首先要知道杨辉三角与组合数的关系。 当你知道与组合数之间的关系后，再看看y总讲解。切记先上网找资料研究一下。 */

#include <iostream>
#define int long long
using namespace std;

int get_C(int n, int m,int sum){ // 从n个元素中，挑选m个元素
    int res = 1;
    for(int i=1,j=n; i<=m; ++i,--j){
        res*=j;
        res/=i;
        if(res>sum) return res; // 一旦大于目标值，就没有必要比较了
    }
    return res;
}

bool find(int k, int num){ // k就是上方的值
    int l = 2*k, r = max(num,l); // 获取，取值范围
    int cnt = -1;
    while(l<=r){
        int mid = l+(r-l)/2;
        if(get_C(mid,k,num)<num){
            l = mid+1;
        }else if(get_C(mid,k,num)>num){
            r = mid-1;
        }else{
            cnt = mid;
            l = mid+1;
        }
    }
    if(cnt!=-1){
        cout<<(cnt+1)*cnt/2+(k+1)<<endl;
        return true;
    }
    return false;
}

signed main(){ // 通过计算，最多n行
    int n;
    cin>>n;
    if(n==1){
      cout<<1<<endl;
      return 0;
    }
    for(int i=16; i>=0; --i){
        if(find(i,n)) break;
    }

    return 0;
}

9、双向排序

题目描述

给定序列 (a1,a2,⋅⋅⋅,an)=(1,2,⋅⋅⋅,n)，即 ai=i。

小蓝将对这个序列进行 mm 次操作，每次可能是将 a1,a2,⋯,aqi 降序排列，或者将 aqi,aqi+1,⋯,an​ 升序排列。

请求出操作完成后的序列。

输入描述

输入的第一行包含两个整数 n,m，分别表示序列的长度和操作次数。

接下来 m​ 行描述对序列的操作，其中第 i 行包含两个整数 pi,qi 表示操作类型和参数。当 pi=0时，表示将 a1,a2,⋅⋅⋅,aqi降序排列；当 pi=1​ 时，表示将 aqi,aqi+1,⋯, 升序排列。

输出描述

输出一行，包含 n 个整数，相邻的整数之间使用一个空格分隔，表示操作完成后的序列。

输入输出样例

示例

输入

3 3
0 3
1 2
0 2

输出

3 1 2

样例说明

原数列为 (1,2,3)​​​​​。

第 1​​​​​ 步后为 (3,2,1)​​​​​。

第 2​​​​ 步后为 (3,1,2)​​。

第 3​​​ 步后为 (3,1,2)。与第 2 步操作后相同，因为前两个数已经是降序了。

评测用例规模与约定

对于 30% 的评测用例，n,m≤1000；

对于 60% 的评测用例，n,m≤5000；

对于所有评测用例，1≤n,m≤100000，0≤pi≤1，1≤qi≤n。

好啦，这道题目，y总讲解的也挺不错的，大家可以直接食用 :: 传送门 ::

/*

细节评审！！！其实直接将大家交给y总，我还是挺不放心的 因为，有些细节确实挺让人头疼。甚至因为这个小细节，我直接被罚坐5个小时。 只是为了去扣，为什么我的答案与标准答案，几乎一模一样，凭什么不对！ 错误示范：

   for(int i=0; i<m; ++i){ // 我觉的这样初始化，非常完美
        int f,pla;
        cin>>f>>pla;
        if(f==0){ // 降序
            while(top>1 && stack[top-2].first==0 && stack[top-2].second<=pla ) top-=2;
            while(top>0 && stack[top-1].first==0) pla = max(pla,stack[--top].second);

            stack[top++] = {0,pla};
            // 其实就这
        }else if(f==1){ // 升序

在原版中，我是这么写的，但是答案确错了。 因为，两个while的顺序我写反了(会导致误判)。如“0 1 0 0”这种模式，使0、1交错的清况误判 正确示范：

    // 这样的呢
    for(int i=0; i<m; ++i){ // 我觉的这样初始化，非常完美
        int f,pla;
        cin>>f>>pla;
        if(f==0){ // 降序
            while(top>0 && stack[top-1].first==0) pla = max(pla,stack[--top].second);
            while(top>1 && stack[top-2].first==0 && stack[top-2].second<=pla ) top-=2;

            stack[top++] = {0,pla};
            // 其实就这
        }else if(f==1){ // 升序

*/

第二个超级抽象的地方就是下方 l<=r 这个必须要加，举个简答的例子（0-1、1-3）这两个区间段

#include <iostream>
#include <vector>
using namespace std;
const int N = 1e5+5;
pair<int,int> stack[N];

int main(){
    int top = 0;
    int n,m;
    cin>>n>>m;

    // 这样的呢
    for(int i=0; i<m; ++i){ // 我觉的这样初始化，非常完美
        int f,pla;
        cin>>f>>pla;
        if(f==0){ // 降序
            while(top>0 && stack[top-1].first==0) pla = max(pla,stack[--top].second);
            while(top>1 && stack[top-2].first==0 && stack[top-2].second<=pla ) top-=2;
            
            stack[top++] = {0,pla};
            // 其实就这
        }else if(f==1){ // 升序
            if(top==0) continue;
            while(top>0 && stack[top-1].first==1) pla = min(pla, stack[--top].second);
            while(top>1 && stack[top-2].first==1 && stack[top-2].second>=pla ) top-=2;

            stack[top++] = {1,pla};
        }
    }

    // 开始插
    vector<int> vec(n+1,0);
    int l = 1, r = n;
    int cnt = n;

    // 初次填充
    for(int i=0; i<top; ++i){
        while(stack[i].first==0 && stack[i].second<r && l<=r) vec[r--]=cnt--;
        while(stack[i].first==1 && stack[i].second>l && l<=r) vec[l++]=cnt--;
    }

    if(top!=0 && stack[top-1].first==0){
        while(l<=r) vec[l++]=cnt--;
    }else{
        while(l<=r) vec[r--]=cnt--;
    }

    for(int i=1; i<=n; ++i){
        cout<<vec[i]<<" ";
    }
    return 0;
}

最后一道题，哎，一言难进....

知识点：

1、蓝桥杯常考基础知识点：

数据类型与取值范围

• int类型 32 位系统中，占4个字节，取值范围是 -2^31 到 2^31-1。
• long类型 一般占8个字节，取值（18个整数左右）
• float类型 占4个字节，用于表示单精度浮点数，有一定的精度范围。
• double类型 占用8个字节，是双精度浮点数，精度更高（通常16~17个整数，long double 19个）

进制转换：

• 二进制、八进制、十进制、十六进制之间转换，其中十六进制，(十->二)可以使用除2取余法。将二进制转换为十六进制，可以每位4位一组转换。
• 位运算与进制之间的关系。如左移一位，相当于乘2

字符编码：

• ASCII码：是一种常见编码，通常由7位、8位二进制数表示一个二进制数表示一个字符。总共可以表示128个 or 256个。
• Unicode编码：为世界上几乎所有的字符都分配了一个唯一的数字编号，包括汉字、希腊字母、阿拉伯字母等各种字符集。常见的 Unicode 编码实现有 UTF-8、UTF-16 等，UTF-8 是一种可变长度的编码方式，它可以用 1 到 4 个字节来表示一个字符，能够很好地兼容 ASCII 码。

计算机存储单位换算

TB（太字节）、GB（吉字节）、MB、KB(千字节)、B、b；

b(1位、1bit)

B(1字节)

KB = 1024B

MB = 1024KB

时间单位换算

1 秒（s）= 1000 毫秒（ms），1 毫秒 = 1000 微秒（μs），1 微秒 = 1000 纳秒（ns）

2、基础数学知识

• 数论
  • 质数：判断一个数是否为质数、质数的筛选（如埃氏筛法、线性筛法）等。
  • 约数：求一个数的约数个数、约数之和，以及最大公约数和最小公倍数的计算方法，如辗转相除法。
  • 同余：同余的概念、性质，以及求解同余方程等。例如，在一些密码学相关的题目中，可能会用到同余的知识来进行加密和解密操作。
• 组合数学
  • 排列组合：计算排列数和组合数，解决一些与计数相关的问题，如在给定条件下的排列方式有多少种，或者从若干元素中选取部分元素的组合方法数等。
  • 鸽巢原理：用于解决一些存在性问题，例如证明在一定数量的物体分配到若干个集合中，必然存在某个集合满足特定条件。
  • 容斥原理：计算多个集合的并集元素个数，通过容斥原理可以避免重复计算，在一些复杂的计数问题中经常会用到。

3、概率论与统计学

• 概率计算：计算事件发生的概率，包括古典概型、条件概率、全概率公式等。例如，在一些抽奖、游戏等场景的题目中，需要运用概率知识来分析结果。
• 期望与方差：理解期望和方差的概念，能够计算随机变量的期望和方差，用于评估随机现象的平均水平和波动程度。

4、几何知识

• 平面几何：掌握点、线、面的相关性质和计算，如两点间距离公式、直线的斜率、三角形的面积、相似三角形的性质等。在一些图形处理、路径规划等类型的题目中会用到平面几何知识。
• 解析几何：将几何问题转化为代数问题进行求解，例如通过建立坐标系，利用直线方程、圆的方程等来解决相关问题。

5、离散数学

• 图论：图的基本概念，如顶点、边、度数、连通图等；图的遍历算法，如深度优先搜索（DFS）、广度优先搜索（BFS）；以及一些经典的图论算法，如最短路径算法（迪杰斯特拉算法、弗洛伊德算法）、最小生成树算法（普里姆算法、克鲁斯卡尔算法）等。图论在解决网络拓扑、路径规划、任务分配等问题中有着广泛的应用。
• 逻辑推理：命题逻辑、谓词逻辑的基本概念和推理规则，能够进行逻辑表达式的化简、证明以及逻辑推理问题的求解。在一些需要根据给定条件进行推理判断的题目中，逻辑推理能力是关键。

6、

O({log_{2}}^{n})

的时间奥秘

通常，他是用到分治法中的，每次区间减半。（如：二分查找）

假设有n个数值，n/2^k=1；

对数转化：2^k=n ::: k =

{log_{2}}^{n}

所以就是这么求log的时间复杂度的。