题目链接

解题思路

小坑有点多，CF这种不考算法的思维题需要多写一些。

• 首先，这个连接是可以反向连接的，所以不需要考虑a[i]和b[i]的大小关系(使用abs()) 开始写的时候特判二者的大小关系实则没有必要

• 其次是当a[i]和b[i]相等时，这意味着从此时开始必须重新计数。
  与之相对应的是当a[i]和b[i]不相等时，此时的数值可以并入左边已有的环。此时max取最优。

• 最后一个害我没过的坑是，此时既可以并入左边，也有可能从此时开始重新计数。
  因为并入左侧，意味着必须舍弃两个接触点之间的长度；而两点之间的长度是有可能比左侧更长的。

总而言之是一道不错的题目，虽然这个题害我痛苦了一个小时+掉分。但是依然是使人思维严密的一个题目。

代码实现

#include<bits/stdc++.h>
#define int long long
using namespace std;

int T;
int n,m;
struct node{
    int len;
    int a,b;
}a[1000100];

signed main(){
    //freopen("data.txt","r",stdin);
    //freopen("C.out","w",stdout);
    cin>>T;
    while(T--){
        cin>>n;
        int maxx=0;
        int ans=0;//maxx记录当前的值，ans记录最大值
        for(int i=1;i<=n;i++){
            cin>>a[i].len;
        }
        for(int i=1;i<=n;i++){
            cin>>a[i].a;
        }
        for(int i=1;i<=n;i++){
            cin>>a[i].b;
        }
        if(n>=2){
            maxx=abs(a[2].b-a[2].a);
            maxx+=2;
            maxx+=a[2].len-1;
            ans=maxx;
        }
        for(int i=3;i<=n;i++){
            if(a[i].a!=a[i].b){//二者不相等，并入左侧
                maxx-=abs(a[i].b-a[i].a);
                maxx+=2; 
                maxx+=a[i].len-1;
                ans=max(maxx,ans);
            }
            if(a[i].a==a[i].b){//二者相等，重新计数
                maxx=0;
                maxx+=2;
                maxx+=a[i].len-1;
                ans=max(maxx,ans);
            }
            if(abs(a[i].b-a[i].a)+2+a[i].len-1 > maxx){//若从此时开始较优，更新之。
                ans=max(ans,abs(a[i].b-a[i].a)+2+a[i].len-1);
                maxx=abs(a[i].b-a[i].a)+2+a[i].len-1;
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}