07.19
1、Heap Paths
从根节点往下，值是单调的。
任务是检查完全二叉树的每条路径，检查这个数据结构是否是堆。
思想：
（1）把输入的值构造成一个完全二叉树。
（2）输出所有的路径，并判断是否是堆。
步骤：
（1）堆的创建。
参考二叉树，如果存储在数组中，按层存储。
头文件 #include <algorithm>
但是先用数组实现了
（2）判断是否是堆
计算叶子结点的个数，即为路径的总数
（思路：先找出来上一层满的有多少）
（3）补充：调整堆
AdjustHeap（）
- 数组实现：参考 https://blog.csdn.net/ahfytao/article/details/47681221
思路：循环+递归，排序
（4）补充：堆的应用：插入一个元素/删除最大的元素
卡在：不知道如何判断有多少条路径
不知道如何按次序输出子节点
参考别人的答案
https://www.liuchuo.net/archives/8027
不知道如何按次序输出子节点:解决：算法 先序遍历的镜像
不知道如何判断有多少条路径：也不用判断，先序遍历输出即可。
07.21
0、dfs
回溯法
考察点：dfs
#include <iostream>
#include <vector>
using namespace std;
vector<int> v;
int a[1009], n, isMin = 1, isMax = 1; //两个标志为，最后最多只有一个为1.
//a[]大小设为1001即可，因为a[0]一般不存储结点，从a[1]开始存储。
void dfs(int index) { //根据index，表示这个index结构下面的都会被调用了
if (index * 2 > n && index * 2 + 1 > n) { //检查是否到最下面了，如果到了就输出
if (index <= n) { //这个用来判断是不是空的某个子节点也进来了
for (int i = 0; i < v.size(); i++)
printf("%d%s", v[i], i != v.size() - 1 ? " " : "\n"); //v[i]是按照节点在栈中排序了的，如果i输出的这个节点不是最后的根结点，就输出空格，如果是最后的，就输出换行
}
} else {
v.push_back(a[index * 2 + 1]); //如果不是到最下面了，就先右边，再左边（根据题目来的）
dfs(index * 2 + 1);
v.pop_back();
v.push_back(a[index * 2]);
dfs(index * 2);
v.pop_back();
}
}
int main() {
cin >> n;
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]); //输入
v.push_back(a[1]); 首先把a[1]入栈
dfs(1); //调用了这一句，其他就都会递归调用了。
for (int i = 2; i <= n; i++) {
if (a[i/2] > a[i]) isMin = 0; //从否定的方面来判断标志位
if (a[i/2] < a[i]) isMax = 0;
}
if (isMin == 1)
printf("Min Heap");
else
printf("%s", isMax == 1 ? "Max Heap" : "Not Heap");
return 0;
}
收获：
（1）长度一般固定一个最大值，N+1即可
（2）dfs下标一般从1开始
（3）变量一般设置为全局变量，好调用
（4）main函数调用一次即可，dfs函数中，先判断是否要输出，如果不输出，把自己的左子树和右子树递归调用。调用的规格是：push,dfs,pop
（5）可能有种特殊情况，只有左子树，但是把空的右子树也调用进去了。这种只会在栈中有变化，输出的时候判断不满足边界条件就不输出它了。
（6）判断边界：
- 检查是否是叶子结点：
index * 2 > n && index * 2 + 1 > n
如果成立的话，就是叶子结点，输出它。如果不成立，再递归调用左子树和右子树。 - 检查是否是空的右子树：
index <= n
如果满足条件的话，是真实存在的结点，如果不满足条件，说明这个是空了的结点。
1、Vertex Coloring
顶点着色，相邻的点颜色不同。需要做的是：检查它给出的情况是否满足每条边的两个顶点颜色不同。
- 需要用到set。其中的元素是有序且不重复的。用set统计颜色的数目。
#include <iostream>
#include <vector> //栈结构，用来存边对应的两个结点。这里不突出栈结构，只是用来存放
#include <set>//可以直接排序，并且不重复
using namespace std;
struct node { int t1, t2; }; //每条边对应的两个结点的结构
int main() {
int n, m, k, i;
cin >> n >> m;
vector<node> v(m);
for (i = 0; i < m; i++) cin >> v[i].t1 >> v[i].t2; //输入边对应的结点的信息
cin >> k;
while (k--) {
int color[10009] = { 0 }; //由于边数最多是10000，所以颜色应该不会超过这个数
bool flag = true;
set<int> se;
for (i = 0; i < n; i++) {
cin >> color[i]; //输入颜色
se.insert(color[i]); //有序排列
}
for (i = 0; i < m; i++) {
if (color[v[i].t1] == color[v[i].t2]) { //如果结点对应的颜色相同，就break
flag = false;
break;
}
}
if (flag)
printf("%d-coloring\n", se.size());
else
printf("No\n");
}
return 0;
}
收获：
（1）set可以用来排序。
（2）先用栈结构来存边信息，再用数组来存储每个节点的颜色。
（3）在数组中比较每个两节点的颜色是否相同，用一个标记为flag来标记结果。
2、battle over cities
猜测应该考察图的知识，并且有权重。
07.27
1、前置题---battle over cities
把 “需要维修多少个地铁” 这个问题转换成 “需要多少次 dfs 才能遍历完整个图”。
#include <iostream>
#include <string.h>
using namespace std;
#define maxn 1001
// 变量定义
int total_cities, highways, check_cities; // 总城市 城市之间的地铁 被检查的城市
bool highway_map[maxn][maxn]; // 定义地铁地图
int check_list[maxn]; // 定义检查列表用于存储检查的城市
bool checked_cities[maxn]; // 判断是否检查过这个城市
// 定义方法递归实现 dfs 遍历节点
void CheckHighway(int source_city) {
// 没查看过就标记为已查看
checked_cities[source_city] = true;
// 查看当前城市连接的城市
for (int i = 1; i <= total_cities; ++i) {
// 若该城市没被检查过（缩短递归次数）并且 含有该城市
if (!checked_cities[i] && highway_map[source_city][i])
CheckHighway(i); //可以实现深度优先搜索。只要是和这个城市相连的并且没有被检查过，就检查它。并递归调用检查它的节点。
}
}
int main() {
// 初始化变量
scanf("%d%d%d", &total_cities, &highways, &check_cities);
for (int i = 0; i < highways; ++i) { // 构建城市地铁图
int source_city, aim_city; // 定义变量接收 源城市 目标城市
scanf("%d%d", &source_city, &aim_city);
highway_map[source_city][aim_city] = true; // 将两个城市对应的值均设置为 true，表示两城市是连通的
highway_map[aim_city][source_city] = true;
}
for (int i = 0; i < check_cities; ++i) { // 构建检查城市列表
scanf("%d", &check_list[i]);
}
// 计算需要维修公路的数量
int times = 0; // 计算需要维修多少条公路
for (int i = 0; i < check_cities; ++i) { // 根据需要检查的城市数量检查城市
times = 0;
memset(checked_cities, false, sizeof(checked_cities)); // 初始化已检查过的城市为 false
checked_cities[check_list[i]] = true; // 将被掠夺的城市设置为 true
for (int j = 1; j <= total_cities; ++j) {
if(!checked_cities[j]){ //只要有城市没检查，就说明有分离的城市了，需要修建一条路
times++;
CheckHighway(j); //把与这条城市想通的所有的城市都遍历了。没遍历的说明不相连，需要新修建一条路。
}
}
printf("%d\n", times-1);
}
return 0;
}
再做这道题的hard版
带了权重，需要测试丢失掉每个城市之后，再把图连接起来需要的费用。
方法1:最小生成树
最小生成树有一个Prime算法
用到的头文件 iostream vector
arc是cost矩阵，用来记录开销。首先置为大数。然后赋值。如果路是好的，不用修，开销置为0.如果路是坏的，就记录开销。
#include<iostream>
#include<vector>
#pragma warning(disable:4996)
using namespace std;
int N, M, s_max = 0;
//定义需要的N，M，
vector<int> re;
int arc[505][505];
vector<int> x;
vector<int> te;
void ins(int t)
{
for (int i = 1;i <= N;i++)
if (i != t) x.push_back(i); //要删除的顶点时t，把除了t之外的所有顶点入栈于x中。
}
int main()
{
for (int t = 0;t < 505;t++)
for (int i = 0;i < 505;i++)
arc[t][i] = 0x3f3f3f3f; //把arc置为一个很大的值，然后再更新。值很大说明这条路修不了。
cin >> N >> M;
while (M--)
{
int a, b, c, d;
scanf("%d %d %d %d", &a, &b, &c, &d);
if (d) arc[a][b] = arc[b][a] = 0; //如果d是1，说明这条路本来就是通的，那么就不需要修建它，花费就是0.
else arc[a][b] = arc[b][a] = c; //如果d是0，更新他的花费是c
}
for (int t = 1;t <= N;t++) //t分别对每个节点都进行操作
{
x.clear(); //x中存放的是除了当前节点的所有节点。
te.assign(N + 1, -1);
ins(t);
int f = x.back(); //f是先从所有的节点中选取出来一个节点。（可以随机选择）
x.pop_back(); //把它删掉
for (int i = 0;i < x.size();i++)//初始化
te[x[i]] = arc[f][x[i]]; //把 “当前选中的节点” 连接 “剩下的节点” 需要的cost 存储在te中。te是初始的花费，后面会进行更新。
int eff = 0;
while (!x.empty())//最小生成树 //如果x还没有空掉
{
int min_s = 0x3f3f3f3f;int v = 0;
for (int i = 0;i < x.size();i++)
{
if (min_s > te[x[i]]) // 根据当前的节点，确定下一个最小路径
{
min_s = te[x[i]];
v = i;
}
}
if (min_s == 0x3f3f3f3f) { eff = min_s;break; } //如果这个点与其他的点都是孤立的，那么off = 0x3f3f3f3f,这个很大的值。
eff += min_s; //eff加上刚才的这个最小的路径。
int ttt=x[v]; //ttt是我找到的下一个顶点
x.erase(x.begin() + v); //把下一个顶点从x中删除
v = ttt;
for (int i = 0;i < x.size();i++)
if (arc[v][x[i]] < te[x[i]]) //te中存放的应该是最小的边信息
te[x[i]] = arc[v][x[i]];
//这一步太妙了。te中存放的是目前为止到x[i]这个点的最小边信息。
//是已经发生过的统计量。新加入顶点后，可能边的权重比原来的大，
//如果大，就不更新了，用原来的边。如果比原来的权重小，就进行更新。
//这样就能保证te中存放的一直是最小的路径。
}
if (eff> s_max) //每一个顶点完了之后，更新s_max。
//如果更新了，说明有了比刚才更大的值，也就是有了更重要的点。需要把之前的清空，放入这个点。
{
s_max = eff;
re.clear();
re.push_back(t);
}
else if (eff == s_max)
re.push_back(t);
//如果两个点同等重要，就都入栈。
}
if (s_max == 0 && re.size() == N) {
//如果去除一个点之后，剩下的cost为0，也就是说剩下的点还都是连通的，那么就输出0，这是特殊情况。
cout << 0 << endl;exit(0);
}
cout << re[0];
for (int t = 1;t < re.size();t++)
cout << " " << re[t];
cout << endl;
//因为进入的时候本来就排好序了，所以如果需要输出的话，按序输出即可。
}
思路：
输入arc矩阵/从一个顶点开始/其余顶点入栈/找到当前顶点的最小边/最小边信息保存在te中/找到下一个顶点/找到下一个最小边/更新cost/看情况更新te/直到所有的顶点都计算过了。
这道题考查的点还挺多的，思路也比较复杂，很棒！
07.28
1、Business
需要考虑花费的时间、ddl、收益。
其实是01背包问题，但是没有给出数据明确的范围。用map。
对动态规划/背包问题还不够熟练，先看一些例题。
参考《王道》第七章——动态规划
（1）递归求解
上楼梯问题
相当于把所有的解通过递归方式都求出来了。重点是递推关系的确定。
稍难一点，n封信装错信封，都装错了，共有几种方式？
用数学里面的排序思想求阶乘就可以。但是这种考虑的不全面，没有考虑到两两互换的情况。
排错公式：F[n] = (n - 1) * F[n - 1] + (n - 1) * F[n - 2]。
最重要的是：求得递推关系式
（2）最长递增子序列（LIS）
用F(i)代表：若序列以ai结尾时：最长子序列的长度
题目：拦截导弹
#include <stdio.h>
int F[26] = {1};
int high[26] = {0};
int main () {
int k = 0,i = 0,j=0;
scanf("%d",&k);
for(i=1;i<=k;i++){
scanf("%d",&high[i]);
}
F[1]= 1;
for(i=2;i<=k;i++){
for(j=1;j<i;j++){
if(high[j]>=high[i] && (F[j] + 1 > F[i])){
F[i] = F[j] + 1;
}
}
}
printf("%d",F[k]);
return 0;
}
给出的答案通过一个max函数
for (int j = 1;j < i;j ++) { //遍历其前所有导弹高度
if (list[j] >= list[i]) { //若j号导弹不比当前导弹低
tmax = max(tmax,dp[j] + 1); //将当前导弹排列在以j号导弹结尾 的最长不增子序列之后，计算其长度dp[j] + 1,若大于当前最大值，则更新最大值
} }
其中dp存储的是 以当前的i结尾，最长子序列的长度。结束后再从里面找出最大的值。
所以自己原来的程序最后少了一步，应该再把F的结果进行比较，找出最大的值才是最长子序列。刚才输出结果正确知识巧合。
（3）最长公共子序列
例题：输入两个字符串，长度都不超过100。输出最长子序列的长度（数字）即可。
收获：
字符串需要用到头文件 #include <string.h>
字符串用 char S[101]存储
while (scanf("%s%s",S1,S2) != EOF) 就会导致循环输入
求字符串的长度，用的是strlen()函数直接求了。
因为字符串数组下标从0开始，所以第i 个字符位置为S1[i-1],表示当前两个字符
循环也是从i开始，for i ,内嵌for j 。由于用到的j也都是之前的，所以这样循环是可以的，不会用到没定义的数据。
最后不需要再比较大小了，只用输出最末尾的数据即可。
（4）状态与状态转移方程---统一思路
之前的笔记
###2、动态规划
最后数值可能较大，存放的数组用long long型
* 后面的结果可能和前两次有关，重点是如何写出正确的逻辑公式。
* 最长递增子序列 LIS
* 最长公共子序列 LCS
if (S1[i - 1] != S2[j - 1]) //因为字符串数组下标从0开始，所以第i 个字符位置为S1[i-1],若当前两个字符不相等
dp[i][j] = max(dp[i][j - 1],dp[i - 1][j]); //dp[i][j]为 dp[i][j - 1] 和 dp[i - 1][j]中较大的一个
else
dp[i][j] = dp[i - 1][j - 1] + 1; //若它们相等，则dp[i][j] 比dp[i - 1][j - 1]再加一
https://pintia.cn/problem-sets/994805342720868352/problems/type/7?page=1
============================================
