3.2 常用技巧精选（一）
3.2.1 尺取法
给出N个数字：，每个数字不大于10000，给出一个整数S，在N个数字中挑选出连续子序列，使这个子序列和大于或等于S。请问这个连续的子序列长度的最小值。
我们设以开始总和最初大于S时的连续子序列为，这时
所以从$a_{s+1}$开始总和最初超过S的连续子序列如果是$a_{s+1}+\cdots+a_{t\prime-1}$的话，必然有$t\le t\prime$。利用这一性质便可以设计如下算法：
(1) 以s=t=sum=0初始化。
(2) 只要依然有sum<S，就不断将sum增加$a_t$，并将t增加1.
(3) 如果(2)中无法满足sum$\ge$S则终止。否则的话，更新res=min(res,t-s)。
(4) 将sum减去$a_s$，s增加1然后回到(2)。
对于这个算法，因为t最多变化n次，因此只需O(n)的复杂度就可以求解这个问题了。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
using namespace std;
int a[100010];
int main()
{
int t;
cin>>t;
while(t-->0)
{
int n,S;
cin>>n>>S;
for(int i=0;i<n;i++)
{
cin>>a[i];
}
int res = n + 1;
int s = 0, t = 0, sum = 0;
for(;;)
{
while(t<n && sum<S)
{
sum += a[t++];
}
if(sum < S) break;
res = min(res,t-s);
sum -= a[s++];
}
if(res > n)
{
res = 0;
}
cout<<res<<endl;
}
}
3.2.2 反转（开关问题）
N头牛排成一列，头要么朝前要么朝后，现在要求确定一个连续反转牛头的连续区间，区间长度为K，要使得所有牛都朝前，且反转次数M尽可能小。求出最小的操作数M和对应的最小的K。
首先，交换区间反转顺序的先后对结果毫无影响。此外，可以知道对同一个区间进行两次以上的反转是多余的，由此，问题就转化成了求需要被反转的区间的集合。于是我们先考虑一下最左端的牛。包含这头牛的区间只有一个，因此如果这头牛面朝前方，我们就能知道这个区间不需要反转。反之，如果这头牛面朝后方，对应的区间就必须进行反转了。而且在此之后这个最左的区间就再也不需要考虑了。这样一来，通过首先考虑最左端的牛，问题的规模就缩小了1。不断的重复下去，就可以无需搜索求出最少所需的反转次数了。
然而，我们需要遍历K，对于每个K我们都要从最左端开始考虑N头牛的情况，最坏情况需要进行N-K+1次的反转操作，而每次操作又要反转K头牛，所以总的复杂度是$O(N^3)$。
对于区间反转部分进行优化：优化的方法是计算第i头牛是否要翻转的时候，只需要知道第i-k+1头到第i头之间的翻转次数，那么维护这个次数即可。
这样，在考虑第i头年时，如果$\sum_{j=i-K+1}^{i-1}f[j]$为奇数的话，则这头牛的方向与起始方向是相反的，否则方向不变。依据如下公式
使用尺取法，每次向右移动一格，需要看看左边出去的那格（第i-k格）是翻转了没有，维护好f数组即可。这样扫一遍的复杂度是$O(n)$，那么总复杂度就是$O(n^2)$。
1 | const int M = 5100; |
有一个m*n的棋盘，每个格子上是0或1，每次可以对一个格子做一次翻转操作，将被操作的格子和上下左右4个格子的0/1翻转。问做少做多少次翻转可以将所有格子翻转成0，输出翻转方案。没有方案时输出“IMPOSSIBLE”。
$1\le m, n \le 15$
回顾一下前情，在之前POJ3276问题中，让最左边的牛反转的方法只有1种，可以直接判断当前的方案是否可行。然而，同样的方法在此题中不能行得通。不妨看最左上角的格子，这里除了翻转(1,1)之外，翻转(1,2)和(2,1)都可以把这个格子翻转，所以之前的直接确定的方法在此行不通。
值得注意的一点是这题中的m，n特别小，简直就是在明示可以有某种枚举的方法。因为本题格子间的状态都是互相影响的，只能通过枚举第一行，逐行往下搜，如何搜索：如果从上到下搜索，当前行是否需要反转取决于上一行的状态，通过翻转当前行使上一行为0，而不是通过上一行翻转为0后，看当前行的状态判断自己是否需要翻转，否则还会继续影响上一行。意思就是不是在当前行中的翻转操作不是为了让当前行中的所有格子都为0，而是要让上一行的所有格子都为0。所以我们可以通过枚举第一行所有的状态，从第二行开始确定翻转状态，直到最后一行结束，如果可以保证最后一行都是0，那么方案可行，否则重新定义第一行的状态，继续搜索，找出使反转次数最少的方案。
3.2.4 折半枚举（双向搜索）
超大背包问题
有重量和价值分别为$w_i, v_i$的n个物品，从这些物品中挑选总重量不超过W的物品，求所有挑选方案中价值总和的最大值
限制条件：$1 \le n \le 40, 1\le w_i, v_i \le 10^{15}, 1 \le W \le 10^{15} $
所谓超大背包问题，W的最大值是$10^15$，使用DP来求解背包问题的复杂度是$O(nW)$，因此不能解决这里的问题。但是n比较小，依此寻求枚举解法。
从所有物品里挑选的全排列的数量为$2^n$中，在这里虽然n很小，但是$2^40$依然顶不住，所以我们想到折半枚举，把物品拆成两半再枚举。我们把前半部分中枚举出的重量和价值总和记为$w_1、 v_1$。这样在后半部分寻找总重$w_2\le W-w_1$时使$v_2$最大的选取方法就好了。
接着我们考虑从枚举得到的$(w_2,v_2)$的集合中高效寻找$max{v_2|w_2 \le W\prime}$的方法。在代码中当然使用pair这个数据结构来维护重量和价值对，那么我们根据重量排序之后可以排除所有$w_2[i] \le w_2[j]$并且$v_2[i] \ge v_2[j]$的j。接下来只要寻找$w_2[i] \le W\prime$的最大的i就可以了。使用二分搜索完成，剩余元素的个数为M（$M\le 2^{(n/2)}$）的话，一次搜素需要$O(\log M)$，所以这个算法的总复杂度是$O(2^{(n/2)}n)。
1 | typedef long long ll; |
3.2.5 坐标离散化
w*h的格子上画了n条垂直或水平的宽度为1的直线。求出这些线将格子划分成了多少个区域。
1<=w,h<=1000000. 1<=n<=500
样例：
w = 10, h = 10, n = 5
x1 = {1, 1, 4, 9, 10}
x2 = {6, 10, 4, 9, 10}
y1 = {4, 8, 1, 1, 6}
y2 ={4, 8, 10, 5, 10}
理解了半天这个样例，意思是( (x1, y1), (x2, y2) )是一条直线。一般求解被分割出的区域的个数使用图的遍历如DFS和BFS算法，需要$w\times h$，但是这个问题中w和h最大为1000000，所以没办法创建出$w\times h$的数组，所以需要使用坐标离散化技巧。
数组里只需要存储有直线的行列以及前后的行列就足够了，这样的话大小最多$6n \times 6n$就足够了（x1的自己、前后，3个，x2的自己、前后，3个，因此则有 $6n \times 6n$）。创建出数组并利用搜索求出区域的个数。（区域可能很大，所以用递归函数实现的话可能会栈溢出，所以在下列代码实现中不用DFS而用BFS）
1 | //输入 |