BZOJ 口胡记录
最近实在是懒的不想打代码。。。好像口胡也算一种训练，那就口胡把。
BZOJ 2243 染色(树链剖分)
首先树链剖分，然后记录下每个区间的左右端点颜色和当前区间的颜色段。再对每个节点维护一个tag标记。剩下的就是很normal的线段树区间合并和标记下传了。
BZOJ 2245 工作安排(费用流)
很normal的拆边费用流。建立虚拟源点s和汇点t。s向产品连边，产品向可以生产它的工人连边，工人向t连边。这里的分段函数是个非递减的分段函数，由于最小费用流的特殊性。这里的分段函数可以用流和费用分割开来。也就是说将工人和t之间的每个边拆成m段边，每段边给个流量和费用。最后求一遍最小费用最大流。
BZOJ 2257 瓶子和燃料(数论)
两个瓶子的燃料之间的可能情况是ax+by(ax+by<=max(a,b))，而min(ax+by)=gcd(a,b)。归纳可以得出k个瓶子的最小燃料是gcd(a1,a2,,,ak)，于是问题变成，找到n个数的k个数使得这k个数的最大公约数最大。处理出这n个数的因子。找到其中出现次数超过k次的最大因子即可。
BZOJ 2298 problem a(DP)
题目可以转化为最多有几个人说真话，考虑每个人给出的信息实际上是一个关于他的rank的一个区间[ai+1,n-bi].给出的信息中，区间重合的次数要不大于于这个区间的长度。于是问题转化为，求出不冲突的区间个数的最大值。这个问题可以用DP解决。令dp[i]表示[1-i]的范围内最多有多少个区间不冲突。则转移显然可得。最后的答案就是n-dp[n].
BZOJ 2324 营救皮卡丘(floyd+费用流)
可以把图通过floyd变成一个拓扑图，然后在拓扑图上面就没有之前的限制了，再费用流建图，跑一跑。
BZOJ 2330 糖果(差分约束系统)
很裸的差分约束，建好图跑一遍最长路，无解的话判个正环即可。
BZOJ 2563 阿狸和桃子的游戏(思维)
注意到题目只需要求出最终桃子的得分-阿狸的得分。我们考虑两个通过边(u,v)连接的两个顶点u和v它们对答案的贡献。由于选的边只能连接自己已经获得的两个顶点。可以把边权转化为点权，即w(u)+=w(u,v)/2,w(v)+=w(u,v)/2.这样是不会改变答案的。然后排序一下算算就ok了。
BZOJ 2438 杀人游戏(强连通分量)
显然知道谁是杀手相当于知道所有人的身份。因此题目的答案即在无向图中选择最少的点，使得能遍历到至少n-1个点（最后一个点可以推理得到）。设结果为x，则答案为(n-x)/n。 所以就可以用Tarjan找出强联通分量然后缩点，得到的DAG上入度为0的点即所要选择的点。如果存在某个点，这个点所在的强联通分量大小为1而且这个店所有的出边到达的点的入度都>1，那么这个点不选也可以遍历到n-1个点，x可以减一。
最新文章
- java基础练习 字符串，控制流，日历，日期等
- EDMA3随笔
- 硅谷新闻3--使用Android系统自带的API解析json数据
- NPOI导出数据到Excel
- 【Hadoop】HIVE 小结概览
- Fresco 源码分析(一) DraweeView-DraweeHierarchy-DraweeController(MVC) DraweeHierachy+DraweeController的分析
- Windows 7 / Windows 10 安装 IPX/SPX
- DataBase First创建数据库
- C++设计模式之命令模式
- cefsharp实现javascript回调C#方法
- Linux常用基础命令
- node.js之fs模块
- Tomcat内核之ASCII解码的表驱动模式
- spring-boot-starter-actuator /info获取空信息
- 转 - Linux安装python3.6
- ipython安装（ jupyter）
- 1.oracle之表管理sql
- Python有趣时刻，这些代码让你大呼"卧槽，怎么会这样"
- 阿里云centos7安装桌面环境
- nyoj 光棍的yy