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

一、最大gcd(P149)

1、题解：

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

• 假设我们现在有$[a1,a2,a3,a4,a5]$，通过修改$a3$我们发现
  

2）也就是说，当我们修改$a3$的值时，gcd的部分组成是不变的

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

2、代码解析：

1）因为我们需要求解区间的$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）通过读题我们发现要满足：任意两个数组元素$ai,aj$，满足

$|ai-aj|<ai\ast 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;
}