itewqq – 第 20 页 – itewqq's blog

2018年8月9日

[带权二分图][KM算法][模板] SGU252 Railway Communication

~~为什么模板题都a的这么艰难~~

调了这么久发现其实原来的就是对的只是样例可以有不同解，蠢的程度也是没谁了。。。

题意就是求DAG上的最小路径覆盖数，而且使得所有路径权值之和最小，而且要输出路径。将每一个点拆成两个点，分别在二分图左右两侧，读入的所有的路都是从左往右。求最小路径覆盖也就是求最大匹配，而在这一条件下要求总长度最小，将边附上权值求最小权最大匹配即可。由于KM算法继续阅读“[带权二分图][KM算法][模板] SGU252 Railway Communication”

2018年8月9日

[CF][构造][思维] CF1017C The Phone Number

这题官方题解给了个Dilworth’s theorem，并不懂是什么东西。。。

写出来一些后可以找规律（多写），然后可以发现就是可以把原序列分成几块连续的上升序列，只不过块之间的相对顺序反了过来。。这个也不知道怎么证明，但是感觉是找不到比这个更好的。。这样的话就相当于LIS+LDS的长度是块的大小加上块的数量。实现的时候注意最后一个块可能不完整。

继续阅读“[CF][构造][思维] CF1017C The Phone Number”

2018年8月9日2018年8月9日

[CF][枚举][预处理][二进制][坑] CF 1017C The Wu

之所以写这个题纯粹是为了提醒自己！数！组！越！界！

暴力去重枚举所有情况，然后前缀和预处理。debug到怀疑学了假的c++，最后的最后发现，数组越界,错误类似于把该写到a[1][x]写到了a[2][x] 里。。

所以数组下标一定要注意啊啊啊啊啊啊啊啊啊
继续阅读“[CF][枚举][预处理][二进制][坑] CF 1017C The Wu”

2018年8月8日

[图论][生成树扩展][LCA] bzoj1977 次小生成树模板题

这个题确实是领悟到了不少东西，lca倍增的思想和用途，思维方法，构建生成树的逻辑，严格次小的要求。发现图论很重要的一个东西就是存储用的数据结构，我不怎么会写前向星于是就很难受了。。就这个题而言是要先求MST，再对MST做LCA，那么就会有两个图，一个是原始的用来求MST，另一个用来求LCA，第二个就是MST这个树本身。所以建了俩图，第二个图是在Kruskal的过程中建立的，与此同时还要记录下来不在MST上的边，以便之后的枚举操作。另外一个需要注意的点就是要求是严格次小，所以的就需要保存一个第二大这么一个数，这个又有很多情况，不同树上区间合并的时候根据两个区间最大的数的关系来处理。

错误的话，1 求LCA的时候应该swap 使得较深的为y，这里写错了 2 数组容量开错，这个今天错了几次，主要是没看清m和n，而且总是蜜汁把m写成n。。 3 数组下标写错（为什么经常做这种蠢事？？？？ 4 跟LL比较大小却初始化为1<<29，，显然不够，改成1<<60就过了，也是最后一个错误
继续阅读“[图论][生成树扩展][LCA] bzoj1977 次小生成树模板题”

2018年8月8日