哒哒哒哒哒

分类

最小生成树(1) 最短路(1) 未归档(121) 题解(2)

/ 注册

全部文章（共125篇）

HDU1251 字典树板子题

题意：中文题，统计以某字符串作为前缀的字符串个数刚学字典树，理解起来十分简单，就是维护一个多叉树，这里用的是链表版本，后面就用的是数组版本了，个人更喜欢数组版本，这里的链表版本就因为莫名其妙的错误 C++能过而g++就会MLE 可能是两者管理内存的方式不一样吧 1 #include...

2019-01-10

0 414

Snowflake Snow Snowflakes POJ - 3349 Hash

题意：一个雪花有六个角给出N个雪花判断有没有相同的（可以随意旋转）参考：https://blog.csdn.net/alongela/article/details/8245005 注意:参考的博客的写法有问题不知道POJ为什么没有卡掉例如数据 1 ...

2018-11-29

0 361

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