许可优化
软件
产品
分类讨论:
然后两种情况取最小值。
情况一：使得 A ，B 数组内 , 0,1 个数相等即可， Ans1= (方案一操作次数 +1) 。
情况二：使得 A ，B 数组内 , 0,1 个数每一位相等即可， Ans2= (方案二操作次数)。
综上：答案为 (Ans1 , Ans2)_{min}。
#include<bits/stdc++.h>
//#pragma GCC optimize(2)
using namespace std;
#define ri register int
int T;
int n;
int a[1000050];
int b[1000050];
int main()
{
int cnta0,cnta1,cntb0,cntb1;
scanf("%d",&T);
while(T--)
{
int ans=0,ansa=0;
cnta1=cnta0=cntb0=cntb1=0;
scanf("%d",&n);
for(ri i=1; i<=n; ++i)
{
scanf("%d",&a[i]);
if(a[i]==0)
{
cnta0++;
}
else
{
cnta1++;
}
}
for(ri i=1; i<=n; ++i)
{
scanf("%d",&b[i]);
if(b[i]==0)
{
cntb0++;
}
else
{
cntb1++;
}
}
int det=abs(cnta1-cntb1);
for(register int i=1; i<=n; ++i)
{
if(det==0)
{
break;
}
if(a[i]!=b[i])
{
det--;
ans++;
}
}
ans++;
//
for(register int i=1; i<=n; ++i)
{
if(a[i]!=b[i])
{
ansa++;
}
}
cout<<min(ansa,ans)<<endl;
}
}
构造题，考虑 b[1] ,最优情况为 b[1]==a[1] ，因为使得 b[2] 的取值情况更多。
为接下来的数据留出更多的机会去选择 , (这里实际上就是贪心策略)。
\because a_i = gcd(b_i,b_{i+1}) 且 a_{i+1} = gcd(b_{i+1},b_{i+2})
\therefore b_{i+1}= gcd(a_i,a_{i+1})
又 \because gcd(b_i,b_{i+1}) =a_i
\therefore 有判断条件：
if(gcd(b_i,b_{i+1}) \ne a_i) 则 puts("NO");
#include<bits/stdc++.h>
//#pragma GCC optimize(2)
using namespace std;
#define ri register int
int T;
int n;
int a[1000050];
int b[1000050];
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(ri i=1;i<=n;++i)
{
scanf("%d",&a[i]);
}
bool ret=1;
b[1]=a[1];
b[n+1]=b[n];
for(ri i=2;i<=n;++i)
{
b[i]=a[i-1]*a[i]/__gcd(a[i],a[i-1]);
if(__gcd(b[i],b[i-1])!=a[i-1])
{
ret=0;
break;
}
}
if(ret==0)
{
puts("NO");
}
else
{
puts("YES");
}
}
}
这题方法多样，这里介绍其中两种 1.dp 2.双指针
考虑 f_i 代表以 i 结尾的 “好数组个数”。
于是考虑前一位 f_{i-1} 能否继承 ?
若能 ，即 f_{i-1}+1 继承 。
否则 ，考虑以 i 为结尾的连续区间的个数 ，易知有 a[i] 个新子区间 。
则有状态转移方程 : f[i] = min(f[i-1]+1,a[i]);
#include<bits/stdc++.h>
//#pragma GCC optimize(2)
using namespace std;
int n,T;
int a[200005];
int f[200005];
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(int i=1;i<=n;++i)
{
scanf("%d",&a[i]);
f[i]=0;
}
f[1]=1;
long long ans=0;
for(int i=1;i<=n;++i)
{
f[i]=min(f[i-1]+1,a[i]);
ans+=f[i];
}
cout<<ans<<endl;
}
}
2.双指针
模拟两个指针 l,r 。
考虑区间 [l,r] 问题 ,
若 a[r]<r-l+1 , 则不满足题目条件。
则左边界偏小， l++ ;
反之， r++ 。
注意循环退出的边界情况
#include<bits/stdc++.h>
//#pragma GCC optimize(2)
using namespace std;
#define int long long
#define ri register int
int T;
int n;
int a[200050];
signed main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(ri i=1;i<=n;++i)
{
scanf("%d",&a[i]);
}
int l=1;
int r=1;
int res=0;
while(l<=r)
{
if(l>n||r>n)
{
break;
}
while(a[r]<r-l+1)
{
++l;
}
res=res+r-l;
r++;
}
cout<<res+n<<endl;
}
}
技术文档
热门文章
155-2731-8020
