ZZXYY's blog

bzoj1010: [HNOI2008]玩具装箱toy【斜率优化DP】

第一道斜率优化DP~ 题目点击这里朴素的DP方程是比较容易想到的（想不到的话说明基本功还不够，多做一点简单DP题目吧）：F[i]表示前i个玩具装好的最小花费，则： F[i]=min(F[j]+(SUM[i]-SUM[j]+i…

bzoj1001: [BeiJing2006]狼抓兔子【最短路径】

题目点击这里题目很好理解就是一道最小割的题目，但是俗话说得好，“看到100就要想到网络流”。然而这道题目N和M都是1000的，所以直接上最大流算法似乎是不太可行的。这里就要充分利用这题里面的图的特点了。可以发现，在这个图里面：任意两…

有向图强连通分量的tarjan算法摸板

其实我在不久之前还以为有向图的强连通分量算法是和无向图的双联通分量算法是一样的呢。。。打的时候发现有点不对劲，的确有向图强连通分量的tarjan是要稍微麻烦一点的。。。代码： var a,next,v,low,dfn,st,be:arra…

bzoj1179:[Apio2009]Atm【tarjan+最短路径】

题目点击这里算是图论的比较简单的综合题目。这怎么看都是单源点最长路啦~但由于路径会有环出现，所以我们就要先用tarjan缩点，这样处理后的图就是一个有向无环图，重新建图后用改造后的spfa就可以啦。代码： var a,next,v,l…

noip2015总结与反思

Day0：也没什么特别啦，复习了一下数论的模板（然而一点都没用上，果然大家还是不喜欢数论题呢） Day1：总体感觉和去年差不多 T1：按照题目模拟即可 T2：有向图最小环。题目性质保证所有的都是简单环，bfs一下就好了 T3：防AK题？…

NOIP2015总结

最后一次正经参加NOIP了啊。。。 DAY1 早上到学校还算早，然后简单miu了几眼以前写的博客的一些模板，然而并没有用到。进机房（我讨厌二号位，一号位都好啊），每次校本课程都在这里所以很熟悉，发现只有逗比ABC就只好装个搜狗，然后今年竟…

bzoj1270[BeijingWc2008]雷涛的小猫【DP】

有段时间没有写了，NOIP就快来了，弄点DP题目做做吧。【bzoj1270】[BeijingWc2008]雷涛的小猫题目是权限题，不过NOI题库可以交。很容易想到朴素DP方程：设f[i,j]为前i棵树，高度为j时能得到的最多柿子数量…

线段树区间修改区间查询模板

一年半以前的古老代码了，现在拿出来可能以后用得上，方便找。 var s,y:array[1..1048576]of int64; n,m,i,k,a,b:longint; c:int64; procedure update&…

NOIP2015初赛总结

好吧，作为倒数第二次参加NOIP，这次可是有相当重要的意义的（吧）。考前还是看去年找到的复习资料，毕竟那个已经很全了。凭借着往年的记忆找到了省实，来的时间刚刚好，到了之后看了下试室位置之后差不多就上去了。（以下时间是当时…

凸包的Andrew算法模板

前段时间学习了一下凸包，网上主要用的是Graham扫描法，但是dwj说Andrew其实会好一点。然后我自己也看了这两种算法，感觉Andrew其实是后者的改进版，虽然没那么容易理解。 Andrew的算法流程大概如下： 1、把所有的点按照横坐标…

bzoj 4004: [JLOI2015]装备购买

【题目描述】脸哥最近在玩一款神奇的游戏，这个游戏里有 n 件装备，每件装备有 m 个属性，用向量zi(aj ,.....,am) 表示 (1≤i≤n; 1≤j≤m)，每个装备需要花费 ci，现在脸哥想买一些装备，但是脸哥很穷，所以总是盘算…

bzoj1801[Ahoi2009]chess 中国象棋【多维DP】

题目点击这里这个，题目的数据是100×100的，所以暴力DFS肯定是不行的啦～由于每行每列最多只能放2个炮，所以可以用一个三维DP 用f[i,j,k]表示放完第i行的炮后，现在有j列有1个炮，k列有2个炮，当然，1个炮都没有的列数就是m…

NOI2015网络同步赛总结与反思

嘛，其实我这个同步赛狗没什么好些的，不过既然做了，就写一下好了... Day x(x<=0) 做了几套弱省胡策，感觉自己弱爆了然后又去被xjoi的题虐... 考试前一天码了几个模板，还有+Rp的程序... Day 1 【比赛前】：…

树链剖分总结

树链剖分，用来解决树上路径的统计问题，对树进行DFS，结合线段树等数据结构可以在logN的时间内解决问题。由于要解决树上的路径问题，而线段树对边建树或者是对点建树都很难将大部分路径上的点或边在一段连续的区间里面，所以我们将树上的路径，或者…

学农总结

前言其实吧，我个人是很不想去学农的，但是没办法，【数据删除】的设定就是这样，那也就只好去了。这几天每天都很累，而且还有各种各样的事情发生，从根本上来说就是换了个地方学习。考虑到这可能是我一生中唯一一次能零距离接触土地，那还是写篇文章记录一…