第 1 场 算法季度赛 蓝桥搜狐畅游(1~5 , 7）

2023-12-29 18:52
文章标签 算法 蓝桥 搜狐 季度 畅游

本文主要是介绍第 1 场 算法季度赛 蓝桥搜狐畅游(1~5 , 7），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1、水题

2、树上dp

3、模拟

4、概率

5、拆位

6、（是没学过的东西了...）

7、组合数学

1. 新年快乐【算法赛】

        

直接模拟

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

 2. 蓝桥圣诞树【算法赛】

思路：其实就是连通块大小小于3。定义dp[u]代表了u的子树中，包含了u这个结点的连通块的大小。 状态转移方程就呼之欲出：dp[u] = 1 + \sum dp[v]，其中v是u的孩子且跟u颜色相同。在树上跑一边dfs把所有节点的dp值求出来即可。然后再看有无大于3的连通块。

        

#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define pb push_back
#define x first
#define y second 
#define endl '\n'
const LL maxn = 4e05+7;
const LL N = 5e05+10;
const LL mod = 1e09+7;
const int inf = 0x3f3f3f3f;
const LL llinf = 5e18;
typedef pair<int,int>pl;
priority_queue<LL , vector<LL>, greater<LL> >mi;//小根堆
priority_queue<LL> ma;//大根堆
LL gcd(LL a, LL b){return b > 0 ? gcd(b , a % b) : a;
}LL lcm(LL a , LL b){return a / gcd(a , b) * b;
}
int n , m;
vector<int>a(N , 0);
void init(int n){for(int i = 0 ; i <= n ; i ++){a[i] = 0;}
}
struct HLD {//轻重链剖分int n;std::vector<int> siz, top, dep, parent, in, out, seq , color , dp;//子树大小 所在重链的顶部节点 深度 父亲 子树DFS序的起点 子树DFS序的终点std::vector<std::vector<int>> adj;int cur = 1;HLD() {}HLD(int n) {init(n);}void init(int n) {this->n = n;siz.resize(n);top.resize(n);dep.resize(n);parent.resize(n);in.resize(n);out.resize(n);seq.resize(n);color.resize(n);dp.resize(n);cur = 0;adj.assign(n, {});}void addEdge(int u, int v) {adj[u].push_back(v);adj[v].push_back(u);}void work(int root = 1) {top[root] = root;dep[root] = 0;parent[root] = -1;dfs1(root);dfs2(root);}void dfs1(int u) {if (parent[u] != -1) {adj[u].erase(std::find(adj[u].begin(), adj[u].end(), parent[u]));}siz[u] = 1;for (auto &v : adj[u]) {parent[v] = u;dep[v] = dep[u] + 1;dfs1(v);siz[u] += siz[v];if (siz[v] > siz[adj[u][0]]) {std::swap(v, adj[u][0]);}}}void dfs2(int u) {in[u] = ++cur;seq[in[u]] = u;dp[u] = 1;for (auto v : adj[u]) {top[v] = v == adj[u][0] ? top[u] : v;dfs2(v);if(color[u] == color[v]){dp[u] += dp[v];}}out[u] = cur;}int lca(int u, int v) {while (top[u] != top[v]) {if (dep[top[u]] > dep[top[v]]) {u = parent[top[u]];} else {v = parent[top[v]];}}return dep[u] < dep[v] ? u : v;}int dist(int u, int v) {return dep[u] + dep[v] - 2 * dep[lca(u, v)];}int jump(int u, int k) {if (dep[u] < k) {return -1;}int d = dep[u] - k;while (dep[top[u]] > d) {u = parent[top[u]];}return seq[in[u] - dep[u] + d];}bool isAncester(int u, int v) {//是否为祖先return in[u] <= in[v] && in[v] < out[u];}int rootedParent(int u, int v) {std::swap(u, v);if (u == v) {return u;}if (!isAncester(u, v)) {return parent[u];}auto it = std::upper_bound(adj[u].begin(), adj[u].end(), v, [&](int x, int y) {return in[x] < in[y];}) - 1;return *it;}int rootedSize(int u, int v) {if (u == v) {return n;}if (!isAncester(v, u)) {return siz[v];}return n - siz[rootedParent(u, v)];}int rootedLca(int a, int b, int c) {return lca(a, b) ^ lca(b, c) ^ lca(c, a);}
}hld;
void solve() 
{cin >> n;string s;cin >> s;hld.init(n + 5);for(int i = 1 ; i <= n ; i ++){hld.color[i] = s[i - 1] - '0';}for(int i = 1 ; i < n ; i ++){int u , v;cin >> u >> v;hld.addEdge(u , v);}hld.work();for(int i = 1 ; i <= n ; i ++){if(hld.dp[i] >= 3){cout <<"NO\n";return;}}cout <<"YES\n";
}            
int main() 
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cout.precision(10);int t=1;cin>>t;while(t--){solve();}return 0;
}

3. 空间复杂度【算法赛】 

        

模拟题，注意数据大小。

#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define pb push_back
#define x first
#define y second 
#define int long long
#define endl '\n'
const LL maxn = 4e05+7;
const LL N = 5e05+10;
const LL mod = 1e09+7;
const int inf = 0x3f3f3f3f;
const LL llinf = 5e18;
typedef pair<int,int>pl;
priority_queue<LL , vector<LL>, greater<LL> >mi;//小根堆
priority_queue<LL> ma;//大根堆
LL gcd(LL a, LL b){return b > 0 ? gcd(b , a % b) : a;
}LL lcm(LL a , LL b){return a / gcd(a , b) * b;
}
int n , m;
vector<int>a(N , 0);
void init(int n){for(int i = 0 ; i <= n ; i ++){a[i] = 0;}
}
void solve() 
{cin >> n;string s;cin >> s;cin >> m;map<string , int> mp;mp["MB"] = 2;mp["KB"] = 1;mp["B"] = 0;int res = n * pow(1024 , mp[s]);cout << res / m << endl;
}            
signed main() 
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cout.precision(10);int t=1;cin>>t;while(t--){solve();}return 0;
}

 

 4. 开关【算法赛】

        

思路：先想最暴力的做法：对于处于(i , j)坐标的灯而言，会被第i次操作1和第j次操作2所影响。最终该灯亮的情况共有两种：1、触发了操作1且没有触发操作2。2、没触发操作1且触发了操作2。那么它最终亮的概率是\frac{a_{i}}{b_{i}}* \frac{1 - c_{j}}{d_{j}} + \frac{1-a_{i}}{b_{i}}* \frac{ c_{j}}{d_{j}}。 对于每个灯都求一遍的话时间复杂度为O(N^{2})。

        现考虑如何去优化，可以发现：将所有灯的概率全加起来的式子是可以合并同类项的，即\sum_{i = 1}^{n} (\frac{a_{i}}{b_{i}}*\sum _{j = 1}^{n} \frac{1 - c_{j}}{d_{j}}) + \sum_{i = 1}^{n}(\frac{1-a_{i}}{b_{i}}* \sum _{j = 1}^{n}\frac{ c_{j}}{d_{j}})。因此只需要预处理出\sum _{j = 1}^{n} \frac{1 - c_{j}}{d_{j}}和\sum _{j = 1}^{n} \frac{c_{j}}{d_{j}}。然后再遍历所有的i即可。这样做复杂度是O(N)的。

        

#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define pb push_back
#define x first
#define y second 
#define int long long
#define endl '\n'
const LL maxn = 4e05+7;
const LL N = 5e05+10;
const LL mod = 998244353;
const int inf = 0x3f3f3f3f;
const LL llinf = 5e18;
typedef pair<int,int>pl;
priority_queue<LL , vector<LL>, greater<LL> >mi;//小根堆
priority_queue<LL> ma;//大根堆
LL qpow(LL a , LL b)//快速幂
{LL sum=1;while(b){if(b&1){sum=sum*a%mod;}a=a*a%mod;b>>=1;}return sum;
}
LL gcd(LL a, LL b){return b > 0 ? gcd(b , a % b) : a;
}LL lcm(LL a , LL b){return a / gcd(a , b) * b;
}void solve() 
{int n;cin >> n;n++;vector<int>a(n , 0) , b(n , 0) , c(n , 0) , d(n , 0);for(int i = 1 ; i < n ; i ++){cin >> a[i];}for(int i = 1 ; i < n ; i ++){cin >> b[i];}for(int i = 1 ; i < n ; i ++){cin >> c[i];}for(int i = 1 ; i < n ; i ++){cin >> d[i];}vector<int>ab(n , 0) , cd(n , 0) ,ba(n , 0) , dc(n , 0);for(int i = 1 ; i < n ; i ++){ab[i] = a[i] * qpow(b[i] , mod - 2);cd[i] = c[i] * qpow(d[i] , mod - 2);ba[i] = (b[i] - a[i]) * qpow(b[i] , mod - 2);dc[i] = (d[i] - c[i]) * qpow(d[i] , mod - 2);ab[i] %= mod;cd[i] %= mod;ba[i] %= mod;dc[i] %= mod;}vector<int>sum1(n , 0) , sum2(n , 0);for(int i = 1 ; i < n ; i ++){sum1[i] = sum1[i - 1] + cd[i];sum2[i] = sum2[i - 1] + dc[i];sum1[i] %= mod;sum2[i] %= mod;}//对于第i行的灯而言，有两种方案使得其亮：ab && !cd  !ab && cdint ans = 0;for(int i = 1 ; i < n ; i ++){ans += ab[i] * sum2[n - 1];ans %= mod;ans += ba[i] * sum1[n - 1];ans %= mod;}cout << ans;
}            
signed main() 
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cout.precision(10);int t = 1;while(t--){solve();}return 0;
}

5. 异或与求和【算法赛】 

        

题意：某不知名高手曾经说过，对于所有情况求和，采用定1求1的思考方式，即遍历右端点，考虑如何O(1)的去处理每个右端点。

        由于i_{1}i_{2}与i_{3}i_{4}不存在关联关系，因此此题可以转化为求解\sum a_{i_{1}} \oplus a_{i_{2}} + \sum a_{i_{3}} \oplus a_{i_{4}}。

然后可以先求\sum a_{i_{1}} \oplus a_{i_{2}}，再求\sum a_{i_{3}} \oplus a_{i_{4}}，过程是差不多的。

        至此，本题其实跟普通的求解 \sum a_{i_{1}} \oplus a_{i_{2}} 差不多，只不过(a_{i_{1}} ,a_{i_{2}})这组数对在求和中不止出现了一次，而是总共出现了(a_{i_{3}} , a_{i_{4}})所能形成的数对的个数。

        然后就是普通的拆位求异或和。

#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define pb push_back
#define x first
#define y second 
#define int long long
#define endl '\n'
const LL maxn = 4e05+7;
const LL N = 5e05+10;
const LL mod = 998244353;
const int inf = 0x3f3f3f3f;
const LL llinf = 5e18;
typedef pair<int,int>pl;
priority_queue<LL , vector<LL>, greater<LL> >mi;//小根堆
priority_queue<LL> ma;//大根堆
LL qpow(LL a , LL b)//快速幂
{LL sum=1;while(b){if(b&1){sum=sum*a%mod;}a=a*a%mod;b>>=1;}return sum;
}
LL gcd(LL a, LL b){return b > 0 ? gcd(b , a % b) : a;
}LL lcm(LL a , LL b){return a / gcd(a , b) * b;
}
int dp1[32] , dp0[32];
void solve() 
{int n;cin >> n;vector<int>a(n , 0);for(int i = 0 ; i < n ; i ++){cin >> a[i];}vector<int>dp(n , 0);int cnt0 = 0 , cnt1 = 0;int ans = 0;for(int j = 0 ; j < 32 ; j ++){cnt0 = 0 , cnt1 = 0;for(int i = 0 ; i < n ; i ++){if((a[i] >> j) & 1){dp[i] = cnt0; cnt1 ++;}else{dp[i] = cnt1;cnt0 ++;}dp[i] %= mod;	int res = n - i - 1;res = res * (res - 1) / 2;res %= mod;ans += ((dp[i] * (1 << j)) % mod) * res;ans %= mod;}}for(int j = 0 ; j < 32 ; j ++){cnt0 = 0 , cnt1 = 0;for(int i = n - 1 ; i >= 0 ; i --){if((a[i] >> j) & 1){dp[i] = cnt0; cnt1 ++;}else{dp[i] = cnt1;cnt0 ++;}dp[i] %= mod;	int res = i;res = res * (res - 1) / 2;res %= mod;ans += ((dp[i] * (1 << j)) % mod)* res;ans %= mod;}//cout << ans << endl;}
//	cout << dp0[1];cout << ans;
}            
signed main() 
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cout.precision(10);int t = 1;while(t--){solve();}return 0;
}

7. 集合统计【算法赛】 

        

思路：将有关联的（相互牵制的）数放在到一个集合。然后根据乘法原理，最终方案数为所有集合能够拿出的方案数的乘积，最后再减去空集即最终答案。

        直接看例子1 3 2 ， 可以发现：（1 ， 2）是相互牵制的一组数（有1就不能有2，有2就不能有1）共有3种取数方案，而（3）是单独的数，这个集合共有2种取数方案。因此包含空集的方案共有3 * 2 = 6 个，再减去1就是答案5了。

        然后再看(1 4 2)这个例子，可以发现（1 ， 2 ， 4）这三个数是相互牵制的，但是需要注意的是：1、4是可以同时取到的，因此这个集合共有5种取数方案。1 4 2 最终的答案也就是9。

        接下来考虑如果一个集合当中有n个数，那么能拿出多少种方案？可以发现，这就是一个简单的dp问题，设dp[i]代表了集合中共有i个元素，能够选择的非空方案数。若不能和前一个数同时选dp[i] = dp[i - 1] + 1（不选择自己 + 只选择自己）。同时又能和前一个数以外的数同时选，因此dp[i] = dp[i]+ dp[i - 2]。

        解决完一个集合的方案数，接下来考虑总共有多少个集合：[r/k + 1 , r]之间的数，其都只是一个元素的集合。同理，[r/k^{2} + 1, r/k]之间的数，都是只有两个元素的集合...以此类推。但是需要注意的是：例如题中1 3 2 这个例子，按照上述思路，[2 , 3] 之间的数都是只有一个元素的集合，那么只有一个元素的集合数应该为2，但是事实并非如此，这是因为2这个元素实际上包含在（1,2）这个集合当中了。因此要求真正的集合数量，还需要减去重复的数。

        假设一个集合元素为(a , ka , k^2a),那么ka会出现在集合大小为2的范围内，k^2a会出现在集合大小为1的范围内，这些都是重复的，需要减去的。因此可以得出，假设集合大小为x的集合共有y个，那么所有集合大小小于x的集合数都要减去y，这样才能避免重复。

        解决完集合数量之后就是用快速幂快速求解了。

#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define pb push_back
#define x first
#define y second 
#define int long long
#define endl '\n'
const LL maxn = 4e05+7;
const LL N = 5e05+10;
const LL mod = 998244353;
const int inf = 0x3f3f3f3f;
const LL llinf = 5e18;
typedef pair<int,int>pl;
priority_queue<LL , vector<LL>, greater<LL> >mi;//小根堆
priority_queue<LL> ma;//大根堆
LL qpow(LL a , LL b)//快速幂
{LL sum=1;while(b){if(b&1){sum=sum*a%mod;}a=a*a%mod;b>>=1;}return sum;
}
LL gcd(LL a, LL b){return b > 0 ? gcd(b , a % b) : a;
}LL lcm(LL a , LL b){return a / gcd(a , b) * b;
}
int inv[200];
void init(){inv[0] = 1;for(int i = 1 ; i < 200 ; i ++){inv[i] = inv[i - 1] + 1;if(i >= 2){inv[i] += inv[i - 2];}inv[i] %= mod;}
}
void solve() 
{int l , r , k;cin >> l >> r >> k;if(k == 1){cout << 0 << endl;		}else{int x = r;int pre = r;vector<int>t;while(x >= l){//[x + 1 , pre] 都是处于一个集合的x /= k;t.pb(pre - max(x , l - 1));pre = x;}int len = t.size();for(int i = len - 1 ; i >= 0 ; i --){for(int j = i - 1 ; j >= 0 ; j --){t[j] -= t[i];}}int ans = 1;for(int i = 0 ; i < len ; i ++){ans *= qpow(inv[i] + 1 , t[i]);ans %= mod;}cout << (ans - 1 + mod) % mod << endl;}
}            
signed main() 
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cout.precision(10);int t = 1;init();cin >> t;while(t--){solve();}return 0;
}

这篇关于第 1 场 算法季度赛 蓝桥搜狐畅游(1~5 , 7）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/550372。

相关文章

不懂推荐算法也能设计推荐系统

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例，告诉我们不懂推荐算法的产品，也能从产品侧出发， 设计出一款不错的推荐系统。 相信很多新手产品，看到算法二字，多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法（注：传统是指科班出身的产品都会接触过）。但对于推荐算法，多数产品对着网上搜到的资源，都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后，更是加大了理解的难度。 但，不了解推荐算法，就无法做推荐系
阅读更多...
康拓展开（hash算法中会用到）

康拓展开（hash算法中会用到）

康拓展开是一个全排列到一个自然数的双射（也就是某个全排列与某个自然数一一对应） 公式： X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。（a[i]在不同应用中的含义不同）； 典型应用： 计算当前排列在所有由小到大全排列中的顺序，也就是说求当前排列是第
阅读更多...
csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

这是一道扩展欧几里得算法的简单应用题，这题是在湖南多校训练赛中队友ac的一道题，在比赛之后请教了队友，然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意：把题意转变下就变成了：求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点：求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个
阅读更多...
综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动，这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升：减少抖动，提高图像的清晰度和细节表现力，使得监控画面更加真实可信。 - 细节增强：在低光条件下，抖
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)

poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大，用原来的O（n^2）会爆。 小白上的O(n^2)解法代码：TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO
阅读更多...
秋招最新大模型算法面试，熬夜都要肝完它

秋招最新大模型算法面试，熬夜都要肝完它

💥大家在面试大模型LLM这个板块的时候，不知道面试完会不会复盘、总结，做笔记的习惯，这份大模型算法岗面试八股笔记也帮助不少人拿到过offer ✨对于面试大模型算法工程师会有一定的帮助，都附有完整答案，熬夜也要看完，祝大家一臂之力 这份《大模型算法工程师面试题》已经上传CSDN，还有完整版的大模型 AI 学习资料，朋友们如果需要可以微信扫描下方CSDN官方认证二维码免费领取【保证100%免费
阅读更多...
dp算法练习题【8】

dp算法练习题【8】

不同二叉搜索树 96. 不同的二叉搜索树 给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。 示例 1： 输入：n = 3输出：5 示例 2： 输入：n = 1输出：1 class Solution {public int numTrees(int n) {int[] dp = new int
阅读更多...
Codeforces Round #240 (Div. 2) E分治算法探究1

Codeforces Round #240 (Div. 2) E分治算法探究1

Codeforces Round #240 (Div. 2) E  http://codeforces.com/contest/415/problem/E 2^n个数，每次操作将其分成2^q份，对于每一份内部的数进行翻转(逆序)，每次操作完后输出操作后新序列的逆序对数。 图一：  划分子问题。 图二： 分而治之，=>  合并 。 图三： 回溯：
阅读更多...
最大公因数：欧几里得算法

最大公因数：欧几里得算法

简述         求两个数字 m和n 的最大公因数，假设r是m%n的余数，只要n不等于0，就一直执行 m=n，n=r 举例 以18和12为例 m n r18 % 12 = 612 % 6 = 06 0所以最大公因数为：6 代码实现 #include<iostream>using namespace std;/
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2