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\)。考虑如果一个点 ......
论文解读(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 ......
学习笔记:什么是Wasserstein distance
简单地说,就是衡量两个概率分布之间的差异。也可以说是将一个概率分布转换成另一个概率分布要花费多少代价。 | ![](https://img2023.cnblogs.com/blog/2051401/202308/2051401-20230823203501853-1468206535.png) | ......
[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 ......
【BZOJ 3364】Distance Queries 距离咨询 题解
[原题](https://vjudge.net/problem/%E9%BB%91%E6%9A%97%E7%88%86%E7%82%B8-3364) 简化题意:有一棵 $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$ 为半径画 ......
Codeforces 1396E - Distance Matching
先考虑一下合法的 $k$ 的上界和下界是什么以及如何达到上界和下界,我们找出树的一个重心 $R$ 并以 $R$ 为根 dfs 一遍整棵树,那么: - 下界为 $\sum(siz_i\bmod 2)$,构造方法是从下往上钦定,对于一个点考虑其所有没有匹配的儿子,如果是偶数个就将它们两两匹配,如果是奇数 ......
紫 distance
# 仅此纪念我爆掉的T3 ## 紫,即RE,运行出错,梦幻,而又不失杀气 ### 根据《雪distance》改编,分为提交前,评测前,评测时,评测后 ![](https://cdn.luogu.com.cn/upload/image_hosting/ab6gvm5l.png) 你说我考试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 ......
[ABC294G] Distance Queries on a Tree 题解
## Description 有一个节点数为 $N$ 的树。边 $i$ 连接 $u_i$ 和 $v_i$,边的权值为 $w_i$。 $Q$ 次询问,询问一共有两种。 ```1 i w``` :改变第 $i$ 条边的权值为 $w$。 ```2 u v``` :输出 $u$ 到 $v$ 的路径距离。 数 ......
「解题报告」ARC103D Distance Sums
给 Kaguya 看了一眼,Kaguya 用了一分钟切了。我看了一个小时。这就是神吗。 考虑一个点往叶子走答案的贡献,显然距离和会变化 $-siz_u + (n - siz_u) = n - 2siz_u$。如果我们以重心为根,那么所有的 $n - 2siz_u > 0$,那么这实际上是一个小根堆。 ......
Prime Distance UVA - 10140
定两个整数 L,R , 求闭区间 [L,R] 中相邻两个质数差值最小的数对与差值最大的数对。 当存在多个时,输出靠前的素数对。 筛 1e6 每个素数,在区间里标记倍数 #include<iostream> #include <algorithm> #include <cstring> using n ......
abc253_e Distance Sequence 题解
题目传送门 简单的动态规划题。 绝对详细! 题意 给定三个整数 $n$、$m$ 和 $k$,求有多少个序列满足以下条件: 对于 $1 \leqslant i \leqslant n$,$1 \leqslant a_i \leqslant m$。 对于 $1 < i \leqslant n$,$\le ......