A. 迷宫

Description:

有一个 $n$n 个点 $n-1$n−1 条边的无向连通图迷宫，其中有些点上面有人

现在所有人的目标都是逃离这个迷宫，而迷宫的出口是 $1$1 号点，每一时刻，会依次发生以下的事情：

1. 在点 $x$x 上的人选择一个点 $f\left(x\right)$f(x) 作为目标，要求 $f\left(x\right)$f(x) 必须是 $x$x ，或者与 $x$x 有边相连的点，且对于 $x\ne y$x̸​=y ，有 $f\left(x\right)\ne f\left(y\right)$f(x)̸​=f(y)
2. 在点 $x$x 上的人移动到 $f\left(x\right)$f(x)
3. 在点 $1$1 号点上的人成功逃脱，从这个游戏里消失

现在你需要求的是：让所有人都成功逃脱至少需要多少时间

Input:

第一行一个正整数 $n$n $(1\le n\le 10^5)$(1≤n≤105)

第二行 $n$n 个整数 $a_1...a_n$a1​...an​ ， $a_i=1$ai​=1 表示一开始第 $i$i 个点上有人， $a_i=0$ai​=0 则表示没有，保证 $a_1=0$a1​=0

接下来 $n-1$n−1 行，每行两个正整数 $(u,v)$(u,v) 描述图中的一条无向边

Output:

输出让所有人成功逃脱至少需要多少时间

Sample Input:

4
0 0 1 1
1 2
2 3
2 4

Sample Output:

3

题目链接

逃离时间耽误的主要原因是同一节点同一时刻只允许一个人通过，所以若多人同时需要通过同一节点则只能排队通过，枚举每个人作为排队队首（其后面的人肯定依次跟随），取最大值即可

AC代码:

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

const int maxn = (int)(1e5 + 5);

struct Edge {int V, Next;};

int Tot;
int Head[maxn];
Edge edges[maxn << 1];

void AddEdge(int U, int V) {
    edges[Tot] = (Edge){V, Head[U]};
    Head[U] = Tot++;
    edges[Tot] = (Edge){U, Head[V]};
    Head[V] = Tot++;
}

int N;
int A[maxn];
int Dep[maxn];
int Cnt[maxn];
int Suffix[maxn];
int MaxDep;
int Ans;

void Dfs(int Cur, int Pre, int Depth) {
    MaxDep = max(MaxDep, Depth);
    Dep[Cur] = Depth;
    if (A[Cur] == 1) Cnt[Depth]++;
    for (int i = Head[Cur]; ~i; i = edges[i].Next) {
        if (edges[i].V == Pre) continue;
        Dfs(edges[i].V, Cur, Depth + 1);
    }
}

int main(int argc, char *argv[]) {
    scanf("%d", &N);
    Tot = 0;
    for (int i = 1; i <= N; ++i) Head[i] = -1;
    for (int i = 1; i <= N; ++i) scanf("%d", &A[i]);
    for (int i = 1, U, V; i < N; ++i) {
        scanf("%d%d", &U, &V);
        AddEdge(U, V);
    }
    Dfs(1, 0, 0);
    for (int i = MaxDep; i >= 0; --i) Suffix[i] = Suffix[i + 1] + Cnt[i];
    for (int i = 1; i <= N; ++i) Ans = max(Ans, Dep[i] + Suffix[Dep[i]] - 1);
    printf("%d\n", Ans);
    return 0;
}

E. 线性探查法

Description:

在大学里选修过数据结构的同学大部分都知道 hash 算法的线性探查法：

假设有一个元素互不相同的正整数数组 $a\left[\mathrm{1...}n\right]$a[1...n] ，我们用以下方法得到数组 $b[\mathrm{0...}n-1]$b[0...n−1] ：

初始时 $b\left[i\right]$b[i] 都为 $-1$−1 ，我们对 $i=\mathrm{1...}n$i=1...n 依次插入 $a\left[i\right]$a[i] ，假设现在要插入的数是 $x$x ，首先我们找到 $x\%n$x%n 这个位置，如果 $b\left[x\%n\right]=-1$b[x%n]=−1 ，则令 $b\left[x\%n\right]=x$b[x%n]=x ，之后结束这次插入；否则看 $b\left[\right(x+1\left)\%n\right]$b[(x+1)%n] 是否等于 $-1$−1 ，如果等于则令 $b\left[\right(x+1\left)\%n\right]=x$b[(x+1)%n]=x ，如果不等于，则继续看 $(x+2)\%n$(x+2)%n …，直到找到一个位置。

完成所有插入后，我们会得到一个数组 $b$b ，现在给定这个数组 $b$b ，你需要求一个字典序最小的 $a\left[\mathrm{1...}n\right]$a[1...n]

Input:

第一行一个正整数 $n(1\le n\le 10^3)$n(1≤n≤103)

第二行 $n$n 个互不相同的正整数，表示 $b[\mathrm{0...}n-1]$b[0...n−1] ， $(1\le b[i]\le 2\times 10^9)$(1≤b[i]≤2×109)

输入数据保证一定有解

Output:

输出 $n$n 个正整数，表示字典序最小的 $a\left[\mathrm{1...}n\right]$a[1...n]

字典序的比较是先比较 $a\left[1\right]$a[1] ，再比较 $a\left[2\right]$a[2] …以此类推

Sample Input:

5
20 16 12 8 4

Sample Output:

4 8 12 16 20

题目链接

哈希线性探查法的逆操作就是拓扑排序（感觉很巧妙）

若有数字需要探查向后放置则其最终放置位置之前所有探查过的位置上的元素都应在此元素放置之前放置

题目要求字典序最小就用一个小顶堆维护即可

AC代码:

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

const int maxn = (int)(1e3 + 5);

struct Edge {int V, Next;};

int Tot;
int Head[maxn];
Edge edges[maxn * maxn];
int InDegree[maxn];

void AddEdge(int U, int V) {
	edges[Tot] = (Edge){V, Head[U]};
	Head[U] = Tot++;
	++InDegree[V];
}

int N;
long long A[maxn];
long long B[maxn];

struct Cmp {
	bool operator () (int Key1, int Key2) {
		return B[Key1] > B[Key2];
	}
};

void TopoSort() {
	priority_queue<int, vector<int>, Cmp > Que;
	for (int i = 0; i < N; ++i)
		if (InDegree[i] == 0) Que.push(i);
	for (int i = 0; i < N; ++i) {
		int Cur = Que.top(); Que.pop();
		A[i] = B[Cur];
		for (int j = Head[Cur]; ~j; j = edges[j].Next) {
			InDegree[edges[j].V]--;
			if (InDegree[edges[j].V] == 0) Que.push(edges[j].V);
		}
	}
}

int main(int argc, char *argv[]) {
	scanf("%d", &N);
	for (int i = 0; i < N; ++i) Head[i] = -1;
	for (int i = 0; i < N; ++i) scanf("%d", &B[i]);
	for (int i = 0; i < N; ++i) {
		int Pos = B[i] % N;
		while (Pos % N != i) {
			AddEdge(Pos % N, i);
			++Pos;
		}
	}
	TopoSort();
	for (int i = 0; i < N; ++i) printf("%d ", A[i]);
	printf("\n");
	return 0;
}

G. 抢红包机器人

Description:

众所周知，camp群里有很多抢红包的机器人，wls对这种号感到很愤怒，他决定把这些机器人全部找出来后踢掉。

wls 研究后发现，由于人的手速是拼不过脚本的，所以如果某个号在某个红包里抢得比某个机器人快，那么这个号肯定也是机器人。

现在 wls 想知道，在群里一定有机器人的情况下，camp 群里至少有几个机器人。

注：机器人并不是每次都会抢红包，而且由于网速问题机器人抢红包的速度也不是固定的，所以有可能有时机器人 a 比 b 快，有时 b 比 a 快。

Input:

第一行两个正整数 $n,m$n,m ,分别表示群员数量和 wls 发的红包数量

接下来 $m$m 行，描述这 $m$m 个红包，每行一开始一个正整数 $k$k ，表示抢了这个红包的人的数量，之后 $k$k 个互不相同的 $[1,n]$[1,n] 内的正整数，表示按照先后顺序给出了抢这个红包的群员的编号。

$1\le n,m\le 100$1≤n,m≤100 ， $1\le k\le n$1≤k≤n

Output:

输出一个整数，表示群里至少有几个机器人

Sample Input:

4 2
3 1 2 3
2 3 1

Sample Output:

1

题目链接

枚举每个红包第一个抢到的人为机器人则在其余各红包内在其之前抢到红包的均为机器人

特判若有人没有抢红包则其为机器人（有且仅有一个）

AC代码:

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

const int INF = 0x3f3f3f3f;
const int maxn = (int)(1e2 + 5);

int N, M;
vector<int> Pack[maxn];
set<int> Flag;
int Ans;

int Check(int Key) {
    set<int> Cnt; Cnt.clear();
    for (int i = 1; i <= M; ++i) {
        if (find(Pack[i].begin(), Pack[i].end(), Key) == Pack[i].end()) continue;
        for (auto it : Pack[i]) {
            if (it == Key) break;
            Cnt.insert(it);
        }
    }
    return (int)Cnt.size() + 1;
}

int main(int argc, char *argv[]) {
    scanf("%d%d", &N, &M);
    for (int i = 1; i <= N; ++i) Flag.insert(i);
    for (int i = 1; i <= M; ++i) Pack[i].clear();
    for (int i = 1, K; i <= M; ++i) {
        scanf("%d", &K);
        for (int j = 1, X; j <= K; ++j) {
            scanf("%d", &X);
            Pack[i].push_back(X);
            if (Flag.find(X) != Flag.end()) Flag.erase(X);
        }
    }
    Ans = INF;
    for (int i = 1; i <= M; ++i) Ans = min(Ans, Check(Pack[i][0]));
    Ans = Flag.empty() ? Ans : 1;
    printf("%d\n", Ans);
    return 0;
}