笔记简单的汇总

原题链接：32737.Xmy

1943

2025-07-28 16:37:21

发布于：江苏

81阅读

0回复

0点赞

7.28 树与图

node
结点的度: 子树的数量
树的度：最大结点的度
叶子结点：度为0的结点
分支结点：度不为0的结点
树的高度：最大层数（1开始或者0开始）

父亲表示法： tree[i]表示i的父节点
孩子表示法：

二叉树：
性质1：二叉树的第k层上，最多有2^(k-1)个结点

性质2：二叉树的前k层最多一共有2^k-1个结点
等比数列求和公式： a1(1-q^n)/(1-q)
拓展：三叉树的前k层最多一共有(3^k-1)/2

性质3：n0 = n2 + 1, n0表示度为0的结点(叶子节点)
点的关系：n = n0+n1+n2; （总的结点数量）
边的关系：n-1 = 2n2 + n1
合并推导：n0 + n1 + n2 = 2n2 + n1 +1 =>性质3

满二叉树一定是完全二叉树，但是完全二叉树不一定是满二叉树

性质4：
具有n个结点的完全二叉树的深度是floor(log(n))+1;

性质5：
完全二叉树中结点编号为i的父节点是i/2，其左孩子为2i, 右孩子为2i+1

二叉树的遍历：
1.先序遍历：根左右
2.中序遍历：左根右
3.后序遍历：左右根

无向完全图: n*(n-1)/2 条边

有向完全图: n*(n-1) 条边

稀疏图：点多边少
稠密图：点少边多

7.25初赛知识点

一、进制转换

1. k进制转换十进制：

按权展开

2. 十进制转k进制：

整数部分： 短除法，k（逆序） 
小数部分： 循环乘，k（正序）

3. 两个小特殊

1）. 16进制与2进制的互转，每4位二进制可以变为1位十六进制，不足补0 
eg1: 269(16) 
0010 0110 1001
2）. 8进制与2进制的互转，每3位二进制可以变为1位八进制，不足补0 
eg2: 1151(8) 
001 001 101 001

eg3:
10101101010101(2)
(16)
(8)

二、前中后缀表达式

单目运算符： i++, --i, !0, ~
双目运算符： &&
三目运算符： (a>b)?(a):(b)

中缀转后缀

三、原码，反码，补码

任何数字在计算机中的存储形式都是{补码}
1: 1001
正数的原码、反码、补码全部相同

原码：真值码
反码：符号位不变，其余位取反
补码: 反码+1
（-1）（int/32bit）
原码：1000 0000 0000 0000 0000 0000 0000 0001
反码：1111 1111 1111 1111 1111 1111 1111 1110
补码：1111 1111 1111 1111 1111 1111 1111 1111

-13：
原码：1000 ... 1101
反码：1111 ... 0010
补码：1111 ... 0011

/*
1 Byte = 8 bit （比特位） 
Byte: 基本单位alc 
bit: 比特, 最小单位

1 KB = 1024 Byte
1 MB = 1024 KB
1 GB = 1024 MB
1 TB = 1024 GB
... 

int
0000 0000 0000 0000 0000 0000 0000 0001
最高位为符号位，0表示正数， 1表示负数 

（-1） 
1000 0000 0000 0000 0000 0000 0000 0001
*/

逻辑运算符
逻辑与 &&
逻辑或 ||
逻辑非 !

位运算符：
1.按位与: &
2.按位或: |
3.按位左移: <<
左移x位：将原来的数放大2^(x)倍
4.按位右移: >>
右移x位：将原来的数缩小2^(x)倍
5.按位异或: ^
6.按位取反: ~

按位与、按位或
转换为二进制之后进行计算， &表示必须两个同时成立， |表示只要成立一个
按位异或:
可以理解为不带进位的加法或者减法
按位取反: ~
int a = 6;
cout << (~a) << endl; //-7
cout << (~9) << endl;
cout << (~10) << endl;
cout << (~(-6)) << endl; //5
取反公式：~n = -(n+1)

四、排列组合

排列与顺序有关，组合与顺序无关

特殊优先
分步乘法，分类加法
捆绑和插空
全排列的情况
排除法
隔板法

7.24 二分答案

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

const int N=2e5+5;
int n,a[N], b[N];
long long m;

bool check(int x){ //可以凑成x套卡牌
    long long sum = 0;
    for (int i=1; i<=n; i++){
    	// x - a[i] 是需要补卡的数量 
        if (x - a[i] > b[i]) return 0;
        else  sum += max(0, x-a[i]); //也可能不需要补牌
    }
    return sum <= m;
}

int upper_ans(long long l, long long r){
    int ans = 0;
    while (l <= r){
        long long mid = l+r>>1;
        //按照mid的套数看下需要补卡多少张 
        if (check(mid)) {
            ans = mid;
            l = mid + 1;
        }
        else r = mid - 1;
    }
    return ans;
}

int main() {
	cin>>n>>m;
    int l = 1e9, r = 0;	//最少的套数和最多的套数 
    for (int i=1; i<=n; i++) {
        cin>>a[i];
        l = min(l, a[i]);
    }
    for (int i=1; i<=n; i++){
        cin >> b[i];
        r = max(r, a[i]+b[i]);
    }
    cout << upper_ans(l, r);
    
	return 0;
}

7.23 二分查找

有帮助，赞一个

去预览

0/2000

全部评论 1

zsy（禁言中，勿扰）

#include<bits/stdc++.h>
using namespace std;
int n,a[200010],b[200010];
long long m;
bool check(int x){
    long long sum=0;
    for(int i=0;i<n;i++){
        if(x-a[i]>b[i]){
            return 0;
        }else{
            sum+=max(0,x-a[i]);
        }
    }
    return sum<=m;
}
int upper_ans(int l,int r){
    int ans=0;
    while(l<=r){
        long long mid=l+r>>1;
        if(check(mid)!=0){
            ans=mid;
            l=mid+1;
        }else{
            r=mid-1;
        }
    }
    return ans;
}
int main(){
    cin>>n>>m;
    int l=1e9,r=0;
    for(int i=0;i<n;i++){
        cin>>a[i];
        l=min(l,a[i]);
    }
    for(int i=0;i<n;i++){
        cin>>b[i];
        r=max(r,a[i]+b[i]);
    }
    cout<<upper_ans(l,r);
    return 0;
}