牛客寒假算法集训营第六场补题题解

2024-06-13 04:18
文章标签 算法 牛客 题解 第六场 补题 寒假 集训营

本文主要是介绍牛客寒假算法集训营第六场补题题解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

网址：https://ac.nowcoder.com/acm/contest/9986

G机器人

知识点：状压dp+__int128
__int128精度比unsigned longlong 大，但是对于cin，cout，printf，scanf都不支持，输入输出模板如下：

inline __int128 read(){//输入模板 __int128 x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;
}
inline void print(__int128 x){//输出模板 if(x<0){putchar('-');x=-x;}if(x>9) print(x/10);putchar(x%10+'0');
}

代码：

#include<bits/stdc++.h>
#include <algorithm>
#include<iostream>
#include <stdio.h>
using namespace std;
const int maxn=5e3+7;
const int base=131;
typedef long long ll;
#define pi acos(-1)
#define INF 0x3f3f3f3f
#define mod 998244353
const int inf=1<<30;
__int128 dp[1<<22]; 
int a[25],b[25];inline void print(__int128 x){//输出模板 if(x<0){putchar('-');x=-x;}if(x>9) print(x/10);putchar(x%10+'0');
}int main()
{int n, m;cin >> n >> m;for (int i = 0; i < n; i++) {cin >> a[i] >> b[i];}for (int i = 0; i < n; i++) dp[1 << i] = a[i] * m + b[i];for (int i = 0; i < (1 << n); i++) {//枚举开始的机器人的使用状态for (int k = 0; k < n; k++) {if (!((i >> k) & 1)) {//第k位的机器人未被使用dp[i | (1 << k)] = max(dp[i | (1 << k)], dp[i] * a[k] + b[k]);}}}print(dp[(1 << n) - 1]);return 0;
}

E网格

知识点：动态规划
题解：dp，另外阅读理解？，题目看了半天没看懂。
选择两个，左右和上下各选择一次，可以进行两次dp。
在这里插入图片描述
上下时同理

代码：

#include<bits/stdc++.h>
#include<iostream>
#include <stdio.h>
using namespace std;
const int maxn=1005;
const int base=131;
typedef long long ll;
#define pi acos(-1)
#define INF 0x3f3f3f3f
#define mod 998244353
const int inf=1<<30;
ll a[maxn][maxn];
ll dp[maxn][maxn][2];
ll dp2[maxn][maxn][2];ll popcnt(ll x)
{ll cnt = x;//x+popcnt（x）while(x) {if(x & 1)cnt++;x >>= 1;}return cnt;
}int main()
{int n,m;cin>>n>>m;for(int i = 1; i <= n ;i++)for(int j = 1; j <= m; j++)cin>>a[i][j];ll ans = 0;for(int i = 1; i <= n; i++){for(int j = 2; j <= m ;j++ ){dp[i][j][0] = max(dp[i][j-1][0],dp[i][j-1][1] + popcnt(a[i][j] ^ a[i][j-1]));dp[i][j][1] = max(dp[i][j-1][1],dp[i][j-1][0]);}ans += max(dp[i][m][0],dp[i][m][1]);}for(int j = 1; j <= m; j++){for(int i = 2; i <= n ;i++ ){dp2[i][j][0] = max(dp2[i-1][j][0],dp2[i-1][j][1] + popcnt(a[i-1][j] ^ a[i][j]));dp2[i][j][1] = max(dp2[i-1][j][1],dp2[i-1][j][0]);}ans += max(dp2[n][j][0],dp2[n][j][1]);}cout << ans << endl;return 0;
}

F组合数

知识点：二项式定理，逆元，数学，虚数快速幂
题解：奇数项/偶数项多项式系数的和2^(n-1) ，要得到题目的式子需要构造式子然后抵消，这个题目中需要引入虚数，就是一个涉及到虚数的快速幂。
最终得到的式子是一份分数，分母为4，题目中又要求了取余，取模运算对于分数不成立，所以需要用到逆元，求4对mod的逆元。
逆元的两种方法;

1、费马小定理（有限制）
p为素数时，a关于mod p的逆元为a^(p-2)mod p。用快速幂模。
但是实际上在acm中题目给的p基本都是质数，所以这是最好用的啦
代码：

#include<bits/stdc++.h>
#include<iostream>
#include <stdio.h>
using namespace std;
const int maxn=1005;
const int base=131;
typedef long long ll;
#define pi acos(-1)
#define INF 0x3f3f3f3f
#define mod 998244353
const int inf=1<<30;struct Complex{ll a,b;Complex(ll _a,ll _b){a = _a,b = _b;}
};//复数Complex mul (Complex A,Complex B){ll a = ((A.a * B.a - A.b * B.b) % mod + mod) % mod;ll b = ((A.a * B.b + A.b * B.a) % mod + mod) % mod;return Complex(a,b);
}//复数乘法Complex add (Complex A,Complex B){ll a = ((A.a + B.a ) % mod + mod) % mod;ll b = ((A.b + B.b ) % mod + mod) % mod;return Complex(a,b);
}//复数加法Complex ksm(Complex A,ll pow){Complex ans (1,0);while(pow){if(pow & 1) ans = mul(ans,A);A = mul(A,A);pow >>= 1 ;}return ans;
}//复数快速幂int main()
{ll n;cin >> n;Complex ans = add(ksm(Complex(2,0) , n) , ksm(Complex(1,1) , n));ans = add(ans , ksm(Complex(1,-1),n));ans = mul(ans,ksm(Complex(4,0),mod-2));//逆元cout<<ans.a<<endl;return 0;
}

2、扩展欧几里得（普遍使用的求逆元方法）

#include<bits/stdc++.h>
#include<iostream>
#include <stdio.h>
using namespace std;
const int maxn=1005;
const int base=131;
typedef long long ll;
#define pi acos(-1)
#define INF 0x3f3f3f3f
#define mod 998244353
const int inf=1<<30;struct Complex{ll a,b;Complex(ll _a,ll _b){a = _a,b = _b;}
};//复数Complex mul (Complex A,Complex B){ll a = ((A.a * B.a - A.b * B.b) % mod + mod) % mod;ll b = ((A.a * B.b + A.b * B.a) % mod + mod) % mod;return Complex(a,b);
}//复数乘法Complex add (Complex A,Complex B){ll a = ((A.a + B.a ) % mod + mod) % mod;ll b = ((A.b + B.b ) % mod + mod) % mod;return Complex(a,b);
}//复数加法Complex ksm(Complex A,ll pow){Complex ans (1,0);while(pow){if(pow & 1) ans = mul(ans,A);A = mul(A,A);pow >>= 1 ;}return ans;
}//复数快速幂ll ext_gcd(ll a, ll b, ll &x, ll &y)
{///扩展欧几里得求逆元，普遍的求法if(b == 0){x = 1;y = 0;return a;}ll r = ext_gcd(b, a%b, x, y);ll temp = x;      //扩展欧几里得的推导x = y;y = temp - a/b*y;return r;
}
int main()
{ll n;cin >> n;Complex ans = add(ksm(Complex(2,0) , n) , ksm(Complex(1,1) , n));ans = add(ans , ksm(Complex(1,-1),n));//ans = mul(ans,ksm(Complex(4,0),mod-2));//逆元ll x,y;ext_gcd(4,mod,x,y);if(x < 0) x += mod;cout<<ans.a * x %mod<<endl;return 0;
}

B系数

知识点：数学，lucas定理
题解：
虽然但是，我并没有学过lucas定理，那么先从lucas定理开始。
Lucas定理是用来求 C(n,m) mod p，p为素数的值。（p最大1e5左右）
排列组合有一个关系： C n m = C n − 1 m + C n − 1 m − 1 C_n^m = C_{n - 1}^m + C_{n - 1}^{ m - 1} Cnm​=Cn−1m​+Cn−1m−1​
就是可以递推，但是当n，m很大时就不行了。

n，m，p都很大时，Lucas定理用来解决大组合数求模。

在这里插入图片描述
上图是个啥东西反正我是看不懂的，在acm中运用主要就是： C n m % p = C n / p m / p ∗ C n % p m % p % p C_n^m \% p = C_{n / p}^{ m / p} * C_{n\%p} ^{m\%p} \% p Cnm​%p=Cn/pm/p​∗Cn%pm%p​%p
对于C(n / p, m / p)，如果n / p 还是很大，可以递归下去，一直到世界的尽头，也就是，一个递归。
代码也是非常简单：

ll lucas(ll n,ll m){if(m==0)return 1;return (C(n%p,m%p)*lucas(n/p,m/p))%p;
}

这个题目由于系数要模三，所以在式子中增减3的倍数对答案没有影响， x 2 + x + 1 − 3 x x^2+x+1-3x x2+x+1−3x,变成 ( x − 1 ) 2 (x-1)^2 (x−1)2 ,多项式变为 ( x − 1 ) 2 n (x-1)^{2n} (x−1)2n,k项系数为 C n k x 2 n − k ( − 1 ) k C_n^k x^{2n-k}(-1)^k Cnk​x2n−k(−1)k

代码：

#include<bits/stdc++.h>
#include<iostream>
#include <stdio.h>
using namespace std;
const int maxn=100005;
const int base=131;
typedef long long ll;
#define pi acos(-1)
#define INF 0x3f3f3f3f
#define mod 3
const int inf=1<<30;
int a[105],b[105],c[105];
int dp[105][105][10005];ll ksm(ll a,ll b ,ll m){ll ans = 1;while(b){if(b & 1) ans = a * ans % m;b >>= 1;a = a * a % m;}return ans;
}
ll C(ll n,ll m) {if(m < 0 || n < m)return 0;ll fz = 1,fm = 1; for(ll i = 1; i <= m; i++){fz = fz * (n + i - m) % mod;fm = fm * i % mod;}return fz * ksm(fm, mod - 2,mod) % mod;
}ll lucas(ll n,ll m){if(m == 0)return 1;return (C(n % mod,m % mod) * lucas(n / mod,m / mod) )% mod;
}
int main()
{int t;cin>>t;ll n,k;while(t--){cin>>n>>k;ll ans = 1;ans = (ksm(-1,2 * n - k,mod)*lucas(2 * n,k) + mod) %mod;cout<<ans<<endl;}return 0;
}

H动态最小生成树

知识点：最小生成树，并查集，线段树，归并

暴力解法：
这个题数据不够ok，可以暴力卡过。直接kruskal，查询的时候重新存一下每次查询的范围的边，然后跑最小生成树。写的时候被一个等号卡了一小时+，太惨了。
代码：

#include<bits/stdc++.h>
#include<iostream>
#include <stdio.h>
using namespace std;
const int maxn=30005;
const int base=131;
typedef long long ll;
#define pi acos(-1)
#define INF 0x3f3f3f3f
#define mod 998244353
const int inf=1<<30;
int pre[maxn];
int deep[maxn];
int n;
struct edge
{int u,v,w;
}ed[maxn],ee[maxn];bool cmp(edge a,edge b)
{return a.w < b.w;
}void init(int n)
{for(int i = 1;i <= n; i++){pre[i] = i;deep[i] = 1;}
}int find(int x)
{if(pre[x] == x)return pre[x];return pre[x] = find(pre[x]);
}void merge(int x,int y)
{int fx = find(x),fy = find(y);if(deep[fx] == deep[fy] ){deep[fy]++;   pre[fx] = fy;}else{if(deep[fx] < deep[fy])pre[fx] = fy;else pre[fy] = fx;}
}ll krusal(int l,int r)
{ll ans = 0;int cnt = 0;sort(ee,ee+r-l+1,cmp);for(int i = 0; i < r-l+1; i++){if(find(ee[i].u) != find(ee[i].v)){merge(ee[i].u,ee[i].v);ans += ee[i].w;cnt++;}}if(cnt == n-1)return ans ;elsereturn -1;
}int main()
{int m,q;cin>>n>>m>>q;for(int i = 1;i <= m;i++)cin>>ed[i].u>>ed[i].v>>ed[i].w;while(q--){init(m);int opt,x,y,z,t,l,r;cin>>opt;if(opt == 1){cin>>x>>y>>z>>t;ed[x].u = y;ed[x].v = z;ed[x].w = t;}else{cin>>l>>r;for(int i = l;i <= r; i++)ee[i-l] = ed[i];ll ans = krusal(l,r);if(ans == -1)cout<<"Impossible"<<endl;elsecout<<ans<<endl;}}return 0;
}

然后是正解

由于查询是在一个连续的范围内查询，可以联想到需要一个线段树优化。
用线段树维护点l到点m的最小生成树构成的边，线段树每次从子树中，找最小的加入，用并查集判断是否成环，如果成环就放弃加入，相当于每次合并为父节点都是在用kruskal。
建树完成后，就可以快速完成单点更新，同样更新后pushup更新对于区间新的最小生成树权值。
查询的时候类似于归并，将范围内线段树维护的最小生成树的边归并为一个ans数组，由于有n个点，最小生成树一定需要n-1条边，不符合输出impossible，符合输出答案。

#include<bits/stdc++.h>
#include<iostream>
#include <stdio.h>
using namespace std;
const int maxn=30005;
const int base=131;
typedef long long ll;
#define pi acos(-1)
#define INF 0x3f3f3f3f
#define mod 998244353
const int inf=1<<30;
int pre[maxn];
int tree[4 * maxn][420];
int ans[300];
int tmp[300];
int n;
struct edge
{int u,v,w;
}ed[maxn],ee[maxn];bool cmp(edge a,edge b)
{return a.w < b.w;
}int find(int x)
{if(pre[x] == x)return pre[x];return pre[x] = find(pre[x]);
}void merge(int x,int y)
{int fx = find(x),fy = find(y);pre[fx] = fy;
}void pushup(int x,int l,int r){for(int i = 1;i <= n; i++){pre[i] = i;tree[x][i] = 0;}int p = 1,q = 1;for(int i = 0 ; i < n ;){int e1 = tree[l][p];int e2 = tree[r][q];if(e1 == 0 && e2 == 0)break;if(e2 == 0 || (ed[e1].w <= ed[e2].w && (e1 != 0))){int uu = ed[e1].u;int vv = ed[e1].v;if(find(uu) != find(vv)){merge(uu,vv);i++;tree[x][i] = e1;}p++;}else{int uu = ed[e2].u;int vv = ed[e2].v;if(find(uu) != find(vv)){merge(uu,vv);i++;tree[x][i] = e2;}q++;}}
}
void hebin(int l)
{for(int i = 1;i <= n; i++){pre[i] = i;tmp[i] = 0;}int p = 1,q = 1;for(int i = 0 ; i < n ;){int e1 = tree[l][p];int e2 = ans[q];if(e1 == 0 && e2 == 0)break;if(e2 == 0 || (ed[e1].w < ed[e2].w &&e1 != 0)){int uu = ed[e1].u;int vv = ed[e1].v;if(find(uu) != find(vv)){merge(uu,vv);i++;tmp[i] = e1;}p++;}else{int uu = ed[e2].u;int vv = ed[e2].v;if(find(uu) != find(vv)){merge(uu,vv);i++;tmp[i] = e2;}q++;}}for(int i = 1;i <= n; i++ )ans[i] = tmp[i];
}void build(int p, int l, int r)
{if(l == r){tree[p][1] = l;return ;}int m = (l + r) / 2;build(p*2, l, m);build(p*2+1, m+1, r);pushup(p,p*2,p*2+1);
}void change(int p,int l,int r,int pos)
{if(l == r){return ;}int m = (l + r) / 2;if(pos <= m)change(p*2, l, m, pos);elsechange(p*2+1, m+1, r ,pos);pushup(p, p*2, p*2+1);}
void qurry(int p,int l,int r,int x,int y)
{if(x <= l && y >= r){hebin(p);return;}int m = (l + r) / 2;if(x <= m)qurry(p*2, l, m ,x ,y);if(y > m)qurry(p*2+1, m+1, r, x ,y);
}int main()
{int m,q;cin>>n>>m>>q;for(int i = 1;i <= m;i++)cin>>ed[i].u>>ed[i].v>>ed[i].w;build(1,1,m);while(q--){int opt,x,y,z,t,l,r;cin>>opt;if(opt == 1){cin>>x>>y>>z>>t;ed[x].u = y;ed[x].v = z;ed[x].w = t;change(1,1,m,x);}else{cin>>l>>r;memset(ans,0,sizeof(ans));qurry(1,1,m,l,r);ll sum = 0;if(ans[n-1] == 0)cout<<"Impossible"<<endl;else{for(int i =  1;i <= n-1 ;i++)sum += ed[ans[i]].w;cout<<sum<<endl;}}}return 0;
}

这篇关于牛客寒假算法集训营第六场补题题解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


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

相关文章

Python中的随机森林算法与实战

Python中的随机森林算法与实战

《Python中的随机森林算法与实战》本文详细介绍了随机森林算法,包括其原理、实现步骤、分类和回归案例,并讨论了其优点和缺点,通过面向对象编程实现了一个简单的随机森林模型,并应用于鸢尾花分类和波士顿房... 目录1、随机森林算法概述2、随机森林的原理3、实现步骤4、分类案例：使用随机森林预测鸢尾花品种4.1
阅读更多...
不懂推荐算法也能设计推荐系统

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

本文以商业化应用推荐为例，告诉我们不懂推荐算法的产品，也能从产品侧出发， 设计出一款不错的推荐系统。 相信很多新手产品，看到算法二字，多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法（注：传统是指科班出身的产品都会接触过）。但对于推荐算法，多数产品对着网上搜到的资源，都会无从下手。特别当某些推荐算法 和 “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份，对于每一份内部的数进行翻转(逆序)，每次操作完后输出操作后新序列的逆序对数。 图一：  划分子问题。 图二： 分而治之，=>  合并 。 图三： 回溯：
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2