首页 > 软件开发 > 软件开发

软件开发2021.5.22 2022蓝桥杯练习赛3

admin 软件开发 2021-05-25 09:26:42 算法 c++ 
后台-系统设置-扩展变量-手机广告位-内容正文底部

2021.5.22 2022蓝桥杯练习赛3

闲话:
1、就难度而言,本次练习赛题目整体比较简单,要是认真补了前两场的题,应该可以轻松做完4到5题。
2、就体验而言,这场练习赛数据普遍交弱,基本上瞎搞都能过。
3、遇到不会的多问,CCSU_MI大佬,CCSU_JPanel大佬。
4、本次做题过程十分快乐。

题目
1、试题 算法训练 矩阵加法
在这里插入图片描述
解析:对应位置相加可以了,学了线代的都知道,没学的也知道。

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n,m;
	cin>>n>>m;
	int a[n+5][m+5],b[n+5][m+5],c[n+5][m+5];
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			cin>>a[i][j];
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			cin>>b[i][j];
			c[i][j]=a[i][j]+b[i][j];
		}
	}	
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			cout<<c[i][j]<<" ";
		}
		cout<<endl;
	}	
}

----------------------------------------------------------------------------------------------------------------------------
2、试题 算法训练 删除多余括号
在这里插入图片描述
----------------------------------------------------------------------------------------------------------------------------
CCSU–JPanel大佬教我的硬模拟

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef pair<char,int>PLL;
string s;
bool vis[300];
stack<PLL>st;

char f(int x,int y){
    bool flag=true;
    for(int i=x+1;i<=y;i++){
        if(vis[i]==0){
            if(s[i]=='+'||s[i]=='-'){
                if(flag) return s[i];
            }
            if(s[i]=='(') flag=false;
            if(s[i]==')') flag=true;
        }
    }
    return ' ';
}

int main(){
    cin>>s;
    for(int i=0;i<s.length();i++){
        if(s[i]=='('){
            if(i==0) st.push({' ',i});
            else{
                if(s[i-1]!='('&&s[i-1]!=')') st.push({s[i-1],i});
                else st.push({' ',i});
            }
        }
        if(s[i]==')'){
            if(i!=s.length()-1){
                PLL t=st.top();
                char x=f(t.y,i);
                if(x=='+'||x=='-'){
                    if(t.x=='*'||t.x=='/'||s[i+1]=='*'||s[i+1]=='/'){
                        st.pop();
                    }
                    else{
                        if(t.x=='-'&&x=='+'){
                            st.pop();
                        }
                        else{
                            st.pop();
                            vis[t.y]=vis[i]=1;
                        }
                    }
                }
                else{
                    st.pop();
                    vis[t.y]=vis[i]=1;
                }
            }
            else{
                PLL t=st.top();
                char x=f(t.y,i);
                if(x=='+'||x=='-'){
                    if(t.x=='*'||t.x=='/'){
                        st.pop();
                    }
                    else{
                        if(t.x=='-'&&x=='+'){
                            st.pop();
                        }
                        else{
                            st.pop();
                            vis[t.y]=vis[i]=1;
                        }
                    }
                }
                else{
                    st.pop();
                    vis[t.y]=vis[i]=1;
                }
            }
        }
    }
    for(int i=0;i<s.length();i++){
        if(!vis[i]) cout<<s[i];
    }
}

----------------------------------------------------------------------------------------------------------------------------
3、试题 算法训练 邮票
在这里插入图片描述
解析:蓝桥杯数据很水,直接无脑dfs就可以了。
思路:
1、dfs(int p,int ne,int sum) 第1个参数表示位置,第2个参数表示已经贴了几张邮票,第3个参数表示当前总和(表示的数)。每次使vis[当前总和]=1
2、本题蓝桥后台数据最大数据为20,10,当n<27都可直接dfs水过。数据过大请看第二段代码。
----------------------------------------------------------------------------------------------------------------------------

#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[300];
bool vis[30000];

void dfs(int p,int ne,int sum){
    if(ne>n||p>m) return;
    vis[sum]=1;
    dfs(p+1,ne,sum);
    dfs(p,ne+1,sum+a[p]);
}

int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>a[i];
        vis[a[i]]=1;
    }
    dfs(1,0,0);
    for(int i=1;i<=26000;i++){
        if(!vis[i]){
            cout<<i-1<<"\n";
            return 0;
        }
    }
}

----------------------------------------------------------------------------------------------------------------------------
CCSU__MI大佬的代码

#include<bits/stdc++.h>
using namespace std;
const int maxn = 25500 + 10;
vector<int>v;
int n, m;
int a[150];
int dp[maxn];
int main()
{
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= m; i++)
	{
		scanf("%d", &a[i]);
		dp[a[i]] = 1;
	}
	sort(a + 1, a + 1 + m);
	for (int i = 1; i <= n * a[m]; i++)
	{
		if (dp[i] == 1)
		{
			v.push_back(i);
			continue;
		}
		else
		{
			int minn = INT_MAX-10;
			for (int j = 0; j < v.size(); j++)
				minn = min(minn, dp[i-v[j]]);
			if (minn + 1 > n)
			{
				printf("%d\n", i - 1);
				break;
			}
			dp[i] = minn + 1;
		}
	}

}

----------------------------------------------------------------------------------------------------------------------------
4、试题 算法提高 贪吃的大嘴
在这里插入图片描述
解析:这个题之前应该已经讲过了,就是一个背包问题,直接套背包模板就行。

#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[55],b[55],dp[20005];
bool vis[20005];
int main(){
    cin>>n>>m;
    memset(dp,0x3f3f3f3f,sizeof(dp));
    dp[0]=0;
    for(int i=1;i<=m;i++) cin>>a[i]>>b[i];
    for(int i=1;i<=m;i++){
        for(int j=0;j<b[i];j++){
            for(int k=n;k>=a[i];k--){
                dp[k]=min(dp[k],dp[k-a[i]]+1);
            }
        }
    }
    if(dp[n]==0x3f3f3f3f) cout<<"><"<<"\n";
    else cout<<dp[n]<<"\n";
}

----------------------------------------------------------------------------------------------------------------------------
5、试题 算法提高 超级玛丽
在这里插入图片描述
解析:裸的线性dp,没任何坑点
思路:
1、在vis数组中讲陷阱位置对应下标变成1。vis[i]=0代表位置i是空地,vis[i]=1代表位置i是陷阱。
2、因为超级玛丽无法连着跳2个单位长度,所以开始for循环一次vis数组,看看有没有连在一块的陷阱。
3、没有连在一块的陷阱。那么就开始dp。
其中dp[1]=1;
转移方程:
if(vis[i]==0) dp[i]=dp[i-1]+dp[i-2]。//第i个位置是空地
if(vis[i]==1) dp[i]=0; //第i个位置是陷阱

#include<bits/stdc++.h>
using namespace std;
int n,m;
bool vis[45];
int dp[45];
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int x; cin>>x;
        vis[x]=1;
    }
    bool flag=0;
    for(int i=2;i<n;i++){
        if(vis[i]==1){
            if(flag==1){
                cout<<"0"<<"\n";
                return 0;
            }
            else{
                flag=1;
            }
        }
        else flag=0;
    }
    dp[1]=1;
    for(int i=2;i<=n;i++){
        if(vis[i]==1) dp[i]=0;
        else dp[i]=dp[i-1]+dp[i-2];
    }
    cout<<dp[n]<<"\n";
}

----------------------------------------------------------------------------------------------------------------------------
6、试题 算法提高 8皇后·改
在这里插入图片描述
解析:在经典8皇后问题上,将原来要求输出的路径改成了输出最大数字和
学习链接:八皇后问题详解(四种解法)
思路:
1、一种是将最后输出路径代码改成求值。最后sort排序输出最大值。(代码1)
2、一种是每次完成一种情况,每次max取值,然后最后输出最大值。(代码2)
----------------------------------------------------------------------------------------------------------------------------
代码1

#include<bits/stdc++.h>
using namespace std;
int ans[10],sum[100],t=0;
int a[10][10];
bool row[10],line1[20],line2[20];
void print()
{
	for(int i=1;i<=8;i++)
	{
		sum[t]+=a[i][ans[i]];
	}
	t++;
}
void f(int step)
{
	for(int i=1;i<=8;i++)
	{
		if(row[i]==false&&line1[step+i]==false&&line2[step+8-i]==false)
		{
			ans[step]=i;
			if(step==8)
			{
				print();
			}
			row[i]=true;
			line1[step+i]=true;
			line2[step+8-i]=true;
			f(step+1);
			row[i]=false;
			line1[step+i]=false;
			line2[step+8-i]=false;
		}
	}
}
int main()
{
	for(int i=1;i<=8;i++)
	{
		for(int j=1;j<=8;j++)
		{
			cin>>a[i][j];
		}
	}
	f(1);
	sort(sum,sum+95,greater<int>());
	cout<<sum[0];
}

----------------------------------------------------------------------------------------------------------------------------
代码2–队友的神仙代码

#include<bits/stdc++.h>
using namespace std;
const int N=10;
char e[N][N];
int n;
int a[N][N];
int col[N],dg[N],udg[N];
int res=0;
void dfs(int u,int sum)
{
    if(u==n)
    {
        res=max(res,sum);
        return ;
    }
    for(int i=0;i<n;i++)
    {
        if(!col[i]&&!dg[n-u+i]&&!udg[u+i])
        {
            e[u][i]='Q';
            col[i]=dg[n-u+i]=udg[u+i]=true;
            dfs(u+1,sum+a[u][i]);
            e[u][i]='.';
            col[i]=dg[n-u+i]=udg[u+i]=false;
        }
    }
}
int main()
{
    n=8;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
          cin>>a[i][j];
          e[i][j]='.';
        }
    }
    dfs(0,0);
    cout<<res<<endl;
    return 0;
}

----------------------------------------------------------------------------------------------------------------------------
CCSU_MI大佬的代码

#include<bits/stdc++.h>
using namespace std;
int a[10][10];
int col[20];
int sum, maxx;
bool check(int c, int r)
{
	for (int i = 1; i < r; i++)
		if (col[i] == c || (abs(col[i] - c) == abs(i - r)))
			return false;
	return true;
}
void dfs(int x)
{
	if (x == 9)
	{
		maxx = max(maxx, sum);
		return;
	}
	for (int i = 1; i <= 8; i++)
	{
		if (check(i, x))
		{
			col[x] = i;
			sum += a[x][i];
			dfs(x + 1);
			sum -= a[x][i];
		}
	}
}
int main() 
{
	for (int i = 1; i <= 8; i++) 
		for (int j = 1; j <= 8; j++) 
			scanf("%d", &a[i][j]);
	dfs(1);
	printf("%d\n", maxx);
}

----------------------------------------------------------------------------------------------------------------------------
总结
1、本场可能dp题较多,但都是一些基础dp。dp题没有什么技巧可言,唯一的方法就是多做dp题。
2、多背模板,一些需要掌握的基础模板都要会用,最好是都可以随时写出来。平时的话推荐有时间可以手写自己的模板,手写代码不同于用电脑写代码,手写代码速度很慢,也没有补全和复制粘贴。多次重复手写代码,有助于提高解题能力
3、学习虽然重要,但还是得加强身体锻炼。比赛长达4小时,有的长达5小时,这还真不是一件容易的事。加强锻炼,在比赛等其他方面才更有优势。(抄上篇的,编不出了)

文章来源:https://blog.csdn.net/curryljx/article/details/117170757

后台-系统设置-扩展变量-手机广告位-内容正文底部
版权声明

本文仅代表作者观点,不代表本站立场。
本文系作者授权发表,未经许可,不得转载。
本文地址:https://www.jcdi.cn/ruanjiankaifa/30823.html

留言与评论(共有 0 条评论)
   
验证码:
后台-系统设置-扩展变量-手机广告位-评论底部广告位

教程弟

https://www.jcdi.cn/

统计代码 | 京ICP1234567-2号

Powered By 教程弟 教程弟

使用手机软件扫描微信二维码