ccpc2021专题

CCPC2021网络赛重赛 umping Monkey(并查集重构 + dfs)

题目链接(hdu 7136) 本题可以根据权值最大的点作为突破口,权值最大的点一定是最优解的最后一步,那么我们可以依次倒推,每次删去最大的点以及该点连接的边最后推到每一个点。 实现过程:我们可以将所有点按照权值从小到大排出,每次枚举出的新点因为权值比前面的大,所以可以将他作为原先连通块的新祖宗,这样在搜寻深度倒推的时候就能够实现优先删除一个连通块中权值较大的点,再删除权值较小的点,每次倒推与该

B - Magical Subsequence (CCPC2021哈尔滨)

思路: (1)问题:对于已知数组,每组依次选两个,尽量选更多组,选的每组和相等;(假定和为x) (2)于是问题拆分为两步, x是多少x确定时,怎样选更多组 (3)对于问题1,注意到A:(1,100),所以x:(2,200)枚举即可; 对于问题2,x确定条件下,显然能选则选最多,此时有两条思路, 前面拿到值从后面找(复杂度O(n^2)且不能保证尽可能长)后面拿到值往前面找,(开st[]数