1648

题目链接 点击打开链接 题目解法 先考虑朴素的 \(dp\) 不难发现有两个断点 \(x,y\) 是重要的，即 \([1,x]\) 在第 \(1\) 行，\([x,y]\) 在第 \(2\) 行，\([y,n]\) 在第 \(3\) 行 不妨枚举断点 \(y\)，然后统计最优的 \(x\) 令 \( ......

2023-09-21 题目 P1648 看守 难度&重要性(1~10):8.5 题目来源 luogu 题目算法 状压 dp，数学 解题思路 这道题我们首先要考虑如何去优化曼哈顿距离。（不然它怎么不玩欧式距离） 首先这是一个普通的曼哈顿距离：\(\sum\limits_{i=1}^d|A_i-B_i| ......

就是 $m$ 组询问**补图的最小生成树**上的树链最大值。有两种基本思路求这棵树。 第一种，Kruskal，基于找到最小的边使两端点不连通。考虑补图中 $(x,y)$ 的边权，它是原图最小生成树上的树链最大值。从小到大枚举补图的边，相当于从小到大枚举原图最小生成树的边 $(u,v,w)$，然后： ......

[原题链接](https://www.luogu.com.cn/problem/P1648 "原题链接") #### 题目大意 $有n个d维空间的点，求其中曼哈顿距离最大的两点之间的曼哈顿距离$\ #### 数据范围 $2\le n\le10^6,1\le d\le 4$\ $这题的贪心思路需要用到 ......

[洛谷传送门](https://www.luogu.com.cn/problem/CF1648E "洛谷传送门") [CF 传送门](https://codeforces.com/problemset/problem/1648/E "CF 传送门") 被一道题创了三天 我们 ......

为啥会有人觉得这是板子题啊/tuu 先对图边双连通分量缩个点，然后考虑对两条边分情况讨论： - 两个桥边，显然答案就是经过这两个桥的路径数量之和，排序取前两大的即可。 - 一个桥边加一个非桥边，答案是经过那个桥边的路径数量，显然桥边数量 $\ge 2$ 肯定不用考虑这种情况，桥边数量 $=1$ 另外 ......

一、并查集 1.1 并查集简介 并查集是一种简单的集合表示，是一种树形数据结构，可处理不相交集合的合并及查询问题。并查集可求联动分支数。 并查集存储： 现有9个元素0~9，建立一个数组（初始化元素为-1），用数组下标表示元素，数组中的数据表示根节点的下标。数组中数据为负数时表示它是根节点。 并查集支 ......