头像

小小_88

湖州职业技术学院




离线:2小时前


最近来访(527)
用户头像
风铃_12
用户头像
lihua777
用户头像
rd0
用户头像
白_33
用户头像
大同一中信息学竞赛队_official
用户头像
MemoPad
用户头像
levelna
用户头像
zhuifeng
用户头像
kkoier
用户头像
鼠鼠我
用户头像
早点睡觉_1
用户头像
reclusive
用户头像
琴忆庭.
用户头像
yxc的小迷妹
用户头像
Nineteen_Zhang
用户头像
cwxzh
用户头像
无所谓我不会出手
用户头像
云衣醉梦
用户头像
lqmm1
用户头像
种花家的兔兔


小小_88
16小时前

MEX and Increments

C++ 代码

/*
要想让数组的 mex 等于 i,其实就是需要凑出 0 ~ i - 1,并且清掉所有的 i。

假设序列中 i 的数量为 cnt[i]。

我们只需要求出凑出 0 ~ i - 1 的最小操作数 res,则让数组的 mex 为 i 的最小操作数
就是 res + cnt[i]

因为操作只能令一个数 + 1,所以 i ~ n 不需要操作,只需要考虑 0 ~ i - 1 中的数。

对于只出现一次的数,肯定要保留,只能去操作出现多次的数,假设现在 0 ~ i - 1 
中只有一个数 x 需要凑,那么先让我们从出现多次的数中取一个最大的数来凑,就能让
操作数最小。

而如果 0 ~ i - 1 中有多个数需要凑,同理我们需要取最大的几个数来凑,同样能让操作数最小。

而如果 0 ~ i - 1 无法被完整凑出,则此时对于更大的 i 也同样无法走出 0 ~ i - 1,此时 mex
就永远不可能为 i,直接令第一个无解的 i 及其后面的所有数都为 -1,即无解。
*/

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

typedef long long LL;

void work()
{
    int n;
    scanf("%d", &n);
    vector<int> a(n), cnt(n + 1), s(n);
    for(int i = 0; i < n; i++) scanf("%d", &a[i]);

    sort(a.begin(), a.end());

    priority_queue<int, vector<int>, greater<int>> dwn;
    priority_queue<int> up;
    for(int i = 0; i < n; i++)
    {
        int j = i;
        while(j + 1 < n && a[j + 1] == a[i]) dwn.push(a[i]), j++;
        cnt[a[i]] = j - i + 1;
        i = j;
    }

    int over = n + 1;
    for(int i = 0; i < n; i++)
            if(!cnt[i])
            {
                if(dwn.size() && dwn.top() < i) dwn.pop();
                else
                {
                    over = i + 1;
                    break;
                }
            }

    LL res = 0;
    for(int i = 0; i < over; i++)
    {
        if(i && !cnt[i - 1]) res += i - 1 - up.top(), up.pop();

        printf("%lld ", res + cnt[i]);

        for(int j = 0; j < cnt[i] - 1; j++) up.push(i);
    }
    for(int i = over; i <= n; i++) printf("-1 ");
    puts("");
}

int main()
{
    int T;
    scanf("%d", &T);
    while(T--) work();
    return 0;
}



小小_88
19小时前

Shinju and the Lost Permutation

C++ 代码

/*
只有当弟 i 次操作后,a[1] = n,此时 c[i] 才会等于 1,其他任何时候 a[1] 都小于 n,
这就保证 c 数组中一定只有一个 1

然后对于弟 i 次操作,我们将最后一个数挪到前面来,如果此时 a[1] > a[2],则 c[i + 1] <= c[i],
如果 a[1] < a[2],则 c[i + 1] = c[i] + 1。因此不管哪种情况,c[i + 1] - c[i] 都一定 <= 1。
如果存在某一个 c[i + 1] - c[i] > 1,则一定无解

由于 c 数组中存在一个 1 会导致我们没法连贯的去判断 c[i + 1] - c[i] <= 1 是否满足,
但是我们可以发现我们每次都是将末尾的数挪到前面来,经过 n 次操作得到的序列就是原序列,
这意味着 c[n + 1] = c[1],所以 c 数组其实是一个环形的连续关系,只有当 c[i] = n 时,
c[i + 1] 是 1,这有这一个位置不连贯,因此我们不停的可以将末尾数挪到前面到,直到 c[1] = 1,
此时整个数组就是连贯的了,而且由于整个操作是环形的,因此如果新数组有解,原数组也有解。

然后我们还需要保证 c[1] = 1 时一定能构造出解才行,这是一定的,首先 a[1] 一定是 n,
假设 c[i] = 2 的位置有 x 个,则我们将 n - x ~ n - 1 都留给 c[i] = 2 的位置,
并且是将这些数从小到大依次留给从前往后的每个位置,按照这个思路同样给 c[i] = 3,
c[i] = 4 等等的位置分配数,最终一定能构造出一个合法解,至于为什么一定正确,可以
自行构造出来验证,比较直观
*/

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>

using namespace std;

void work()
{
    int n;
    scanf("%d", &n);
    vector<int> a(n);
    for(int i = 0; i < n; i++) scanf("%d", &a[i]);

    if(count(a.begin(), a.end(), 1) != 1)
    {
        puts("NO");
        return;
    }

    int p = find(a.begin(), a.end(), 1) - a.begin();
    rotate(a.begin(), a.begin() + p, a.end());
    for(int i = 1; i < n; i++)
        if(a[i] - a[i - 1] > 1)
        {
            puts("NO");
            return;
        }
    puts("YES");
}

int main()
{
    int T;
    scanf("%d", &T);
    while(T--) work();
    return 0;
}



基环树的相关概念

基环树: 给定一棵无向树,包含 $n$ 个点 $n-1$ 条边,在树中任意两个点之间加一条边,此时树中有且仅有一个环,此时整棵树的形状应该是以环为中心,环上每个点都可能向环外延伸出一棵子树,这就是一棵基环树。对于每棵基环树,恰好有 $n$ 个点 $n$ 条边。

可以发现,仙人掌是有多个简单环,而基环树只有一个简单环,因此基环树其实是一个特殊的仙人掌。

如果给基环树中每条边一个方向,环上边的方向都要一致,如果以环上每个点为根的子树上的边都是指向环外,则称为外向树。如果以环上每个点为根的子树上的边都是指向环内,则称为内向树。

若干棵基环树构成的图,被称为基环(树)森林。若干棵外向树构成的图,被称为外向树森林。若干棵内向树构成的图,被称为内向树森林。

对于一张图,如果图中每个点恰好有 $1$ 条入边或恰好有 $1$ 条出边,那么这张图一定是一个基环森林。


基环树的应用:

基环树问题的常见题型就是求树上的某些信息。

在求树上的信息的时候一般有两种常见的做法,一种是对于环上节点用单调队列求最值,从而快速得到某些信息。一种是将环上某一条边删去,将基环树问题转化成普通的树上问题,用树形 $dp$ 来求。

具体题型可参考:岛屿问题骑士问题




创世纪问题

解题思路:

由于每个点可以限制另外一个点,如果我们看作从每个点向他限制的点连边,则本题就是一个基环森林。我们就是要在一个基环森林中选尽可能多的点,使得每个点都能被某一个没选中的点限制。

由于基环森林中每一棵基环树都是相互独立的,因此我们可以单独考虑每一棵基环树中最多能选择多少个点。

我们先考虑如果在一棵普通的树中如何求,一个点被限制就意味着有一个点指向它,因此就是要保证每个点的父节点都不能被选择,这样的方案我们可以用树形 $dp$ 来求。

设 $f_{u,0}$ 表示从以 $u$ 为根的子树中选若干个点,且不选 $u$ 的所有方案的最大值。设 $f_{u,1}$ 表示从以 $u$ 为根的子树中选若干个点,且选择 $u$ 的所有方案的最大值。

设 $u$ 的每个父节点为 $s$,可得状态转移方程:

$$
\begin{cases}
f_{u,0} = \sum \max{\lbrace f_{s,0}, f_{s,1} \rbrace} \newline
f_{u,1} = \max \lbrace f_{u,0} - \max{\lbrace f_{t,0},f_{t,1} \rbrace} + f_{t,0} + 1 \rbrace~~(t \in s)
\end{cases}
$$

可以发现这里的树形 $dp$ 中每个点的状态是通过父节点递推过来的,因此我们需要建一个反向边,反向递推。

但是基环树是没法做树形 $dp$ 的,因此我们可以将环上某一条边断开,这样基环树就能变成一棵普通的树,就能做树形 $dp$ 了,我们取环上一点 $p$,将 $p \rightarrow A_p$ 的边断开,此时我们可以将所有方案分成两类,一类是
不用 $p \rightarrow A_p$ 这条边,这就意味着要么不选 $A_p$,要么选 $A_p$ 并且有另外一条边指向 $A_p$。此时没有用到 $p \rightarrow A_p$ 这条边,所以对 $p$ 没有任何限制,我们从 $p$ 开始求一遍树形 $dp$,最终得到两个状态 $f_{p,0}$ 和 $f_{p,1}$,由于 $p$ 选不选都行,因此这一类的答案就是这两个状态取一个最大值。

另一类是用 $p \rightarrow A_p$,这意味着我们一定要选 $A_p$,且一定不选 $p$,那么我们只需要在做树形 $dp$ 的过程中特判一下 $A_p$ 一定要选即可,最终同样得到两个状态 $f_{p,0}$ 和 $f_{p,1}$,由于 $p$ 此时一定不能选,因此这一类的答案就是 $f_{p,0}$

最终再从这两类情况的答案中取一个最大值,就是整个的答案。

注意,本题按照每个点向它限制的点连边的话,会得到一棵内向树,由于内向树有多个入度为 $0$ 的点,而树形 $dp$ 需要从一个根节点往下递归,因此这里需要建反向边,此时将 $p \rightarrow A_p$ 这条边删掉后,$p$ 就是根节点,我们就可以从 $p$ 进行递推,而前面我们分析树形 $dp$ 时也分析到需要建反向边,这里一举两得。


C++ 代码

#include <iostream>
#include <cstring>

using namespace std;

const int N = 1000010, INF = 0x3f3f3f3f;

int n;
int h[N], e[N], rm[N], ne[N], idx; //邻接表
bool st[N], ins[N]; //st 记录每个点是否被搜过,ins 记录每个点是否在栈中
//f[i][0] 表示从 i 为根的子树中选若干个节点,且不选 i 的所有方案的最大值
//f[i][i] 表示从 i 为根的子树中选若干个节点,且选择 i 的所有方案的最大值
int f1[N][2], f2[N][2];
int res; //记录答案

void add(int a, int b) //添加边
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

void dfs_f(int u, int ap, int f[][2]) //树形 dp 求以 u 根为的子树中必选 ap 的所有方案的最大值
{
    //不选 u
    for(int i = h[u]; i != -1; i = ne[i])
    {
        if(rm[i]) continue;
        int j = e[i];
        dfs_f(j, ap, f);
        f[u][0] += max(f[j][0], f[j][1]);
    }

    //如果 u 必选,则 u 已经被 p 限制,其他子节点可选可不选
    if(u == ap) f[u][1] = f[u][0] + 1;
    else
    {
        //选 u
        f[u][1] = -INF;
        for(int i = h[u]; i != -1; i = ne[i])
        {
            if(rm[i]) continue;
            int j = e[i];
            f[u][1] = max(f[u][1], f[u][0] - max(f[j][0], f[j][1]) + f[j][0] + 1);
        }
    }
}

void dfs_c(int u, int from) //找出所有基环树的环
{
    st[u] = ins[u] = true;
    for(int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if(!st[j]) dfs_c(j, i);
        else if(ins[j]) //找到环
        {
            rm[i] = 1; //将边 ap -> p 删去
            dfs_f(j, -1, f1); //不用边 ap -> p
            dfs_f(j, u, f2); //用边 ap -> p(必选 ap,必不选 p)
            res += max(max(f1[j][0], f1[j][1]), f2[j][0]); //累加所有方案的最大值
        }
    }
    ins[u] = false;
}

int main()
{
    scanf("%d", &n);

    memset(h, -1, sizeof h); //初始化邻接表

    for(int i = 1; i <= n; i++)
    {
        int a;
        scanf("%d", &a);
        add(a, i); //有向边
    }

    //找出所有基环树的环
    for(int i = 1; i <= n; i++)
        if(!st[i])
            dfs_c(i, -1);

    printf("%d\n", res);

    return 0;
}


活动打卡代码 AcWing 359. 创世纪

#include <iostream>
#include <cstring>

using namespace std;

const int N = 1000010, INF = 0x3f3f3f3f;

int n;
int h[N], e[N], rm[N], ne[N], idx; //邻接表
bool st[N], ins[N]; //st 记录每个点是否被搜过,ins 记录每个点是否在栈中
//f[i][0] 表示从 i 为根的子树中选若干个节点,且不选 i 的所有方案的最大值
//f[i][i] 表示从 i 为根的子树中选若干个节点,且选择 i 的所有方案的最大值
int f1[N][2], f2[N][2];
int res; //记录答案

void add(int a, int b) //添加边
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

void dfs_f(int u, int ap, int f[][2]) //树形 dp 求以 u 根为的子树中必选 ap 的所有方案的最大值
{
    //不选 u
    for(int i = h[u]; i != -1; i = ne[i])
    {
        if(rm[i]) continue;
        int j = e[i];
        dfs_f(j, ap, f);
        f[u][0] += max(f[j][0], f[j][1]);
    }

    //如果 u 必选,则 u 已经被 p 限制,其他子节点可选可不选
    if(u == ap) f[u][1] = f[u][0] + 1;
    else
    {
        //选 u
        f[u][1] = -INF;
        for(int i = h[u]; i != -1; i = ne[i])
        {
            if(rm[i]) continue;
            int j = e[i];
            f[u][1] = max(f[u][1], f[u][0] - max(f[j][0], f[j][1]) + f[j][0] + 1);
        }
    }
}

void dfs_c(int u, int from) //找出所有基环树的环
{
    st[u] = ins[u] = true;
    for(int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if(!st[j]) dfs_c(j, i);
        else if(ins[j]) //找到环
        {
            rm[i] = 1; //将边 ap -> p 删去
            dfs_f(j, -1, f1); //不用边 ap -> p
            dfs_f(j, u, f2); //用边 ap -> p(必选 ap,必不选 p)
            res += max(max(f1[j][0], f1[j][1]), f2[j][0]); //累加所有方案的最大值
        }
    }
    ins[u] = false;
}

int main()
{
    scanf("%d", &n);

    memset(h, -1, sizeof h); //初始化邻接表

    for(int i = 1; i <= n; i++)
    {
        int a;
        scanf("%d", &a);
        add(a, i); //有向边
    }

    //找出所有基环树的环
    for(int i = 1; i <= n; i++)
        if(!st[i])
            dfs_c(i, -1);

    printf("%d\n", res);

    return 0;
}



骑士问题

解题思路:

如果将每个骑士向讨厌的人连边,则可以看作每个点只有一条出边,因此这就是一个基环森林。

然后要求我们在基环森林中选出若干个点,使得任意两个点没有公共边,要求选出的最大点权和。

可以发现基环森林中每棵基环树的选法都是独立的,因此我们可以对于每棵基环树单独考虑如何选点。如果是一棵普通的树,我们可以直接用树形 $dp$ 来求,但是本题是一棵基环树,存在循环依赖就没法用 $dp$ 了。

我们可以考虑将一条边断开,取环上某一点 $p$,$p$ 讨厌 $A_p$,则所有方案可以分成两种,一种是选 $p$,一种是不选 $p$,如果我们将 $p \rightarrow A_p$ 这条边断开,那么基环树就会变成一棵树,我们就可以在树上做树形 $dp$ 了,我们要在做树形 $dp$ 的时候把选 $p$ 不选 $p$ 的方案都枚举到,我们可以分别枚举这两种方案。对于不选 $p$ 的情况,此时 $A_p$ 可选可不选,因此 $p \rightarrow A_p$ 这条边就没有意义了,因为此时 $A_p$ 选还是不是和 $p$ 没有关系了,那么这条边删去就不会造成任何影响,我们直接在删完边的树上求一遍树形 $dp$ 即可。

这里的树形 $dp$ 我们设 $f_{u,0}$ 表示在以 $u$ 为根的子树中选若干个点且不选 $u$ 的所有方案的最大值,$f_{u,1}$ 表示在以 $u$ 为根的子树中选若干个点且选 $u$ 的所有方案的最大值。

则状态转移方程也比较好考虑,设 $u$ 的每一个子节点是 $s$,得到以下状态转移方程:

$$
\begin{cases}
f_{u,0} = \sum \max{\lbrace f_{s,0}, f_{s,1} \rbrace} \newline
f_{u,1} = \sum f_{s,0}
\end{cases}
$$

最终我们对于 $p$ 会得到两个状态 $f_{p,0}$ 和 $f_{p,1}$,此时不选 $p$ 的所有方案的最大值就是 $f_{p,0}$

然后考虑选 $p$ 的情况,此时就意味着 $A_p$ 一定不能选,那么我们仍然可以按照上述的树形 $dp$ 来做,但是在 $A_p$ 这里需要特判一下,$A_p$ 只能不选。这样我们又能得到两个状态 $f_{p,0}$ 和 $f_{p,1}$,此时选 $p$ 的所有方案的最大值就是 $f_{p,1}$。

最终我们从两个情况的最大值中取一个最大值就是答案。以上就是本题的全部思路,树形 $dp$ 的时间复杂度是 $O(n)$ 的

注意,如果从每个骑士向讨厌的人连边,则整个图会是一个内向树森林,会有若干个入度为 $0$ 的段,而我们做树形 $dp$ 时是需要选择一个根节点往下递推的,因此我们建边的时候需要反向建边,建一棵外向树。


C++ 代码

#include <iostream>
#include <cstring>

using namespace std;

typedef long long LL;

const int N = 1000010, INF = 0x3f3f3f3f;

int n;
//rm[i] 表示 i 边是否被删掉
int h[N], e[N], rm[N], w[N], ne[N], idx; //邻接表
bool st[N], ins[N]; //st 记录每个点是否被搜过,ins 记录每个点是否在栈中
//设 f[i][0] 表示以 i 为根的子树中选若干个点,且不选 i 的所有方案的最大值
//设 f[i][1] 表示以 i 为根的子树中选若干个点,且选 i 的所有方案的最大值
LL f1[N][2], f2[N][2];
LL res = 0; //记录答案

void add(int a, int b) //添加边
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

void dfs_f(int u, int ap, LL f[][2]) //树形 dp 求以 u 为根的子树中 u 不选 ap 的所有方案的最大值
{
    //不选 u
    for(int i = h[u]; i != -1; i = ne[i])
    {
        if(rm[i]) continue; //如果当前边已经被删,直接跳过
        int j = e[i];
        dfs_f(j, ap, f);
        f[u][0] += max(f[j][0], f[j][1]);
    }

    //选 u
    f[u][1] = -INF;
    if(u != ap) //如果 u != ap,说明 u 可以选
    {
        f[u][1] = w[u];
        for(int i = h[u]; i != -1; i = ne[i])
        {
            if(rm[i]) continue;
            int j = e[i];
            f[u][1] += f[j][0];
        }
    }
}

void dfs_c(int u, int from) //找出 u 所在的基环树的环
{
    st[u] = ins[u] = true;
    for(int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if(!st[j]) dfs_c(j, i);
        else if(ins[j]) //找到环
        {
            rm[i] = 1; //将 u -> j 的边删掉
            dfs_f(j, -1, f1); //不选 j 的情况
            dfs_f(j, u, f2); //选 j 的情况
            res += max(f1[j][0], f2[j][1]); //累加上两种情况的最大值
        }
    }
    ins[u] = false;
}

int main()
{
    scanf("%d", &n);

    memset(h, -1, sizeof h); //初始化邻接表

    for(int i = 1; i <= n; i++)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(b, i); //有向边
        w[i] = a;
    }

    //求出所有基环树的环
    for(int i = 1; i <= n; i++)
        if(!st[i])
            dfs_c(i, -1);

    printf("%lld\n", res);

    return 0;
}


活动打卡代码 AcWing 1080. 骑士

#include <iostream>
#include <cstring>

using namespace std;

typedef long long LL;

const int N = 1000010, INF = 0x3f3f3f3f;

int n;
//rm[i] 表示 i 边是否被删掉
int h[N], e[N], rm[N], w[N], ne[N], idx; //邻接表
bool st[N], ins[N]; //st 记录每个点是否被搜过,ins 记录每个点是否在栈中
//设 f[i][0] 表示以 i 为根的子树中选若干个点,且不选 i 的所有方案的最大值
//设 f[i][1] 表示以 i 为根的子树中选若干个点,且选 i 的所有方案的最大值
LL f1[N][2], f2[N][2];
LL res = 0; //记录答案

void add(int a, int b) //添加边
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

void dfs_f(int u, int ap, LL f[][2]) //树形 dp 求以 u 为根的子树中 u 不选 ap 的所有方案的最大值
{
    //不选 u
    for(int i = h[u]; i != -1; i = ne[i])
    {
        if(rm[i]) continue; //如果当前边已经被删,直接跳过
        int j = e[i];
        dfs_f(j, ap, f);
        f[u][0] += max(f[j][0], f[j][1]);
    }

    //选 u
    f[u][1] = -INF;
    if(u != ap) //如果 u != ap,说明 u 可以选
    {
        f[u][1] = w[u];
        for(int i = h[u]; i != -1; i = ne[i])
        {
            if(rm[i]) continue;
            int j = e[i];
            f[u][1] += f[j][0];
        }
    }
}

void dfs_c(int u, int from) //找出 u 所在的基环树的环
{
    st[u] = ins[u] = true;
    for(int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if(!st[j]) dfs_c(j, i);
        else if(ins[j]) //找到环
        {
            rm[i] = 1; //将 u -> j 的边删掉
            dfs_f(j, -1, f1); //不选 j 的情况
            dfs_f(j, u, f2); //选 j 的情况
            res += max(f1[j][0], f2[j][1]); //累加上两种情况的最大值
        }
    }
    ins[u] = false;
}

int main()
{
    scanf("%d", &n);

    memset(h, -1, sizeof h); //初始化邻接表

    for(int i = 1; i <= n; i++)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(b, i); //有向边
        w[i] = a;
    }

    //求出所有基环树的环
    for(int i = 1; i <= n; i++)
        if(!st[i])
            dfs_c(i, -1);

    printf("%lld\n", res);

    return 0;
}



岛屿问题

解题思路:

本题每一个点都会向外连一条出边,因此一定是一个基环森林。本题要求每个基环树中任意两点之间的距离最大值的总和。

由于是一个基环森林,里面每一棵基环树都是相互独立的,因此我们可以对于每一棵基环树,单独算一下,任意两个点之间距离的最大值,累加起来就是答案。

接下来的问题就是对于一棵基环树,如何快速求出任意两个点之间距离的最大值。我们可以将所有点对分成两类,一类是两个点属于同一棵子树,则此时这两个点的路径只会用到子树内的边,不会用到环上的边,这样就是单纯在一棵树内求任意两个点之间距离的最大值也就是求树的直径,可以用树形 $dp$ 来求,枚举子树上所有点作为最高点,求出向下走的最长路和次长路,就是经过当前点的直径,枚举所有点取一个最大值就是整棵子树的直径。

另一类就是两个点不属于同一棵子树,此时这两个点之间的路径必然会经过环,我们可以将路径分成三部分,一部分是环上的路径,另外两部分是环上任意两个点往下走的路径,由于要求最大距离,因此这三部分都要尽可能的大,而环上每个点往下走的最长距离一定是固定的,因此我们可以预处理一下环上每个点往下走的最长距离 $d_i$,然后枚举环上任意两个点 $a, b$,此时这条路径应该是 $d_a+ d_b + S_{a,b}$,其中 $S_{a,b}$ 表示 $a,b$ 之间的最长距离。这里肯定不能直接枚举环上的任意两点,太慢了,需要考虑优化。

可以发现 $S_{a, b}$ 和 $S_{b,a}$ 是相同的,因此我们可以枚举一种方向,就是设 $a$ 在 $b$ 的顺时针方向上,这样我们只需要枚举 $a$,就能枚举到环上所有的情况,此时对于任意的 $a$,我们需要在环上找到一个 $b$,使得 $d_a+d_b+S_{a,b}$ 最大,由于 $S_{a,b}$ 其实是一个区间和,因此我们可以预处理一下前缀和,设 $S_x$ 为顺时针方向的前缀和,则此时路径长度变成 $d_a+d_b+S_a-S_b$,此时 $a$ 是固定的,因此 $d_a+S_a$ 是固定的,我们只需要求 $d_b-S_b$ 的最大值,我们可以拆环成链,再将链复制一遍接在后面,若 $n$ 为环的长度,则我们每次枚举链上任意一个长度为 $n$ 的区间,都是环上的任意一个情况,我们就是要在任意一个情况中取 $d_b-S_b$ 的最大值,这就是一个滑动窗口求最值的问题。可以用单调队列来求,这样这一步也是 $O(n)$ 的时间了。

以上就是整个的思路,对于每棵基环树单独求最长距离,再累加在一起就是答案。

这里还有一个细节,对于基环树,如何找出环,这里可以用一个 $dfs$ 来找环,用一个栈记录一下我们递归的路径,当搜到路径中的某个点时,就找到环了,再把这个环取出来即可。


C++ 代码

#include <iostream>
#include <cstring>

using namespace std;

typedef long long LL;

const int N = 1000010, M = N * 2;

int n;
int h[N], e[M], w[M], ne[M], idx; //邻接表
int fu[N], fw[N]; //记录每个点的父节点和它与父节点之间边的权值
bool st[N], ins[N]; //记录每个点是否被搜过,每个点是否在栈中
int cir[N], ed[N], cnt; //cir 连续的存储所有环,ed 表示每一段环的终点
LL s[N]; //s[i] 表示 i 到所在环第一个点的前缀和
LL d[N * 2], sum[N * 2]; //拆环成链后的新序列、拆环成链后的前缀和数组
int q[N * 2]; //单调队列
LL ans = 0; //记录每棵基环树的直径

void add(int a, int b, int c) //添加边
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

void dfs_c(int u, int from) //找出所有基环树的环
{
    st[u] = ins[u] = true; //标记
    for(int i = h[u]; i != -1; i = ne[i])
    {
        if(i == (from ^ 1)) continue;
        int j = e[i];
        fu[j] = u, fw[j] = w[i];
        if(!st[j]) dfs_c(j, i);
        else if(ins[j]) //找到环
        {
            cnt++;
            ed[cnt] = ed[cnt - 1];
            LL sum = w[i];
            for(int k = u; k != j; k = fu[k])
            {
                s[k] = sum;
                sum += fw[k];
                cir[++ed[cnt]] = k;
            }
            s[j] = sum, cir[++ed[cnt]] = j;
        }
    }
    ins[u] = false; //弹栈
}

LL dfs_d(int u) //统计从 u 往下走的最大距离
{
    st[u] = true;
    LL d1 = 0, d2 = 0;
    for(int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if(st[j]) continue;
        LL dist = dfs_d(j) + w[i];
        if(dist >= d1) d2 = d1, d1 = dist;
        else if(dist > d2) d2 = dist;
    }
    ans = max(ans, d1 + d2); //情况 1
    return d1;
}

int main()
{
    scanf("%d", &n);

    memset(h, -1, sizeof h); //初始化邻接表

    for(int i = 1; i <= n; i++)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(i, a, b), add(a, i, b); //无向边
    }

    //找出所有基环树的环
    for(int i = 1; i <= n; i++)
        if(!st[i])
            dfs_c(i, -1);

    memset(st, 0, sizeof st); //清空标记
    for(int i = 1; i <= ed[cnt]; i++) st[cir[i]] = true; //标记环上的点

    LL res = 0; //记录答案
    for(int i = 1; i <= cnt; i++)
    {
        ans = 0;
        int sz = 0; //记录环的大小
        for(int j = ed[i - 1] + 1; j <= ed[i]; j++) //找出环中所有点
        {
            int k = cir[j];
            d[sz] = dfs_d(k);
            sum[sz] = s[k];
            sz++;
        }
        //拆环成链
        for(int j = 0; j < sz; j++)
            d[sz + j] = d[j], sum[sz + j] = sum[j] + sum[sz - 1];

        //单调队列
        int hh = 0, tt = -1;
        for(int j = 0; j < sz * 2; j++)
        {
            if(hh <= tt && j - q[hh] + 1 > sz) hh++;
            if(hh <= tt) ans = max(ans, d[j] + sum[j] + d[q[hh]] - sum[q[hh]]); //情况2
            while(hh <= tt && d[q[tt]] - sum[q[tt]] <= d[j] - sum[j]) tt--;
            q[++tt] = j;
        }
        res += ans; //累加答案
    }
    printf("%lld\n", res);

    return 0;
}


活动打卡代码 AcWing 358. 岛屿

#include <iostream>
#include <cstring>

using namespace std;

typedef long long LL;

const int N = 1000010, M = N * 2;

int n;
int h[N], e[M], w[M], ne[M], idx; //邻接表
int fu[N], fw[N]; //记录每个点的父节点和它与父节点之间边的权值
bool st[N], ins[N]; //记录每个点是否被搜过,每个点是否在栈中
int cir[N], ed[N], cnt; //cir 连续的存储所有环,ed 表示每一段环的终点
LL s[N]; //s[i] 表示 i 到所在环第一个点的前缀和
LL d[N * 2], sum[N * 2]; //拆环成链后的新序列、拆环成链后的前缀和数组
int q[N * 2]; //单调队列
LL ans = 0; //记录每棵基环树的直径

void add(int a, int b, int c) //添加边
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

void dfs_c(int u, int from) //找出所有基环树的环
{
    st[u] = ins[u] = true; //标记
    for(int i = h[u]; i != -1; i = ne[i])
    {
        if(i == (from ^ 1)) continue;
        int j = e[i];
        fu[j] = u, fw[j] = w[i];
        if(!st[j]) dfs_c(j, i);
        else if(ins[j]) //找到环
        {
            cnt++;
            ed[cnt] = ed[cnt - 1];
            LL sum = w[i];
            for(int k = u; k != j; k = fu[k])
            {
                s[k] = sum;
                sum += fw[k];
                cir[++ed[cnt]] = k;
            }
            s[j] = sum, cir[++ed[cnt]] = j;
        }
    }
    ins[u] = false; //弹栈
}

LL dfs_d(int u) //统计从 u 往下走的最大距离
{
    st[u] = true;
    LL d1 = 0, d2 = 0;
    for(int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if(st[j]) continue;
        LL dist = dfs_d(j) + w[i];
        if(dist >= d1) d2 = d1, d1 = dist;
        else if(dist > d2) d2 = dist;
    }
    ans = max(ans, d1 + d2); //情况 1
    return d1;
}

int main()
{
    scanf("%d", &n);

    memset(h, -1, sizeof h); //初始化邻接表

    for(int i = 1; i <= n; i++)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(i, a, b), add(a, i, b); //无向边
    }

    //找出所有基环树的环
    for(int i = 1; i <= n; i++)
        if(!st[i])
            dfs_c(i, -1);

    memset(st, 0, sizeof st); //清空标记
    for(int i = 1; i <= ed[cnt]; i++) st[cir[i]] = true; //标记环上的点

    LL res = 0; //记录答案
    for(int i = 1; i <= cnt; i++)
    {
        ans = 0;
        int sz = 0; //记录环的大小
        for(int j = ed[i - 1] + 1; j <= ed[i]; j++) //找出环中所有点
        {
            int k = cir[j];
            d[sz] = dfs_d(k);
            sum[sz] = s[k];
            sz++;
        }
        //拆环成链
        for(int j = 0; j < sz; j++)
            d[sz + j] = d[j], sum[sz + j] = sum[j] + sum[sz - 1];

        //单调队列
        int hh = 0, tt = -1;
        for(int j = 0; j < sz * 2; j++)
        {
            if(hh <= tt && j - q[hh] + 1 > sz) hh++;
            if(hh <= tt) ans = max(ans, d[j] + sum[j] + d[q[hh]] - sum[q[hh]]); //情况2
            while(hh <= tt && d[q[tt]] - sum[q[tt]] <= d[j] - sum[j]) tt--;
            q[++tt] = j;
        }
        res += ans; //累加答案
    }
    printf("%lld\n", res);

    return 0;
}



Cyclic Rotation

C++ 代码

/*
对于 a 序列每次的操作其实就是将前面的 x 删掉,将后面的某个 x 复制一份。

我们可以倒着考虑,如果 b 能通过逆操作变成 a,则 a 也就能变成 b。

考虑逆操作,逆操作其实就是能将某一个 x 前面连续的 x 移动到前面任意一个位置上

我们用 cnt[i] 表示有 cnt[i] 个 i 可以放在前面任意一个位置

我们从后往前枚举每个数 b[i],如果 b[i] 前面有 s 个和 b[i] 相同的数,则我们令 cnt[b[i]] += s - 1,
表示有 s - 1 个灵活的 b[i] 可以操作。然后和 a 序列进行配对,假设 a 序列从后往前配对到 j,如果
a[j] == b[i],则直接配对成功,继续配对下一个,如果 a[j] != b[i],则此时我们需要用到备选数,
如果 cnt[a[j]] > 0,则我们可以取出一个 a[j] 放到 b[i] 的后面,这样他就能和 a[j] 进行配对,
然后继续配对下一个数,如果 cnt[a[j]] == 0,则目前无法和 a[j] 进行配对,说明无解。
*/

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>

using namespace std;

void work()
{
    int n;
    scanf("%d", &n);
    vector<int> a(n + 1), b(n + 1);
    for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
    for(int i = 1; i <= n; i++) scanf("%d", &b[i]);

    vector<int> cnt(n + 1);
    for(int i = n, j = n; i >= 1; i--)
    {
        while(j - 1 >= 1 && b[j - 1] == b[j]) cnt[b[j--]]++;

        if(j < 1 || a[i] != b[j])
        {
            if(cnt[a[i]]) cnt[a[i]]--;
            else
            {
                puts("NO");
                return;
            }
        }
        else j--;
    }
    puts("YES");
    return;
}

int main()
{
    int T;
    scanf("%d", &T);
    while(T--) work();
    return 0;
}