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

2024-06-07 22:52
文章标签 题目 贪心 18 部分 查集 st 码蹄集 2024oj

本文主要是介绍码蹄集部分题目（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;
}

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

⭐点赞收藏不迷路~

这篇关于码蹄集部分题目（2024OJ赛18期；并查集+ST表+贪心）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1040526。

相关文章

usaco 1.3 Barn Repair（贪心）

usaco 1.3 Barn Repair（贪心）

思路：用上M块木板时有 M-1 个间隙。目标是让总间隙最大。将相邻两个有牛的牛棚之间间隔的牛棚数排序，选取最大的M-1个作为间隙，其余地方用木板盖住。 做法： 1.若，板（M） 的数目大于或等于 牛棚中有牛的数目（C），则 目测 给每个牛牛发一个板就为最小的需求~ 2.否则，先对 牛牛们的门牌号排序，然后 用一个数组 blank[ ] 记录两门牌号之间的距离，然后 用数组 an
阅读更多...
poj 3190 优先队列+贪心

poj 3190 优先队列+贪心

题意： 有n头牛，分别给他们挤奶的时间。 然后每头牛挤奶的时候都要在一个stall里面，并且每个stall每次只能占用一头牛。 问最少需要多少个stall，并输出每头牛所在的stall。 e.g 样例： INPUT: 51 102 43 65 84 7 OUTPUT: 412324 HINT: Explanation of the s
阅读更多...
poj 1182 并查集 食物链类

poj 1182 并查集 食物链类

题意： 有n只动物，分别编号1....n。所有动物都属于A，B，C中的一种，已知A吃B，B吃C，C吃A。 按顺序给出下面两种共K条信息： 1. x 和 y 属于同一类。 2. x 吃 y 。 然而这些信息可能会出错，有可能有的信息和之前给出的信息矛盾，也有的信息可能给出的 x 和 y 不在n的范围内。 求k条信息中有多少条是不正确的。 解析： 对于每只动物，创建3个元素 i
阅读更多...
poj 2976 分数规划二分贪心（部分对总体的贡献度） poj 3111

poj 2976 分数规划二分贪心（部分对总体的贡献度） poj 3111

poj 2976： 题意： 在n场考试中，每场考试共有b题，答对的题目有a题。 允许去掉k场考试，求能达到的最高正确率是多少。 解析： 假设已知准确率为x，则每场考试对于准确率的贡献值为： a - b * x，将贡献值大的排序排在前面舍弃掉后k个。 然后二分x就行了。 代码： #include <iostream>#include <cstdio>#incl
阅读更多...
题目1254：N皇后问题

题目1254：N皇后问题

题目1254：N皇后问题 时间限制：1 秒 内存限制：128 兆 特殊判题：否 题目描述： N皇后问题，即在N*N的方格棋盘内放置了N个皇后，使得它们不相互攻击（即任意2个皇后不允许处在同一排，同一列，也不允许处在同一斜线上。因为皇后可以直走，横走和斜走如下图)。 你的任务是，对于给定的N，求出有多少种合法的放置方法。输出N皇后问题所有不同的摆放情况个数。 输入
阅读更多...
题目1380：lucky number

题目1380：lucky number

题目1380：lucky number 时间限制：3 秒 内存限制：3 兆 特殊判题：否 提交：2839 解决：300 题目描述： 每个人有自己的lucky number，小A也一样。不过他的lucky number定义不一样。他认为一个序列中某些数出现的次数为n的话，都是他的lucky number。但是，现在这个序列很大，他无法快速找到所有lucky number。既然
阅读更多...
POJ2010 贪心优先队列

POJ2010 贪心优先队列

c头牛,需要选n头（奇数）；学校总共有f的资金， 每头牛分数score和学费cost，问合法招生方案中,中间分数（即排名第(n+1)/2）最高的是多少。 n头牛按照先score后cost从小到大排序； 枚举中间score的牛,  预处理左边与右边的最小花费和。 预处理直接优先队列贪心 public class Main {public static voi
阅读更多...
POJ1988带权并查集

POJ1988带权并查集

M u v 将u所在的堆移动到v所在的堆的上面 C u 求u的下面有多少块 带权并查集 import java.io.BufferedReader;import java.io.InputStream;import java.io.InputStreamReader;import java.io.PrintWriter;import java.math.BigInteger;i
阅读更多...
POJ1703带权并查集

POJ1703带权并查集

D： u v  u与v在不同的集合 A： u v  查询u与v的关系 1)压缩路径过程        fu->root   0  1  u-fu 0                 0  1   1                 1  0 2)合并过程 fu->fv      u->fu   0 1   v->fv 0            1 0 1            0
阅读更多...
ural 1820. Ural Steaks 贪心

ural 1820. Ural Steaks 贪心

1820. Ural Steaks Time limit: 0.5 second Memory limit: 64 MB After the personal contest, happy but hungry programmers dropped into the restaurant “Ural Steaks” and ordered  n specialty steaks
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2