走方格(DP)
题目
文章图片
解释
- f[i][j]存放走到[i][j]的方案个数
#include
using namespace std;
const int N=40;
int f[N][N];
int n,m;
int main()
{
cin>>n>>m;
f[1][1]=1;
for(int i=1;
i<=n;
i++)
for(int j=1;
j<=m;
j++)
{
if(i==1&&j==1)
continue;
if(i%2==0&&j%2==0)
{
f[i][j]=0;
}
else
{
f[i][j]=f[i-1][j]+f[i][j-1];
}
}
cout<
算法二(一维动规)
#include
using namespace std;
const int N=40;
int f[N];
int n,m;
int main()
{
cin>>n>>m;
f[1]=1;
for(int i=1;
i<=n;
i++)
for(int j=1;
j<=m;
j++)
{
if(i==1&&j==1)
continue;
if(i%2==0&&j%2==0)
{
f[j]=0;
}
else
{
f[j]=f[j-1]+f[j];
}
}
cout<
解码(字符串处理+模拟) 题目
文章图片
解释 代码段 想复杂了的二逼代码
#include
#include
#include
#include
const int N = 1e6 + 10;
using namespace std;
int main()
{
string s;
cin >> s;
char ans[N];
int cnt = 1;
int size = s.size();
stackc;
for (int i = 0;
i < size;
i++)
{
if (s[i] > '9')//是字母
{
if (c.empty())
c.push(s[i]);
else
{
if (s[i] != c.top())
{
ans[cnt++] = c.top();
c.pop();
c.push(s[i]);
}
else
{
int m = 1;
while (s[i] == c.top()&&i
正常人思维
#include
#include
#include
using namespace std;
int main()
{
string s;
cin>>s;
for(int i=0;
i='0' && s[i]<='9')
{
int t=s[i]-'0';
for(int j=0;
j
网格分析(并查集!)
题目
文章图片
解释
- 题目要求有n个节点
- 操作一为将节点a和节点b合并
- 操作二为将当前节点以及节点所在的集合所有节点的权值都加b
- 并查集典型题
- 并查集的树形有几个特征
- 树形分为三种
- x自身是根节点x的父节点是根节点(这两种情况不需要对权值进行操作)
- x的祖父节点是根节点
- 每次调用find函数,针对第三种情况一定会路径压缩成第二种树形
- 所以此时需要将x的父节点的权值down下来给x,再路径压缩
- 由此可以得出一个结论,并查集树形的每个分支长度不会大于3
- 需要注意到每次权值的增加都是存储在根节点上
- 如果二刷看不懂请针对如下数据进行推算
数据+图示
【蓝桥刷题冲冲!|【真题】第十一届蓝桥真题】输入样例2:
11 20
2 5 90
2 3 21
2 3 83
1 11 7
1 10 11
1 3 9
1 4 9
1 2 1
1 3 9
2 7 54
1 8 6
1 3 4
2 6 9
1 10 4
1 2 4
1 10 7
1 1 3
1 1 7
2 6 85
2 3 75
输出样例2:
75 75 179 75 90 94 129 94 75 129 129
文章图片
代码段
#include
using namespace std;
const int N=10010;
int p[N],d[N];
int n,m;
int find(int x)
{
if(p[x]==x||p[x]==p[p[x]])return p[x];
//如果当前点是根节点或者当前点的祖父节点是根节点则不需要进行任何操作直接返回
int r=find(p[x]);
//如果父节点也不是根节点的话,那必然祖父节点是根节点
d[x]+=d[p[x]];
//在路径压缩之前,先将父节点的权值down下来
p[x]=r;
//进行路径压缩
return r;
}
int main()
{
cin>>n>>m;
for(int i=1;
i<=n;
i++)
p[i]=i;
while(m--)
{
char op;
cin>>op;
int a,b;
cin>>a>>b;
if(op=='1')
{
a=find(a),b=find(b);
if(a!=b)//不在同一个集合之中
{
d[a]-=d[b];
//因为合并前根节点的权值不能加到新合并的集合,所以这里作差
p[a]=b;
//b作为a的父节点
}
}
else
{
a=find(a);
//找到a的根节点
d[a]+=b;
//将权值累积在根节点上
}
}
for(int i=1;
i<=n;
i++)
{
if(i==find(i))
cout<
推荐阅读
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
- 蓝桥真题|【蓝桥真题五】带三百人训练了十天精选蓝桥真题,看看他们都练些什么(三门语言题解)
- python|【小白向】蓝桥杯练习系统——基础练习部分python语句解析
- leetcode|算法入门之字符串(Python)【初级算法——字符串】【蓝桥杯练习】【力扣练习】
- 数据结构与算法|【蓝桥杯】 BASIC-16 分解质因数
- 备战蓝桥杯|蓝桥杯python组十二届省赛真题+解析+代码(通俗易懂版)
- 备战蓝桥杯|蓝桥杯python组十一届省赛真题+解析+代码(通俗易懂版)
- 备战蓝桥杯|2020年第十一届蓝桥杯省赛Python组(真题+解析+代码)(作物杂交)
- 备战蓝桥杯|2021年第十二届蓝桥杯省赛Python组(真题+解析+代码)(直线)
- 备战蓝桥杯|2021年第十二届蓝桥杯省赛Python组(真题+解析+代码)(时间显示)