1. Toy模板网首页
  2. > Toy博客

蓝桥杯1024第 2 场算法双周赛题解+Ac代码

8月前 作者：东方翱翔 分类：Toy博客 阅读(30) 违法举报

这篇具有很好参考价值的文章主要介绍了蓝桥杯1024第 2 场算法双周赛题解+Ac代码。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

提醒：篇幅可能有点长，为了方便，大家可以直接看目录快速查找想要的内容
1.新生【算法赛】 - 蓝桥云课 (lanqiao.cn)

题面：

思路：上届小桥获得了第14届总冠军，那么这届是第15届，直接输出15就是答案

2.铺地板【算法赛】 - 蓝桥云课 (lanqiao.cn)

题面：

input:

4
7 6
2 2
12 8
1 12

output:

Yes
No
Yes
No

蓝桥杯1024第 2 场算法双周赛题解+Ac代码,蓝桥杯&数据结构与算法,蓝桥杯,职场和发展

思路：思维/数学

1.对于每一块地板，如果能被凑出来，那么一定是2*3地砖组合出来的，无论2*3地砖怎么放都为6的倍数，故长为n,宽为m的地板，n*m%6==0一定成立

2.这里还要注意一个特判，就是如果长或宽为1（例如n=6,m=1），那么是6的倍数也无法满足要求（不能切割地砖）

Ac_code：java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int T=sc.nextInt();

        while(T-->0){
            int n=sc.nextInt(),m=sc.nextInt();

            if(n==1||m==1) System.out.println("No");
            else if(n*m%6==0) System.out.println("Yes");
            else System.out.println("No");
        }
    }
}

3.摆玩具【算法赛】 - 蓝桥云课 (lanqiao.cn)

题面：

input:

5 2
2 5 7 10 13

output:

8

蓝桥杯1024第 2 场算法双周赛题解+Ac代码,蓝桥杯&数据结构与算法,蓝桥杯,职场和发展

思路：思维/贪心

简述题意：给一个长度为n的不下降数组,分成k个子数组，使子数组的极差的总和最小

1.对数组中相邻两数的差记为 f[0],f[1],f[2],f[3]....f[n-2],并对其累加记为sum（这里注意数组是不下降的），故f数组中的元素是>=0的。

2.此时可以发现sum就是将长度为n的数组的极差值。

3.但是题目有一个限制条件分成k个子数组，k等于1时,sum就是答案，k>=2时，此时贪心的想让相差大的分开多开一个子数组，以满足极差总和最小

举个栗子：

        h数组: 2 5 7 10 13

        f数组:3 2 3 3

        k等于2时,删除一个最大的数3，有3个3，故有三种情况分子数组的情况都满足条件，

        删除第一个3为：子数组分为 [2], [5 7 10 13],极差和为：0+8

        删除第二个3 为：子数组分为[2,5,7], [10,13]，极差和为：5+3

        删除第三个3为：子数组分为[2,5,7,10],[13]，极差和为：8+0

4.实现时对f数组排序，用总和减去f中（k-1)个最大的数

Ac_code:C++

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include<stack>
#include<cmath>
#include <unordered_set>
#include <unordered_map>
#include<set>
#include <map>


using namespace std;

typedef long long LL;
typedef pair<int,int>PII;

#define x first
#define y second
#define ls u<<1
#define rs u<<1|1
#define all(ss) ss.begin(),ss.end()

int const mod1=998244353;   
int const mod2=1e9+7;
int const N=2e5+7;
int const INF=0x3f3f3f3f;

int T;
int n,k;
int a[N];
int f[N];

void solve(){
    scanf("%d%d",&n,&k);
    for(int i=0;i<n;i++)    scanf("%d",a+i);
    
    LL sum=0;   //累加差值
    for(int i=1;i<n;i++)    f[i-1]=a[i]-a[i-1],sum+=f[i-1];
    sort(f,f+n-1);
    for(int i=n-2;i>=0&&--k;i--)    sum-=f[i];  //减去(k-1)个最大的数
    cout<<sum<<endl;
} 

void init(){
    
}

int main()
{
    //std::ios::sync_with_stdio(false);   cin.tie(0); cout.tie(0);
    T=1;
    //cin>>T;
    //scanf("%d",&T);
    
    init();
    
    while(T--){
        solve();
    }
	
	return 0;
}

4.通关【算法赛】 - 蓝桥云课 (lanqiao.cn)

题面：

input:

4 5
0 3 5
1 2 8
1 3 9
3 1 15

output:

3

蓝桥杯1024第 2 场算法双周赛题解+Ac代码,蓝桥杯&amp;数据结构与算法,蓝桥杯,职场和发展

蓝桥杯1024第 2 场算法双周赛题解+Ac代码,蓝桥杯&amp;数据结构与算法,蓝桥杯,职场和发展

思路：bfs+堆优化

简述题意：给一个以1为根的有向树和初始的经验，问最多能覆盖的结点为多少个

设与1相连且小于已有经验的结点集合记为S

1.,很容易想到一个暴力做法，就是对所有小于当前经验值的遍历一遍，看是否可以扩展树的大小，没有一个结点可以更新，直接输出答案，有一个结点可以更新，就可以再次进入循环遍历一遍S集合中的所有元素，但是这个方法会tle,故要优化。

2.我们换一个思考方式，把与1相连的结点但是还没有加入到集合S中的集合，记录到一个小根堆中，每次从小根堆中取出最小的闯关所需要经验值，看是否可以加入到集合中，可以加入集合中接着循环判断，不可以直接跳出循环输出答案

Ac_code:C++

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include<stack>
#include<cmath>
#include <unordered_set>
#include <unordered_map>
#include<set>
#include <map>


using namespace std;

typedef long long LL;
typedef pair<int,int>PII;

#define x first
#define y second
#define ls u<<1
#define rs u<<1|1
#define all(ss) ss.begin(),ss.end()

int const mod1=998244353;   
int const mod2=1e9+7;
int const N=2e5+7;
int const INF=0x3f3f3f3f;

int T;
int n,m;
int a[N];

//v[i]:通过第i关所需要的最低经验值
//w[i]:通过第i关可以获得的经验值
int w[N],v[N];
vector<int>g[N];    //g[x]:x结点可以到达的所有结点

int bfs(){
    //first：通过第second关的最低经验值
    //second:结点编号
    priority_queue<PII,vector<PII>,greater<PII>>heap;   //小根堆
    heap.push({v[1],1});    
    int res=0;
    
    LL W=m; //一开始的经验值
    while(heap.size()){
        PII temp=heap.top();    heap.pop();
        int id=temp.y,min_v=temp.x;
        if(min_v>W) break;  //最低经验值都比已有经验值大，直接break
        W+=w[id];   //累加经验
        res++;  //闯关++
        for(int y:g[id])    heap.push({v[y],y});    //代表挑战的关入堆
    }
    return res;
}

void solve(){
    scanf("%d%d", &n, &m);
    for(int i=1;i<=n;i++){
        int fa; scanf("%d%d%d",&fa,w+i,v+i);
        g[fa].push_back(i);
    }
    
    cout<<bfs()<<endl;
} 

void init(){
    
}

int main()
{
    //std::ios::sync_with_stdio(false);   cin.tie(0); cout.tie(0);
    T=1;
    //cin>>T;
    //scanf("%d",&T);
    
    init();
    
    while(T--){
        solve();
    }
	
	return 0;
}

5.串门【算法赛】 - 蓝桥云课 (lanqiao.cn)

题面：

input:

4
1 2 3
1 3 4
1 4 5

output:

15

蓝桥杯1024第 2 场算法双周赛题解+Ac代码,蓝桥杯&amp;数据结构与算法,蓝桥杯,职场和发展

思路：dfs求树的直径

简述题意：n个节点，n-1条边，选择一个结点为起点，输出访问所有结点的最小值

1.直接求很难，那么换个思路，每个结点必须遍历一次，那么每条边至少加一次，每条边加一次的总和记为sum,我们的目的就是让一些边遍历两次或者两次以上的可能尽量小，那么找出最长第一条路径max_len（注意是权值最大），让它只遍历一次,就能保证答案最小，那么sum-max_len就是遍历两次的边权值，答案就是sum+sum-max_len。

2.那么这么求sum,max_len呢？sum很好求，直接累加边权值即可，max_len其实是最大的一条路径(树的直径)，那么就转化求树的直径即可。

3.求树的直径（最大的一条路径），这里有通解，就是随便找一个点，dfs一遍记录最大路径的值与结点编号，在用第一次记录的结点编号第二次dfs,更新最大的max_len即可。（这里感兴趣证明的可以查树的直径，还有注意一点就是树的直径不能有负权边，不然不能用此方法求解，要数形dp才能求解）

Ac_code：C++

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include<stack>
#include<cmath>
#include <unordered_set>
#include <unordered_map>
#include<set>
#include <map>


using namespace std;

typedef long long LL;
typedef pair<int,int>PII;

#define x first
#define y second
#define ls u<<1
#define rs u<<1|1
#define all(ss) ss.begin(),ss.end()

int const mod1=998244353;   
int const mod2=1e9+7;
int const N=2e5+7;
int const INF=0x3f3f3f3f;

int T;
int n,m;
int a[N];
vector<PII>g[N];    //first:结点编号，second:权值
int start;  //起始结点
LL max_len; //最长的一条路径

//dfs代码较短，第一次接触可能有点难，不过可以慢慢理解
void dfs(int x,int fa,LL val){
    if(max_len<val) max_len=val,start=x;    //全局更新答案
    for(PII k:g[x]){
        if(k.x==fa) continue;   //不要往回更新
        dfs(k.x,x,val+k.y);
    }
}

void solve(){
    scanf("%d", &n);
    LL sum=0;
    for(int i=1;i<n;i++){
        int a,b,c;  scanf("%d%d%d",&a,&b,&c);
        g[a].push_back({b,c});
        g[b].push_back({a,c});
        sum+=c;
    }
    
    dfs(1,-1,0);    //找起点
    dfs(start,-1,0);    //用起点找到最长的路径
    cout<<sum+sum-max_len<<endl;
    
} 

void init(){
    
}

int main()
{
    //std::ios::sync_with_stdio(false);   cin.tie(0); cout.tie(0);
    T=1;
    //cin>>T;
    //scanf("%d",&T);
    
    init();
    
    while(T--){
        solve();
    }
	
	return 0;
}

6.神奇数【算法赛】 - 蓝桥云课 (lanqiao.cn)

题面：

input:

100
130

output:

5

思路：数位dp

简述题意：求[l,r]中神奇树的个数，神奇数的定义假设有n（n>=2）位数 s1,s2..sn,对数位s1+s2+..+sn-1的总和为sum,sum%sn==0则为神奇数，10<=-l<=r<=1e200

数位初学者入门这里推荐灵神：2376. 统计特殊整数 - 力扣（LeetCode）

1.数位dp的一般求法[1,x]中合法的数，但是我们要求的是[l,r],这里采用前缀和思想pre[r]-pre[l-1]

2.这里采用记忆化搜索，一般用4个参数，本题的4个参数为枚举到了第pos位,前面总和为sum,是否有限制limit，是否有前导0用num

3.枚举到最后一位时，枚举最后一位可以填那些数，满足记录合法数返回即可

Ac_code:C++

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include<stack>
#include<cmath>
#include <unordered_set>
#include <unordered_map>
#include<set>
#include <map>


using namespace std;

typedef long long LL;
typedef pair<int,int>PII;

#define x first
#define y second
#define ls u<<1
#define rs u<<1|1
#define all(ss) ss.begin(),ss.end()

int const mod1=998244353;   
int const mod2=1e9+7;
int const N=2e5+7;
int const INF=0x3f3f3f3f;

int T;
int n,m;
int a[N];
string s;

//f[pos][sum]:枚举到了第pos位，前pos-1位的总和为sum,且没有限制的合法数
//200个9=200*9，这里多开7个
int f[207][1807];

int dfs(int pos,int sum,bool limit,bool num){
    int up=limit?s[pos]-'0':9;
    if(pos==(int)s.size()-1){
        int cnt=0;  //记录合法数
        for(int i=1;i<=up;i++)  //枚举最后一位填什么
            cnt+=sum%i==0;
        return cnt;
    }
    if(num&&!limit&&f[pos][sum]!=-1) return f[pos][sum];
    
    int res=0;
    //只有两位数了，就不能删除了
    //要不然可以删除最高一位
    if(pos<(int)s.size()-2&&!num)    res=dfs(pos+1,0,false,false);
    
    for(int i=num?0:1;i<=up;i++)
        res=(res+dfs(pos+1,sum+i,limit&&i==up,true))%mod1;
    
    if(num&&!limit) f[pos][sum]=res;    //记忆化
    return res;
    
}

int check(string s){
    int sum=0,last=s.back()-'0';
    if(last==0) return 0;   //最后一位不能为0
    for(int i=0;i<s.size()-1;i++)   sum+=s[i]-'0';
    return sum%last==0?1:0;
}

void solve(){
    string l,r; cin>>l>>r;
    
    s=l;
    memset(f,-1,sizeof f);
    int left=dfs(0,0,true,false);
    
    s=r;
    memset(f,-1,sizeof f);
    int right=dfs(0,0,true,false);
    
    //前缀和思想，但是多减了一个l,故要加上check(l)
    int ans=((right-left+check(l))%mod1+mod1)%mod1;
    cout<<ans<<endl;
    
} 

void init(){
    
}

int main()
{
    //std::ios::sync_with_stdio(false);   cin.tie(0); cout.tie(0);
    T=1;
    //cin>>T;
    //scanf("%d",&T);
    
    init();
    
    while(T--){
        solve();
    }
	
	return 0;
}

7.小蓝的疑问【算法赛】 - 蓝桥云课 (lanqiao.cn)

题面：

蓝桥杯1024第 2 场算法双周赛题解+Ac代码,蓝桥杯&amp;数据结构与算法,蓝桥杯,职场和发展蓝桥杯1024第 2 场算法双周赛题解+Ac代码,蓝桥杯&amp;数据结构与算法,蓝桥杯,职场和发展input:

7 4
2 9 8 7 8 6 4
1 2
1 3
2 4
2 6
3 5
3 7
1 2
1 1
3 1
2 1

output:

8
9
8
7

思路：

简述题意：给你一颗以1为根的有向树，q个询问，对于每个询问x,k,输出x结点为根x记为第0层，输出所有第k层结点的最大值

1，一个简单暴力的方法就是，对每个询问bfs求除第k层结点的值，取max输出即可

TLE_code:C++(超时代码，过了60%的样例)

打蓝桥杯的话，可以获得60%的分，也建议学一学

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include<stack>
#include<cmath>
#include <unordered_set>
#include <unordered_map>
#include<set>
#include <map>


using namespace std;

typedef long long LL;
typedef pair<int,int>PII;

#define x first
#define y second
#define ls u<<1
#define rs u<<1|1
#define all(ss) ss.begin(),ss.end()

int const mod1=998244353;   
int const mod2=1e9+7;
int const N=2e5+7;
int const INF=0x3f3f3f3f;

int T;
int n,q;
int w[N];
vector<int>g[N];

//求以k为根的第k层结点的最大值
int bfs(int start,int k){
    int res=-1;
    queue<PII>q;    //first:结点编号，second:层数
    q.push({start,0});
    
    while(q.size()){
        PII temp=q.front(); q.pop();
        int id=temp.x,depth=temp.y;
        
        for(int y:g[id]){
            if(depth==k-1) res=max(res,w[y]);
            else    q.push({y,depth+1});
        }
    }
    
    return res;
}

void solve(){
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++)   scanf("%d",w+i);
    for(int i=1;i<n;i++){
        int a,b;    scanf("%d%d",&a,&b);
        g[a].push_back(b);
    }
    
    while(q--){
        int a,b;    scanf("%d%d",&a,&b);
        printf("%d\n",bfs(a,b));
    }
} 

void init(){
    
}

int main()
{
    //std::ios::sync_with_stdio(false);   cin.tie(0); cout.tie(0);
    T=1;
    //cin>>T;
    //scanf("%d",&T);
    
    init();
    
    while(T--){
        solve();
    }
	
	return 0;
}

最后一题正解后续更新.....感觉写不出正解了（更改博客时间2023/10/29）

描述有误，或者描述不好理解，欢迎指正

希望对你有用，欢迎关注，点赞，收藏文章来源地址https://www.toymoban.com/news/detail-737615.html

到了这里，关于蓝桥杯1024第 2 场算法双周赛题解+Ac代码的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • 蓝桥杯双周赛算法心得——铺地板（质因数）

    蓝桥杯双周赛算法心得——铺地板（质因数）

    大家好，我是晴天学长，这是第二周的蓝桥杯的双周赛，题可出的又好又灵活啊！真不错！💪💪💪 1) .铺地板 2) .算法思路 1.导入java.util包中的Scanner类，以从用户那里读取输入。 2.main方法是程序的入口点。 3.创建一个Scanner对象，用于从标准输入读取输入。 4.从用户那里读取

    2024年02月08日
    浏览(31)
  • 「蓝桥·算法双周赛」第一场公开赛【待补题填坑】

    「蓝桥·算法双周赛」第一场公开赛【待补题填坑】

    给定四个字符，判断是否其中有三个相同，另一个与他们不同  二叉树性质问题，不了解二叉树也完全可以做。 要注意的是每次都从第一行的第一个点开始走，给一个字符串按照它走，输出最后的结果就行。 往左走坐标就变成了2*pos-1，往右就变成了2*pos 画个树理解一下就好

    2024年02月07日
    浏览(37)
  • 第 122 场 LeetCode 双周赛题解

    第 122 场 LeetCode 双周赛题解

    A 将数组分成最小总代价的子数组 I 枚举：枚举后两个子数组的起始下标 B 判断一个数组是否可以变为有序 模拟：模拟冒泡排序的过程，若相邻元素大小关系需要交换位置，但其二进制下数位为 1 的数目不同，则返回false，若完成排序返回true C 通过操作使数组长度最小 脑筋急

    2024年01月22日
    浏览(30)
  • 【蓝桥杯】蓝桥杯双周赛第二场ABCD题

    【蓝桥杯】蓝桥杯双周赛第二场ABCD题

    知识点：下一届是第几届蓝桥杯……         新一届蓝桥杯大赛即将在2024年拉开序!         作为大一新生的小蓝，在听说了这场盛大的比赛后，对其充满了期待与热情。但作为初次参赛的新手，他对蓝桥杯的相关赛制和历史并不了解。于是，他决定寻求上届蓝桥杯总冠

    2024年02月08日
    浏览(32)

  • 【蓝桥杯】蓝桥杯双周赛第二场E题

    知识点：树的直径          过年了。         蓝桥村可以抽象为n个节点，n - 1条边的一棵树，每条边有边权长度wi。         小蓝可以选择任意一个点作为起点，然后选择一条路径，可以访问每一个节点最少一次。他想知道最短的路径长度是多少。 输入格式         第一

    2024年02月06日
    浏览(31)

  • leetcode 122双周赛 解题思路+代码

    本人水平有限，只做出3道，最后1道放弃。 给你一个长度为 n 的整数数组 nums 。 一个数组的 代价 是它的 第一个 元素。比方说，[1,2,3] 的代价是 1 ，[3,4,1] 的代价是 3 。 你需要将 nums 分成 3 个 连续且没有交集 的子数组。 请你返回这些子数组的 最小 代价 总和 。 示例 1： 输

    2024年02月20日
    浏览(35)
  • 零基础！无门槛！高额现金奖励！优秀的大学生都在打这场算法双周赛

    零基础！无门槛！高额现金奖励！优秀的大学生都在打这场算法双周赛

       spacespace     大家好，我是执梗。在蓝桥杯中获得过十三届 Java B 组国一以及十四届 C++ B 组的国一。今天主要为大家带来一个好消息，蓝桥杯将为各位喜爱算法的小伙伴带来全新的算法双周赛。如果你热爱算法竞赛，或者准备参加十五届的蓝桥杯比赛，那么一定不要错过

    2024年02月08日
    浏览(51)
  • [LeetCode周赛复盘] 第 111 场双周赛20230819

    [LeetCode周赛复盘] 第 111 场双周赛20230819

    T1 对向双指针。 T2 子序列/同向双指针。 T3 LIS/状态DP。 T4 数位DP。 2824. 统计和小于目标的下标对数目 1. 题目描述 2. 思路分析 类似两数之和，由于顺序无关，把数据排序。 设置l,r=0,n-1。 若a[l]+a[r]target,则a[l]+ 任意a[l+1…r]都target。则这r-l个数都可以和l组队。 3. 代码实现 2825

    2024年02月11日
    浏览(38)
  • [LeetCode周赛复盘] 第 102 场双周赛20230415

    [LeetCode周赛复盘] 第 102 场双周赛20230415

    T4卡了半小时，真的不应该。 T1 模拟。 T2 前缀和模拟。 T3 分层遍历。 T4 floyd/dij(我觉得dij不是正解)。 链接: 6333. 查询网格图中每一列的宽度 1. 题目描述 2. 思路分析 按题意模拟即可。 3. 代码实现 链接: 6334. 一个数组所有前缀的分数 1. 题目描述 2. 思路分析 不要被题目的一堆

    2023年04月16日
    浏览(35)

  • 竞赛 双周赛

    分段 块定义为网格图中 2 x 2 的一个子矩阵。对于 左上角格子为 [x, y] 的块 ，其中 0 = x m - 1 且 0 = y n - 1 ，包含坐标为 [x, y] ，[x + 1, y] ，[x, y + 1] 和 [x + 1, y + 1] 的格子。 任意一个点 (x, y)，包含它的块为 [x-1, y-1], [x-1, y], [x, y-1], [x, y]，其中坐标不能越界。 BFS / DFS, 树状数组 方

    2024年02月12日
    浏览(27)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包