旺崽的博客

AtCoder Beginner Contest 196 E.Filters

发表于 2021-03-26 分类于 ACM Valine：

Problem Statement

Given are integer sequences $A=(a_1,a_2,…,a_N)$, $T=(t_1,t_2,…,t_N)$, and $X=(x_1,x_2,…,x_Q)$.
Let us define $N$ functions $f_1(x),f_2(x),…,f_N(x)$
as follows:

$f_i(x)= \begin{cases} x+a_i\ (t_i=1)\\ max(x,a_i)\ (t_i=2)\\ min(x,a_i)\ (t_i=3) \end{cases}$

Sample Input 1

3
-10 2
10 1
10 3
5
-15 -10 -5 0 5

Sample Output 1

利用几何作图发现上述三个操作总是会形成如下的图形：
在这里插入图片描述
那么我们只需要维护三个变量：$low$ 下界，$high$ 上界和 $add$ 加数即可，AC代码如下:

n = int(input())
low, high, add = -10 ** 18, 10 ** 18, 0
for _ in range(n):
    a, t = map(int, input().split())
    if t == 1:
        low += a
        high += a
        add += a
    elif t == 2:
        low = max(low, a)
        high = max(high, a)
    elif t == 3:
        low = min(low, a)
        high = min(high, a)
q = int(input())
s = input()
list = [int(_) for _ in s.split()]
for x in list:
    print(min(high, max(low, x + add)))

LeetCode 82 删除排序链表中的重复元素 II

发表于 2021-03-25 分类于 ACM Valine：

题目链接

存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除链表中所有存在数字重复情况的节点，只保留原始链表中没有重复出现的数字。

返回同样按升序排列的结果链表。

示例 1：

1 2	输入：head = [1,2,3,3,4,4,5] 输出：[1,2,5]

示例 2：

1 2	输入：head = [1,1,1,2,3] 输出：[2,3]

链表操作~
我的方法是遍历一遍链表结点，对某一结点 $q$，判断 $q.next$ 的值和 $q.next.next$，如果相等就存下那个值 $val$，新建一个指针右移到值不为 $val$ 的结点上，再把这个结点接到 $q.next$ 上，重复上述操作即可，AC代码如下：

class Solution:
    def deleteDuplicates(self, head: ListNode) -> ListNode:
        q = ListNode()
        q.next = head
        ans = q
        while q and q.next and q.next.next:
            while q.next and q.next.next and q.next.val == q.next.next.val:
                val = q.next.val
                p = q.next
                while p and p.val == val:
                    p = p.next
                q.next = p
            q = q.next
        return ans.next

LeetCode 1631 最小体力消耗路径

发表于 2021-03-22 分类于 ACM Valine：

题目链接

你准备参加一场远足活动。给你一个二维 rows x columns 的地图 heights ，其中 heights[row][col] 表示格子 (row, col) 的高度。一开始你在最左上角的格子 (0, 0) ，且你希望去最右下角的格子 (rows-1, columns-1) （注意下标从 0 开始编号）。你每次可以往上，下，左，右四个方向之一移动，你想要找到耗费体力最小的一条路径。

一条路径耗费的体力值是路径上相邻格子之间高度差绝对值的最大值决定的。

请你返回从左上角走到右下角的最小体力消耗值。

示例 1：

在这里插入图片描述

输入：heights = [[1,2,2],[3,8,2],[5,3,5]]
输出：2
解释：路径 [1,3,5,3,5] 连续格子的差值绝对值最大为 2 。
这条路径比路径 [1,2,2,2,5] 更优，因为另一条路径差值最大值为 3 。

示例 2：

在这里插入图片描述

1
2
3

输入：heights = [[1,2,3],[3,8,4],[5,3,5]]
输出：1
解释：路径 [1,2,3,4,5] 的相邻格子差值绝对值最大为 1 ，比路径 [1,3,5,3,5] 更优。

示例 3：

在这里插入图片描述

1
2
3

输入：heights = [[1,2,1,1,1],[1,2,1,2,1],[1,2,1,2,1],[1,2,1,2,1],[1,1,1,2,1]]
输出：0
解释：上图所示路径不需要消耗任何体力。

二分+BFS~
我们可以二分最短距离，每一次从左上角往右下角 BFS 即可，注意 BFS 过程中的标记请尽量用数组完成，map 会非常耗时，AC代码如下：

class Solution {
private:
    int m, n, dir[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};
public:
    bool check(int x, vector<vector<int>> &heights) {
        queue<pair<int, int>> q;
        vector<int> vis(m * n);
        pair<int, int> a, b;
        q.push({0, 0});
        vis[0] = 1;
        while (!q.empty()) {
            a = q.front();
            q.pop();
            if (a.first == m - 1 && a.second == n - 1) {
                return 1;
            }
            for (int i = 0; i < 4; i++) {
                b.first = a.first + dir[i][0];
                b.second = a.second + dir[i][1];
                if (b.first >= 0 && b.first < m && b.second >= 0 && b.second < n && !vis[b.first * n + b.second] &&
                    abs(heights[a.first][a.second] - heights[b.first][b.second]) <= x) {
                    vis[b.first * n + b.second] = 1;
                    q.push(b);
                }
            }
        }
        return 0;
    }

    int minimumEffortPath(vector<vector<int>> &heights) {
        m = heights.size(), n = heights[0].size();

        int l = 0, r = 1000000;
        while (l <= r) {
            int mid = l + r >> 1;
            if (check(mid, heights)) r = mid - 1;
            else l = mid + 1;
        }
        return l;
    }
};

LeetCode 1579 保证图可完全遍历

发表于 2021-03-22 分类于 ACM Valine：

题目链接

Alice 和 Bob 共有一个无向图，其中包含 n 个节点和 3 种类型的边：

类型 1：只能由 Alice 遍历。
类型 2：只能由 Bob 遍历。
类型 3：Alice 和 Bob 都可以遍历。

给你一个数组 edges ，其中 edges[i] = [typei, ui, vi] 表示节点 ui 和 vi 之间存在类型为 typei 的双向边。请你在保证图仍能够被 Alice和 Bob 完全遍历的前提下，找出可以删除的最大边数。如果从任何节点开始，Alice 和 Bob 都可以到达所有其他节点，则认为图是可以完全遍历的。

返回可以删除的最大边数，如果 Alice 和 Bob 无法完全遍历图，则返回 -1 。

示例 1：

在这里插入图片描述

1
2
3

输入：n = 4, edges = [[3,1,2],[3,2,3],[1,1,3],[1,2,4],[1,1,2],[2,3,4]]
输出：2
解释：如果删除 [1,1,2] 和 [1,1,3] 这两条边，Alice 和 Bob 仍然可以完全遍历这个图。再删除任何其他的边都无法保证图可以完全遍历。所以可以删除的最大边数是 2 。

示例 2：

在这里插入图片描述

1
2
3

输入：n = 4, edges = [[3,1,2],[3,2,3],[1,1,4],[2,1,4]]
输出：0
解释：注意，删除任何一条边都会使 Alice 和 Bob 无法完全遍历这个图。

示例 3：

在这里插入图片描述

1
2
3

输入：n = 4, edges = [[3,2,3],[1,1,2],[2,3,4]]
输出：-1
解释：在当前图中，Alice 无法从其他节点到达节点 4 。类似地，Bob 也不能达到节点 1 。因此，图无法完全遍历。

这题就是比较简单的并查集，我们分别对两个人建立一个并查集，先删公共边中的累赘边，再分别删各自独占边中的累赘边即可，AC代码如下:

class Unionset {
public:
    vector<int> father;
    vector<int> sum;
    int cnt = 0;
public:
    void init(int n) {
        father.resize(n);
        for (int i = 0; i < n; i++) father[i] = i;
        sum.resize(n);
        cnt = n;
    }

    int findFather(int x) {
        return x == father[x] ? x : father[x] = findFather(father[x]);
    }

    bool Union(int x, int y) {
        x = findFather(x), y = findFather(y);
        if (x == y) return 0;
        if (sum[x] < sum[y]) swap(x, y);
        father[y] = x;
        sum[x] += sum[y];
        --cnt;
        return 1;
    }
};

class Solution {
public:
    int maxNumEdgesToRemove(int n, vector<vector<int>> &edges) {
        Unionset a = Unionset();
        Unionset b = Unionset();
        int ans = 0;
        a.init(n);
        b.init(n);
        for (auto &i:edges) --i[1], --i[2];
        for (auto &i:edges) {
            if (i[0] == 3) {
                if (!a.Union(i[1], i[2])) ans++;
                else b.Union(i[1], i[2]);
            }
        }
        for (auto &i:edges) {
            if (i[0] == 1) {
                if (!a.Union(i[1], i[2])) ans++;
            }
            if (i[0] == 2) {
                if (!b.Union(i[1], i[2])) ans++;
            }
        }
        if (a.cnt != 1 || b.cnt != 1) return -1;
        return ans;
    }
};

题目描述

牛牛站在一个棱长为的正三棱锥内部的中心。（牛牛是不可移动的）
（所谓正三棱锥，指六条棱都相等的三棱锥。正三棱锥的中心指到 4 个顶点距离都相等的那个点）
在这里插入图片描述

如上图，$AB=AC=BC=AD=BD=CD=a$，牛牛站在P点，$PA=PB=PC=PD$
他拿着一个染色喷雾，可以用来给正三棱锥的内表面染色。
已知喷雾能喷洒的距离为。也就是说，三棱锥内表面距离牛牛不超过的点才有可能被染色。牛牛想知道，正三棱锥内表面能被他染色的最大面积是多少？
ps：牛牛可看成一个无大小的点。重力对于喷雾的影响忽略不计。

输入描述:

两个正整数和
$1 \leq a, r \leq 1000$

输出描述:

染色的最大面积。若你的答案和正确答案误差不超过 $1 \times 10^{-3}$
，则认为你的答案正确。

示例1

输入

1 1

输出

1.73205

这题就是简单几何，实际上就是球体和三棱锥相交的表面积，粗略画一下图发现很简单，就 $3$ 种情况：

喷洒距离 $r$ 小于正四面体内接圆的半径，此时答案为 $0$
喷洒距离 $r$ 小于正四面体外接圆的半径，大于等于内接圆的半径，这种情况有两种可能，一种是整个圆内含于三角形，此时的喷射面积就是四个圆的面积；另一种可能就是圆与三角形相交，下图展示一个面的情况
喷洒距离 $r$ 大于等于正四面体外接圆的半径，此时答案就是正四面体的表面积

在这里插入图片描述
显然难点就是算这个相交部分的面积了，相交部分的面积我们就用三角形的面积减去三个类三角形的面积即可，我们可以对一个角进行分析，如下图：

类三角形的面积=上三角形的面积-(扇形面积-下三角形的面积)
我们设几个参数名：

相交部分面积 $ans$
内接圆半径 $mn$
外接圆半径 $mx$
下三角形面积 $S1$，底 $A$，高为 $H$，斜边长 $L$
上三角形面积 $S2$，底 $A$
扇形面积 $S3$，对应弧长 $l$，圆形角 $\alpha$

下三角形的斜边长为：

$L=\sqrt{r^2-mn^2}$

可以通过反三角函数先算出角 $p$ 的大小：

$p=arccos(\frac{\sqrt3*a}{L*6})$

那么：

$q=\frac{\pi}{3}-p=\frac{\pi}{3}-arccos(\frac{\sqrt3*a}{L*6})$

那么圆形角 $\alpha$ 为：

$\alpha=2*q$

所以弧长既可以计算如下：

$l=\alpha *L=2*q*L$

所以扇形面积：

$S3=\frac{l*L}{2}=q*L^2=(\frac{\pi}{3}-arccos(\frac{\sqrt3*a}{L*6}))*L^2$

下三角的底 $A$ 为：

$A=2*L*sin(q)$

下三角的高 $H$ 为：

$H=L*cos(q)$

所以：

$S1=\frac{A*H}{2}=L^2*sin(q)*cos(q)$

上三角形是很明显是一个等边三角形，面积为：

$S2=\frac{\sqrt 3*A^2}{4}=\sqrt 3*L^2*sin^2(q)$

最后答案就是：

$ans=\frac{\sqrt 3*a^2}{4}-3*(S2-(S3-S1))$

那最后的答案就是 $4*ans$，AC代码如下：

#include <bits/stdc++.h>

typedef long long ll;
using namespace std;
#define PI acos(-1)
double a, r;

int main() {
    cin >> a >> r;
    double mx = sqrt(6) / 4 * a, mn = sqrt(6) / 12 * a, mid = sqrt(2) / 4 * a;
    if (r < mn) printf("0.00000\n");
    else if (r < mid) {
        printf("%.5f\n", 4 * PI * (r * r - mn * mn));
    } else if (r < mx) {
        double q = PI / 3 - acos(sqrt(3) * a / (6 * sqrt(r * r - mn * mn)));
        double s1 = (r * r - mn * mn) * sin(q) * cos(q);
        double s2 = sqrt(3) * (r * r - mn * mn) * sin(q) * sin(q);
        double s3 = q * (r * r - mn * mn);
        printf("%.5f\n", sqrt(3) * a * a - 12 * (s1 + s2 - s3));
    } else printf("%.5f\n", sqrt(3) * a * a);
    return 0;
}

题目描述

你拿到了一棵树，请你给每个顶点染成红色或蓝色。
要求：每个红点周围有且仅有一个红点，每个蓝点周围有且仅有一个蓝点。
“周围”的定义：某点周围的点指通过邻边直接连接的点。
所谓树，即没有自环、重边和回路的无向连通图。

输入描述:

第一行一个正整数 $n$，代表树的顶点个数。$(1 \leq n \leq 100000)$
接下来的 $n-1$ 行，每行两个正整数 $u$ 和 $v$，代表点 $u$ 和点 $v$ 有一条边连接。 $(1 \leq u,v \leq n)$
保证输入的一定是一棵合法的树。

输出描述:

如果可以达成染色的要求，请输出一个长度为 $n$ 的字符串，第 $i$ 个字符代表第 $i$ 个顶点的染色情况，’B’ 代表蓝色，’R’ 代表红色。（若有多种合法染色的方法，输出任意一种即可）
否则直接输出 $-1$。

示例1

输入

输出

RRBB

示例2

输入

输出

-1

题解写得有点复杂，我换种思路，采取自底向上染色的方法，对一个叶子结点来说，显然它只能和其父亲同色，我们就给其一对相同的编号，若遍历一遍树刚好能拆成偶数对，证明可以染色，那再遍历一遍染色即可，编号过程如下图：
在这里插入图片描述
若在编号过程中发现某一结点的父亲已经染色，证明其父亲已和其他结点组成一对，那么这个结点必无法染色，则直接输出 $-1$ 即可，AC代码如下：

#include <bits/stdc++.h>

typedef long long ll;
using namespace std;
const int N = 1e5 + 5;
vector<int> G[N];
int n, x, y, cnt, id[N] = {1}, ans[N];

void dfs1(int son, int father) {//编号
    for (auto kid:G[son]) {
        if (kid != father) dfs1(kid, son);
    }
    if (!id[son]) {
        if (id[father]) {//若父亲结点已被编号直接输出-1
            printf("-1\n");
            exit(0);
        }
        id[father] = id[son] = ++cnt;
    }
}

void dfs2(int son, int father, int color) {//染色
    ans[son] = color;
    for (auto kid:G[son]) {
        if (kid != father) dfs2(kid, son, (id[kid] == id[son] ? color : color ^ 1));
    }
}

int main() {
    cin >> n;
    for (int i = 0; i < n - 1; i++) {
        cin >> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    dfs1(1, 0);
    dfs2(1, 0, 0);
    for (int i = 1; i <= n; i++) putchar(ans[i] ? 'R' : 'B');
    return 0;
}

LeetCode 959 由斜杠划分区域

发表于 2021-03-22 分类于 ACM Valine：

题目链接

在由 1 x 1 方格组成的 N x N 网格 grid 中，每个 1 x 1 方块由 /、\ 或空格构成。这些字符会将方块划分为一些共边的区域。

（请注意，反斜杠字符是转义的，因此 \ 用 \\ 表示）。

返回区域的数目。

示例 1：

输入：
[
  " /",
  "/ "
]
输出：2
解释：2x2 网格如下：

在这里插入图片描述

示例 2：

输入：
[
  " /",
  "  "
]
输出：1
解释：2x2 网格如下：

在这里插入图片描述

示例 3：

输入：
[
  "\\/",
  "/\\"
]
输出：4
解释：（回想一下，因为 \ 字符是转义的，所以 "\\/" 表示 \/，而 "/\\" 表示 /\。）
2x2 网格如下：

在这里插入图片描述

示例 4：

输入：
[
  "/\\",
  "\\/"
]
输出：5
解释：（回想一下，因为 \ 字符是转义的，所以 "/\\" 表示 /\，而 "\\/" 表示 \/。）
2x2 网格如下：

在这里插入图片描述

示例 5：

输入：
[
  "//",
  "/ "
]
输出：3
解释：2x2 网格如下：

在这里插入图片描述

思维+并查集~
我们可以将一格分成四块，那么对每一格的划分就有下面三张情况，合并对应的编号即可：
在这里插入图片描述
对每一个大格，只有两种相邻情况，合并相应的编号即可：

最后返回连通块的数目即可~
离散化处理：初始化连通块数目置为 $4NN$，将二维坐标离散成一维，$(x,y)->4(xN+y)$
AC代码如下：

class Unionset {
public:
    vector<int> father;
    vector<int> sum;
    int cnt = 0;
public:
    void init(int n) {
        father.resize(n);
        for (int i = 0; i < n; i++) father[i] = i;
        sum.resize(n);
        cnt = n;
    }

    int findFather(int x) {
        return x == father[x] ? x : father[x] = findFather(father[x]);
    }

    bool Union(int x, int y) {
        x = findFather(x), y = findFather(y);
        if (x == y) return 0;
        if (sum[x] < sum[y]) swap(x, y);
        father[y] = x;
        sum[x] += sum[y];
        --cnt;
        return 1;
    }
};

class Solution {
public:
    int regionsBySlashes(vector<string> &grid) {
        int N = grid.size();
        Unionset u = Unionset();
        u.init(4 * N * N);
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < grid[i].size(); j++) {
                int id = 4 * (i * N + j);
                if (grid[i][j] == '/') {
                    u.Union(id, id + 3);
                    u.Union(id + 1, id + 2);
                } else if (grid[i][j] == '\\') {
                    u.Union(id, id + 1);
                    u.Union(id + 2, id + 3);
                } else {
                    u.Union(id, id + 1);
                    u.Union(id + 1, id + 2);
                    u.Union(id + 2, id + 3);
                }
                if (i + 1 < N) {
                    u.Union(id + 2, 4 * ((i + 1) * N + j));
                }
                if (j + 1 < N) {
                    u.Union(id + 1, 4 * (i * N + j + 1) + 3);
                }
            }
        }
        return u.cnt;
    }
};

现代社交离不开微信，QQ，那么今天就教你用 Python 生成自己的个性二维码😎
这里用到了 MyQR 库，下面是 github 的地址：
[MyQR](https://github.com/qiulongquan/MyQR)
官方介绍：
制作普通二维码、带有图片的艺术二维码和动态二维码。这个库可以直接在 Pycharm 的 Settings 的 Project interpreter 里点 + 号下载，也可以在 cmd 里用 pip 命令安装。
下载完后导包：

1	from MyQR import myqr

下面就让我们来看看里面最主要的 run 函数，源码如下：

1	def run(words, version=1, level='H', picture=None, colorized=False, contrast=1.0, brightness=1.0, save_name=None, save_dir=os.getcwd()):

words

words 里面放的就是二维码的内容，举个例子：

1	myqr.run(words='i love you')

生成如下二维码：
在这里插入图片描述扫码就会出现：

1	i love you

当然 words 里面也可以放地址，比如：

1	myqr.run(words='https://www.baidu.com')

生成如下图片：
在这里插入图片描述
扫码就能直接进入百度界面~
那么如何添加我们个人的二维码呢？我们只需要将我们的QQ或者微信二维码解析一下草料二维码(将二维码图片上传解码) 得到地址，下面是我解析我的QQ二维码获得的地址，并用该地址生成了二维码(有人可能会问，我用二维码图片再生成二维码图片，我是不是脑子有问题😒，别急，下面教你把二维码跟图片结合)：

1	myqr.run(words='https://qm.qq.com/cgi-bin/qm/qr?k=l-4r-RKlP8E1nGoHSWUzNvUPR6w6p5eK&noverify=0')

在这里插入图片描述

picture

这是比较强大的一个地方，可以将二维码和图片结合，注意如果图片不是和 py 文件在同一目录下会报错，这次我用下图和上述的QQ二维码解码地址结合：

1 2	myqr.run(words='https://qm.qq.com/cgi-bin/qm/qr?k=l-4r-RKlP8E1nGoHSWUzNvUPR6w6p5eK&noverify=0', picture='1.jpg')

在这里插入图片描述
效果如下：

不难发现这是黑白的，明显更丑了，所以我们用到了下面第三个参数😀

colorized

bool 类型，设置为 True 时即可看到彩色的二维码图片了，还是用上面的图片举例：

1
2
3

myqr.run(words='https://qm.qq.com/cgi-bin/qm/qr?k=l-4r-RKlP8E1nGoHSWUzNvUPR6w6p5eK&noverify=0',
         colorized=True,
         picture='1.jpg')

在这里插入图片描述
这效果不就来了，你们找喜欢的图片与二维码结合即可~
下面介绍一下这个函数非常强大的一个功能：动态二维码

动态二维码

picture 不仅能放静图，还能放 GIF 动图，比如我用下面这张图片

1
2
3

myqr.run(words='https://qm.qq.com/cgi-bin/qm/qr?k=l-4r-RKlP8E1nGoHSWUzNvUPR6w6p5eK&noverify=0',
         colorized=True,
         picture='1.gif')

在这里插入图片描述
效果如下：

学到这里你就掌握了生成个性二维码的诀窍了，是不是很简单，不仅微信和QQ可以，你们同样可以给自己的网站(博客，微博，gihub)等生成个性二维码，下面再补充一个小点

save_name

设置生成图片的名字和格式，比如可以把 JPG 格式的可以保存成 PNG 格式的图片，保存的位置和 py文件同一目录，下面挂一段代码：

from MyQR import myqr
myqr.run(
    words='https://u.wechat.com/MHPhZxXSgAvAzy_oDqCUPkg',
    picture='1.jpg',
    colorized=True,
    save_name='zaizai.png'
)

学到这里就结束啦，快去试试生成你自己的个性二维码吧！😁

LeetCode 1489 找到最小生成树里的关键边和伪关键边

发表于 2021-03-22 分类于 ACM Valine：

题目描述

给你一个 $n$ 个点的带权无向连通图，节点编号为 $0$ 到 $n-1$ ，同时还有一个数组 $edges$ ，其中 $edges[i] = [from_i, to_i, weight_i]$ 表示在 $from_i$ 和 $to_i$ 节点之间有一条带权无向边。最小生成树 (MST) 是给定图中边的一个子集，它连接了所有节点且没有环，而且这些边的权值和最小。

请你找到给定图中最小生成树的所有关键边和伪关键边。如果从图中删去某条边，会导致最小生成树的权值和增加，那么我们就说它是一条关键边。伪关键边则是可能会出现在某些最小生成树中但不会出现在所有最小生成树中的边。

请注意，你可以分别以任意顺序返回关键边的下标和伪关键边的下标。

示例 1：

在这里插入图片描述

输入：n = 5, edges = [[0,1,1],[1,2,1],[2,3,2],[0,3,2],[0,4,3],[3,4,3],[1,4,6]]
输出：[[0,1],[2,3,4,5]]
解释：上图描述了给定图。
下图是所有的最小生成树。
注意到第 0 条边和第 1 条边出现在了所有最小生成树中，所以它们是关键边，我们将这两个下标作为输出的第一个列表。
边 2，3，4 和 5 是所有 MST 的剩余边，所以它们是伪关键边。我们将它们作为输出的第二个列表。

在这里插入图片描述

示例 2 ：

在这里插入图片描述

1
2
3

输入：n = 4, edges = [[0,1,1],[1,2,1],[2,3,1],[0,3,1]]
输出：[[],[0,1,2,3]]
解释：可以观察到 4 条边都有相同的权值，任选它们中的 3 条可以形成一棵 MST 。所以 4 条边都是伪关键边。

这题的关键是找边，所以只能用最小生成树的 Kruskal 算法。
我们先给所有边编号，先求一遍最小生成树的权值和 $value$，然后依次遍历所有边 $i$，先算去掉边 $i$ 的最小生成树的权值和 $v$，若此时无法构造最小生成树或者 $v>value$，则这条边一定是关键边；再算伪关键边，我们加上这条边的权值，再算一次最小生成树的权值和 $v$，若 $v=value$，证明该边没有出现在所有的最小生成树中，一定是伪关键边，AC代码如下：

class Unionset {
public:
    vector<int> father;
    vector<int> sum;
    int cnt = 0;
public:
    void init(int n) {
        father.resize(n);
        for (int i = 0; i < n; i++) father[i] = i;
        sum.resize(n);
        cnt = n;
    }

    int findFather(int x) {
        return x == father[x] ? x : father[x] = findFather(father[x]);
    }

    bool Union(int x, int y) {
        x = findFather(x), y = findFather(y);
        if (x == y) return 0;
        if (sum[x] < sum[y]) swap(x, y);
        father[y] = x;
        sum[x] += sum[y];
        --cnt;
        return 1;
    }
};

class Solution {
public:
    vector<vector<int>> findCriticalAndPseudoCriticalEdges(int n, vector<vector<int>> &edges) {
        int m = edges.size();
        for (int i = 0; i < m; i++) edges[i].push_back(i);
        sort(edges.begin(), edges.end(), [](const auto &u, const auto &v) { return u[2] < v[2]; });
        int value = 0;
        Unionset a = Unionset();
        a.init(n);
        for (auto i:edges) if (a.Union(i[0], i[1])) value += i[2];
        vector<vector<int>> ans(2);
        for (int i = 0; i < m; i++) {
            Unionset b = Unionset();
            b.init(n);
            int v = 0;
            for (int j = 0; j < m; j++) {
                if (i != j && b.Union(edges[j][0], edges[j][1])) v += edges[j][2];
            }
            if (b.cnt != 1 || (b.cnt == 1 && v > value)) {
                ans[0].emplace_back(edges[i][3]);
                continue;
            }
            Unionset c = Unionset();
            c.init(n);
            c.Union(edges[i][0], edges[i][1]);
            v = edges[i][2];
            for (int j = 0; j < m; j++) {
                if (i != j && c.Union(edges[j][0], edges[j][1])) v += edges[j][2];
            }
            if (v == value) ans[1].push_back(edges[i][3]);
        }
        return ans;
    }
};

2021牛客寒假算法基础集训营2 F.牛牛与交换排序

发表于 2021-03-22 分类于 ACM Valine：

题目链接

题目描述

牛牛有一个数组，数组元素是 $1$ 到 $n$ 的排列，即数组的值在 $1\sim n$ 范围内，且每个数字仅出现 $1$ 次。
牛牛想要将该数组变为升序排列的，他可以进行如下的操作。

首先他要确定一个长度 $k$，$k$ 的范围在 $1\sim n$ 之间。
接下来他将会进行若干次操作。在每轮操作中他都可以选择一段长度为k的子数组，然后进行区间的翻转操作。

他可以做任意次数的操作，但是要求他每次选择的子数组区间满足 $li \leq l{i+1}$，并且区间长度等于一开始选定的 $k$，也就是说一旦某一次操作选择了数组的某个位置进行区间翻转操作，下一次做区间翻转的位置将会比上一次更靠右。

牛牛发现，并不总是存在一个 $k$ 可以使得数组排序变为有序，请你告诉牛牛是否存在一个 $k$ 能够在满足规则的情况下完成排序。

输入描述:

第一行输入一个正整数 $n(1 \leq n \leq 10^5)$ 表示数组的大小。
接下来输出一行 $n$ 个正整数表示一个排列，即每个数的大小范围在 $1$ 到 $n$ 且每个正整数仅出现一次。

输出描述:

如果存在至少一个 $k$ 能够使牛牛完成排序，请先在一行中输出一个 “yes”，然后另起一行输出一个可以满足排序的k，要求k的范围在 $\left[ 1,n \right]$ 之间，如果有多解，你可以输出任意一个。

反之如果不存在任何一个k可以完成排序，请直接在一行输出一个 “no”

示例1

输入

1 2	5 5 2 1 4 3

输出

1
2

yes
3

示例2

输入

1 2	5 1 2 3 4 5

输出

1
2

yes
1

示例3

输入

1 2	5 5 4 3 2 1

输出

1
2

yes
5

思维+模拟~
因为每次区间的选择都只能往右走，也就是对某一位置 $i$，若它的 $pos[i]$(它在所给数组中的位置)在右边，那么必须只能一次操作将其换回原位，也就是说我们只要找到第一个不在原位置的 $i$，那么 $k$ 一定就是 $pos[i]-i+1$~
找到该位置后我们就要去想用什么数据结构能模拟一次排序数组的过程，显然这个数据要能从头取，也能从尾取，所以很容易想到双端队列，对翻转这个操作我们通常的技巧就是设置一个翻转标记，而不需要真的把队列翻转，例如原本翻转标记 $flag=0$，我们这是从队头弹出，队尾插入，翻转后只需要从队尾弹出，队头插入即可，STL 里面就有 $deque$ 这个数据结构，不熟悉的同学可以去自学一下~
整个模拟过程简单描述如下：

先存 $k$ 个元素
每次拿位置 $i$ 和队头队尾进行匹配，匹配成功执行相应的弹出插入操作和修改对应的翻转标记，不匹配直接输出 $no$ 即可

AC代码如下：

#include <bits/stdc++.h>

typedef long long ll;
using namespace std;
const int N = 1e5 + 5;
int n, k, flag = 0, a[N], pos[N];
deque<int> q;

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        pos[a[i]] = i;
    }
    for (int i = 1; i <= n; i++) {
        if (pos[i] != i) {
            k = pos[i] - i + 1;
            break;
        }
    }
    if (!k) {
        cout << "yes\n" << "1";
        return 0;
    }
    for (int i = 1; i <= k; i++) q.push_back(a[i]);
    for (int i = k + 1; i <= n + k; i++) {
        if (!(flag % 2)) {
            if (i - k == q.front()) q.pop_front();
            else if (i - k == q.back()) flag ^= 1, q.pop_back();
            else {
                cout << "no";
                return 0;
            }
        } else if (flag % 2) {
            if (i - k == q.back()) q.pop_back();
            else if (i - k == q.front()) flag ^= 1, q.pop_front();
            else {
                cout << "no";
                return 0;
            }
        }
        if (i <= n) {
            if (flag % 2) q.push_front(a[i]);
            else q.push_back(a[i]);
        }
    }
    cout << "yes\n" << k;
    return 0;
}