统计路径数 刚开始想到的其实是按照权值从大到小边统计边删点,但感觉复杂度很假。 那么就可以考虑正向加点(按照权值从小到大),用并查集维护连通块。注意在合并的时候要保证把权值小的点合并到权值大的点,才能保证每个连通块记录的是最大权值。 那么只要待添加点或连通块的权值小于等于当前点就能合并。 对答案的贡献的计算只需要两个连通块权值相同,然后连通块大小相…
A-Download More RAM 题意:初始RAM为 $k$ ,给出 $n$ 个占用 $a_i$ ,使用后得到 $b_i$ 的软件,每次使用时,软件会暂时占E用 $a_i$ 的RAM,使用后释放并获得额外 $b_i$ 的RAM,当你所持有的RAM小于所需的RAM时不能使用软件。问至多最后能拥有多少RAM。 思路:贪心从小到大排序之后扫一遍就行…
2021_ICPC_沈阳站 B、J 题解 (BFS) J- Luggage Lock 链接:https://ac.nowcoder.com/acm/contest/24346/ Eileen has a big luggage and she would pick a lot of things in the luggage every time …
题目链接:D - 8 Puzzle on Graph 题意:有一个包含$9$个节点,$m$条边的图,给出8个棋子初始位置p : $1,2,3,4...$在$p_1,p_2,p_3.....$每次操作可以将与空位相邻的节点交换位置,问至少经过多少次操作可以将棋子放到与编号对应的位置,即 【 $1,2,3,4,5,6,7,8,空 $】 思路:可以考虑将…
[TOC] A.Find Subsequence B.operation 描述 Define a~b = ((a&b) + (a|b))>>1 Given an array of size nn, in one operation, choosing two adjacent elements a, b, using a~b to repl…
树形dp的坑emmmm,会填的QWQ 乘法逆元 用处及定义 乘法逆元一般用于求$\frac{a}{b} \pmod p$的值。 ...