阳陂湖(国际)研学中心 XP02-1笔记
2025-08-15 16:29:42
发布于：浙江
XP02-1 Day01 模拟枚举、贪心：
1. 算法的特性：
1.1 有穷性
1.2 确定性
1.3 可行性
1.4 0个或多个输入多个
1.5 1个或多个输出
2. 执行次数称为语句频度,记为T(n)
3. 大O记法简化规则:
3.1 O(1)代表所有常数时间复杂度
3.2 修改后的时间频度函数T(n)
3.3 若最高阶系数存在且不是1，则删去该系数
4. 求时间复杂度:
4.1 构建一个有常数项,有非常数项的表达式
4.2 删掉常数项
4.3 保留最高阶
4.4 删掉最高阶的系数
5. 1s的运行次数约为10^8次(超过该上限后,代码会TLE!!!)
6. 前缀和数组:
前缀和是一个常见的算法技巧，用于快速计算数组中某个区间内元素的和
例如用pre[i]表示a数组中前i个数之和:
a = {3,4,1,3,2};
pre = {3,7,8,11,13};
pre[L-1] + sum(L,R) = pre[R]
sum(L,R) = pre[R] - pre[L-1]
pre[i] = pre[i-1] + a[i]
7.差分数组:
差分是一种数学运算方法，一维差分是指数列中相邻两项之间的差值
例如用d[i]表示a数组中第i个数与第i-1个数的差:
a = {3,4,1,3,2};
d = {3,1,-3,2,-1};
d[i] = a[i] - a[i-1]
d[i] + a[i - 1] = d[i]
将原数组a的第i~j项增加n时,差分数组d的第i项+n,第j+1项-n
XP02-1 Day02 二分查找：
1. 二分查找定义:
二分查找（Binary Search）是一种在有序数组中查找特定元素的算法,
通过分治策略将搜索范围逐步缩小至目标值。
其核心思想是将数组分为两半,i 比较中间元素与目标值的大小,f
根据比较结果选择继续在左半部分或右半部分查找,
每次操作都将搜索范围减半。
2. 二分查找步骤(通过不断缩小搜索范围,直到找到目标元素或搜索范围为空)
(1)初始化左右边界left和right;
(2)计算中间位置mid = (left + right) / 2；
(3)当左边界小于等于右边界时,执行以下操作:
(a)中间元素等于目标元素,则查找成功;
(b)如果中间元素小于目标元素,则更新左边界为mid+1
(c)如果中间元素大于目标元素,则更新右边界为mid-1e
3. 二分查找时间复杂度:
求n个有序的数,二分查找的复杂度:
看n除以多少次2为0
即看n除以___次2为1 + 1
为log n向下取整 + 1
时间复杂度1次可以忽略,所以二分查找的时间复杂度 = O(log n)
4. 代码实现二分查找:
int BinarySearch(int a[],int l,int r,int x){
while(l <= r){
int mid = (l + r) / 2;
if(x == a[mid]) return mid;
else if(a[mid] > x) r = mid - 1;
else if(a[mid] < x) l = mid + 1;
}
return -1;
}
5. 二分求下界:
5.1 下界:
在一个非降序列a[N]中查找x
(1)x存在 ==> 返回x首次出现的i
(2)x不存在 == > 则返回插入x后仍保持有序的起始位置
5.2 步骤:
假设表中元素是非降序排列
重复做:
(1) 得到中间元素mid
(2)将a[mid]与目标x比较:
a[mid] == x: 保存答案,往a[mid]左边找,更新右端点
a[mid] > x: 保存答案,往a[mid]左边找,更新右端点
a[mid] < x:往a[mid]右边找,更新左端点
5.3 实现:
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int a[N];
int lowerbound(int a[],int l,int r,int x){
int ans = r + 1;
while(l <= r){
int mid = (l + r) / 2;
if(x <= a[mid]){
ans = mid;
r = mid - 1;
}
else l = mid + 1;
}
return ans;
}
6. 二分求上界:
6.1 上界:
在一个非降序列a[N]中查找x
(1)x存在 ==> 返回x最后一次出现位置的下一个位置j
(2)x不存在 == > 则返回插入x后仍保持有序的起始位置
6.2 步骤:
假设表中元素是非降序排列
重复做:
(1) 得到中间元素mid
(2)将a[mid]与目标x比较:
a[mid] == x: 往a[mid]右边找,更新左端点
a[mid] > x: 保存答案,往a[mid]左边找,更新右端点
a[mid] < x:往a[mid]右边找,更新左端点
6.3 实现:
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int a[N];
int upper_bound(int a[],int l,int r,int x){
int ans = r + 1;
while(l <= r){
int mid = (l + r) / 2;
if(x < a[mid]){
ans = mid;
r = mid - 1;
}
else l = mid + 1;
}
return ans;
}
7. 若求上下界时,无满足条件数据,则返回N+1
8. STL二分算法:
8.1 lower_bound:
lower_bound使用二分查找算法来寻找序列中第一个大于或等于指定值的元素
该函数将返回一个指向该元素的地址
如果没有找到符合条件的元素,它将返回超出范围的位置
头文件:algorithm
lower_bound(a + 1,a + n + 1,x) - a;
tips:地址不建议直接输出如果要得到下标志、可以与首地址做差
8.2 upper_bound:
upper_bound使用二分查找算法来寻找序列中第一个大于指定值的元素
该函数将返回一个指向该元素的地址
如果没有找到符合条件的元素,它将返回超出范围的位置
头文件:algorithm
upper_bound(a + 1,a + n + 1,x) - a;
在a + 1 ~ a + n + 1范围内进行二分查找
9 计算x在有序序列中出现次数 = x的上届 - x 的下界
XP02-1 Day03 二分答案：
只要满足单调性、二段性即可使用二分方法。
T1 保护环境(题目链接：https://www.acgo.cn/problemset/info/43051?homeworkId=10850&teamCode=1898611936787804160)
方法1：枚举 枚举锯片高度的所有可能，从大到小检测，找到第一个砍得>=m的高度。
锯片高度的最大值：所有树的高度最大值；
锯片高度的最小值：0。
Check函数：
bool check(long long x) {
long long sum = 0; // 获得木材
for (int i = 1; i <= n; i++) { // 检查
if (a[i] > x) sum += a[i] - x;// 若树的高度<锯子的高度，则锯下来0
}
return sum >= m; // 若sum >= m返回真，否则返回假
}
时间复杂度：O(1015)，超时。
方法2：二分答案 求锯片的最大高度：
锯片越高，能砍得的木头总和越小；
锯片越低，能砍得的木头总和越大。
→具有单调性，可以使用二分答案。
参考代码：
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
int mx = 0;
int a[1000010] = {};
for (int i = 1; i <= n; i++) {
cin >> a[i];
mx = max(mx, a[i]);
}
int l = 0, r = mx, ans = 0;
while (l <= r) {
int mid = (l + r) / 2;
long long sum = 0;
for (int i = 1; i <= n; i++) {
int length;
if (a[i] >= mid) length = a[i] - mid;
else length = 0;
sum += length;
}
if (sum >= m) {
ans = mid;
l = mid + 1;
}
else r = mid - 1;
}
cout << ans;
return 0;
}
T2 光头强之单干☆( 题目链接：https://www.acgo.cn/problemset/info/41411?homeworkId=10850&teamCode=1898611936787804160）
方法1：枚举 枚举小段所有可能，从大到小检查，找到的第一个符合条件的即为答案。
Check函数：
bool check(int x) {
long long cnt = 0;
for (int i = 1; i <= n; i++) cnt += a[i] / x;
return cnt >= m;
}
方法2：二分答案
参考代码：
#include <bits/stdc++.h>
using namespace std;
int main() {
long long n, m;
cin >> n >> m;
long long mx = 0;
long long a[n + 1] = {};
for (ll i = 1; i <= n; i++) {
cin >> a[i];
mx = max(mx, a[i]);
}
if (mx < m) {
cout << 0;
return 0;
}
long long l = 1, r = mx, ans = 0;
while (l <= r) {
ll mid = (l + r) / 2;
ll sum = 0;
for (ll i = 1; i <= n; i++) {
sum += a[i] / mid;
}
if (sum >= m) {
ans = mid;
l = mid + 1;
}
else r = mid - 1;
}
cout << ans;
return 0;
}
XP02-1 Day04 初赛专题：
1. 进制转化:
1.1 相关概念解释:
数 码: 进制中每一位上数的表示
十 进 制: 每一位可取 0~9 这十个数码,计数的基数为10,超过9须用多位数进行表示
二 进 制: 每一位可取 0~1 这两个数码,计数的基数为10,超过9须用多位数进行表示
八 进 制: 每一位可取 0~7 这八个数码,计数的基数为10,超过9须用多位数进行表示
十六进制: 每一位可取 09,AF 这十六个数码,计数的基数为10,超过9须用多位数进行表示
位 权: 进制中某一位上的"1"所表示的大小
1.2 K进制转十进制:
按位权展开法:将各个数码与它的权值相乘再相加
对于一个k进制数:小数点从右往左看,第i位的权值为k^i(i-1)
e.g. 1011.110(二进制) = 12^3 + 02^2 + 12^1 + 12^0 + 12^-1 + 12^-2 + 0*2^-3
1.3 十进制转K进制(K≠10):
整数部分:除基倒排余法,不断除以K,直到被除数为0,倒读余数即为所求进制下的该数
小数部分:循环乘法:乘K取整,小数部分积为0结束,结果正序排列
2. 前中后缀表达式:
2.1 相关概念解释:
中缀表达式 指运算符在操作数中间 e.g. a+b
前缀表达式(波兰式) 指一种没有括号的算是表达式 运算符在操作数前间 e.g. +a b
后缀表达式(逆波兰式) 指一种没有括号的算是表达式 运算符在操作数后间 e.g. a b+
2.2 中缀表达式转后缀表达式 :
e.g. 12 * (3 + 4) - 5 / 6
=((12 * (3 + 4)) -(5 / 6))
=((12 (3 4 +) *) - (5 6 /))
=12 3 4 + * 5 6 / -
2.3 中缀表达式转前缀表达式 :
e.g. a + b * c - ( d + e)
=((a + (b * c)) - ( d + e))
=((a + (* b c)) - (+ d e))
=(- + a * b c + d e)
=- + a * b c + d e
3. 原码反码补码:
3.1 意义: 原码反码补码是计算机存储一个具体数字的编码方式,
数值在计算机中是以补码的方式存储和运算
3.2 机器数&真值: 一个数在计算机中的二进制表示形式,叫做这个数的机器数
机器数是带符号的,它的最高位作为符号位:0表示正数,1表示负数
机器数对应的真正数被称为真值
3.2 原码:原码是计算机中对数字的二进制定点表示方法，在数值前面增加一位符号位
3.3 反码:正数的反码与原码相同,负数的反码为原码除符号位全部取反
3.4 补码:正数的补码与原码相同,负数的补码等于反码加一
4. 位运算:
4.1位运算的概念:
计算机中的所有数据(无论是整数,字符,浮点数等)都以二进制形式存储
例如,整数6在二进制中表示为110,位运算就是直接对这些二进制位进行操作
4.2 常见位运算:
1. 按位与 &
2. 按位或 |
3. 按位非 ~
4. 按位异或 ^
5. 按位左移 <<
6. 按位右移 >>
4.3 按位与 &:
按位与&的运算规则,将两个二进制数低位对齐,不足高位补零
对两个数字进行比较,只有当两个相应的二进制位都为1时,结果的相应位才会为1,其余为0
e.g. 7 & 10 = 2
0 1 1 1
& 1 0 1 0
---------------
0 0 1 0
4.4 按位或 |:
按位或|的运算规则,将两个二进制数低位对齐,不足高位补零
对两个数字进行比较,只有当两个相应的二进制位都为0时,结果的相应位才会为0,其余为1
e.g. 6 | 10 = 14
0 1 1 0
| 1 0 1 0
---------------
1 1 1 0
4.5 按位非 ~:
按位非~的运算规则,将一个二进制数每一位取反,即0变1,1变0
e.g ~6 = -7
~ 0 1 1 0
--------------------
1 0 0 1
对于非负整数X: ~X = -(X + 1) ~(-(X + 1)) = ~ -(X + 1) = X
4.6 按位异或 ^:
按位异或^的运算规则,将两个二进制数低位对齐,不足高位补零
对两个数字安慰进行比较,当两个数相同为0,不同为1
e.g. 5 ^ 9 = 12
0 0 1 0 1
| 0 1 0 0 1
---------------
0 1 1 0 0
4.7 按位右移 >>:
按位右移>>的运算规则,>> a就将二进制数右移a位,高位补零,低位丢弃
e.g. 9 >> 1 = 4
9 = 1001 --> 0100 = 4
4.8 按位左移 <<
按位左移 <<的运算规则,<< a就将二进制数左移a位,高位丢弃,低位补零
e.g. 1<< 1 = 2
1 = 1001 --> 0010 = 2
4.9 规律:
右移 : n >> m == n / 2 ^ m (整除)
左移 : n << m == n * 2 ^ m
6. 排列组合:
6.1 加法原理:
加法原理是分类计数原理,常用于排列组合中
具体是指做一件事情,完成它有n类方式:
第一类方式有M1种方法,第二类方式有M2种方法……第n类方式有Mn种方法,那么完成这件事情共有M1+M2+……+Mn种方法
6.2 乘法原理:
做一件事,完成它需要分成n个步骤,做第一 步有m1种不同的方法,做第二步有m2种不同的方法……做第n步有mn种不同的方法
那么完成这件事共有 N=m1×m2×m3×…×mn 种不同的方法。
6.3 排列的定义:
排列数公式就是从n个不同元素中,任取m(m≤n)个元素(被取出的元素各不相同),按照一定的顺序排成一列,叫做从n个不同元素中取出m个元素的一个排列
排列与元素的顺序有关,加法原理和乘法原理是排列和组合的基础
6.4 全排列:
若从n个数中选取n个,则被称为全排列
6.5 排列的不同可能性个数计算 :
从n个不同元素中,任取m(m≤n)个元素排列
A(n,m) = n! / (n -m)!(0!=1)
A(n,n) = n!(全排列)
e.g A(9,7) = 9! / (9 - 7) ! = 181440
A(3,3) = 3! = 6
6.6 组合的不同可能性个数计算 :
从n个不同元素中,任取m(m≤n)个元素组合
*****) = C(n,n - m) = n! / (n - m)!·m!
A(n,n) = *****) · A(m,m)
e.g C(9,7) = C(9,2) = 9! / 7! · 2! = 9 · 8 · 7! / 7! · 2! = 9 · 8 / 2 = 36
7.埃式筛法:
7.1 简介:
由希腊数学家埃拉托斯特尼所提出的一种检定素数的算法
用于求自然数N以内的全部素数
其思想是把不大于根号N以内的所有素数的倍数全部筛除,剩余的自然数就都是素数
7,2 代码实现:
#include <bits/stdc++.h>
using namespace std;
int main(){
int p[2000010] = {0};
p[1] = 1;
for(int i = 1;i <= sqrt(n);i++){
if(p[i] == 0){
for(int j = 2 * i;j <= n){
j++;
p[j] = 1;
}
}
}
int cnt = 0;
for(int i = 2;i <= n;i++){
if(p[i] == 0) cnt++
}
cout << cnt;
}
什么?!张文武不发笔记了?!他不发我发!(本帖由 @1234567890 赞助发出)
欢迎补充_
求推!
这里空空如也
有帮助，赞一个