一、最大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因此我们可以使用前缀/后缀的思想来预处理一下
for(int i=1;i<=n;i++) pre[i]=gcd(pre[i-1],a[i]);
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];
for(int i=1;i<=n;i++) pre[i]=gcd(pre[i-1],a[i]);
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
∣ai−aj∣<ai∗aj,并且我们发现
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)
{
ll res=0;
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)
{
ll res=0;
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];
while (q--)
{
int x, y;cin >> x >> y;
for (const auto &i : st[x])
{
st[y].insert(i);
}
st[x].clear();
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[y].insert(i);
}
a[x].clear();
}
else
{
for(auto &i:a[y])
{
a[x].insert(i);
}
a[y].clear();
swap(a[x],a[y]);
}
cout<<a[y].size()<<'\n';
}
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[y].insert(i);
}
a[x].clear();
}
else
{
for(auto &i:a[y])
{
a[x].insert(i);
}
a[y].clear();
swap(a[x],a[y]);
}
cout<<a[y].size()<<'\n';
}
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int _=1;
while(_--) solve();
return 0;
}