当前位置: 首页 > article >正文

算法日记41:思维提升(最大gcd+好数组+简单的减法+球的颜色)

一、最大gcd(P149)

在这里插入图片描述

1、题解:

1)对于这种我们可以修改某个数字的,我们可以枚举能够修改的元素,观察规律

  • 假设我们现在有 [ a 1 , a 2 , a 3 , a 4 , a 5 ] [a1,a2,a3,a4,a5] [a1,a2,a3,a4,a5],通过修改 a 3 a3 a3我们发现
    在这里插入图片描述

2)也就是说,当我们修改 a 3 a3 a3的值时,gcd的部分组成是不变的

在这里插入图片描述

3)又因为 g c d gcd gcd随着元素增加,是非严格递减的,因此,当b3=gcd(a1~a2)或者b3=gcd(a4~a5)时结果是最大的

2、代码解析:

1)因为我们需要求解区间的 g c d gcd gcd因此我们可以使用前缀/后缀的思想来预处理一下

 	//前缀来维护(1~i)的gcd
    for(int i=1;i<=n;i++) pre[i]=gcd(pre[i-1],a[i]);  

    //后缀来维护(i~n)的gcd
    for(int i=n;i>=1;i--) last[i]=gcd(last[i+1],a[i]);

    //遍历求解删除的元素
    int res=-1;
    for(int i=1;i<=n;i++) res=max(res,gcd(pre[i-1],last[i+1]));

3、完整代码如下:

#include<bits/stdc++.h>
using namespace std;  

const int N=2e5+7;
int a[N];
int pre[N],last[N];

int gcd(int a,int b){return b==0 ? a : gcd(b,a%b);};

void solve()
{
    memset(a,0,sizeof(a));
    memset(pre,0,sizeof(pre));
    memset(last,0,sizeof(last));
    
    int n;cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];

    //前缀来维护(1~i)的gcd
    for(int i=1;i<=n;i++) pre[i]=gcd(pre[i-1],a[i]);  

    //后缀来维护(i~n)的gcd
    for(int i=n;i>=1;i--) last[i]=gcd(last[i+1],a[i]);

    //遍历求解删除的元素
    int res=-1;
    for(int i=1;i<=n;i++) res=max(res,gcd(pre[i-1],last[i+1]));
    cout<<res<<'\n'; 
}

int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int _=1;cin>>_;
    while(_--) solve();
    return 0;
}

二、好数组

在这里插入图片描述

1、题解:

1)通过读题我们发现要满足:任意两个数组元素 a i , a j ai,aj ai,aj,满足

∣ a i − a j ∣ < a i ∗ a j |ai-aj|<ai*aj aiaj<aiaj,并且我们发现 a i , a j ai,aj ai,aj有以下几种情况

  • 1#a[i]=0,a[j]=0,不满足条件
  • 2#a[i]=0,a[j]>0,不满足条件
    在这里插入图片描述
  • 3#a[i]>0,a[j]>0,我们发现此时一定成立
    在这里插入图片描述

2)因此,我们只需要判断是否有0存在即可

2、代码解析

void solve()
{
    int n;cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];

    for(int i=1;i<=n;i++) 
    {
      if(a[i]==0) 
      {
        cout<<"NO"<<'\n';
        return ;
      }
    }
    cout<<"YES"<<'\n';
}

三、简单的减法

在这里插入图片描述

1、题解:

1)拿到题目,我们发现:贪心/构造/DP都不好做,也就是正向考虑很困难,我们可以考虑用求解->求证,但是此时我们就需要单调性的支撑

在这里插入图片描述

2)通过观察我们发现,操作次数mid确实存在单调性

在这里插入图片描述

  • 因此我们可以使用二分答案来判断答案的合法性
    在这里插入图片描述

3)那么我们如何判断这个操作次数是否合法呢?(check(mid)的写法)

  • 首先,当我们的元素大小>mid时,会出现重复选择的情况,因此我们可以直接把元素缩小为mid(因为不能重复选择一个数字,因此一个元素最多被选择mid次)
    在这里插入图片描述
bool check(ll x)  //判断x次操作是否合法
{
  ll res=0; //表示这个数组在x次操作下能够符合条件的总的元素次数
  for(ll i=1;i<=n;i++)
  {
    res+=min(x,a[i]);
  }
  if(res>=x*k)  return true;  //表示合法
  else return false;
}

2、完整代码

#include <bits/stdc++.h>
using namespace std;

const int N=1e5+7;
typedef long long ll;
ll a[N];
ll n,k;

bool check(ll x)  //判断x次操作是否合法
{
  ll res=0; //表示这个数组在x次操作下能够符合条件的总的元素次数
  for(ll i=1;i<=n;i++)
  {
    res+=min(x,a[i]);
  }
  if(res>=x*k)  return true;  //表示合法
  else return false;
}

void solve()
{
  cin>>n>>k;
  for(int i=1;i<=n;i++) cin>>a[i];

  ll l=0,r=2e14+7;  //二分枚举操作次数
  while(l+1<r)
  {
    ll mid=(l+r)>>1;
    if(check(mid)) l=mid; //判断这个操作是否合法
    else r=mid;
  }
  cout<<l<<'\n';
}

int main()
{
  ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
  int _=1;
  while(_--) solve();
  return 0;
}

四、球的颜色

在这里插入图片描述

1、题解:

1)拿到题目,我们最朴素的想法就是按照题目的意思来模拟样例,也就是遍历x中的所有元素,插入到y中去

set<int> st[N];	//表示第i个盒子
while (q--) 
{
   int x, y;cin >> x >> y;
   
   for (const auto &i : st[x]) //遍历st[x]中的所有小球
   {
     st[y].insert(i);	//插入到y中去
   }
   st[x].clear();	//清空小盒子 x
   cout << st[y].size() << '\n';
 }

2)但是我们发现让大盒子->小盒子这一过程时间复杂度非常之高,因此我们可以始终让小盒子->大盒子来使得时间复杂度降低

在这里插入图片描述

  while(q--)
  {
    ll x,y;cin>>x>>y;
    //因为小盒子->大盒子 一定比大盒子->小盒子来的快,
    //因此我们应该始终让小盒子->大盒子
    if(a[x].size()<=a[y].size()) //此时是小盒子->大盒子
    {
      for(auto &i:a[x]) //取出a[x]中的所有球
      {
        a[y].insert(i);   //插入到a[y]中
      }
      a[x].clear();  //清空小盒子x
    }
    else  //此时是大盒子->小盒子
    {
      for(auto &i:a[y]) //
      {
        a[x].insert(i); //小盒子->大盒子
      }
      a[y].clear();  //清空小盒子y
      swap(a[x],a[y]);  //再把(x,y)交换回来
    }
    cout<<a[y].size()<<'\n'; //输出y中的元素个数
  }

2、完整代码如下:

#include <bits/stdc++.h>
using namespace std;

const int N=3e5+7;
typedef long long ll;

set<ll>a[N];  //用来表示一个盒子,自动排序去重

void solve()
{
  ll n,q;cin>>n>>q;
  for(ll i=1;i<=n;i++)  
  {
    ll x;cin>>x;
    a[i].insert(x); //初始化盒子
  }
  while(q--)
  {
    ll x,y;cin>>x>>y;
    //因为小盒子->大盒子 一定比大盒子->小盒子来的快,
    //因此我们应该始终让小盒子->大盒子
    if(a[x].size()<=a[y].size()) //此时是小盒子->大盒子
    {
      for(auto &i:a[x]) //取出a[x]中的所有球
      {
        a[y].insert(i);   //插入到a[y]中
      }
      a[x].clear();  //清空小盒子x
    }
    else  //此时是大盒子->小盒子
    {
      for(auto &i:a[y]) //
      {
        a[x].insert(i); //小盒子->大盒子
      }
      a[y].clear();  //清空小盒子y
      swap(a[x],a[y]);  //再把(x,y)交换回来
    }
    cout<<a[y].size()<<'\n'; //输出y中的元素个数
  }
}

int main()
{
  ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
  int _=1;
  while(_--) solve();
  return 0;
}

http://www.kler.cn/a/588958.html

相关文章:

  • Cookie与Session详解
  • QuickAPI 和 DBAPI 谁更香?SQL生成API工具的硬核对比(一)
  • 从零实现区块链共识算法:用Python解锁去中心化世界的关键
  • 企业管理杂谈:产品经理的选拔和培养——企业产品创新发展的关键
  • Python核心语法-数据基本运算(一)
  • 玩转python:通俗易懂掌握高级数据结构:collections模块之defaultdict
  • Android第二次面试总结(项目拷打实战)
  • 线性代数(1)用 excel 计算鸡兔同笼
  • 0CTF 2016 piapiapia 1
  • Kafka的流量控制机制
  • 玩转python:通俗易懂掌握高级数据结构-collections模块之UserList
  • AI大语言模型LLM学习-基于Vue3的AI问答页面
  • 深入解析前后端分离架构:原理、实践与最佳方案
  • [IP]RGMII
  • 通过deepseek学习lua写网页
  • 人工智能与机器学习——系统学习规划
  • 鸿蒙应用开发—ZDbUtil高效使用数据库
  • 82.HarmonyOS NEXT 性能优化指南:从理论到实践
  • 【大模型】Transformer、GPT1、GPT2、GPT3、BERT 的论文解析
  • 【RabbitMQ】rabbitmq在spring boot中的使用