USACO Gold题填(bei)坑(nue)计划
做起来果然比Silver带感多了,更能体现我智商癌的本质。
感觉自己还真是萎废,这种题还做得一卡一卡的
BZOJ1230 线段树
BZOJ1231 一开始没想出来,后来发现是状压DP
BZOJ1233 好神的贪心+DP,首先一个草堆要最高必须要底层最瘦。证明好像其它地方有,然后就可以DP了,记录第i个到第n个最优情况下有多瘦、有多高。一开始没注意底层宽度不一定具有单调性,然后就wa了,后来看了一下式子发现要用单调队列优化。
BZOJ1571 直接DP
BZOJ1572 首先把工作按照截止日期排个序,然后从后往前枚举时间点用个set什么的每个时间点选取最大价值的。
BZOJ1574 贪心,把跟那些点相邻的点都打上标记,最后从起点DFS能到达多少没打标记的点,最后用n-cnt就是答案了
BZOJ1575 预处理出每个区间的误差值和,最后DP一下
BZOJ1577 按照右端点排序,然后依次放就好了。
BZOJ1578 一个东西第i天买进第j天卖出相当于每天都买入卖出,所以直接算出每天最多有多少钱,也就是每天背包一下。
BZOJ1581 DP,设ai,j代表前i+j位放了i个0和j个1,有多少种方案。算第k大也是扫一遍什么的就好了
BZOJ1583 直接算,只不过题意是真的艹蛋
BZOJ1584 发现k最大只能是200,所以直接DP好了
BZOJ1585 好久没做网络流的题目了裸的最小割没看出来TAT
BZOJ1589 BFS
BZOJ1590 trie
BZOJ1592 离散化+DP
BZOJ1593 我写的splay,调起来极其带感
BZOJ1596 贪心
BZOJ1597 斜率优化
BZOJ1692 后缀数组
BZOJ1694 DP,算的是这段距离对答案的总贡献所以并没有后效性
BZOJ1697 想到了正解一开始并不敢写= = 对于每个置换环要不就用其中最小的节点在上面移,要不就把全局最小的移进来。
BZOJ1699 重题了
BZOJ1702 前缀和一下然后差分一下然后排个序
BZOJ1703 猜了个结论就是不能确认的关系的对数
BZOJ1704 乱搞
BZOJ1705 DP,因为增加的高度不会太大,但是不能只开到10,我反正开到20才过
BZOJ1706 矩阵快速幂
BZOJ1707 乱搞
BZOJ1708 背包
BZOJ1709 首先找到一个有对手的格子,答案就只能放在它的八个方向的格子上
BZOJ1710 DP
BZOJ1711 TAT果然网络流荒废太久了都不记得了,建图S->F->N->D->T
BZOJ1712 乱搞+快速幂
BZOJ1690 分数规划+二分答案+找负环,感觉好神啊。一开始还没看到路线是个环,感觉无论如何都不能理解= =
BZOJ1604 好神的规律题啊,可以看这里。
BZOJ1598 K短路,然而因为是拓扑图所以可以用A*算法。记得我以前是看过鼎爷的论文的然而已经忘得差不多了= =