哒哒哒哒哒

未归档

最小生成树(1) 最短路(1) 题解(2)

/ 注册

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

Antenna Placement POJ - 3020 二分图匹配匈牙利拆点建图最小路径覆盖

题意：图没什么用给出一个地图地图上有点一次可以覆盖2个连续的点（左右或者上下表示连续）问最少几条边可以使得每个点都被覆盖最小路径覆盖最小路径覆盖=|G|-最大匹配数证明：https://blog.csdn.net/qq_345...

2018-11-24

0 445

Asteroids POJ - 3041 匈牙利算法+最小点覆盖König定理

题意：给出一个N*N的地图N 地图里面有K个障碍你每次可以选择一条直线消除这条直线上的所有障碍（直线只能和列和行平行）问最少要消除几次题解：如果（x，y）上有一个障碍则把X加入点集 V1 、Y加入点集V2 并且X Y连一条边这样构成一个新图如果选择 V...

2018-11-24

0 393

二分图最小点覆盖König定理的简单证明（加入自己理解）

第一次更改：http://blog.sina.com.cn/s/blog_51cea4040100h152.html 讲的更细致增广路：https://blog.csdn.net/qq_37457202/article/details/80161274 --------------------...

2018-11-24

0 714

Fence Repair POJ - 3253 哈夫曼思想优先队列

题意：给出一段无限长的棍子，切一刀需要的代价是棍子的总长，例如21切一刀变成什么长度都是代价21 列如7切成5 和2 也是代价7题解：可以利用霍夫曼编码的思想短的棍子就放在底层长的尽量切少一次直接用优先队列取前2个和一个然后代价加起来就好有一个小trick就是只有一个棍子的时候要特判...

2018-11-21

0 310

Sorting It All Out POJ - 1094 拓扑排序

题意：给N个字母，和M个偏序关系求一个可确定的全序，可确定是指没有其他的可能例如A>B D>B 那么有ADB DAB两种，这就是不可确定的其中，M个偏序关系可以看做是一个一个按时间给出的，如果还没给完就已经满足条件了，后面的可以不用管题解：拓扑水题，直接用拓扑排序暴力其中如果途...

2018-11-21

0 372

Codeforces Round #518 (Div. 2) B. LCM gcd+唯一分解定律

题意：给出b 求lcm(a,b)/a 在b从1-1e18有多少个不同得结果思路lcm*gcd=a*b 转换成 b/gcd(a,b) 也就是看gcd(a,b)有多少个值可以把b 由唯一分解定理分解一下然后组合一下各个因子就是由多少种了注意：因为唯一分解定律都是素数 ...

2018-11-04

0 390

Codeforces Round #514 (Div. 2) C. Sequence Transformation 思维构造

题意给出一个1-n的集合 gcd 集合里面的所有数得到的一个数然后自己选择删去一个数要使得到的数构成的数列的字典序最大思路： gcd所有数那gcd得到的数肯定要小于数组中最小的数所以刚开始都是1 所以优先删去1 那就要使gcd所有数经可能快得到 2 ...

2018-11-04

0 447

ceil以及double的精度问题

Codeforces Round #518 (Div. 2) A CF一道水题，总过不去后面看了一下数据发现是精度出问题了 1000000000000000000 1 1 1000000000000000000这里发现 ceil(1000000000000000000*1.0+1)/1 还是...

2018-11-01

0 346

P1387 最大正方形 dp

思路: i j的最大正方形等于min(他的斜上方的的最大正方形,他的上方有的连续1，他的左方有的连续1)+1 #include<bits/stdc++.h> using namespace std; const int INF=10000000; int mp[205][205...

2018-10-31

0 409

P1508 Likecloud-吃、吃、吃

数字金字塔3条路 f[i][j]=max(max(f[i-1][j],f[i-1][j-1]),f[i-1][j+1])+a[i][j]; #include<bits/stdc++.h> using namespace std; const int INF=10000000; i...

2018-10-31

0 306