最长简单环 CF eduRound 103 C 思维

题意

给定条链，每条链有个点，表示第条链的第1个点连接上一条链的第几个点，表示第条链的最后一个点连接上一条链的第几个点。

问最长的简单环的长度。

思路

我首先将数据重新处理，是无用的，整体往左移一个位置。这样，表示的就是第条链点分别连接下一条链的第1个点和最后一个点。

1. 当重合，会将全图切割成若干个环，答案只能在切分的环内产生
2. 考虑不重合的情况，维护单链对环的贡献，容易想到如果要尽可能触及尽可能远的链，就只能收纳，直到某个重合，再重新计算对环的贡献
3. 由于连的是下一条链的两端，于是随时可以放弃继续连，直接在下一条链成环

考虑到这里，就可以过第二个test case了，但是漏洞依然存在：维护之前的半环，可能还不如直接放弃，转而维护本链的。于是本题通过。

Solution

#include <bits/stdc++.h>
#define sc(x) scanf("%lld", &(x))
#define pr(x) printf("%lld\n", (x))
#define rep(i, l, r) for (int i = (l); i <= (r); ++i)
using namespace std;
typedef long long ll;
const int N = 1e5 + 7;
const int mod = 1e9 + 7;
ll c[N], a[N], b[N];
int main() {
    ll t, x, n;
    sc(t);
    while (t--) {
        sc(n);
        for (int i = 1; i <= n; ++i) sc(c[i]);
        sc(x);
        for (int i = 1; i < n; ++i) sc(a[i]);
        sc(x);
        for (int i = 1; i < n; ++i) sc(b[i]);
        ll ans = 0, now = abs(a[1] - b[1]) + 1;
        for (int i = 2; i <= n; ++i) {
            ans = max(ans, now + c[i]);
            if (a[i] > b[i]) swap(a[i], b[i]);
            ll up = a[i];
            ll down = c[i] - b[i] + 1;
            ll tot = up + down;
            ll out = tot > c[i] ? c[i] : tot;
            ll in = abs(a[i] - b[i]) + 1;
            now = max(now + out, in);
            if (a[i] == b[i]) {
                ans = max(ans, now);
                now = 1;
            }
        }
        pr(ans);
    }
    return 0;
}
/*
3
3
3 4 2
-1 1 4
-1 2 1
*/