学习内容：线性技巧，二分，贪心，搜索，dp，数学，图论
线性技巧：
了解什么是线性？
线性指的是数组这样一对一的操作
实在很难讲，所以拿例题砍竹子举例
这道题的大致思路：
最后的高度都要砍成 1 我们可以开一个二维数组，从下往上放，最下面一层统一赋值为 1 最上面那一层放输入进来的 h_i 中间放每根柱子每次操作后的高度，这个数组放好以后，从最上面一层开始遍历每一行有几节，cnt+=每行的节数最后输出cnt。
AC code：
#include<bits/stdc++.h>
using namespace std;
int cnt;
#define LL long long
int h[10000005];
long long b[7][200005];
//定义数组
void init()
{
int n;
cin>>n;
vector<vector<LL>> tmp(n+1,vector<LL>(7, 0));
for(int i=1;i<=n;i++)
{
LL a;
cin>>a;
stack<LL> q; //这里用栈来模拟刚刚说的过程
while(a>1)
{
q.push(a);
a=a/2+1;
a=sqrt(a); //a自己入栈，每次操作后的a入栈，最后都是1所以1不用入栈
}
int index=0;
while(q.size())
{
tmp[i][index++]=q.top();
q.pop();
}// 很像bfs，是把操作步骤，形成一个表，刚刚说的表
}
int res=0;
for(int i=0;i<=6;i++)
{
for(int j=1;j<=n;j++)
{
if(tmp[j][i] and tmp[j][i]!=tmp[j-1][i]) res++;
}
}
cout<<res<<'\n';
//数有多少接并输出
}
int main()
{
init();
return 0;
}
贪心
贪心是一种算法
这个算法如字面意思，比如你有一个包，你要装东西，你能装就装。
这个算法是需要证明的，一旦举出反例就不能用此算法
拿例题小埋公司的IPO方案举例
思路
贪心往往需要排序，这里可以用结构体，但是需要写cmp，也可以使用pair数组
每个pair能存两个东西，分别用name.first和name.second访问
再写sort，同样要cmp但是简单 A_i 从大到小排序 B_i 在 A_i 一样的时候从小到大排，排序好后把前 k 个的 A_i 加起来输出搞定！
AC code：
#include<bits/stdc++.h>
using namespace std;
const int N=150005;
int n,k;
long long w;
pair<int,int> pr[N]; //定义pair数组
int main()
{
cin>>n>>w>>k;
for(int i=1;i<=n;i++)
{
cin>>pr[i].second>>pr[i].first;
}
sort(pr+1,pr+1+n);
priority_queue<pair<int,int>> hq; //这里用优先队列存储，自动排序
int p=1;
while(k--)
{
while(p<=n and pr[p].first<=w) //判断当前的资本能不能启动这个项目
{
hq.push(make_pair(pr[p].second,pr[p].first));
p++;
}
if(hq.empty()) break; //空了跳出（题目没说n>=k）
auto tmp=hq.top(); //去队头+丢队头
hq.pop();
w+=tmp.first; //全部加起来
}
cout<<w<<endl;
return 0;
}
二分
也是一种算法，最简单的例子
在1~100之间猜数字，我最多7次保证才到
先猜50，如果大了，区间更新为1~50
如果小了区间更新为51~100
再猜中间的
2^7 是128比100大肯定能猜到
都不用拿例题举例其实是本人累了、
但是有些时候二分不一定是枚举数据，而是枚举数之间的间距，数的个数……
搜索
又是搜索算法2写到普及3唯一一次努力写完的
dfs
一条路走到底，要么出口要么死路，出口结束程序，思路返回到上一个分叉口，极其暴力时间复杂度 O(2)
bfs
遇到分叉口，有多少个分叉，分身出多少人，最先走到终点的那个人一定是最短路径，我觉得bfs的优点是速度快和一下就能找到最短路径（这是dfs没有的），缺点是没法统计路径数量（dfs的优点）
有很多例题拿小埋排列序列举例
思路：
一层一层搜（dfs）这个数选好了下一个数，第一个数出来了第二个是（有方法保证比第一个大），所以还要一个计数器，记录这是第几大的当他=k的时候输出
AC code
#include<bits/stdc++.h>
using namespace std;
int n,k,ans[1000005],vis[1000005];
int cnt;
void dfs(int s)
{
if(s>n){
cnt++;
if(cnt==k)
for(int i=1;i<=n;i++) cout<<ans[i];
return;
}
for(int i=1;i<=n;i++)
{
if(vis[i]) continue;
vis[i]=1;
ans[s]=i;
dfs(s+1);
vis[i]=0;
}
}
void solve()
{
cin>>n>>k;
dfs(1);
}
int main()
{
solve();
return 0;
}
