E3-G
E3-G Swamp
题目描述
Oh no! Q 被派到了一片沼泽做生态调查，他需要前往沼泽的 $n 个地点（编号为个地点（编号为个地点（编号为 1,2,…,n$ ），Q一开始在 1 号点。这 n 个地点中有 m 条边使它们联通。连接$ u,v $的边会经过深度为 hu,vh_{u,v}hu,v 的泥潭。有洁癖的 Q 想让他的鞋子尽可能干净，请你帮他算出从 1 号点开始走完剩下的 $(n−1) $个地点，Q 需要经过的最深泥潭的最小深度。
输入
第一个数为数据组数 t(5≤t≤15).t (5≤t≤15).t(5≤t≤15).
对于每组数据，每行2个整数n,m(1≤n≤2×105,1≤m≤4×105).n,m (1≤n≤2×10^5,1≤m≤4×10^5).n,m(1≤n≤2×105,1≤m≤4×105).
接下来m行，每行三个整数u,v,hu,v(1≤u,v≤n),hu,vu,v,h_{u,v} (1≤u,v≤n), h_{u,v}u,v,hu,v(1≤u,v≤n),hu,v 在 int 范围内，代表地点 u 到地点 v 有一条通路，且需要经过深度为$ h_{u,v}$ 的泥潭 ...
并查集
并查集
定义
并查集是一种树形数据结构，用于处理一些不相交集合的合并，查询问题。
主要构成
一个数组pre[]pre[ ]pre[]，记录了每个点的前驱节点是谁；
两个函数：find(x)find(x)find(x)，用于查找指定节点属于哪个分支（集合）；join(x,y)join(x,y)join(x,y)，合并两个节点；
作用
求连通分支数（一个图中互不连通的连通子图数）；
意义
当我们判断两点是否连通时，可以往根部进行查找，只要两点可由相同的一点的分支下来那么两点就是连通的。
用集合中某个元素来代表这个集合，则该元素称为此集合的代表元。
实现
pre[]
我们用一个数组来记录每节点的前驱，比如pre[5]=6pre[5]=6pre[5]=6代表5号节点的前驱节点是6号节点。如果一个节点的前驱节点是它自己，则说明此节点为根节点。
find(x)
查找xxx所在分支的根节点，从xxx开始通过pre[x]pre[x]pre[x]获取它的前驱节点，重复获取直到抵达根节点。
12345678int find(int x){ while(pre[x]!=x) { ...
C4-E
C4-E 图查询最小距离
题目描述
给出一个 $n $个点 mmm 条边的有向图，共有 qqq 次询问，每次询问两个点$ u$ 到 $v $的最小距离，若从点 uuu 无法到达点$ v$，则输出 −1。
注意：图中可能有重边，且我们认为任意一点到其自身的距离为 0。
输入
第一行两个正整数$ n,m (1≤n≤300,1≤m≤\frac {n(n−1)}2)$，分别表示图中点的数量和边的数量。
接下来$ m$ 行，每行三个正整数 u,v,w(1≤u,v≤n,1≤w≤109)u,v,w (1≤u,v≤n,1≤w≤10^9)u,v,w(1≤u,v≤n,1≤w≤109)，表示从点$ u $到点 vvv 有一条距离为$ w $的有向边。
第$ m+2$ 行一个正整数 $q (1≤q≤10^5) $表示询问的次数。
接下来 qqq 行，每行两个正整数$ u,v (1≤u,v≤n)，表示询问从点，表示询问从点，表示询问从点 u $到点 $v $的最小距离。
输出
对于每组询问，输出一个整数表示点$ u$ 与点 $v $之间的最小距离。
输入样例
123456789103 41 2 41 3 23 ...
E2-D
E2-D Who can I see
题目描述
Thiamine 班上现在要体检，全班 n(1≤n≤3×105)n(1≤n≤3×10^5)n(1≤n≤3×105) 位同学排成了一队，第 iii 位同学身高为 ai(1≤ai≤109)a_i(1≤a_i≤10^9)ai(1≤ai≤109) ，正如世界上没有两朵雪花一样，也没有两个同学身高一样。
因为大家还不是很熟悉，每个人都在前后看自己的同学是谁。每个人想知道自己都能看到谁，正如某老师所说，编程是一门体力活，对身体有很大的损伤，同学们的颈椎都受到了损伤，不能抬头，故：
当$ j<i 时，第时，第时，第 i 位同学能看到第位同学能看到第位同学能看到第 j $位同学当且仅当 ak≤ai(j≤k≤i)a_k≤a_i(j≤k≤i)ak≤ai(j≤k≤i)
当$ j>i$ 时，第$ i 位同学能看到第位同学能看到第位同学能看到第 j $位同学当且仅当 ak≤ai(i≤k≤j)a_k≤a_i(i≤k≤j)ak≤ai(i≤k≤j)
输入
第一个数为数据组数 $T(1≤T≤10) $；
接下来 T 组数据，每组数据包含 ...
E3-A
E3-A 小水獭和蓝园
题目描述
小水獭正在浏览沙河校区的蓝园（BlueGraden）（Blue Graden）（BlueGraden）。
小水獭想将蓝园中 $n $朵花发往学院路，这 $n $朵花的重量分别为 a1,a2,…,ana_1,a_2,…,a_na1,a2,…,an，一个快递可以运送任意一朵花，或运送两朵重量之和不超过 mmm 的花。
小水獭想知道，它最少需要发几个快递才能将所有的花发往学院路，你能帮帮它嘛？
输入格式
第一行一个正整数 t（1≤t≤10）t（1≤t≤10）t（1≤t≤10），表示数据组数。
对于每组数据，第一行两个正整数 n,m（1≤n≤105，1≤m≤109）n,m（1≤n≤10^5，1≤m≤10^9）n,m（1≤n≤105，1≤m≤109），含义同题目描述。
第二行 $n $个整数 a1,a2,…,an（1≤ai≤m）a_1,a_2,…,a_n（1≤a_i≤m）a1,a2,…,an（1≤ai≤m），含义同题目描述。
输出格式
对于每组数据，输出一行一个正整数，表示最少需要的快递数量。
输入样例
1234525 51 2 3 4 52 32 ...
E2-C
E2-C 杀戮尖塔
题目描述
BellalabellaBellalabellaBellalabella 喜欢玩一个叫做杀戮尖塔的游戏。游戏一共有 nnn 层，每层有 kkk 个关卡，编号为 1,2,…,k1,2,…,k1,2,…,k。玩家每通过一关，则可以进入下一层 kkk 个关卡中任意一个。当通过 nnn 层时则会抵达 BossBossBoss 房挑战最终 BossBossBoss。
BellalabellaBellalabellaBellalabella 觉得这个这个游戏太简单了，因此她给自己设置了两个 debuffdebuffdebuff：
相邻两层不能挑战编号相同的关卡，即如果进入了第$ i（1≤i<n）$层的第 j（1≤j≤k）j（1≤j≤k）j（1≤j≤k）关，则不可进入第 i+1i+1i+1 层的第 jjj 关。
共有 mmm 层被设置了陷阱，层数分别为 a1,a2,…,ama_1,a_2,…,a_ma1,a2,…,am，被设置陷阱的层不可进入第 kkk 关，即仅可以进入第 1,2,…,k−11,2,…,k−11,2,…,k−1 关。
请问在 de ...
