18duangduang

未归档

计算几何(1) 题解(71)

/ 注册

全部文章 / 未归档（共26篇）

树上距离问题

https://ac.nowcoder.com/acm/contest/35/D对于某个点x,以x为根的子树上，所有与x距离大于等于k的点与x的距离之和。解法一：离线处理。https://ac.nowcoder.com/acm/contest/view-submission?submission...

2020-08-21

0 548

dp

简单dp:https://ac.nowcoder.com/acm/problem/16664 背包1.https://ac.nowcoder.com/acm/problem/178712.https://ac.nowcoder.com/acm/problem/512163.https://ac.no...

2020-07-26

0 485

计算几何之模拟退火

1.POJ1379 HDU 1109题面相同题意：给定0——X,0——Y的矩形，给定n个点的坐标，在矩形中求得一个点是的该点到所有点的最短距离最大。(保留小数 )分析：模拟退火(随机化)算法，可求解精度要求较小的几何寻点问题.随机选取多个(20个)初始点，进行多次随机坐标变换，并且根据降温概率进行...

模拟退火

2020-07-08

0 661

各种子矩阵问题

1.求01矩阵中最大子正方形的面积.(n<=1e3) https://leetcode-cn.com/problems/maximal-square/ 分析：考虑动态规划。表示以为当前最大正方形的右下角时的正方形的最大边长。那么转移方程： #include<bits/stdc+...

2020-07-05

0 622

最短路合集

1.条件类型最短路 https://ac.nowcoder.com/acm/contest/370/B 题意：n个点，m无向边，n个点有一部分是特殊的点，求从1走到n最短路是多少。并且该最短路满足走过的特殊点不超过K.分析: 将所有点的状态分离成K个点(K分层图)，表示到当前该点的走过的特殊点有...

最短路

2020-07-04

0 564

各种矩阵选数问题

最近做的矩阵选数问题比较多，写一篇博客。 1.每个人戴不同帽子的方案数. https://leetcode-cn.com/problems/number-of-ways-to-wear-different-hats-to-each-other/ 题目大意:有n个人40顶帽子，每个人喜欢不同的帽子...

2020-05-06

1 939