算法竞赛进阶指南第一章

53 阅读 0 评论 35 点赞

我是靠谱客的博主精明白云，最近开发中收集的这篇文章主要介绍算法竞赛进阶指南第一章，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

1.位运算

没啥特别重要的东西，只需要知道有符号的整数是用补码来存的,对补码的每一位取反，则数值上变成-1.

好题：求 (a^b) 对p取模的值，其中(1≤a,b,p≤10^{18})
分析：将 (a^b) 看作b个a相加. b太大怎么办？类似快速幂优化即可.

2.二分and三分

主要用于求特定的答案，即这个答案是能够求出来的，而不是问是否存在，有多少个之类的…… 三分法在使用时需要注意：如果在函数中存在一段值相等的部分，三分法就不再适用,事实上出现这种情况也有解决的方法，如果最后确定了左端点l和右端点r,从l到r枚举一遍所有点判断一下答案即可.

3.平均数问题

如果解题中出现了n个数的平均数T,将这n个数都减去T,以后与0比较即可. 比如要判断一个区间内的数的平均数是否大于x,那么将这n个数都减去x,然后看操作之后的数的和是否大于0即可.

4.中位数问题

如何求中位数？对顶堆！
经典模型：货仓选址问题.
上面两个都是书上涉及到的比较简单的处理方法，有些复杂的问题可能会用到减去偏移量，与中位数比较等方法.
减去偏移量这个方法会在以后提到，与中位数比较则是常用的判定中位数是否存在的一种方法. 二分出中位数x，将比二分出的数大的数标为1，小的数标为-1，求序列的最大连续子段和，若大于0，则x可以是原序列的中位数.接着(l = mid + 1),继续二分.

5.逆序对

归并排序和树状数组都可以求. 一个比较强大的应用是n*m数码的有解性判定.
(N×N)的棋盘，N为奇数时，与八数码问题相同。逆序奇偶同性可互达.
(N)为偶数时，空格每上下移动一次，奇偶性改变。称空格位置所在的行到目标空格所在的行步数为空格的距离（不计左右距离），若两个状态的可相互到达，则有两个状态的逆序奇偶性相同且空格距离为偶数，或者，逆序奇偶性不同且空格距离为奇数数。否则不能。

6.倍增

用来加速枚举，替代二分.
有些题目可以二分，但是在一些极端数据下，二分不如枚举快，这时就可以用倍增来加速枚举，替代二分.举个例子：
给定一个整数T,求出最大的k，满足(Σa_i≤T(1≤i≤k)), 如果T特别小，序列特别长，那么二分就要一步一步缩回来，而倍增则可以从起点一下子找到答案.

7.贪心

收益与代价问题，问题规模一般很大，时间不足以支持dp.
基本策略：在收益最大的前提下让代价尽量最小. 一般涉及到排序，采取决策包容性大的方式排序, 第i次选择时尽量选当前能选到，下一次不一定能选到的.

8.习题

https://ac.nowcoder.com/acm/contest/1004

poj2965 The Pilots Brothers’ refrigerator

枚举 / 位运算 / 搜索

https://www.cnblogs.com/RioTian/p/13461765.html

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int main() {
	char s[5][5];
	int mark[5][5];
	int x[20], y[20];
	memset(mark, 0, sizeof(mark));
	for (int i = 0; i < 4; i++) cin >> s[i];
	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 4; j++) {
			if (s[i][j] == '+') {
				mark[i][j] = !mark[i][j];//下面的操作中，i，j这个位置翻转了操作了两次，等于没操作，所以上边这里再操作一次，这样让这个位置                                                           也被操作了
				for (int k = 0; k < 4; k++) {
					mark[i][k] = !mark[i][k];
					mark[k][j] = !mark[k][j];
				}
			}
		}
	}
	int ans = 0;
	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 4; j++) {
			if (mark[i][j]) {
				x[ans] = i + 1;
				y[ans] = j + 1;
				ans++;
			}
		}
	}
	printf("%dn", ans);
	for (int i = 0; i < ans; i++) printf("%d %dn", x[i], y[i]);
	return 0;
}

poj2083 Fractal

递归 / 分形

#include<iostream>
using namespace std;
const int N=749;
int n;
char a[N][N];
void solve(int n,int x,int y){
    if(n==1)a[x][y]='X';
    else
        if(n>1){
            int num=1;
            for(int i=2;i<n;i++)
                num*=3;
            solve(n-1,x,y);
            solve(n-1,x,y+num*2);
            solve(n-1,x+num,y+num);
            solve(n-1,x+num*2,y);
            solve(n-1,x+num*2,y+num*2);
        }
}
int main(){
    while(cin>>n&&n!=-1){
       int num=1;
        for(int i=1;i<n;i++)
            num*=3;
        for(int i=0;i<num;i++)
        {
            for(int j=0;j<num;j++)
                a[i][j]=' ';
            a[i][num]='';
        }
        solve(n,0,0);
        for(int i=0;i<num;i++)
                printf("%sn",a[i]);
        printf("-n");
    }
}

poj3714 Raid

记录一下是哪种类型的点，然后求不同类型的点的最近点对

#include<bits/stdc++.h>
using namespace std;
typedef long double ld;
const int N = 1e5 + 10;
const int inf = 0x3f3f3f3f;
int n;
struct node {
	int x, y;
	bool z;
	bool operator < (const node w) const {
		return x < w.x;
	}
}e[N <<1];
node a[N], b[N];

double s(node x, node y) {
	if (x.z == y.z) return inf;
	return sqrt((ld)(x.x - y.x) * (x.x - y.x) + (ld)(x.y - y.y) * (x.y - y.y));
}

double s(int l, int r) {
	if (l == r) return inf;
	if (l + 1 == r) return s(e[l], e[r]);
	int mid = (l + r) >> 1;
	return min(s(l, mid), s(mid, r));
}

int main() {
	//freopen("in.txt", "r", stdin);
	ios::sync_with_stdio(false), cin.tie(0);
	int t; cin >> t;
	while (t--) {
		cin >> n;
		for (int i = 1; i <= n; ++i)cin >> e[i].x >> e[i].y, e[i].z = 0;
		for (int i = 1; i <= n; ++i)cin >> e[i + n].x >> e[i + n].y, e[i + n].z = 1;
		sort(e + 1, e + 2 * n + 1);
		printf("%.3fn", s(1, 2 * n));
	}
}

poj1723 Soldiers

排序 / 中位数 / 货仓选址问题拓展

问题简述：

有N个士兵，每个士兵开始站的坐标是（x，y），现在使得将N个士兵站在同一个水平线（即所有士兵的y坐标相同）并且x坐标相邻，每个士兵每次可以移动一个位置（分别在x和y方向移动）。求出最少的移动步数。

问题分析：

这是一个最优化问题，可以使用中位数计算来解决。

x方向和y方向可以分别来考虑。

y方向就是一个简单的中位数计算。

x方向是坐标相邻，可以先将x位置排序，然后往中间靠，也是一个中位数计算问题。x方向分别移动到a+i的位置，那么士兵就相邻了，即x[i]=a+i，那么x[i]-i=a。用中位数来算的话，首先将x方向进行排序，然后让x[i]=x[i]-i，再次排序后求中位数即可。

#include<bits/stdc++.h>
using namespace std;
const int N = 10000;
int x[N], y[N];
int main() {
    int n; while (cin >> n) {
        for (int i = 0; i < n; i++)
            cin >> x[i] >> y[i];
        sort(x, x + n);
        for (int i = 0; i < n; i++) x[i] -= i;
        sort(x, x + n);
        sort(y, y + n);
        int ans = 0, x_median, y_median;
        if (n % 2 == 1) {
            x_median = x[n / 2];
            y_median = y[n / 2];
        }
        else {
            x_median = (x[n / 2 - 1] + x[n / 2]) / 2;
            y_median = (y[n / 2 - 1] + y[n / 2]) / 2;
        }
        for (int i = 0; i < n; i++)
            ans += abs(x_median - x[i]) + abs(y_median - y[i]);
        cout << ans << endl;
    }
}

poj1050 To the Max

贪心 / DP

题目大意：给你一个n*n的矩阵，要求找出其中的子矩阵，使个元素的和最大，输出最大值。

题目分析：

分别把第二行加到第一行求最大子段和，再第三行加到第一行求最大子段和，....，第n行...；
再把第三行，第四行，....，n行依次加到第二行，分别求最大子段和。
记录过程中的最大值即可。

#include<bits/stdc++.h>
using namespace std;
const int N = 100;
int g[N][N], ans = -114514;
int main() {
   // freopen("in.txt", "r", stdin);
    ios::sync_with_stdio(false), cin.tie(0);
    int n; scanf("%d", &n);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            scanf("%d", &g[i][j]);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            g[i][j] += g[i][j - 1];
    for (int i = 1; i <= n; ++i)
        for (int j = i; j <= n; ++j) {
            int sum = 0;
            for (int k = 1; k <= n; ++k) {
                sum += g[k][j] - g[k][i - 1];
                ans = max(ans, sum);
                if (sum < 0) sum = 0;
            }
        }
    printf("%dn", ans);
    return 0;
}

Hdu4864 Task

贪心

题目不难，就是读题烦

分析：贪心题目，比赛的时候想到贪心。是给机器选工作。工作时间跟小于机器最接近的，然后另一个价值yi。不好贪心。

中间又想到把他们的值放在一个矩阵中贪心，转化为在一个子矩阵中求结果，这个思想也是非常好的，可是大前提没有考虑正确，事实上是给工作选机器。为什么呢？

由于题目求让完毕的任务最多，所以能够把工作和机器都按时间从大到小，然后价值从大到小，然后给每一个工作找机器。首先全部的工作时间比当前任务的工作时间大的都能够选，我们贪心选择当中价值最小的满足条件的一个机器，把大的留给后面的。这样思路就没有错了、

然后是处理，假设直接写的话接近O（n^2),必超时，開始想到的优先队列，可是优先队列返回的是最小的。我们要的是首先要满足大于当前任务价值。所以不行，然后能够用vector，也能够直接用一个数组处理。由于时间都是满足条件的，仅仅要贪心选择一个最优的价值。所以能够用一个哈希数组，非常easy的小处理了。

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
struct node{
	int x,y;
}ts[101000],mas[101000];

bool cmp(const node &a,const node &b)
{
	if(a.x!=b.x)return a.x>b.x;
	if(a.y!=b.y)return a.y>b.y;
}
int book[120];
int main()
{
	int n,m;
	while(~scanf("%d%d",&n,&m))
	{
		for(int i=0;i<n;i++)
			scanf("%d%d",&mas[i].x,&mas[i].y);
		for(int i=0;i<m;i++)
			scanf("%d%d",&ts[i].x,&ts[i].y);
		sort(mas,mas+n,cmp);
		sort(ts,ts+m,cmp);
		memset(book,0,sizeof(book));
		long long ans=0,count=0;
		for(int i=0,j=0;i<m;i++)
		{
			while(j<n and mas[j].x>=ts[i].x)//满足当前的x,意味着后续的x都可以满足 
			{
				book[mas[j].y]++;
				j++;
			}
			for(int k=ts[i].y;k<=100;k++)
			{
				if(book[k])
				{
					book[k]--;
					ans++;
					count+=ts[i].x*500+ts[i].y*2;
					break;
				}
			}
		}
		printf("%lld %lldn",ans,count);
	}
	return 0;
}