distance
P9678 [ICPC2022 Jinan R] Tree Distance
更好的阅读体验 P9678 [ICPC2022 Jinan R] Tree Distance 支配对，不是非常难。 显然如果 \(a\leq b<c\leq d\) 且 \(dis(a,d)>dis(b,c)\) 则点对 \((a,d)\) 是无用的，猜想点对数不会太多，事实也正是如此。 树上距离是 ......
CF1881F Minimum Maximum Distance 题解
因为白点对 \(f_i\) 没有贡献，所以可以重构出一棵原树的子树，使得所有的叶子都为标记点且标记点数量不变（没有删去标记点）。因为没有标记被删去且结构不变，所以这棵树的答案与原树答案相同。 现在，对于所有节点，到它距离最大的标记点一定在叶子上。那么问题就变为：求出树上任意一点到所有叶子节点的最大距 ......
Wasserstein距离的python代码实现scipy.stats.wasserstein_distance解释
在官方文档scipy.stats.wasserstein_distance — SciPy v1.8.0.dev0+1869.838cfbe Manual (osgeo.cn)页面中 scipy.stats.wasserstein_distance(u_values, v_values, u_wei ......
[Codeforces] CF1591C Minimize Distance
CF1591C Minimize Distance 题目 一条线上有 \(n\) （\(1 \le n \le 2 \cdot 10^5\)）个仓库，第 \(i\) 个仓库的位置是 \(x_i\) （\(1 \le i \le n\)）。 你有 \(n\) 箱货物，要分别运到这 \(n\) 个仓库里 ......
[LeetCode] 1334. Find the City With the Smallest Number of Neighbors at a Threshold Distance
There are n cities numbered from 0 to n-1. Given the array edges where edges[i] = [fromi, toi, weighti] represents a bidirectional and weighted edge b ......
CF 628 C Bear and String Distance
题面翻译 题目描述： Limak是一只小北极熊。他喜欢单词——只由小写字母构成，长度为n的单词。 他规定dist(s,s')的值为s与s'在26个字母中的间距。如，dist(c,e)=dist(e,c)=2,dist(a,z)=dist(z,a)=25。 而且，当dist两个单词时，其值为dist第 ......
[论文阅读] EMO@ Earth Mover Distance Optimization for Auto-Regressive Language Modeling
Pre title: EMO: Earth Mover Distance Optimization for Auto-Regressive Language Modeling accepted: arXiv2023 paper: https://arxiv.org/abs/2310.04691 co ......
CodeForces 1246F Cursor Distance
洛谷传送门 CF 传送门 发现一个性质：能跳不超过 \(j\) 步到达 \(i\) 的所有点形成一段区间。设这这段区间为 \([L_{i, j}, R_{i, j}]\)。 那么答案即为： \[\sum\limits_{i = 1}^n \sum\limits_{j = 0} n - R_{i, j ......
AT_abc301_h [ABC301Ex] Difference of Distance
AT_abc301_h [ABC301Ex] Difference of Distance 更好的阅读体验 一道基础图论，很好口胡，但是实现不太简单。 考虑离线，把询问挂在边上，按边权从小到大处理。 处理到一个边权时，把边权小于它的边的两端用并查集合并，对于等于这个边权的边在并查集上建图，跑一边 t ......
* Codeforces Round 665 (Div. 2) A. Distance and Axis
有一个点 \(A\) 在 \(OX\) 正坐标轴上的 \(x\) 坐标为 \(n\) 。需要找到一个点 \(B\) ，使得 \(||OB| - |AB||= k\) 。 现在给出非负整数 \(n\) \(k\) ，你可以执行任意次以下操作： 每步操作可以使 \(A\) 的坐标加一或减一。 询问最少需 ......
Codeforces Round 903 (Div. 3) F. Minimum Maximum Distance（图论）
Codeforces Round 903 (Div. 3) F. Minimum Maximum Distance 思路 对标记点更新fg，从0开始进行bfs，更新d1为所有点到0的距离 获得到0最远的标记点L，从L开始bfs，更新d2为所有点到L的距离 获得距离L最远的标记点R，从R开始bfs，更 ......
CF1881F Minimum Maximum Distance
给定一棵树，树上的一些点被打上了标记，定义一个节点的贡献为其到所有标记节点距离的最大值，求最小贡献。 \(n \le 2 \times 10^5\)。 这道题的原题是 CF337D（甚至要更困难一些）。 很套路的换根 DP 啊。我们考虑设 \(f_i\) 为 \(i\) 子树内的标记节点到 \(i\ ......
题解 [ARC165C] Social Distance on Graph
赛时：看不懂题，啊这！ 赛后：就这？ 题目描述 有一个简单相连的无向图，其顶点数为 \(n\)，编号为 \(1\) 至 \(n\)。图中有 \(m\) 条加权边，第 \(i\) 条边连接顶点 \(a_i\) 和 \(b_i\)，权重为 \(w_i\)。此外，连接两个顶点的简单路径的权重是简单路径中包 ......
Codeforces Round 783 (Div. 2) B. Social Distance
\(m\) 张椅子被顺序排成一个圈，编号从 \(0\) 到 \(n - 1\) ， \(n\) 个人打算入座，第 \(i\) 个人希望左右 \(a_i\) 张椅子没有人坐。是否存在满足所有的意愿的情况下可以全部入座。\(n\) 个人不必顺序入座。 观察一：总共有 \(m\) 张椅子，\(n\) 个人 ......
CF1446F Line Distance
Dqy 7。 计几结论拍脸，感觉不如原神。 Binary search is your friend. 考虑二分答案，二分一个距离 \(r\)，考虑求出 \(d(O,AB)>r\) 的无序点对 \((A,B)\) 数量。 以 \(r\) 为半径作圆 \(C:x^2+y^2=r^2\)。考虑如果一个点 ......
AtCoder Beginner Contest 201 E - Xor Distances
# E - Xor Distances [原题链接](https://atcoder.jp/contests/abc201/tasks/abc201_e) 题意：设dist(i,j)即i到j之间路径的异或和，求树上所有两点之间dist（i，j)的和 思路：dist(i,j) = dist(i,1)^ ......
论文解读（WDGRL）《Wasserstein Distance Guided Representation Learning for Domain Adaptation》
Note：[ wechat：Y466551 | 可加勿骚扰，付费咨询 ] 论文信息 论文标题：Wasserstein Distance Guided Representation Learning for Domain Adaptation论文作者：Jian Shen、Yanru Qu、Weinan ......
[CF1794E] Labeling the Tree with Distances 题解
# [CF1794E] Labeling the Tree with Distances 题解 ## 题目描述 给你一个树，边权为 $1$。给定 $n-1$ 个数，你需要将这些数分配到 $n-1$ 个节点上。 一个点 $x$ 是好的，当且仅当存在一种分配方案，所有被分配数的点到 $x$ 的最短路径长 ......
学习笔记：什么是Wasserstein distance
简单地说，就是衡量两个概率分布之间的差异。也可以说是将一个概率分布转换成另一个概率分布要花费多少代价。 |  | ......
[LeetCode][72]edit-distance
# Content Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2. You have the following three ......
Tree Distances I
# Tree Distances I ## 思路 先考虑只算节点 $1$ 的答案，我们发现如果要每个节点都这么算一次的话，绝对会 简化题意：有一棵 $n$ 个点的树， $q$ 组询问，每次询问回答两点间的距离。 令 $dis[i][j]$ 表示 $i$ 到 $j$ 的距离，根节点 ......
【题解】[2023牛客多校] Distance
题目传送门：[[2023牛客多校] Distance](https://ac.nowcoder.com/acm/contest/57360/B) # 题意 对于任意两个元素个数相同的set：A、B，每次可以执行以下两种操作之一： + 将A中的任意元素加一 + 将B中的任意元素加一 $C(A, B)$ ......
扫描线Manhattan Distance
# Problem C. Manhattan Distance 主要算法：扫描线 二分 来源： XIII Samara Regional Intercollegiate Programming Contest Russia, Samara, March 29, 2020 >题意 ：给你二维平面上的n ......
Codeforces 1446F - Line Distance
[感觉这种类似于让你找第 $k$ 大距离的计算几何题其实都挺套路的。](https://www.cnblogs.com/tzcwk/p/Codeforces-607E.html) 二分一个答案 $t$，然后思考一下什么样的点对满足原点到它们的连线的距离 $\le t$。以原点为圆心 $t$ 为半径画 ......
834. Sum of Distances in Tree (Hard)
Description 834. Sum of Distances in Tree (Hard) There is an undirected connected tree with n nodes labeled from 0 to n - 1 and n - 1 edges. You are g ......
Codeforces 1396E - Distance Matching
先考虑一下合法的 $k$ 的上界和下界是什么以及如何达到上界和下界，我们找出树的一个重心 $R$ 并以 $R$ 为根 dfs 一遍整棵树，那么： - 下界为 $\sum(siz_i\bmod 2)$，构造方法是从下往上钦定，对于一个点考虑其所有没有匹配的儿子，如果是偶数个就将它们两两匹配，如果是奇数 ......
紫 distance
# 仅此纪念我爆掉的T3 ## 紫，即RE，运行出错，梦幻，而又不失杀气 ### 根据《雪distance》改编，分为提交前，评测前，评测时，评测后  你说我考试AK,可我却 ......
Distance to Work (牛客多校) (圆和简单多边形相交面积 + 二分半径)
#include<bits/stdc++.h> using namespace std; const double eps = 1e-9; //浮点数精度控制 #define Vector point #define Point point const double PI = acos(-1); s ......