前言
这次萌新联赛考到了很多数学知识
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;
}