码蹄集部分题目（2024OJ赛18期；并查集+ST表+贪心）

1🐋🐋史莱姆融合（钻石；并查集）

时间限制：1秒

占用内存：128M

🐟题目描述

🐟题目思路

这道题目使用并查集，同一集合的所有元素的最顶上的祖父节点是统一的。这里记录每个集合的最左端元素（最顶上的祖父节点）和最右端元素，便于集合更新。

MT3052 史莱姆融合_哔哩哔哩_bilibili

🐟代码

#include<bits/stdc++.h> 
​
using namespace std;
const int N=1e6+5;
int n,fa[N],so[N],nxt[N];//集合最左端fa，集合最右端so，下一个元素nxt
​
int find(int x) {return x==fa[x]?x:(fa[x]=find(fa[x]));}//找集合最左端元素
​
void merge(int i,int j)//集合合并
{int x=find(i),y=find(j);//两个集合的最左端if(x!=y){nxt[so[x]]=y;//第一个集合的最右端的下一个元素就是第二个集合的最左端元素fa[y]=x;//更新最左端so[x]=so[y];//更新最右端}
}
​
int main( )
{int x,y;cin>>n;for(int i=1;i<=n;i++) fa[i]=so[i]=i;for(int i=0;i<n-1;i++){cin>>x>>y;merge(x,y);}for(int i=find(1);i;i=nxt[i]) cout<<i<<" ";return 0;
}

2🐋🐋区间最小值（钻石；ST表）

时间限制：1秒

占用内存：128M

🐟题目描述

🐟题目思路

ST表用于解决区间最值问题，基于分治和倍增思想。

• ST表中定义了一个二维数组mn[N] [M]，mn[i] [j]表示区间[i, i + 2^j + 1]内的最大值

• 根据倍增思想，给出状态转移方程mn[i] [j] = max(mn[i] [j - 1], mn[i + 2^j - 1^] [j - 1])

ST表详解推荐：ST表详解-CSDN博客

🐟代码

#include<bits/stdc++.h> 
​
using namespace std;
const int N=1e5+5;
int m,n,a[N],mn[N][50],Lg[N],ans;
​
void pre()
{Lg[1]=0;for(int i=2;i<=n;i++) Lg[i]=Lg[i>>1]+1;//求对数，得到每段的区间结束位置
}
​
void ST_create()
{for(int i=1;i<=n;i++) mn[i][0]=a[i];//mn[i][j]，当j为0时，区间长度2^j为0，则区间最大值就是区间的唯一元素a[i]for(int j=1;j<=Lg[n];j++)//之前已经计算过区间长度为0的情况，这里区间长度由2^1 到 2^Lg[n] {for(int i=1;i<=n-(1<<j)+1;i++)//确定区间左端点，区间范围为[i, i + 2^j - 1],所以 i + 2^j - 1 <= n{mn[i][j]=min(mn[i][j-1],mn[i+(1<<(j-1))][j-1]);//状态转移方程}}
}
​
int ST_query(int l,int r)//区间查询
{int k=Lg[r-l+1];return min(mn[l][k],mn[r-(1<<k)+1][k]);
}
​
int main( )
{int a1,a2;cin>>n>>m;for(int i=1;i<=n;i++) cin>>a[i];pre();ST_create();while(m--){cin>>a1>>a2;cout<<ST_query(a1,a2)<<endl;}return 0;
}

3🐋🐋区间gcd（钻石；ST表）

时间限制：1秒

占用内存：64M

🐟题目描述

🐟题目思路

这道题目也是使用ST表，pre、create和query除了将min改成gcd没有变化，gcd使用递归的方式求取。

MT3051 区间gcd_哔哩哔哩_bilibili

🐟代码

用时少：

#include<bits/stdc++.h> 
​
using namespace std;
const int N=2e5+5;
int m,n,a[N],mn[N][50],Lg[N],ans;
​
int read()
{int ans=0;char ch=getchar();while(ch<'0'||ch>'9') ch=getchar();while(ch>='0'&&ch<='9'){ans=ans*10+ch-'0';ch=getchar();}return ans;
}
​
void write(int x)
{if(x>=10) write(x/10);putchar(x%10+'0');
}
​
int gcd(int a,int b){return b==0?a:gcd(b,a%b);}
​
void pre()
{Lg[1]=0;for(int i=2;i<=n;i++) Lg[i]=Lg[i>>1]+1;//求对数，得到每段的区间结束位置
}
​
void ST_create()
{for(int i=1;i<=n;i++) mn[i][0]=a[i];//mn[i][j]，当j为0时，区间长度2^j为0，则区间最大值就是区间的唯一元素a[i]for(int j=1;j<=Lg[n];j++)//之前已经计算过区间长度为0的情况，这里区间长度由2^1 到 2^Lg[n] {for(int i=1;i<=n-(1<<j)+1;i++)//确定区间左端点，区间范围为[i, i + 2^j - 1],所以 i + 2^j - 1 <= n{mn[i][j]=gcd(mn[i][j-1],mn[i+(1<<(j-1))][j-1]);//状态转移方程}}
}
​
int ST_query(int l,int r)//区间查询
{int k=Lg[r-l+1];return gcd(mn[l][k],mn[r-(1<<k)+1][k]);
}
​
int main( )
{int a1,a2;n=read();m=read();for(int i=1;i<=n;i++) a[i]=read();pre();ST_create();while(m--){a1=read();a2=read();ans=ST_query(a1,a2);write(ans);putchar('\n');}return 0;
}

占内存少：

摘自——小码_63705

#include<bits/stdc++.h> 
​
using namespace std;
const int N=3e5+5;
​
int gcd(int a,int b)
{if(!b) return a;else return gcd(b,a%b);
}
​
int dp[N][20],a[N],len[N];
​
int query(int l,int r)
{int k=len[r-l+1];return gcd(dp[l][k],dp[r-(1<<k)+1][k]);
}
​
inline int read()
{char c=getchar();int x=0,f=1;while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}return x*f;
}
​
int main( )
{len[0]=1;for(int i=2;i<N-2;i++) len[i]=len[i/2]+1;int n;n=read();int ncase;ncase=read();for(int i=1;i<=n;i++) {*(a+i)=read();dp[i][0]=a[i];}for(int j=1;j<=len[n];j++){for(int i=1;i<=n;i++){dp[i][j]=gcd(dp[i][j-1],dp[i+(1<<j-1)][j-1]);}}while(ncase--){int l=read(),r=read();printf("%d\n",query(l,r));}return 0;
}

4🐋🐋检测敌人（钻石；贪心）

时间限制：1秒

占用内存：128M

🐟题目描述

🐟题目思路

贪心思路：一个设备检测尽可能多的敌人。

不同于用设备找敌人，这道题目需要用敌人找设备，以敌人为圆心画圈，找到可用检测到我的x轴上的所有范围，那么在这个范围内放设备都可以检测到我。

贪心的实现就是通过对比两个区间是否有重叠，得知可否共用设备。

【码蹄集进阶塔全题解08】算法基础：贪心 MT2080 – MT2092_哔哩哔哩_bilibili

🐟代码

#include<bits/stdc++.h> 
​
using namespace std;
const int N=1005;
struct node
{double x,y,l,r;bool v;
}e[N];
​
bool cmp(node a,node b)
{return a.r<b.r;
}
​
int main( )
{int n;double r;while(cin>>n>>r&&!(n==0&&r==0)){bool flag=false;memset(e,0,sizeof(e));for(int i=1;i<=n;i++){cin>>e[i].x>>e[i].y;if(r*r<e[i].y*e[i].y) flag=true;//以每个敌人为圆心画圆，圆圈范围内的仪器能检测到敌人else//计算能检测到敌人的x轴坐标范围{e[i].l=-sqrt(r*r-e[i].y*e[i].y)+e[i].x;e[i].r=sqrt(r*r-e[i].y*e[i].y)+e[i].x;e[i].v=false;}}if(flag){cout<<-1<<endl;continue;}sort(e+1,e+1+n,cmp);int ans=0;for(int i=1;i<=n;i++){if(e[i].v==false)//表示这个敌人还没能被检测到{for(int j=i;j<=n;j++){if(e[j].v==false&&e[j].l<=e[i].r&&e[j].r>=e[i].r) e[j].v=true;//我们有重叠区域，用一个设备就行了}e[i].v=true;ans++;//所需设备数加一}}cout<<ans<<endl;}return 0;
}

5🐋🐋小码哥的福利（钻石；贪心）

时间限制：1秒

占用内存：128M

🐟题目描述

🐟题目思路

贪心思路：每次分甜品都要尽可能地达到平均值。

这道题目的思路就是，将所有手下按耐受度排序，将所有甜品按甜度排序；找到能吃掉这个甜品的手下，让他全部吃掉；然后对所有手下吃掉的甜品数量进行分配。根据耐受度限制，甜品只能往右分，也就是往耐受度高的手下那里分，那么每次都计算出来从我到最后一个手下我们吃的甜品数量的平均值，然后如果我吃的比这个平均值多，就把多的甜品分给下一个人，以此类推我从头遍历到尾。

【码蹄集进阶塔全题解08】算法基础：贪心 MT2080 – MT2092_哔哩哔哩_bilibili

🐟代码

#include<bits/stdc++.h> 
​
using namespace std;
#define ll long long
const int N=55;
ll n,m,a[N],sum[N],ans;
struct node
{ll b,c;
}sweet[N];
​
int cmp(node a,node b){return a.b<b.b;}
​
ll add(int l,int r)
{ll ans=0;for(int i=l;i<=r;i++) ans+=sum[i];return ans;
}
​
int main( )
{cin>>n;ll maxm=0;for(int i=1;i<=n;i++){cin>>a[i];maxm=max(maxm,a[i]);}sort(a+1,a+1+n);cin>>m;for(int i=1;i<=m;i++){cin>>sweet[i].b;if(sweet[i].b>maxm)//甜品的甜度超过手下的最大甜品耐受度了，无法吃完{cout<<-1<<endl;return 0;}}for(int i=1;i<=m;i++) cin>>sweet[i].c;sort(sweet+1,sweet+1+m,cmp);//按照甜度大小排列for(int i=1;i<=m;i++)//遍历所有甜品i{for(int j=1;j<=n;j++)//遍历所有手下j{if(sweet[i].b<=a[j]){sum[j]+=sweet[i].c;//手下j吃掉甜度为i的所有甜品break;}}}//平均化吃掉的数量//甜品转移只能向右转移，也就是转移给耐受度更高的手下for(int i=1;i<=n;i++)//遍历所有手下{ll tmp=(add(i,n))/(n-i+1);//将往右的这些所有吃的甜品数量平均if(tmp<=sum[i])//这个人吃多了，分走甜品{sum[i+1]+=sum[i]-tmp;sum[i]=tmp;}}for(int i=1;i<=n;i++) ans=max(ans,sum[i]);//找出最大sumcout<<ans<<endl;return 0;
}

6🐋🐋屠龙勇者（黄金；贪心）

时间限制：1秒

占用内存：128M

🐟题目描述

🐟题目思路

贪心思想：用最强的勇士砍最大的头。

那么就是将d和w数组分别排序，最多有m-n个spare的勇士可以用来砍这个头，所以对i来说最强的勇士就是第i+m-n个勇士，如果这个最强的勇士都没法砍这个头，那么就失败了。同样的贪心思想，这些spare的勇士也是能力值低的那些。

🐟代码

#include<bits/stdc++.h> 
​
using namespace std;
const int N=1e5+5;
int d[N],w[N],n,m;
int main( )
{cin>>n>>m;for(int i=1;i<=n;i++) cin>>d[i];for(int i=1;i<=m;i++) cin>>w[i];sort(d+1,d+1+n);sort(w+1,w+1+m);if(n>m){cout<<"NO";return 0;}for(int i=n;i>=1;i--){if(w[i+m-n]<d[i])//最多有m-n个spare的勇士{cout<<"NO";return 0;}}cout<<"YES";return 0;
}

有问题我们随时评论区见~

⭐点赞收藏不迷路~