码蹄集部分题目（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]);//找出最大sum
    cout<<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;
}

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

⭐点赞收藏不迷路~

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/688769.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

SAP ABAP 创建表结构 SE11

SAP ABAP 创建表结构 SE11

目录 一&#xff0c;创建表 &#xff1a;T-code:SE11 二&#xff0c;编辑内容&#xff1a; 1&#xff0c;内容说明&#xff1a;必填项&#xff0c;属性&#xff1a;锁定不可更改 2&#xff0c;出荷と更新 &#xff13;&#xff0c;項目 A&#xff1a;表的第一个项目必须是…
阅读更多...
编写程序提示用户输入一个数目(例如:100)、年利率(例如:5)以及月份数(例如:6)，然后显示给定月份后账户上的钱数。

编写程序提示用户输入一个数目(例如:100)、年利率(例如:5)以及月份数(例如:6)，然后显示给定月份后账户上的钱数。

(财务应用程序:复利值)假设你每月向银行账户存 100美元&#xff0c;年利率为5%&#xff0c;那么每 月利率是 0.05/12-0.00417。 第一个月之后&#xff0c;账户上的值就变成:100*(10.00417)100.417 第二个月之后&#xff0c;账户上的值就变成(100100.417)*(10.00417)-201.252 第…
阅读更多...
【Python报错】已解决ImportError: cannot import name ‘xxx‘

【Python报错】已解决ImportError: cannot import name ‘xxx‘

成功解决“ImportError: cannot import name ‘xxx’”错误的全面指南 一、引言 在Python编程中&#xff0c;ImportError是一种常见的异常类型&#xff0c;它通常表明Python解释器在尝试导入某个模块或模块中的某个成员时遇到了问题。当看到错误消息“ImportError: cannot imp…
阅读更多...
解密智慧校园解决方案：赋能数字化教育的未来

解密智慧校园解决方案：赋能数字化教育的未来

在当今数字化时代&#xff0c;智慧校园解决方案正以惊人的速度改变着教育界的面貌。随着科技的快速发展&#xff0c;数字化教育已经逐渐成为现代教育的核心。智慧校园解决方案作为一个集技术、教育和创新于一体的综合性项目&#xff0c;为学校提供了许多机遇和挑战。本文将揭示…
阅读更多...
嵌入式Linux系统中RTC应用的操作详解

嵌入式Linux系统中RTC应用的操作详解

第一：RTC的作用以及时间简介 “RTC”的英文全称是Reul-Time Clock，翻译过来是实时时钟芯片．实时时钟芯片是日常生活中应用最为广泛的电子器件之一，它为人们或者电子系统提供精确的实时时间，实时时钟芯片通过引脚对外提供时间读写接口，通常内部带有电池，保证在外部系统关…
阅读更多...
width: 100%和 width: 100vw这两种写法有什么区别

width: 100%和 width: 100vw这两种写法有什么区别

width: 100%; 和 width: 100vw; 是两种不同的 CSS 写法&#xff0c;它们在实际应用中会有不同的效果。以下是这两种写法的主要区别&#xff1a; width: 100%; 定义&#xff1a;将元素的宽度设置为其包含块&#xff08;通常是父元素&#xff09;宽度的 100%。效果&#xff1a;元…
阅读更多...
Maven核心功能依赖和构建管理

Maven核心功能依赖和构建管理

1.依赖管理和配置 Maven 依赖管理是 Maven 软件中最重要的功能之一。Maven 的依赖管理能够帮助开发人员自动解决软件包依赖问题&#xff0c;使得开发人员能够轻松地将其他开发人员开发的模块或第三方框架集成到自己的应用程序或模块中&#xff0c;避免出现版本冲突和依赖缺失等…
阅读更多...
springboot停车微信小程序小程序-计算机毕业设计源码92714

springboot停车微信小程序小程序-计算机毕业设计源码92714

摘 要 在信息飞速发展的今天&#xff0c;网络已成为人们重要的信息交流平台。每天都有大量的农产品需要通过网络发布&#xff0c;为此&#xff0c;本人开发了一个基于springboot停车微信小程序小程序。 对于本停车微信小程序的设计来说&#xff0c;它主要是采用后台采用java语…
阅读更多...
Android Webview 详解

Android Webview 详解

一 简介 一个基于webkit引擎、展现web页面的控件 Android 4.4前&#xff1a;Android Webview在低版本 & 高版本采用了不同的webkit版本的内核Android 4.4后&#xff1a;直接使用了Chrome内核 1.1 作用 在 Android 客户端上加载h5页面在本地 与 h5页面实现交互 & …
阅读更多...
关于RDMA传输的基本流量控制

关于RDMA传输的基本流量控制

Basic flow control for RDMA transfers | The Geek in the Corner (wordpress.com) 文心一言 已经介绍了使用发送/接收操作和RDMA读写操作&#xff0c;那么现在是一个很好的机会来结合这两种方法的元素&#xff0c;并讨论一般的流量控制。还会稍微谈谈RDMA带有立即数据的写操…
阅读更多...
《机器学习特征提取》

《机器学习特征提取》

书籍&#xff1a;Building Feature Extraction with Machine Learning: Geospatial Applications 作者&#xff1a;Bharath.H. Aithal&#xff0c;Prakash P.S. 出版&#xff1a;CRC Press 书籍下载-《机器学习特征提取》这是一本面向专业人士和研究生的实用指南&#xff0c…
阅读更多...
uniapp uni-popup内容被隐藏问题

uniapp uni-popup内容被隐藏问题

今天开发新需求的时候发现uni-popup 过一会就被隐藏掉只留下遮罩(css被更改了)&#xff0c;作者进行了如下调试。 1.讲uni-popup放入其他节点内 失败&#xff01; 2.在生成dom后在打开 失败&#xff01; 3.uni-popup将该节点在包裹一层 然后将统计设置样式&#xff0c;v-if v-s…
阅读更多...
selenium中， quit 和close的区别

selenium中， quit 和close的区别

close时 """ close和quit的区别 close关闭当前页 (只是关闭了当前) quit离开整个浏览器 &#xff08;走远了&#xff09; """ from selenium import webdriver import time# 创建浏览器驱动对象 from selenium.webdriver.co…
阅读更多...
抢人！抢人！抢人！ IT行业某岗位已经开始抢人了！

抢人！抢人！抢人！ IT行业某岗位已经开始抢人了！

所谓抢滩鸿蒙&#xff0c;人才先行。鸿蒙系统火力全开后&#xff0c;抢人已成鸿蒙市场的主题词&#xff01; 智联招聘数据显示&#xff0c;春节后首周&#xff0c;鸿蒙相关职位数同比增长163%&#xff0c;是去年同期的2.6倍&#xff0c;2023年9-12月鸿蒙相关职位数同比增速为3…
阅读更多...
深入理解C++多线程系列——线程基础

深入理解C++多线程系列——线程基础

概念 在现代计算机中&#xff0c;多线程编程是一种强大的并发执行计数&#xff0c;允许多个线程在单个程序内部并行执行&#xff0c;提高程序的执行效率和响应速度。线程&#xff0c;作为CPU调度的最小单元&#xff0c;它被用来执行程序中的指令。一个线程是进程中的一个单一顺…
阅读更多...
跨境电商测评自养号需要解决哪些问题？

跨境电商测评自养号需要解决哪些问题？

现在做测评工作室这块的&#xff0c;真正有技术的每天单都做不过来&#xff0c;同样也滋生出很多找别人买个设备和账号就以为自己懂了&#xff0c;直接开始教学来割韭菜&#xff0c;很多人没接触过这行业&#xff0c;不知道里面的水很深&#xff0c;花了钱&#xff0c;却没有掌…
阅读更多...
移动端 UI 风格，魅力无限

移动端 UI 风格，魅力无限

移动端 UI 风格&#xff0c;打造极致体验
阅读更多...
在推荐四款软件卸载工具，让流氓软件无处遁形

在推荐四款软件卸载工具，让流氓软件无处遁形

Revo Uninstaller Revo Uninstaller是一款电脑软件、浏览器插件卸载软件&#xff0c;目前已经有了17年的历史了。可以扫描所有window用户卸载软件后的残留物&#xff0c;并及时清理&#xff0c;避免占用电脑空间。 Revo Uninstaller可以通过命令行卸载软件&#xff0c;可以快速…
阅读更多...
ChatGPT-4o独家揭秘：全国一卷高考语文作文如何轻松斩获满分？

ChatGPT-4o独家揭秘：全国一卷高考语文作文如何轻松斩获满分？

​一、2024年全国一卷高考 二、2018年全国一卷高考 三、2016年全国一卷高考 一、2024年全国一卷高考 技术进步的悖论&#xff1a;我们的问题真的在减少吗&#xff1f; 引言 随着互联网的普及和人工智能的应用&#xff0c;越来越多的问题能够快速得到解答。然而&#xff0c;这引…
阅读更多...
msvcr120.dll丢失怎样修复？为什么msvcr120.dll文件很重要

msvcr120.dll丢失怎样修复？为什么msvcr120.dll文件很重要

msvcr120.dll​ 是一个属于 Microsoft Visual C 2013 Redistributable package 的动态链接库文件。这个文件对于运行使用 Visual Studio 2013 开发的应用程序是必要的&#xff0c;因为它包含了C运行时库的一部分功能&#xff0c;这些功能是标准C库中与输入/输出操作、字符串操作…
阅读更多...
最新文章

Copyright @ 2022~2023