题目概述：一次操作选定一个区间，将区间内数的总和赋给区间内的某个数并清零区间内的其他数。判断(a)序列是否能变成(b)序列，如果能则输出最小操作数。
满分做法:
用双指针记录现在到了&a&序列的位置和(b)序列的位置，每次(b[i])不等于0时，(ans++),如果本身a[i]本身就符合条件再减回来。剩下的加就行了，如果加不够就输出-1.
另外需要开始判总和是否相等。
#include<queue>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<iostream>
using namespace std;
typedef long long ll;
const int maxm=1e+7;
int t,n,ans;
int a[maxm],b[maxm];
int solve()
{
int r=1;
ll sum=0;
ans=0;
for(int i=1;i<=n;i++)
{
if(!b[i]) continue;
ans++;
int l=r;
sum=0;
while((sum<b[i])&&(r<=n)) sum+=a[r++];
if(sum!=b[i]){
return -1;
}
if(i>=l&&i<=r-1&&a[i]==b[i]) ans--;//;如果段只包含了自己并且位置相同，我们就不需要浪费操作在它身上
}
return ans;
}
int main()
{
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
ll sum1=0,sum2=0;
for(int i=1;i<=n;i++)
scanf("%d",a+i),sum1+=a[i];
for(int i=1;i<=n;i++)
scanf("%d",b+i),sum2+=b[i];
if(sum1!=sum2)//如果b[i]后面有连续的0，下面的就不能输出-1了
{
printf("-1
");
continue;
}
printf("%d
",solve());
}
return 0;
}
满分做法：
因为都是2次幂(前面的值相加一定比新的小)，所以这个题直接最小生成树，记录一个到根节点的前缀和，(dis[x]+dis[y]-2*dis[lca])即为答案.
#include<queue>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<iostream>
using namespace std;
typedef long long ll;
const int maxm=3e5+7;
const ll mo=998244353;
int n,m,q;
int pre[maxm*2],last[maxm],other[2*maxm],l;
ll len[2*maxm];
int f[maxm];
int jump[maxm][23],dep[maxm];
ll inv=1;
ll w[maxm];
struct node
{
int x,y;
ll z;
}t[maxm];
void add(int x,int y,ll z)
{
l++;
pre[l]=last[x];
last[x]=l;
other[l]=y;
len[l]=z;
}
int find(int x)
{
if(x!=f[x])
f[x]=find(f[x]);
return f[x];
}
void dfs(int x)
{
for(int p=last[x];p;p=pre[p])
{
int v=other[p];
if(v==jump[x][0])
continue;
jump[v][0]=x;
dep[v]=dep[x]+1;
w[v]=(w[x]+len[p])%mo;
dfs(v);
}
}
int lca(int x,int y)
{
if(dep[x]<dep[y])
swap(x,y);
for(int j=0;j<=19;j++)
{
if((dep[x]-dep[y])&(1<<j))
x=jump[x][j];
}
if(x==y) return x;
for(int j=19;j>=0;j--)
{
if(jump[x][j]!=jump[y][j])
{
x=jump[x][j];
y=jump[y][j];
}
}
return jump[x][0];
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
f[i]=i;
for(int i=1;i<=m;i++)
{
inv=inv*2ll%mo;
scanf("%d%d",&t[i].x,&t[i].y);
t[i].z=inv;
int fx=find(t[i].x);
int fy=find(t[i].y);
if(fx!=fy)
{
f[fx]=fy;
add(t[i].x,t[i].y,t[i].z);
add(t[i].y,t[i].x,t[i].z);
}
}
dfs(1);
for(int j=1;j<=19;j++)
{
for(int i=1;i<=n;i++)
jump[i][j]=jump[jump[i][j-1]][j-1];
}
scanf("%d",&q);
for(int i=1;i<=q;i++)
{
int x,y;
scanf("%d%d",&x,&y);
printf("%lld
",((w[x]+w[y])%mo-(2*w[lca(x,y)])%mo+mo)%mo);//注意负数取模
}
return 0;
}