暑假补题记 6

whatdo / 2023-08-14 / 原文

Problem - C - Codeforces

找最大的简单环

题解：首先就是如果有一条链的左右起点相同，那么起点链就要强制更换

然后就是一直递归的去跑，不断判断这个链可不可以当起点链，就是当它比前面跑的环都大的时候，那我们就把这个链当做新的起点链，否则一直跑环就可以了，最后一条链一般都直接加上即可因为最后一个环肯定可以跑完这一条链

 if(abs(b[i+1]-c[i+1])>sum+a[i]-(abs(b[i+1]-c[i+1])+1)) sum=abs(b[i+1]-c[i+1])+1;

这里就是更新成新的起点链，注意前面的abs不可以加1因为无论如何他要成环经过你的链会用到两个或者一个点

#include <bits/stdc++.h>
#pragma  GCC optimize("Ofast")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cmath>
//#define double long double
#define int long long
#define endl '\n';
using namespace std;
const int N=1e5+7,M=1e1;
const int INF = 0x3f3f3f3f;
const int mod=998244353;
typedef pair<int,int> PII;

int a[N],b[N],c[N];

int32_t  main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int t;
    cin>>t;
    while (t--) {
        int n;
        cin >> n;
        for (int i = 1; i <= n; i++) cin >> a[i];
        for (int i = 1; i <= n; i++) cin >> b[i];
        for (int i = 1; i <= n; i++) cin >> c[i];


        int x = 0, y = 0;
        x = b[2], y = c[2];
        int sum = abs(x - y) + 1;
        int ans =  0;
        for (int i = 2; i < n; i++) {
            if (b[i + 1] == c[i + 1]) {
                ans = max(ans, sum + a[i]);
                sum = 1;
            } else {
                ans=max(ans,sum+a[i]);
                if(abs(b[i+1]-c[i+1])>sum+a[i]-(abs(b[i+1]-c[i+1])+1)) sum=abs(b[i+1]-c[i+1])+1;
                else sum+=a[i]-abs(b[i+1]-c[i+1])+1;
            }

        }
        sum+=a[n];
        ans=max(ans,sum);
        cout << ans << endl;

    }


}