文章目錄

• • @[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;
}

---