当前位置: 首页 > news >正文

河南萌新联赛2025第(五)场:信息工程大学补题

文章目录

    • @[TOC](文章目录)
  • 前言
  • A.宇宙终极能量调和与多维时空稳定性验证下的基础算术可行性研究
  • B.中位数
  • C.中位数+1
  • F.中位数+4
  • G.简单题
  • H.简单题+
  • I.Re:从零开始的近世代数复习(easy)
  • K.狂飙追击
  • L.防k题

前言

这次萌新联赛考到了很多数学知识


A.宇宙终极能量调和与多维时空稳定性验证下的基础算术可行性研究

在这里插入图片描述
这题纯属文字题,只需要关注“经典线性叠加”
直接输出2就行了

B.中位数

在这里插入图片描述
在这里插入图片描述
这题开始对中位数的定义有点遗忘,后来想起来了,该题其实求的就是最大值与最小值的中位数

#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define pii pair<int,int>
#define fi first
#define se second
#define int long long
#define endl '\n'
const int N=1e6+6;
int a[N];
signed main()
{int n;cin>>n;for(int i=1;i<=n;i++){cin>>a[i];}if(n==1){cout<<a[1]/2;}else {sort(a+1,a+n+1);cout<<(a[1]+a[n])/2;}return 0;} 

C.中位数+1

在这里插入图片描述
这题就是求动态中位数,利用两个优先队列,一个是从小到大,一个是从大到小,大堆放小值,小堆放大值

#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define pii pair<int,int>
#define fi first
#define se second
#define int long long
#define endl '\n'
const int N=1e5+6;
int a[N];
signed main()
{int n;cin>>n;priority_queue<int>pq;priority_queue<int,vector<int>,greater<int>>pq1;for(int i=1;i<=n;i++){cin>>a[i];pq.push(a[i]);if(pq.size()>pq1.size()+1)//为了让两个队列的长度差保持<=1,维护后面奇数时输出的大堆堆顶是中位数{pq1.push(pq.top());pq.pop();}if(!pq1.empty()&&pq.top()>pq1.top())//维护大堆放小值,小堆放大值{int z=pq.top();int y=pq1.top();pq.pop();pq1.pop();pq.push(y);pq1.push(z);}if(i%2==1)//奇数时输出大堆堆顶{cout<<pq.top()<<" ";}else//偶数时输出大堆堆顶+小堆堆顶然后/2{cout<<(pq.top()+pq1.top())/2<<" ";}}return 0;
}

F.中位数+4

在这里插入图片描述
这题其实就是十进制转化为其他进制过程

#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define pii pair<int,int>
#define fi first
#define se second
#define int long long
#define endl '\n'
const int N=1e6+6;
int a[N];
signed main()
{int n,k;cin>>n>>k;int sum=0;if(n<k){cout<<"0";}else{while(n>1){if(n%k==0)//此时余数为0,所以++{sum++;n=n/k;}else{break;}}cout<<sum;}return 0;} 

G.简单题

在这里插入图片描述
在这里插入图片描述
这个是行列式,当时看一直以为+1就行了,还是知道的太少了
在这里插入图片描述
最后计算知道,该题为一个斐波那契数列,对二取模后就有一个规律,见代码

#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define pii pair<int,int>
#define fi first
#define se second
#define int long long
#define endl '\n'
signed main()
{int n;cin>>n;if(n%3==1){cout<<"1";}else{cout<<"0";}return 0;
}

H.简单题+

在这里插入图片描述
这个就是求斐波那契数列前n项和
其有一个规律:s[n]=f[n+2]-1
所以求n后面第二项-1就行了,对于求斐波那契数列也有规律
n为奇数时:
在这里插入图片描述n为偶数时:
在这里插入图片描述

#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define pii pair<int,int>
#define fi first
#define se second
#define int long long
#define endl '\n'
unordered_map<int,int>mp;
const int mod=998244353;
int mc(int x)
{if(mp.count(x)){return mp[x];}if(x==0)return 0;else if(x==1||x==2)return 1;else{int k=x/2;int a=mc(k);int b=mc(k+1);if(x%2!=0){return mp[x]=(b*b%mod+a*a%mod)%mod;//奇数时}else{return mp[x]=(a*((2*b%mod-a+mod)%mod))%mod;//偶数时}}
}
signed main()
{int n;cin>>n;if(n==1)cout<<"1";else if(n==2)cout<<"2";else{int sum=mc(n+2)-1+mod;sum=sum%mod;cout<<sum;}return 0;
}

I.Re:从零开始的近世代数复习(easy)

在这里插入图片描述
在这里插入图片描述
这题真的是服我自己了,当时根本没看到、k=2,本来想用共同祖先写,当时想着有好几个怎么求,没有想到后面出现了k=2。这题就是利用共同祖先写,利用倍增找到两个点的最近共同祖先,然后在遍历整个树的时候提前定义一个数组代表从根节点到该点权值,最和简单相加相减就行了

#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define pii pair<int,int>
#define fi first
#define se second
#define int long long
#define endl '\n'
const int N=1e5+6;
int a[N];
int b[N]={0};
int c[N];
int h[N]={0};
int fa[N][25];
vector<int>ve[N];
int n;
void dfs(int fu,int zi)//遍历整个树
{h[zi]=h[fu]+1;fa[zi][0]=fu;c[zi]=c[fu]+a[fu];//计算根节点到该点的权值for(int i=1;i<=20;i++){fa[zi][i]=fa[fa[zi][i-1]][i-1];}for(auto it:ve[zi]){dfs(zi,it);}
}
int lca(int a,int b)//倍增求LCA
{if(h[a]<h[b]){swap(a,b);}for(int i=20;i>=0;i--){if(h[fa[a][i]]>=h[b]){a=fa[a][i];}}if(a==b){return a;}for(int i=20;i>=0;i--){if(fa[a][i]!=fa[b][i]){a=fa[a][i];b=fa[b][i];}}return fa[a][0];
}
signed main()
{cin>>n;for(int i=1;i<=n;i++){cin>>a[i];}for(int i=1;i<n;i++){int u,v;cin>>u>>v;b[v]++;//计算入度,找根节点ve[u].push_back(v);}int x;for(int i=1;i<=n;i++){if(b[i]==0){x=i;}}dfs(0,x);int q;cin>>q;while(q--){int k;cin>>k;int p,q;cin>>p>>q;int z=lca(p,q);int z1=c[p]+c[q]-c[z]+a[p]+a[q]-a[z];cout<<z1<<endl;}return 0;} 

K.狂飙追击

在这里插入图片描述
由于它这个m是变化的,所以不能只进行一些简单的判断,利用dfs搜索,对x,y分别搜索,如果符合就计算最少步数

#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define pii pair<int,int>
#define fi first
#define se second
#define int long long
#define endl '\n'
int sx,sy,tx,ty;
bool bl=0;
int maxx=INT_MAX;
void dfs(int x,int y,int z)
{if(x>tx||y>ty){return ;}if(x==tx&&y==ty){bl=1;maxx=min(maxx,z);return ;}int m=max(x,y);int x1=x+m;int y1=y+m;dfs(x1,y,z+1);dfs(x,y1,z+1);
}
signed main()
{cin>>sx>>sy>>tx>>ty;if(sx>tx||sy>ty){cout<<"-1";}else{dfs(sx,sy,0);if(bl==1){cout<<maxx;}else{cout<<"-1";}}return 0;
}

对dfs遍历举个例
从1,2到4,5
在这里插入图片描述

L.防k题

在这里插入图片描述
在这里插入图片描述
这题就是一个二分答案题,先套模板再判断check成立条件

#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define pii pair<int,int>
#define fi first
#define se second
#define int long long
#define endl '\n'
const int N=1e6+6;
int n,m,z,p,q;
int check(int mid)
{int i=0;int n1=n,m1=m,z1=z,p1=p,q1=q;while(p1>0){for(int i=1;i<=3;i++){n1-=q;if(n1<=0){mid--;n1=n;}}if(mid<=0)//很重要,因为在上面的循环中可能减去多次,导致mid<0,所以不能只判断其是否等于零{return 0;}p1-=mid*(i*z+m1);i++;}return 1;   
}
signed main()
{cin>>n>>m>>z>>p>>q;int l=1;int r=N;while(l<r){int mid=(l+r)/2;if(check(mid)==1){r=mid;}else{l=mid+1;}}cout<<r;return 0;
}

http://www.lryc.cn/news/620964.html

相关文章:

  • TensorFlow深度学习实战(32)——深度Q网络(Deep Q-Network,DQN)
  • Azure微软云内网接入问题
  • 老生常谈之引用计数:《More Effective C++》条款29
  • 位操作:底层编程利器
  • 通过网页调用身份证阅读器http websocket方法-华视电子————仙盟创梦IDE
  • Uniapp 中 uni.request 的二次封装
  • 22.Linux samba服务
  • 15、C语言预处理知识点总结
  • 18.14 全量微调实战手册:7大核心配置提升工业级模型训练效率
  • 并发编程原理与实战(二十三)StampedLock应用实战与其他锁性能对比分析
  • 深度学习ubuntu系统常用指令和技巧
  • VisDrone数据集,专为无人机视觉任务打造
  • Linux面试题及详细答案 120道(1-15)-- 基础概念
  • 9.【C++进阶】继承
  • 开源数据发现平台:Amundsen 快速上手指南
  • 微服务、分布式概念-以及集群部署 vs 分布式部署
  • C# LINQ 全面教程:从入门到精通
  • 【19-模型训练细节 】
  • Linux 编译过程中遇到 TMPDIR 空间不足的问题
  • 算法应用上新!自适应更新策略差分进化算法求解球形多飞行器路径规划问题,附完整MATLAB代码
  • 智慧城市SaaS平台/专项管理系统
  • PyCharm 2025.2:面向工程师的 AI 工具
  • Nginx学习笔记(九)—— Nginx Rewrite深度解析
  • 学习嵌入式第二十八天
  • python爬虫学习(2)
  • 大模型微调方法讲解
  • linux 软硬链接详解
  • 服务器数据恢复—误删服务器卷数据的数据恢复案例
  • ESXI 6.7服务器时间错乱问题
  • QT+Yolov8 推理部署,ONNX模型 ,实例分割+目标检测