首页 > 编程语言 >蓝桥 第 3 场 算法季度赛 前5题题解，剩下的后续发上去补上

蓝桥 第 3 场 算法季度赛 前5题题解，剩下的后续发上去补上

时间：2024-07-03 19:29:32浏览次数：28  
标签：Lan Qiao int 题解 ll cin 蓝桥 发上去 x1

第1题 全国科普行动日【算法赛】

题目传送门

直接输出就行，没多大操作可言：

#include <iostream>
using namespace std;
int main()
{
  cout<<"6.29";
  return 0;
}

第2题 A%B【算法赛】

题目传送门

题目有点小坑，因为也可能是负数，所以需要特判一下，上代码就可以看懂了：

#include <iostream>
using namespace std;

int main() {
    int T;
    cin >> T;

    while (T--) {
        long long A, B;
        cin >> A >> B;
        long long remainder = A % B;
        if (remainder < 0) {
            remainder += abs(B);
        }
        
        cout << remainder << endl;
    }

    return 0;
}

第3题 能量圆盘【算法赛】

题目传送门

一开始被题目中说的1与n是相连的给蛊惑了，后面亲自写了一个数据来验证，似乎没有什么用，单纯拿来蛊惑人心的，使用map记录一下出现次数最多的数字是什么，然后用n减去这个最大值就行了，因为每个数都必须变成同一个数，这样做毋庸置疑是最小次数：

#include<bits/stdc++.h>

using namespace std;
using ll = long long;

const ll N = 1e4 + 5;
const ll inf = 1e18;

ll a[N], dp[N];
map<ll, ll>mp;

bool cmp_value(const pair<ll, ll> left, const pair<ll, ll> right) {
	return left.second < right.second;
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	ll n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		mp[a[i]]++;
	}
	ll k=0,maxx=0;
	for(auto i=mp.begin();i!=mp.end();i++){
		if(i->second>maxx){
		    maxx=i->second;
		    k=i->first;
		}
	}
	ll ans=n-maxx;
//	if(a[1]==a[n]&&mp[k]==maxx&&k!=a[1]){
//		ans--;
//	}
	cout<<ans;
	return 0;
}

第4题 植物保留【算法赛】

题目传送门

这个题是一个二分题，不过群里面也听说有人用贪心来做了，但是一眼就看出是贪心，我就没想到其他方法了，直接二分答案，若答案能够成立（就是说这个值的数的树能够成立）就增大l，使得答案变大继续判断，否则r变小继续判断：

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const ll N = 1e5 + 5;
const ll inf = 1e18;

ll a[N];
ll n, m;

bool check(ll mid) {
    ll segments = 1;
    ll last_position = a[1];

    for (int i = 2; i <= n; ++i) {
        if (a[i] - last_position >= m) {
            segments++;
            last_position = a[i];
        }
    }

    return segments >= mid;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }

    sort(a + 1, a + n + 1);

    ll l = 1, r = n;
    ll ans = 0;

    while (l <= r) {
        ll mid = (l + r) / 2;
        if (check(mid)) {
            ans = mid;
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }

    cout << ans << "\n";

    return 0;
}

第5题 龙骑士军团【算法赛】

题目传送门

题目大意：找到[a,b]里面的一个起点，[c,d]里面的一个终点，使得这个区间和最大。

因为在打游戏，做这题的时候没时间，粗略看了一下，是一个线段树问题，前面我也发了6篇线段树，所以能轻松看出来，不过由于各种原因调了好久（输出提示的地方忘记删了）也相当于给大家提个醒，下次一定要注意了。

思路如下：说到区间和，不得不想到前缀和，但是前缀和是sum[l,r]=a[r]-a[l-1];这样的话不难想到将前缀和数组作为线段树的“根”，维护一个最大值和最小值的线段树，然后直接在左区间找最小值，右区间找最大值，两个相减就得到了，但是，需要注意这个a[l-1]，左区间的最后一个不能被取到，而左区间的前一个能被取到，这样的话就难办了，而我思考后想到——可以将线段树整体右移动一格，然后呢就空出第一个位置来了，查询的时候就用

ll str=query(1,1,n+1,l-1,r-1);

 ll end=queryy(1,1,n+1,l,r);

但是需要明白，l和r需要自加一下，因为整体右移动了，接下来直接看代码就行。

这个线段树比较好写，相较于之前的几棵树，这个没有laze和down函数，也没有数据更新函数，比较轻松的： 

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const ll N = 2e5 + 5;
const ll inf = 1e18;

ll tree_max[N<<2],tree_min[N<<2],a[N];

ll lson(ll i){
	return i<<1;
}
ll rson(ll i){
	return i<<1|1;
}
void up(ll i){
	tree_max[i]=max(tree_max[lson(i)],tree_max[rson(i)]);
	tree_min[i]=min(tree_min[lson(i)],tree_min[rson(i)]);
}
void build(ll i,ll pl,ll pr){
	if(pl==pr){
		tree_max[i]=tree_min[i]=a[pl];
		return;
	}
	ll mid=(pl+pr)>>1;
	build(lson(i),pl,mid);
	build(rson(i),mid+1,pr);
	up(i);
}

ll query(ll i,ll pl,ll pr,ll L,ll R){
	if(L<=pl&&pr<=R){
		return tree_min[i];
	}
	ll mid=(pl+pr)>>1;
	ll minn=inf;
	if(L<=mid){
		minn=min(minn,query(lson(i),pl,mid,L,R));
	}
	if(R>mid){
		minn=min(minn,query(rson(i),mid+1,pr,L,R));
	}
	return minn;
}

ll queryy(ll i,ll pl,ll pr,ll L,ll R){
	if(L<=pl&&pr<=R){
		return tree_max[i];
	}
	ll mid=(pl+pr)>>1;
	ll maxx=-inf;
	if(L<=mid){
		maxx=max(maxx,queryy(lson(i),pl,mid,L,R));
	}
	if(R>mid){
		maxx=max(maxx,queryy(rson(i),mid+1,pr,L,R));
	}
	return maxx;
}

int main() {
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int n,q;
    cin>>n>>q;
    for(int i=2;i<=n+1;i++){
      cin>>a[i];
      a[i]+=a[i-1];
    }
    build(1,1,n+1);
    while(q--){
      ll l,r;
      cin>>l>>r;
      l++,r++;
      ll str=query(1,1,n+1,l-1,r-1);
      cin>>l>>r;
      l++,r++;
      ll end=queryy(1,1,n+1,l,r);
      cout<<end-str<<'\n';
    }
    return 0;
}

因为我每周六都要去打游戏，所以算法赛没多少时间写，这次算法赛感觉还行，好久没写这种题了，连二分的那个题都写了6次才过，废了，后面的题没时间看，感觉应该也还行，能写，今天先发这几个题，后面的3个题我会陆续发，可以收藏期待一下吖，那么今天学习到此结束，拜拜吖！

第6题 热身操领队【算法赛】

题目传送门

这题我能看出来是线段树，但是不太会做，尝试无果后请教了学长，然后学长轻轻松松解出来了，不得不说学长强的可怕，看了学长思路后，我也尝试重新写了一下，也理解了是什么意思，不过下次再出我也不一定做得出来，应该是叫做离散化吧，没听说过，这题语言不好讲，直接看代码好一点：

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
const ll N = 2e5 + 5;

ll tree[N << 2], rk[N], a[N], v[N], n;

ll lson(ll i) {
	return i << 1;
}
ll rson(ll i) {
	return i << 1 | 1;
}

void up(ll i) {
	tree[i] = tree[lson(i)] + tree[rson(i)];
}

void updata(ll i, ll pl, ll pr, ll L, ll R, ll a) {
	if (pl == pr) {//给每次进来的人加上去，进来多少人就加多少
	
		tree[i] += a;
		return ;
	}
	ll mid = (pl + pr) >> 1;
	if (L <= mid) {//单点更新
		updata(lson(i), pl, mid, L, R, a);
	} else {
		updata(rson(i), mid + 1, pr, L, R, a);
	}
	up(i);
}

ll query(ll i, ll pl, ll pr, ll L, ll R) {//线段树板子，用来查询区间和
	if (L <= pl && pr <= R) {
		return tree[i];
	}
	ll mid = (pl + pr) >> 1;
	ll ans = 0;
	if (L <= mid) {
		ans += query(lson(i), pl, mid, L, R);
	}
	if (R > mid) {
		ans += query(rson(i), mid + 1, pr, L, R);
	}
	return ans;
}

ll chek(ll num) {//二分查找中位数
// 如果左边区间和大于中位数，说明中位数在左边，反之在右边
	int l = 1, r = n;
	while (l <= r) {
		int mid = l + r >> 1;
		if (query(1, 1, n, 1, mid) >= num) {
			r = mid - 1;
		} else l = mid + 1;
	}
	return l;
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> v[i] >> a[i];
		rk[i] = v[i];
	}
	sort(rk + 1, rk + 1 + n);
	int cont = 0;
	for (int i = 1; i <= n; i++) {
		if (rk[i] != rk[i - 1]) {
			rk[++cont] = rk[i];
		}//将身高的类型统计出来，即身高的“排名”
	}
	for (int i = 1; i <= n; i++) {
		//pos查找该更新什么地方
		int pos = lower_bound(rk + 1, rk + 1 + cont, v[i]) - rk;
		updata(1, 1, n, pos, pos, a[i]);//在该身高位置处更新数据（累加）
		if (tree[1] % 2) {
			cout << rk[chek(tree[1] / 2 + 1)] << '\n';
		} else {
			cout << rk[min(chek(tree[1] / 2), chek(tree[1] / 2 + 1))] << '\n';
		}
	}
	return 0;
}

很累啊，难想出来的，看来我实力还不够，差得远哭哭哭。 

第7题 单词博弈【算法赛】

题目传送门​​​​​​​

这个题就是一个大模拟题，我写了好久，一直只能通过80%，写的我裂开了，最后借鉴了一位大佬的代码，感觉都是纯模拟，不知道为什么我的就过不了，这是我的代码（没AC版）：

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const ll N = 1e5 + 5;

struct cmp {
    bool operator()(const string& s1, const string& s2) const {
        // 自定义的比较逻辑
        return s1 > s2;
    }
};

priority_queue<string, vector<string>, cmp>Lan, Qiao;

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    ll n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        string a;
        cin >> a;
        Lan.push(a);
    }
    for (int i = 1; i <= m; i++) {
        string a;
        cin >> a;
        Qiao.push(a);
    }
    string now = Lan.top();
    Lan.pop();
    ll i = 0;
    while (1) {
        i++;
        if (i % 2) {
            if(Qiao.empty()){
                cout<<"L";
                return 0;
            }
            while (!Qiao.empty()) {
                string temp = Qiao.top();
                Qiao.pop();
                m--;
                if (temp > now) {
                    if (temp[0] == now[0] || temp[0] == now[0] + 1) {
                        now = temp;
                        break;
                    } else {
                        cout << "L";
                        return 0;
                    }
                } else {
                    while (!Qiao.empty() && temp <= now) {
                        temp = Qiao.top();
                        Qiao.pop();
                        m--;
                    }
                    if (temp[0] == now[0] || temp[0] == now[0] + 1) {
                        now = temp;
                        break;
                    } else {
                        cout << "L";
                        return 0;
                    }
                }
            }
        } else {
            if(Lan.empty()){
                cout<<"Q";
                return 0;
            }
            while (!Lan.empty()) {
                string temp = Lan.top();
                Lan.pop();
                n--;
                if (temp > now) {
                    if (temp[0] == now[0] || temp[0] == now[0] + 1) {
                        now = temp;
                        break;
                    } else {
                        cout << "Q";
                        return 0;
                    }
                } else {
                    while (!Lan.empty() && temp <= now) {
                        temp = Lan.top();
                        Lan.pop();
                        n--;
                    }
                    if (temp[0] == now[0] || temp[0] == now[0] + 1) {
                        now = temp;
                        break;
                    } else {
                        cout << "Q";
                        return 0;
                    }
                }
            }
        }
        if (n == 0) {
            if (!Qiao.empty()) {
                string temp = Qiao.top();
                Qiao.pop();
                m--;
                if (temp > now) {
                    if (temp[0] == now[0] || temp[0] == now[0] + 1) {
                        cout << "Q";
                        return 0;
                    }
                } else {
                    while (!Qiao.empty() && temp <= now) {
                        temp = Qiao.top();
                        Qiao.pop();
                        m--;
                    }
                    if (temp[0] == now[0] || temp[0] == now[0] + 1) {
                        cout << "Q";
                        return 0;
                    } else {
                        cout << "L";
                        return 0;
                    }
                }
            } else {
                cout << "L";
                return 0;
            }
        }

        //
        if (m == 0) {
            if (!Lan.empty()) {
                string temp = Lan.top();
                Lan.pop();
                n--;
                if (temp > now) {
                    if (temp[0] == now[0] || temp[0] == now[0] + 1) {
                        cout << "L";
                        return 0;
                    }
                } else {
                    while (!Lan.empty() && temp <= now) {
                        temp = Lan.top();
                        Lan.pop();
                        n--;
                    }
                    if (temp[0] == now[0] || temp[0] == now[0] + 1) {
                        cout << "L";
                        return 0;
                    } else {
                        cout << "Q";
                        return 0;
                    }
                }
            } else {
                cout << "Q";
                return 0;
            }
        }
    }
    return 0;
}

可以看到我写了160多行代码，好多地方都判断了，就是过不了，难受死了，如果有知道我错什么地方的，欢迎直接评论告诉我。

接下来是大佬的AC代码：

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5;

string Lan[N], Qiao[N];

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> Lan[i];
    }
    
    for (int i = 0; i < m; i++) {
        cin >> Qiao[i];
    }
    
    int x1 = 1, x2 = 0;

    while (x1 <= n && x2 < m) {
        if ((Qiao[x2] > Lan[x1 - 1] && Qiao[x2][0] == Lan[x1 - 1][0]) ||
            (Qiao[x2] > Lan[x1 - 1] && Qiao[x2][0] == (char)(Lan[x1 - 1][0] + 1))) {
            x1++;
        } else {
            x2++;
            continue;
        }
        
        if ((Lan[x1 - 1] > Qiao[x2] && Lan[x1 - 1][0] == Qiao[x2][0]) ||
            (Lan[x1 - 1] > Qiao[x2] && Lan[x1 - 1][0] == (char)(Qiao[x2][0] + 1))) {
            x2++;
        } else {
            while (x1 <= n) {
                if ((Lan[x1 - 1] > Qiao[x2] && Lan[x1 - 1][0] == Qiao[x2][0]) ||
                    (Lan[x1 - 1] > Qiao[x2] && Lan[x1 - 1][0] == (char)(Qiao[x2][0] + 1))) {
                    x2++;
                    break;
                } else {
                    x1++;
                }
            }
        }
    }

    if (x1 == n + 1) {
        cout << "Q" << endl;
    } else if (x2 == m) {
        cout << "L" << endl;
    }
    
    return 0;
}

这个我感觉也是模拟，不知道为什么就可以过了555。

标签：Lan,Qiao,int,题解,ll,cin,蓝桥,发上去,x1
From： https://blog.csdn.net/2401_82683560/article/details/140071900

相关文章

  • 流固耦合可能遇到的问题解决办法
    (纯私人经验)双向流固耦合中出现的一些问题及解决方法:1.出现负网格，可以加密网格，可以去提升网格质量，六面体网格尽量用icemcfd画，四面体就用自带的完全可以，可以增加刚度降低变形量从而消除负网格，可以调整弹簧光顺参数，一般经验取值一个0.6一个0.5，可以缩小时间步长，还可以在fluent......
  • 题目 3293: 蓝桥杯2024年第十五届决赛真题-数位翻转
    https://www.dotcpp.com/oj/problem3293.html 题目描述小明创造了一个函数f(x)用来翻转x的二进制的数位（无前导0）。比如f(11)=13，因为11=(1011)2，将其左右翻转后，变为13=(1101)2；再比如f(3)=3，f(0)=0，f(2)=f(4)=f(8)=1等等。小明随机出了一个长度为......
  • 洛谷 P5723 【深基4.例13】质数口袋 题解
    题面传送门观察题目，我们可以看到这是一道朴素的，判断质数的一道题目。何为质数？质数就是除了111和这个本身，没有其他因数的数。特别的，......
  • AT_arc180_a [ARC180A] ABA and BAB 题解
    思路首先一个浅显易得的结论，当\(A\)或\(B\)连续出现时，我们可以将它们分成两段，每段都可以看作一个独立事件，结果数只和每个独立事件的样本点有关。我们设独立事件共有\(tot\)个，每个独立事件的样本点为\(w_i\)，则显然有\(ans=\prod_{i=1}^{tot}w_i\)。接下来该找\(w_i\)......
  • 题解 - 数字计数
    题目思路简析正解是数位dp，但是我不太会，所以我打分块。考虑从\(10^6\)到\(2\times10^6\)和从\(3\times10^6\)到\(4\times10^6\)，其中真正的区别只有观察到数据范围是\(10^{12}\)，分为一些块，每块长\(10^6\)会比较均衡，所以共有\(10^6\)个块。最差情况是\(n=10^6+1......
  • 题解 - 数字计数
    题目思路简析正解是数位dp，但是我不太会，所以我打分块。考虑从\(10^6\)到\(2\times10^6\)和从\(3\times10^6\)到\(4\times10^6\)，其中真正的区别只有观察到数据范围是\(10^{12}\)，分为一些块，每块长\(10^6\)会比较均衡，所以共有\(10^6\)个块。最差情况是\(n=10^6+1......
  • 07/02/2024 融合热身赛赛后总结&题解
    一、总体情况考试一共有五道题。这次考试失误严重，C题非常水的一道题做了快两个小时，严重影响了心态和做其它题的时间。最终3个小时只做了A,C......
  • [JLU] 数据结构与算法上机题解思路分享-第三次上机
    前言首先，请务必自己尽全力尝试实现题目，直接看成品代码，思维就被拘束了，也很容易被查重。这里只是思路解析的博客，代码仓库在JLU_Data_Structures_Record希望你能在这里找到你想要的:)正文A图的创建分数10作者朱允刚单位吉林大学请编写程序创建一个有向图。有向图中包含......
  • AT_tdpc_number 数 题解
    题目传送门前置知识数位DP|记忆化搜索解法本题的提交在luogu上挂了，建议去原站或Vjudge上提交。基础数位DP，记录当前位置、已填的数码之和，接着记忆化搜索即可。需要注意的是\(0\bmodd=0\)，如果写得不太好看（未处理前导零）的话需要减去其贡献。代码#include<bits/......
  • SP8177 JZPEXT - Beautiful numbers EXTREME 题解
    题目传送门前置知识数位DP|同余解法同余的传递性：若\(\begin{cases}a,b\in\mathbf{Z}\\p,q\in\mathbb{N}^{*}\\q|p\end{cases}\)，则当\(a\equivb\pmod{p}\)时有\(a\equivb\pmod{q}\)。故在本题中\(\bmod\)各非零数码均等于\(0\)等价于\(\bmod\)各......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99