X03-2班笔记
2024-08-20 16:08:34
发布于：广东
拓扑排序
拓扑排序要解决的问题是给一个有向无环图的所有节点排序。
一个有向无环图的拓扑排序可能不唯一
每次排序入度为0的节点，更新与之相连的结点入度，后面没记上 好像是直到排序完成
运算符优先级
1.*
2.%
1.++,--
2.<<,>>
3.&
4.^(异或)
5.|
6.&&
7.||
十进制小数转二进制
乘2取整，整数部分正序排列
e.g.
(0.25)10 = (?)2
0.25 x 2 = 0.5 ...... 0
0.5 x 2 = 1 ...... 1
so,(0.25)10 = (0.01)2
文件读写
freopen(const char *filename,const char*mode,FILE *stream)
filename:要打开的文件名。mode:打开文件的模式，可以是"w","r","a"......stream:要重新定向的流，可以是stdin,stdout当然也可以用自定义文件指针
"等下。。。有ofstream我用freopen干嘛"
"c"[1]
对拍
"对拍" 是一种测试算法或程序的方法。它的基本思想是使用两个或多个不同的算法对相同的输入进行运算，然后检查输出是否一致。
- 运行第一种算法，输出到1.out
- 运行第二种算法，输出到2.out
- 比较1.out和2.out是否相同，不相同就退出
- 更换输入，继续循环
#include<bits/stdc++.h>
using namespace std;
bool work(){
//1.生成数据
ofstream fout("1.in");
fout << (rand() % 10000);
fout.close();//记得关！！！
//2.运行两个程序
system("1.exe");
system("2.exe");//要先把两个程序编译,确保输入文件名称
return system("fc 1.out 2.out");//要先确保输出的是哪个文件
//3.比较
}
int main(){
srand(time(0));//设置种子
for(int i = 0;i < n;i++){
if(!work()){
cout << "woc崩了";
break;
}
}
}
动态规划
动态规划是一种表格处理法，或记忆递归法，在对问题求解时，通过把原问题分解为相对简单的子问题的方式求解复杂问题的一种方法。
拿一道非常神奇甚至没法贪心的找零题来：
原题链接（2024集训营的）
这道题直接贪心会这样：
比如找15钱，贪心先拿11，后面拿4张1 。
但实际上可以直接拿3张5钱 。
但使用动态规划：
来打个表——
| 0元 | 1元 | 2元 | ... | 5元 |
|---|---|---|---|---|
| 0张 | 1张 | 2张 | ... | ?张 |
此时5元和0元，4元相关联
在四张上加，要5张
而从0元上加，只要一张
所以这里的结果是——
| 5元 |
|---|
| 1张 |
动态规划的特点
- 无后效性，一个状态阶段不被未来的状态影响
- 最优子结构，比如将此题的
f(i)划分为f(i - 1),f(i - 5),f(i - 11),则需先知道它们的答案才能得出f(i)。 - 子问题重叠，
不想记了
最后是这题的递推AC代码 （虽然你们也交不了）
火了我就发题面
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;cin >> n;
vector<int> dp(n + 1);
for(int i = 1;i <= n;i++){
dp[i] = dp[i - 1] + 1; //凑出i - 1状态下再加1元的状态
if(i >= 5/*防止RE*/) dp[i] = min(dp[i],dp[i - 5] + 1);// 凑出i - 5状态下再加5元的状态,与上一个答案作比较
if(i >= 11/*防止RE x 2*/) dp[i] = min(dp[i],dp[i - 11] + 1);// 凑出i - 11状态下再加11元的状态,与上一个答案作比较
}
cout << dp[n];//输出答案
//时间复杂度：O(n)
//递推式。。。算了懒得写了
}
又有一题
打表，习惯了......
| 编号 | 能力 | 最长长度 |
|---|---|---|
| 1 | 1 | 1(第一个，没得递推) |
| 2 | 5 | 1 |
| 3 | 3 | 2 |
| 4 | 4 | 2 |
| 5 | 6 | 2,3,3,4->4 |
| 6 | 9 | 2,3,3,4,5->5 |
| 7 | 7 | 2,3,3,4,5->5 |
| 8 | 8 | 2,3,3,4,5,6->6 |
得出结果：
那么这个过程用代码复现就是——
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;cin >> n;
vector<int> d(n + 1);
vector<int> dp(n + 1,1);
for(int i = 1;i <= n;i++){
cin >> d[i];
}
int maxm = 0;
for(int i = 2;i <= n;i++){
for(int j = 1;j < i;j++){
if(d[j] <= d[i]) dp[i] = max(dp[i],dp[j] + 1);
}
maxm = max(dp[i],maxm);
}
cout << maxm;
}
然后，又是一题。。。。。。
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;cin >> n;
vector<int> d(n + 1);
vector<int> dp(n + 1,1);
for(int i = 1;i <= n;i++){
cin >> d[i];
}
int maxm = 0;
for(int i = 2;i <= n;i++){
for(int j = 1;j < i;j++){
if(d[j] <= d[i]) dp[i] = max(dp[i],dp[j] + 1);
}
maxm = max(dp[i],maxm);
}
cout << maxm;
}
当然，还有。
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;cin >> n;
vector<int> h(n);
for(int i = 0;i < n;i++){
cin >> h[i];
}
vector<int> a(n),b(n),team;
//a[i]表示第i个人作为结尾上升的最大长度，b[i]表示第i个人作为结尾下降的最大长度
//team存储上升最长
for(int i = 0;i < n;i++){
int pos = lower_bound(team.begin(),team.end(),h[i]) - team.begin();
if(pos == team.size())team.push_back(h[i]);//最大，站在前一个学生后面
else team[pos] = h[i];//替换较矮的学生
a[i] = team.size();
}
vector<int> y;
for(int i = n - 1;i >= 0;i--){
//找第一个大于等于h[i]的身高
int pos = lower_bound(y.begin(),y.end(),h[i]) - y.begin();
if(pos == y.size())y.push_back(h[i]);
else y[pos] = h[i];
b[i] = y.size();
}
int maxi = 0;
for(int i = 0;i < n;i++){
maxi = max(maxi,a[i] + b[i] - 1);
}
cout << n - maxi;
}
又来。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
树的存储方式
- 双亲存储法(父亲存储法)
- 孩子存储法
- 树的邻接表存储法
双亲存储法
利用树中除根节点外，每个节点都有唯一的父节点的性质。
const int N = 10;
struct Node{
int data,parent;
} tree[N];
tree[i].parent表示编号为i的树节点的父亲.
孩子存储法
每个节点存储自己孩子的位置信息，可以使用vector存储。
const int N = 10;
struct Node{
int data;
vector<int> child;
} tree[N];
tree[i].chile 存储着结点i的孩子的位置信息。
邻接表存储法
邻接表主要是记录一个顶点的邻接点和邻接边信息的结构。
若含有边权，数据节点中增加权重w。
树的直径
树的直径定义为树中最远的两个节点之间的距离。
表达逝树
表达逝树是一种特殊的树，它的非叶结点是操作符，叶节点是操作数。
因为操作符的操作一般为两个，所以表达式树多为二叉树。
老师说用不了这俩。。。joker ↩︎
全部评论 3
顶！
顶！
顶！
顶！
顶！顶！顶！顶！顶！顶！顶！顶！顶！顶！顶！顶！顶！顶！顶！顶！顶！顶！顶！顶！顶！顶！顶！顶！顶！顶！顶！顶！顶！顶！顶！顶！顶！顶！顶！顶！顶！顶！顶！顶！顶！2024-08-20 来自 广东
0
有帮助，赞一个