【考试总结】之动规 5 是怎么挂的–litble
T1 青蛙的烦恼 题目描述：池塘中有 n 片荷叶恰好围成了一个凸多边形，有一只小青蛙恰好站在 1 号荷叶上，小青 蛙想通过最短的路程遍历所有的荷叶（经过一个荷叶一次且仅一次），小青蛙可以从一片荷 叶上跳到另外任意一片荷叶上。 题目分析： 青蛙怎么烦恼的我不知道，反正我很烦恼。 我有一句那啥不知当讲不 阅读更多…
【考试总结】6.17 罚款赛
论如何让 AC 代码爆 0(然后被 CY 老师罚款) T1:frog 题意: 有一个点坐标在实数范围内的凸多边形，有一只青蛙从一号顶点开始跳，每次可以从任意一个顶点跳到任意一个顶点。求这只青蛙不重复遍历多边形的每个顶点的最少跳跃距离和。节点数小于等于 720(其实 100000+也可以做) 思路: 阅读更多…
【题解】Keywords Search AC 自动机 HDU – 2222
1. 题目 传送门=￣ω￣= 2. 题解 AC 自动机模板题 其实 AC 自动机就是在 trie 树上跑 kmp。。。 一开始为了追求代码短写递归，结果不知道怎么的不停地 WA。。。 调一晚上放弃了，老老实实地打了 bfs 版的。。。 于是很快就 AC 了 真是气人！ 推荐一篇 AC 自动机的博客： ht 阅读更多…
【题解】营业额统计 Treap HNOI2002 BZOJ – 1588
1. 题目 传送门=￣ω￣= 2. 题解 平衡树模板题 写个 treap，资瓷找前驱、找后驱、插入即可。 代码： #include <bits/stdc++.h> using namespace std; typedef long long LL; struct N{LL d,f,s;N 阅读更多…
【题解】Tree(POJ1741) 树的点分治+卡常 -boshi
此生此世做过的第一恶心的树型 DP 题意: 很简单：就是要求一棵树上相距距离不超过 k 的点有几对。多组数据，n<=10000 分析: 看到不能 $O(n^2)$赶紧想有没有带 $log$的算法。没想到。于是百度。网上说是树的点分治，大概看懂了。 算法思想: 对于一棵树，其中任何一条路径都有 阅读更多…
【题解】网络收费 动态规划 树型 dp bzoj1495 codevs1787 —— by litble
题外话 这题…. 真 jay 形！ 简述题意 由于 codevs 和 bzoj 上的题意都不完整，在此简述题意（~~然而再怎么简述这个题意都很长啊~~ )。 一棵满二叉树的叶子节点是用户，网络公司很 jay 形，要求捆绑收费，对于每一对用户 i,j，要收的费用是 w[i][j]×k，w[ 阅读更多…
【题解】永无乡 [HNOI2012] treap 启发式合并 并查集 BZOJ – 2733
1. 题目 BZOJ 传送门=￣ω￣= LUOGU 传送门=￣ω￣= CODEVS 传送门=￣ω￣= 2. 题解 真是气死人啦！ 调了一晚上+一个课间操，都没找出 bug。 重写了 3 次 treap，第一次用指针，第二次用 vector，第三次用静态数组。。。 都错的一模一样！ 为什么呢？ 中午绝 阅读更多…
【题解】普通平衡树 treap BZOJ – 3224
1. 题目 传送门＝￣ω￣＝ 2. 题解 这题调了我好久好久啊！ 其实就一模板题，用来学 Treap。。。 一开始写的指针树，都不知道飞到哪里去了 后来写了个数组的但是超级辣鸡，数组都能段错误。。。 然后照着 hzwer 的代码改了一下，还是有错误。 最后无语了，自己重写了一份。 然而还是 WA 了一次 阅读更多…
【算法】最小费用最大流模板& 教程 -boshi
算法由来： 在最大流中，我们需要做的只是不停地增广，但是增广全部结束后的残量网络并不唯一，因此不同的增广方式构成的最大流对应了不同的流量。因此，如果给最大流添加一个条件：$\sum{flow*price}$最小，那么可以 增大题目难度缩小解集范围，更有实用价值与普遍适用性。 算法一般步骤： 最小费用 阅读更多…
【题解】Going Home (HDU1533) -boshi
题意: 一个地图上有很多小人要回家，每个小人都可以去任意一栋不同的房子，每个小人去一栋房子的花费为房子和人的曼哈顿距离。求最小支付多少花费可以使小人都回家？ 思路: 直接套用最小费用最大流。1. 把每个小人和每个房子连边，容量为 1，费用为距离；2. 把超级源点和每个小人连边，容量为 1，费用为 0 阅读更多…