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

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。

相关文章

LeetCode11. 盛最多水的容器题解

LeetCode11. 盛最多水的容器题解

LeetCode11. 盛最多水的容器题解 题目链接： https://leetcode.cn/problems/container-with-most-water 示例 思路 暴力解法 定住一个柱子不动，然后用其他柱子与其围住面积，取最大值。 代码如下： public int maxArea1(int[] height) {int n = height.length;int
阅读更多...
代码随想录算法训练营：12/60

代码随想录算法训练营：12/60

非科班学习算法day12 | LeetCode150:逆波兰表达式 ，Leetcode239: 滑动窗口最大值  目录 介绍 一、基础概念补充： 1.c++字符串转为数字 1. std::stoi, std::stol, std::stoll, std::stoul, std::stoull（最常用） 2. std::stringstream 3. std::atoi, std
阅读更多...
人工智能机器学习算法总结神经网络算法(前向及反向传播)

人工智能机器学习算法总结神经网络算法(前向及反向传播)

1.定义，意义和优缺点 定义: 神经网络算法是一种模仿人类大脑神经元之间连接方式的机器学习算法。通过多层神经元的组合和激活函数的非线性转换，神经网络能够学习数据的特征和模式，实现对复杂数据的建模和预测。(我们可以借助人类的神经元模型来更好的帮助我们理解该算法的本质，不过这里需要说明的是，虽然名字是神经网络，并且结构等等也是借鉴了神经网络，但其原型以及算法本质上还和生物层面的神经网络运行原理存在
阅读更多...
大林 PID 算法

大林 PID 算法

Dahlin PID算法是一种用于控制和调节系统的比例积分延迟算法。以下是一个简单的C语言实现示例： #include <stdio.h>// DALIN PID 结构体定义typedef struct {float SetPoint; // 设定点float Proportion; // 比例float Integral; // 积分float Derivative; // 微分flo
阅读更多...
LeetCode 算法：二叉树的中序遍历 c++

LeetCode 算法：二叉树的中序遍历 c++

原题链接🔗：二叉树的中序遍历 难度：简单⭐️ 题目 给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。 示例 1： 输入：root = [1,null,2,3] 输出：[1,3,2] 示例 2： 输入：root = [] 输出：[] 示例 3： 输入：root = [1] 输出：[1] 提示： 树中节点数目在范围 [0, 100] 内 -100 <= Node.
阅读更多...
【Java算法】滑动窗口 下

【Java算法】滑动窗口 下

​ ​    🔥个人主页： 中草药 🔥专栏：【算法工作坊】算法实战揭秘 🦌一.水果成篮 题目链接：904.水果成篮 ​ 算法原理 算法原理是使用“滑动窗口”（Sliding Window）策略，结合哈希表（Map）来高效地统计窗口内不同水果的种类数量。以下是详细分析： 初始化：创建一个空的哈希表 map 用来存储每种水果的数量，初始化左右指针 left
阅读更多...
ROS2从入门到精通4-4：局部控制插件开发案例(以PID算法为例)

ROS2从入门到精通4-4：局部控制插件开发案例(以PID算法为例)

目录 0 专栏介绍1 控制插件编写模板1.1 构造控制插件类1.2 注册并导出插件1.3 编译与使用插件 2 基于PID的路径跟踪原理3 控制插件开发案例(PID算法)常见问题 0 专栏介绍 本专栏旨在通过对ROS2的系统学习，掌握ROS2底层基本分布式原理，并具有机器人建模和应用ROS2进行实际项目的开发和调试的工程能力。 🚀详情：《ROS2从入门到精通》 1 控制插
阅读更多...
算法与数据结构面试宝典——回溯算法详解（C#，C++）

算法与数据结构面试宝典——回溯算法详解（C#，C++）

文章目录 1. 回溯算法的定义及应用场景2. 回溯算法的基本思想3. 递推关系式与回溯算法的建立4. 状态转移方法5. 边界条件与结束条件6. 算法的具体实现过程7. 回溯算法在C#，C++中的实际应用案例C#示例C++示例 8. 总结回溯算法的主要特点与应用价值 回溯算法是一种通过尝试各种可能的组合来找到所有解的算法。这种算法通常用于解决组合问题，如排列、组合、棋盘游
阅读更多...
LeetCode：经典题之141、142 题解及延伸

LeetCode：经典题之141、142 题解及延伸

系列目录 88.合并两个有序数组 52.螺旋数组 567.字符串的排列 643.子数组最大平均数 150.逆波兰表达式 61.旋转链表 160.相交链表 83.删除排序链表中的重复元素 389.找不同 1491.去掉最低工资和最高工资后的工资平均值 896.单调序列 206.反转链表 92.反转链表II 141.环形链表 142.环型链表 目录 系列目录141. 环形链表常量因子 1
阅读更多...
【图像识别系统】昆虫识别Python+卷积神经网络算法+人工智能+深度学习+机器学习+TensorFlow+ResNet50

【图像识别系统】昆虫识别Python+卷积神经网络算法+人工智能+深度学习+机器学习+TensorFlow+ResNet50

一、介绍 昆虫识别系统，使用Python作为主要开发语言。通过TensorFlow搭建ResNet50卷积神经网络算法（CNN）模型。通过对10种常见的昆虫图片数据集（‘蜜蜂’, ‘甲虫’, ‘蝴蝶’, ‘蝉’, ‘蜻蜓’, ‘蚱蜢’, ‘蛾’, ‘蝎子’, ‘蜗牛’, ‘蜘蛛’）进行训练，得到一个识别精度较高的H5格式模型文件，然后使用Django搭建Web网页端可视化操作界面，实现用户上传一
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2