CodeChef – Chef and Problems 分块

题意:

Screenshot
题意

分析:

由于自己在看 2015 年的集训队论文的时候看见了这道题目, 于是就看见了这道 CodeChef 毒题.

我们可以考虑分成 若干个区间, 每一个区间分别处理出答案, 但是我们考虑的并不能够合并这个答案, 于是我们只能另寻他路了!

如果我们暴力处理处 solve(i,j) 表示块 i ~ 块 j 的答案, 那么对于边界的情况再暴力二分一下最远对吧, 而且这题的a[i]比较的小, 可以开下一个vector的”桶”, 存贮各个位置,之后二分用 那么复杂度就是:

  1. 块的预处理:  Screenshot(即枚举块的左端点,然后暴力for过去存找max)
  2. 块的区间询问:Screenshot(因为已经处理完了! )
  3. 边界点的询问: 每一次二分用lower_bound 或者 upper_bound寻找

代码:

代码

 

POJ2987 Firing 闭合图

题目:

某Dark公司要解雇员工, 解雇员工获得的开心值有正有负, 但是有一点就是解雇了这个员工还要解雇他的下属,求最大的∑开心值!并且输出最小的裁员工的人数

分析:

其实就是最大权闭合图, 关键就是在于不要忘记了[S,T] 中 V1 = S – {s} ! 所以就可以利用最小割来寻找这个集合的点数了!那么我们的V1集合就是至少需要解雇这么多的人的集合, 其实可以意会一下!

而且最小割就是这个集合V1的”终点”, 即这些边的cap必定为 0 (最小割性质!)

于是最后DFS一下cap!=0 的边就是 S 集合的点就好了! 最后输出ans – 1 (不包括 s 点!)

但是可能有人问 : 比如在最佳的答案是 15, 再加入2个人, 选了 A 必须选 B, Happy_a = – Happy_b ! 那么照常理来说就是不会选这两人,但是Dinic的时候会不会加入答案呢?

of course not! 🙂

因为这样的话 s – > A 的边, 与 B – > t 的边都是最小割的边,所以不会被计算进去! (我们可以认为是最小割的”最简性”, 自编的! )

记住: 满流的边就是属于割, 不满流的边(dfs到的) 就是属于S集合! 因为此题要的是最小人数, 所以我们可以这么做!

代码:

代码

负载平衡问题

题目:

捕获.PNG

分析:

其实我打的是最小费用最大流的模板, 那么其实这道题目的思路非常的简单,但是我强调一下注意的细节:

  1. 注意每一个点的原先的 size
  2. 注意这个排列是环形排列,所以两个点之间的最短运输距离要注意一下!

.                   int x = i , y = j ;

.                   if(i > j)         swap(x,y);

.                    int dis = min(abs(x – y) , 1 + abs(1 – x) + abs(n – y));

.                    if(i == j) add(i, i + n, a[i], abs(i – j));

.                    else add(i, j + n, min(a[i] , tot / n – a[j]), dis);

代码:

代码

 

网络流24题

题记:

看上去机房的dalao们都早就攻克了网络流,所以我也写了一些的题解以此来记录这些东西!

但是有一些题目由于是模板,而且网上真的有好多厉害的博客,就稍微讲的少了一点!请见谅!

继续阅读 网络流24题

飞行员配对方案问题

裸的一个二分图的模板!

如果有不懂的可以上百度去搜索一下:

u=2543358439,2520347586&fm=58&bpow=600&bpoh=600.jpg

其实博主之前也是看这位的博客的,挺好的,但是少了一点总结:传送门

个人觉得其实二分图的精髓就是一个贪心,对于当前的节点,看看之前的点能不能腾出一个“位置”让这个节点能够有二分图匹配!那么依照这个性质,我们可以干很多事情啦!

代码:

代码

分块–优美的暴力

分块

其实就是相当于分治的思想  对于每一块分别进行维护从而达到降低复杂度的效果

其实就像这样:对于这几个独立的区域分别进行询问或修改,最后累加成答案

草图

确定块大小

先将块的大小设置成k 多为:捕获

我们可以先算出每一个操作的复杂度进行分析,然后捕获.PNG我们会得到一个多项式(含k的式子),求其最小值,于是我们有这几种方法:

1.基本不等式

捕获
基本不等式

2.图像法(GeoGebra)

捕获.PNG
GeoGebra

 

3.求导

想必大家都很熟悉了!就不一一赘述了!

基本操作:

其实就是这样:

块.png
对于区间覆盖的块打个标记,两边未完全覆盖的块直接暴力修改(询问)

闲话不多说,我们直接开始讲题目就好了!

T1:教主的魔法

题意简化:

支持2种操作:

  1. M  : 区间询问[l,r]中元素大于 C 的个数 C变值
  2. A  : 区间将[l,r]中的每一个元素加上 w, w变值

样例:

input:

5 3

1 2 3 4 5

A 1 5 4

M 3 5 1

A 1 5 4

ouput:

2

3

分析:

我们将每一个块内的元素分别进行排序,对于某个询问数字 x  只要二分一下位置就好了!

修改:

对于边界的情况暴力处理直接把元素加上 w,

整个块的话就标记一个 addmark[ ] 来表示区间加上了多少

询问

边界情况就直接 for 一遍

整块的话就可以二分 x + addmark[i] 的位置,对答案产生贡献就好了!

代码:

代码

T2:[HNOI2010]弹飞绵羊

题意:

有一个a序列:对于位置i,可以跳到i + a[i] 的位置

我们认为出界就是i 跳跃之后的位置超过了序列长度n

支持2种操作:

  1. 询问 位置i的跳出界的次数!
  2. 单点修改a[i]的权值

样例:

input:

4
1 2 1 1
3
1 1
2 1 1
1 1

output:

2

3

分析:

我们可以将序列分成捕获段,每一段的点储存信息:

  1. 跳出该块的跳跃次数
  2. 跳出该块之后的位置

那么我们对于每一个询问就可以 sqrt(n) 的时间内计算贡献

而且我们修改时只需要对于一个长度为根号n的块金星秀高就好了,那么我们的复杂度就是

捕获

代码:

代码

分块小结论:

1.我们对于询问区间大于(小于)某一个数的问题可以直接用分块,对于每一个块进行排序来解决问题

2.其实每一个问题都是优化而来的,我们发现其实想T2一样,其实我们可以O(1)询问答案,O(n)修改值的,但是就是这样会TLE,询问复杂度太大了,那么我们就可以将分块来介入,就像将这个O(n)的修改简化为O(sqrt(n))复杂度的式子来计算,但是询问的复杂度升高,也变成根号的,那么平均一下就可以解决了!这就是我所理解的分块:

对于问题规模缩小化,将询问与修改的复杂度进行平均来达到效果!