二分法——《算法笔记》

发表于 2020-01-06 | 分类于三更有梦书为枕

字数统计: 1,262 字 | 阅读时长 ≈ 5 分钟

1. 二分法适用范围

二分法适用在一个严格单调序列中找到给定的某个数。

2. 二分法模板提要

首先，在库中的有lower_bound()和upper_bound()两个函数，对于lower_bound()来说，它是寻找第一个满足条件“值大于等于x”的元素的位置；而对于upper_bound()来说，它是寻找第一个满足条件“值大于x”的元素的位置。对于此类寻找有序序列中第一个满足某条件的元素的位置的问题，有固定的模板，如下：

//二分区间位左闭右闭的[left, right]，初值必须能覆盖解的所有可能取值
int solve(int left, int right)
{
	int mid;
	while (left < right) //对于[left, right]来说，left == right意味着找到唯一位置
	{
		mid = (left + right) / 2;
		if (条件成立) //条件成立，第一个满足条件的元素的位置<=mid
		{
			right = mid; //往左子区间[left, mid]寻找
		}else //条件不成立，则第一个满足该条件的元素的位置>mid
		{
			left = mid + 1;//往右子区间[mid+1, right]寻找
		}
	}
	return left; //返回最终确定的位置
}

阅读全文 »

划分、解决、合并：分治法——《挑战程序设计竞赛》

发表于 2019-07-04 | 分类于三更有梦书为枕

字数统计: 378 字 | 阅读时长 ≈ 2 分钟

4.6.1 数列上的分治法

给定一个1~n的排列 $a_0,a_1,\cdots, a_{n-1}$ ，求这个数列中的逆序数对。

我们可以把一个大的数列A分成左右两个子数列B、C，那么数列A中所有的逆序对必定来自于以下三者其一：
(1) i,j都属于左子数列B的逆序对(i,j);
(2) i,j都属于右子数列C的逆序对(i,j);
(3) i属于B而j属于C

对于这(1)和(2)，可以通过递归求得，对于(3)，我们可以对数列C中的每个数字，统计数列B中比它大的数字的个数，再把结果加起来就好。代码如下，复杂度为$O(n\log n)。

typedef long long ll;
//输入
vector<int> A;
ll merge_count(vector<int> &a)
{
	int n = a.size();
	if(n<=1) return 0;
	ll cnt = 0;
	vector<int> b(a.begin(), a.begin()+n/2);
	vector<int> c(a.begin() + n/2, a.end());
	
	cnt += merge_count(b); //(1)
	cnt += merge_count(c); //(2)
	//此时b和c就已经分别排好序了
	//(3)
	int ai = 0, bi = 0, ci = 0;
	while(ai < n)s
	{
		if(bi < b.size() && (ci == c.size() || b[bi] <= c[ci])) //ci == c.size()这个判断是，如果c数列已经全部找完了，剩下的全是b数列里的树，就不能看在有逆序数的存在
		{
			a[ai++] = b[bi++];
		}
		else
		{
			cnt += (n/2 -bi);
			a[ai++] = c[ci++];
		}
	}
	return cnt;
}
void solve()
{
	printf("%lld\n", merge_count(A));
}

4.6.3 平面上的分治法

双端队列的运用——《挑战程序设计竞赛》

发表于 2019-07-04 | 分类于三更有梦书为枕

字数统计: 261 字 | 阅读时长 ≈ 1 分钟

滑动最小值
给定一个长度为n的数列 $a_0, a_1, \cdots, a_{n-1}$ 和一个整数k。求数列$bi = \min{a_i,a{i+1},\cdots,a_{i+k-1} }(i=0,1,\cdots,n-k)。
限制条件：
$1\le k \le n \le 10^6$, $0 \le a_i \le 10^9$

使用双端队列可以在O(n)时间内解决这个问题。最开始时双端队列为空，然后不断维护双端队列使它按照下面的顺序，存储用于计算后面的最小值a的元素的下标。

$设双端队列从头部开始的元素的值为x_i，则x_i < x_{i+1}且a_i < a_{i+1}$

// 输入
int n, k;
int a[MAX_N];

int b[MAX_N]; //保存答案的数组
int deq[MAX_N];

void solve()
{
	int s = 0, t = 0; //双端队列的头部和尾部
	for(int i=0;i<n;i++)
	{
		while(s<t && a[deq[t-1]] >= a[i]) t--;
		deq[t++] = i;
		if(i-k+1 >= 0)
		{
			b[i-k+1] = a[deq[s]];
			if(deq[s] == i-k+1)
			{//从双端队列的头部删除元素
				s++;
			}
		}
	}
	for(int i=0;i<=n-k;i++)
	{
		printf("%d%c",b[i],i==n-k?'\n':' ');
	}
}

栈的运用——《挑战程序设计竞赛》

发表于 2019-07-03 | 分类于三更有梦书为枕

字数统计: 1,724 字 | 阅读时长 ≈ 7 分钟

POJ 2559: Largest Rectangle in a Histogram

给定从左到右n个矩形，已知这此矩形的宽度都为1，长度不完全相等，为$h_1,h_2, \cdots, h_n$。这些矩形相连排成一排，求在这些矩形包括的范围内能得到的面积最大的矩形，打印出该面积。所求矩形可以横跨多个矩形，但不能超出原有矩形所确定的范围。
$1\le n \le 100000$
输入
7 2 1 4 5 1 3 3
输出
8

阅读全文 »

网络流解决问题——《挑战程序设计竞赛》

发表于 2019-07-01 | 分类于三更有梦书为枕

字数统计: 1,163 字 | 阅读时长 ≈ 5 分钟

3.5.1 最大流

求解最大流的Ford-Fulkerson算法的邻接表实现的例子如下：

#include<iostream>
#include<queue>
#include<vector>
#define MAX_V 10000
#define INF 0x3f3f3f3f
using namespace std;

//求解最大流问题的基础代码
struct edge{int to, cap, rev;};
vector<edge> G[MAX_V]; //邻接表
bool used[MAX_V];

void add_edge(int from, int to, int cap){
    //第三个参数反向边是在G[to]中来自from边（反向边）的index。
    G[from].push_back((edge){to,cap,G[to}.size()});
    //因为刚刚from的邻接表中加了一个元素，所以要得到正确的反向边的index，就要减一
    G[to].push_back((edge){from,0,G[from}.size()-1}) }

int dfs(int v,int t,int f)
{
    if(v == t)return f;
    used[v] = true;
    for(int i=0;i<G[v].size();i++)
    {
        edge &e = G[v][i];
        if(!used[e.to] && e.cap > 0)
        {
            int d = dfs(e.to, t, min(f.e.cap));
            G[e.to][e.rev].cap += d;
            return d;
        }
    }
    return 0;
}

int max_flow(int s, int t)
{
    int flow = 0;
    for(;;)
    {
        memset(used, 0, sizeof(used));
        int f = dfs(s, t, INF);
        if(f == 0) return flow;
        flow += f;
        
    }
}

记最大流的流量为F，那么该算法最多进行F次深度优先搜索，所以其复杂度为$O(F|E|)$。不过，这是一个很松的上界，达到这种最坏复杂度的情况几乎不存在。

阅读全文 »

熟练掌握动态规划——《挑战程序设计竞赛》

发表于 2019-06-28 | 分类于三更有梦书为枕

字数统计: 1,388 字 | 阅读时长 ≈ 6 分钟

3.4.1 状态压缩DP

可能在一些DP的递推关系式中，下表不是普通的整数，但是我们可以把它编码成一个整数，或者给它们定义一个全序关系并用二叉搜索树存储，从而可以记忆化搜索来求解。

旅行商问题：
给定一个n个顶点组成的带权有向图的距离矩阵d(I,j)（INF表示没有边）。要求从顶点0出发，经过每个顶点恰好一次后再回到顶点0。问所经过的边的总权值的最小值是多少？
$2\le n \le 15$
$0\le d(i,j) \le 1000$

阅读全文 »

树状数组——《挑战程序设计竞赛》

发表于 2019-06-28 | 分类于三更有梦书为枕

字数统计: 77 字 | 阅读时长 ≈ 1 分钟

树状数组(Binary Indexed Tree(B.I.T), Fenwick Tree)是一个查询和修改复杂度都为log(n)的数据结构。给一个初始值全为0的数列，$a_1, a_2, \cdots, a_n$，树状数组可以进行如下操作：

给定i，计算$a_1+a_2+\cdots+a_i$
给定i和x，执行$a_i+=x$

线段树——《挑战程序设计竞赛》

发表于 2019-06-27 | 分类于三更有梦书为枕

字数统计: 2,932 字 | 阅读时长 ≈ 13 分钟

3.3.1 线段树

线段树是一种二叉搜索树，它将一个区间划分成一些单元区间，每个单元区间对应线段树中的一个叶结点（并非完全二叉树！！！）。实际应用时一般还要开4N的数组以免越界。

线段树的构造代码如下：

#include <iostream>
using namespace std;
 
const int maxind = 256;
int segTree[maxind * 4 + 10];
int array[maxind]; 
/* 构造函数，得到线段树 */
//区间为[begin, end]
void build(int node, int begin, int end)  
{  
    if (begin == end)  
        segTree[node] = array[begin]; /* 只有一个元素,节点记录该单元素 */
    else  
    {   
    	/* 递归构造左右子树 */ 
        build(2*node, begin, (begin+end)/2);  
        build(2*node+1, (begin+end)/2+1, end); 
		 
		/* 回溯时得到当前node节点的线段信息，保存最小值 */  
	    if (segTree[2 * node] <= segTree[2 * node + 1])  
	        segTree[node] = segTree[2 * node];  
	    else  
	        segTree[node] = segTree[2 * node + 1];  
    }  
}
 
int main()
{
	array[0] = 1, array[1] = 2,array[2] = 2, array[3] = 4, array[4] = 1, array[5] = 3;
	build(1, 0, 5);
	return 0;
}

阅读全文 »

常用技巧精选(一)——《挑战程序设计竞赛》

发表于 2019-06-27 | 分类于三更有梦书为枕

字数统计: 2,908 字 | 阅读时长 ≈ 13 分钟

3.2 常用技巧精选（一）

3.2.1 尺取法

Subsequence

给出N个数字： $a_0, a_1, \cdots, a_{n-1}$ ，每个数字不大于10000，给出一个整数S，在N个数字中挑选出连续子序列，使这个子序列和大于或等于S。请问这个连续的子序列长度的最小值。

我们设以 $a_s$ 开始总和最初大于S时的连续子序列为 $a_s+\cdots+a_{t-1}$ ，这时

$a_{s+1}+\cdots+a_{t-2} < a_s+\cdots+a_{t-2} < 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)的复杂度就可以求解这个问题了。

#include<iostream>
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;
    }

}

阅读全文 »

数学问题的解题窍门——《挑战程序设计竞赛》

发表于 2019-06-26 | 分类于三更有梦书为枕

字数统计: 433 字 | 阅读时长 ≈ 2 分钟

2.6.2 有关素数的基础算法

埃氏筛法

素数的个数：
给定整数n，请问n以内有多少个素数？

首先将2到n范围内的所有整数写下来，其中最小的数字2是素数，将表中所有2的倍数都划去，表中剩余的最小数字是3，它不能被更小的数整除，所以是素数，再将所有3的倍数划去。以此类推：

int prime[MAX_N]; //第i个素数
bool is_prime[MAX_N + 1];
//返回n以内素数的个数
int sieve(int n)
{
	int p = 0;
	for(int i=0;i<=n;i++)is_prime[i]=true;
	is_prime[0] = is_prime[1] = false;
	for(int i=2;i<=n;i++)
	{
		if(is_prime[i])
		{
			prime[p++] = i;
			for(int j=2*i;j<=n;j+=i) is_prime[j] = false;
		}
	}
	return p;
}

埃氏筛法的复杂度仅有$O(n\log\log n)$。

阅读全文 »

Faded Cosine

To say goodbye is to die a little.