【习题总结】差分问题

for(int i=2;i<=n;i++)     if(a[i]>a[i-1]) ans+=a[i]-a[i-1];
	cout<<ans+a[1];

  类似地： 此题的操作数也是差分相加减，修改前缀，加上基准值即可。

#include<bits/stdc++.h>
    #define fi first
    #define se second
    #define pb push_back
    #define LL long long
    #define PII pair<int, int> 
    #define PDD pair<double,double>
    using namespace std;
    typedef long long readtype;
    const int maxn = 1e5 + 5;
    const int inf = INT_MAX;
    const LL mod = 1e9 + 7;
    const double eps=1e-6;
     
    LL T;
     
    inline readtype read(){
          
   
    	readtype X=0; bool flag=1; char ch=getchar();
    	while(ch<0||ch>9) {
          
   if(ch==-) flag=0; ch=getchar();}
    	while(ch>=0&&ch<=9) {
          
   X=(X<<1)+(X<<3)+ch-0; ch=getchar();}
    	if(flag) return X;
    	return ~(X-1);
    }
     
    inline int double_cmp(double a,double b)
    {
          
   
        if(fabs(a-b)<eps) return 0;
        if(a<b) return -1;
        return 1;
    }
     
    int main(){
          
    
    	T = read();
    	while(T--)
    	{
          
   
    		int n = read();
    		int cnt_a=0,cnt_b=0;
    		string s1,s2;
    		cin>>s1;
    		cin>>s2;
    		s1=$ +s1;
    		s2=$ +s2;
    		if(s1[1]!=s2[1] || s1[n]!=s2[n])
    		{
          
   
    			cout<<-1<<endl;
    			continue;
    		}
    		vector<int> a(n+1,0);
    		vector<int> b(n+1,0);
    		vector<int> diff_a(n+1,0);
    		vector<int> diff_b(n+1,0);
    		for(int i=1;i<=n;i++)
    		{
          
   
    			a[i]=s1[i]-0;
    			diff_a[i]=a[i]^a[i-1];
    			b[i]=s2[i]-0;
    			diff_b[i]=b[i]^b[i-1];
    			if(i!=1)
    			{
          
   
    				cnt_a+=diff_a[i];
    				cnt_b+=diff_b[i];
    			}
    		}
    		if(cnt_a==cnt_b)
    		{
          
   
    			LL res=0;
    			int i=2,j=2;
    			while(i<=n && j<=n)
    			{
          
   
    				if(diff_b[j] && diff_a[i])
    				{
          
   
    					res+=abs(i-j);
    					i++;
    					j++;
    				}
    				else if(diff_b[j] && !diff_a[i]) i++;
    				else if(!diff_b[j] && diff_a[i]) j++;
    				else
    				{
          
   
    					i++;
    					j++;
    				}
    			}
    			cout<<res<<endl;
    		}
    		else
    		{
          
   
    			cout<<-1<<endl;
    		}
    	}
    	return 0;
    }

#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define LL long long
#define PII pair<int, int> 
#define PDD pair<double,double>
using namespace std;
const int maxn = 1e5 + 5;
const int inf = 0x3f3f3f3f;
const LL mod = 1e9 + 7;
int T;

inline int read(){
          
   
	int X=0; bool flag=1; char ch=getchar();
	while(ch<0||ch>9) {
          
   if(ch==-) flag=0; ch=getchar();}
	while(ch>=0&&ch<=9) {
          
   X=(X<<1)+(X<<3)+ch-0; ch=getchar();}
	if(flag) return X;
	return ~(X-1);
}

 
int main(){
          
    
	T = read();
	while(T--)
	{
          
   
		int n = read();
		vector<int> a(n+1);
		for(int i = 1; i <= n; i++)
			a[i]=read();
        vector<int> b;
        for(int i=2;i<=n;i++)
            b.pb((a[i]-a[i-1]+3)%3);
        b.pb((a[1]-a[n]+3)%3);
        int cnta=0,cntb=0;
        for(auto num:b)
        {
          
   
            if(num==1)
                cnta++;
            else if(num==2)
                cntb++;
        }
        if(cnta>=cntb)
            puts("Yes");
        else    
            puts("No");
	}
	return 0;
}