食用注意事项：部分代码并未经过编译请以编译后为准，由于我的输入法有非常大的问题，可能在部分位置出现了奇奇怪怪的字符，请告知我更改，非常感谢，如果有没有写全的地方也可以提供学术支持，我会将您的名字放在感谢版里。

算法不好就背板子。

猫类的初赛笔记……

Day1萌萌STL

讲的是set和map还有一大堆的函数/kk

说实话set&map之前在xes听过一次怎么感觉讲的完全是俩个东西哇而且我们xes完全没有讲过auto这种高级的东西哇。

mapmap 我们定义一个map<string,int> 插入：insert() 比如说

mp.insert({"xiaoming",20});
mp.insert(make_pair("xiaobei",15);
mp.["xiaotian"]=10;

元素访问

1.下标访问法 cout<<mp["xiaoming"]<<endl; 自动插值的特性：mp["beibei"]你没有给它赋值的话就有一个随机定值比如(beibei,0)

2.atat访问法 cout<<mp.at("xiaobei")<<endl;

3.find访问

mp.find("xiaotian");
auto it=mp.find();//科普一下auto
//aoto会自动匹配数据类型。
if(it!=mp.end()) //find函数找不到时返回end()
  cout<<"键（下标）"<<it.first()<<endl;
  cout<<"值："<<it.second()<<endl;

删除

我们一般使用erase()来删除。 1.按key mp.erase("xiaoming"); 2.迭代器 mp.erase(it); 3.按区间删除 mp.erase(mp.begin(),mp.end())

容器遍历

累死了不更新了等我后续吧

&是取地址符

我们一般使用for循环遍历

简写版

for(aotu it:mp)
cout<<it.first()<<" "<<it.second.();

//c++14以上支持

Day搜索。

前面老师讲了一大堆总之今天就是把板子打打就行了。

爆搜

//二进制枚举qwq！板子开始qwq 
for(int i=0;i<(1<<n);i++)
{
    //枚举i的每一个二进制位是否被选
    for(int j=0;j<n;j++)//枚举n个二进制位qwq
    {
        if(i>>j&1)
        {
            //开始操作
        }
    }
}

STL的函数。

bitset<>由于有了这个东西我们上面的爆搜就可以

//二进制枚举qwq！板子开始qwq 
for(int i=0;i<(1<<n);i++)
{
    bitset<114514>b(i)//把i转为二进制串
    //枚举i的每一个二进制位是否被选
    for(int j=0;j<n;j++)//枚举n个二进制位qwq
    {
        if(b[j])
        {
            //开始操作
        }
    }
}

TipsTipsb.count()表示统计二进制01的个数qwq。

关于定义常量的一些东西qwq

const是在程序里面发挥常量最用。

constexpr编译时发挥作用。（稍微快一点。）

感觉比快读优化TLE好

说实话你优化TLE还不如优化核心代码，加些快读真的没啥用（亲测。

萌萌dfs来之。搜索概念，用01串表示子集qwq

#include<bits/stdc++.h>
using namespace std;
//path 路径
void dfs(int depth,string p)
{
	//1.结束条件
	if(depth>n)
	{
		cout<<p<<"\n";
		return;
	 } 
	 //调用自己。（寻找子问题的解）
	 //不选
	 dfs(depth+1,p+"0"); 
	 //选
	 dfs(depth+1,p+"1"); 
 } 
int main()
{
  //输入
  dfs(1,"");
	return 0;
}

如果你需要子集和，那么

#include<bits/stdc++.h>
using namespace std;
//path 路径
void dfs(int depth,int sum)
{
	//1.结束条件
	if(depth>n)
	{
		ans+=sum;
    return ;
	 } 
	 //调用自己。（寻找子问题的解）
	 //不选
	 dfs(depth+1,sum); 
	 //选
	 dfs(depth+1,sum+=a[depth]); 
 } 
int main()
{
  //输入
  dfs(1,0);
	return 0;
}

next_permutation全排列函数,嗯对就是一定要把next_permutation放到do while里！

于是我们的全排列就变成了这个样子也是非常之简单

#include<bits/stdc++.h>
using namespace std;
const int N=114514;
long long n,a[N];
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
    {
        a[i]=i;
    }
    do
    {
        for(int i=1;i<=n;i++)
        {
            cout<<a[i]<<" ";
        }
        cout<<endl;
    }while(next_permutation(a+1,a+n+1));
	return 0;
}

day3 dfs

1.dfs的概念 2.dfs的回溯

这里没有记下来……

1.地图---->二维表格---->二维数组

2.点---->坐标(行列)---->（x.yx.y)坐标系！？ 不是我刚刚想到坐标系老师就说到坐标系了？！

3.墙---->障碍物---->存在图里

4.起点&终点---->存在图里

5.已经走过的路径---->标记的数组记录vis[][]

6.方向---->偏移数组---->dx[]={1,0,0,-1} dy[]={0,1,-1,0} 提供一个很好用的dfs板子 lgP1605 可达P0429

#include<bits/stdc++.h>
using namespace std;
const int N=114;
long long n,m,a[N][N],t;
long long dx[]={1,0,0,-1},dy[]={0,1,-1,0};
long long vis[N][N],sx,sy,fx,fy;
long long qwq=0,x,y;
void dfs(int x,int y)
{
    if(x==fx&&y==fy)
    {
        qwq++;
        return;
    }
    for(int i=0;i<4;i++)
    {
        int nx=x+dx[i];
        int ny=y+dy[i];
        //判断下一个位置对不对(nx,ny)是否合理
        if(nx<1||nx>n||ny<1||ny>m||a[nx][ny]||vis[nx][ny]) continue;
        vis[nx][ny]=1;
        dfs(nx,ny);
        vis[nx][ny]=0;
    }
}
int main()
{
    cin>>n>>m>>t;
    cin>>sx>>sy>>fx>>fy; 
    for(int i=1;i<=t;i++)
    {
        cin>>x>>y;
        a[x][y]=1;
    }
    vis[sx][sy]=1;
    dfs(sx,sy);
    cout<<qwq;
    return 0;
}

Day4 bfs

地图---->二维表格---->二维数组

点---->坐标(x,y)---->(行，列)

路径---->标记访问---->vis[][]

路径长度---->dist[][] distance:距离

方向---->偏移数组---->dx[]={1,-1,0,0} dy[]={0,0,1,-1}

猫猫又来提供经典板子了

#include<bits/stdc++.h>
using namespace std;
const int N=114;
long long dist[N][N],n,m;
char g[N][N];
long long dx[]={1,-1,0,0},dy[]={0,0,1,-1};
struct node
{
    int x,y;
};
int bfs(int sx,int sy)
{
    memset(dist,-1,sizeof(dist));//全部初始化为-1
    queue<node>q;//队列，存格子
    q.push({sx,sy});
    dist[sx][sy]=1;
    while(q.size())
    {
        auto u=q.front();//获取队头
        q.pop();//删除队头
        if(u.x==n&&u.y==m)
        {
            return dist[n][m];
        }
        for(int i=0;i<4;i++)//遍历4个风向
        {
            int nx=u.x+dx[i];
            int ny=u.y+dy[i];
            //不出界，不碰障碍，有没有访问
            if(nx<1||nx>n||ny<1||ny>m) continue;
            if(g[nx][ny]=='#') continue;
            if(dist[nx][ny]!=-1) continue;
            //走的路径等于下个位置+1
            dist[nx][ny]=dist[u.x][u.y]+1;
            q.push({nx,ny});  
         }
    }
    return -1;//找不到了
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>g[i][j];
        }
    }
    cout<<bfs(1,1);
    return 0;
}

Day5 图论

无向图：边没有具体指向关系

有向图：边有具体的指向关系

路径（自己上课学）

度数：

1.有向图：入度&出度

2.无向图：连接这个节点边的数量

无向图的度数之和=边数*2

有向图=(入度之和+出度之和）=边数*2

连通图：任意两个不同的顶点之间都存在至少一条路径

有n个节点无向连通图有至少n-1个边

有n个节点的有向连通图有至少n个边

完全图：图中任意两个顶点之间有且只有一条边

有n个节点无向完全图有等差数列求和公式条边 （？(n*(n-1)/2) 有n个节点的有向完全图有n*(n-1)个边

Day6 dp

主要就是推推动态转移方程之类的，板子

最长上升子序列：

#include<bits/stdc++.h>
using namespace std;
const int N=1e5;
long long a[N],dp[N],n,ans;
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		dp[i]=1;
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<i;j++)
		{
			if(a[j]<a[i])
			{
				dp[i]=max(dp[i],dp[j]+1);
			}
		}
		ans=max(ans,dp[i]);
	}
	cout<<ans;
	return 0;
}

最长公共子序列

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll N=1005;
ll dp[N][N];
string a,b;
int main()
{
	cin>>a>>b;
	ll la=a.size();
	ll lb=b.size();
	for(int i=1;i<=la;i++)
	{
		for(int j=1;j<=lb;j++)
		{
			if(a[i-1]==b[j-1])
			{
				dp[i][j]=dp[i-1][j-1]+1;
			}
			else
			{
				dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
			}
		}
	}
	cout<<dp[la][lb];
	return 0;
}

状态机DP(并非状压)

0：未选最后一个店铺 （前一个店铺已选/未选）

1：选择最后一个店铺 （前一个店铺未选）

动态规划

1.状态表示f[i][0/1]

1.1集合走了i个店铺且当前位于j的所有选法

1.2属性看题目

2.状态计算集合划分

f[i][0]有两种情况

如果最后一步的前一步状态是1f[i-1][0]

反之就是f[i-1][1]

所以状态转移方程为f[i][0]=max(f[i][0],f[i-1][1])

如果是f[i][1]那么就是最后一步从0到1写出来就是f[i-1][0] f[i][1]=f[i-1][0]+w[i]其中w[i]表示第i家的现金

题目大盗阿福

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=114514;
ll n,w[N],f[N][2],t;
void solve()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>w[i];
    }
    memset(f,0,sizeof(f));
    f[0][1]=-1e18;
    f[0][0]=0;
    for(int i=1;i<=n;i++)
    {
        f[i][0]=max(f[i-1][0],f[i-1][1]);
        f[i][1]=f[i-1][0]+w[i];
    }
    cout<<max(f[n][0],f[n][1])<<endl;
}
int main()
{
    cin>>t;
    while(t--)
    {
        solve();
    }
    return 0;
}

环形DP解题方法：破环成链

8.1背包问题

01背包：一个物品最多只能选一次影响背包内能装的因素：？

动态规划：状态表示f[i][j]

集合&属性：

集合：从前i个物品中选且物品总体积<=j的所有选法

属性：Max

状态计算：集合划分

01背包问题模板

#include<bits/stdc++.h>
using namespace std;
const int N=114,M=250;
long long dp[N][M],v[N],w[N],n,m;
int main()
{
    cin>>m>>n;
    for(int i=1;i<=n;i++) cin>>v[i]>>w[i];
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=m;j++)
        {
            if(j>=v[i])
            {
                dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i]]+w[i]);
            }
            else
            {
                dp[i][j]=dp[i-1][j];
            }
        }
    }
    cout<<dp[n][m];
    return 0;
}

完全背包

#include<bits/stdc++.h>
using namespace std;
const long long N=114,M=300;
long long dp[N][M],v[N],w[N],n,m;
int main()
{
    cin>>m>>n;
    for(int i=1;i<=n;i++) cin>>v[i]>>w[i];
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=m;j++)
        {
            for(int k=0;k*v[i]<=j;k++)
            {
                dp[i][j]=max(dp[i][j],dp[i-1][j-k*v[i]]+k*w[i]);
            }
        }
    }
    cout<<"max="<<dp[n][m];
    return 0;
}

我们发现完全背包（优化后）和01背包的状态转移方程

完全dp[i][j-v[i]]+w[i]

01dp[i-1][j-v[i]]+w[i]

只有ii有区别一个是i-1一个是ii

还有啊，注意判断j<v[i]的情况

由于这种文章写长了以后输入法会卡我会再开一个blogblog写

优化一下问题！？

附优化代码

#include<bits/stdc++.h>
using namespace std;
const long long N=114,M=300;
long long dp[N][M],v[N],w[N],n,m;
int main()
{
    cin>>m>>n;
    for(int i=1;i<=n;i++) cin>>v[i]>>w[i];
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=m;j++)
        {
            if(j>=v[i])
            {
                dp[i][j]=max(dp[i-1][j],dp[i][j-v[i]]+w[i]);
            }
            else
            {
                dp[i][j]=dp[i-1][j];
            }
        }
    }
    cout<<"max="<<dp[n][m];
    return 0;
}
  1. Language
  2. 主题
  3. 关于
  2. 粤ICP备19104337号   可达信奥官网   域
  5. Powered by Hydro v5.0.4 Community