基本算法总结篇

本文主要是介绍基本算法总结篇，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

基本算法总结篇

位运算
- 飞行员兄弟
- - 解题思路：
  - 技巧
递归
- 分形
分治
- 平面最近点对
二分
- 防线
- 赶牛入圈
- - 离散化
中位数
- 糖果传递【环形纸牌均分问题】
- 士兵
贪心
- 耍杂技的牛
- 任务
前缀和
- 最大子矩阵的和(二维列前缀和）

位运算

飞行员兄弟

题目链接

解题思路：

对于棋盘的每一个开关都有开或者关两种状态，所以总的状态数为 2 16 2^{16} 216.没有超出int 的范围，所以我们可以用一个整数来代表棋盘的状态。意思是我们把4*4的矩阵变为一个一维的形式每一位是0或者1。0表示开，1表示关（+）。在遍历所有状态的时候，第 i为为1就表示按下第i位的开关，而按下开关之后的变化，我们可以有如下图，直接异或一个值即可。之后检验最后的状态是否全开（全0）。

在这里插入图片描述

技巧

因为异或满足结合律，所以我们不用一个一个的去异或每一行每一列的值，而是直接一次异或其总和即可。
二维小标与一维下标之间的转化。对于从0开始存的，二维小标(i,j)变为一维的公式是 i * n + j . 一维变为二维则是, x = k /n , y = k % n;

代码：

#include <bits/stdc++.h>
using namespace std;

typedef pair <int, int> PII; // 维护两个元素

vector<PII> res; // 储存答案

int state; // 状态压缩 1 表示 关; 0 表示 开 

int change[4][4];

int get(int x, int y) // 求出二维矩阵 (x, y) 的编号
{
    return 4 * x + y;
}

int main() {

    char stuc;

    for(int i = 0; i < 4; i ++) {
        for(int j = 0; j < 4; j ++) {

            cin >> stuc;
            if(stuc == '+') {
                state += 1 << get(i, j);
                // 因为当前的开关是关上的，
                // 所以用路径压缩的方式将 state 的当前编号设为 1
            }

        }
    }

    for(int i = 0; i < 4; i ++) {
        for(int j = 0; j < 4; j ++) {

            for(int k = 0; k < 4; k ++)
            {
                // 预处理九个数的异或值
                change[i][j] += 1 << get(i, k); 
                change[i][j] += 1 << get(k, j);
                // 处理 i 行 j 列的异或值
            }

            change[i][j] -= 1 << get(i, j);
            // 减去相同的元素
        }
    }

    for(int k = 0; k < (1 << 16) ; k ++) { 
    // 枚举每个开关按或不按的所有状态
        int now = state;
        // 保存原来的矩阵
        vector<PII> path;

        for(int i = 0; i < 16; i ++) {
            if( (k >> i) & 1) {
            // 如果 k 没关时
                int x = i / 4, y = i % 4;
                // 找出 k的 (x, y) 的坐标
                now ^= change[x][y]; // 因为已经预处理过了
                path.push_back({x, y}); // 加入临时答案
            }
        }

        if(!now && ( res.empty() || res.size() > path.size()))
        {
            // 满足条件并选最小的数
            res = path;
        }
    }

    cout << res.size() <<endl; // 输出元素个数

    for(int i = 0; i < res.size(); i ++) {
        // 输出方案数
        cout<< res[i].first + 1<<" "<< res[i].second + 1 <<endl;
    }
}

递归

分形

题目链接

解题思路：

这道题目思维难度不是很大，我们主要是要看清题目的输出格式，其实当n>1的时候，每一个输出，都可以看作成为九宫格。
接着我们可以注意一下每两个X之间的空格，就可以发现一定的规律。

代码：

#include <bits/stdc++.h>
using namespace std;
int a[1010][1010],n,m,i,j;
int power(int a,int b)
{
    int ans=1;
    while(b)
    {
        if (b&1)
            ans*=a;
        a*=a;
        b>>=1;
    }
    return ans;
}
void dg(int n,int x,int y)
{
    if (n==1)
    {
        a[x][y]=1;
        return ;
    }
   int len=power(3,n-2);//枚举len的长度，也就是枚举两个X之间的空格数
    dg(n-1,x,y);//左上
    dg(n-1,x+2*len,y);//右上
    dg(n-1,x+len,y+len);//中间
    dg(n-1,x,y+2*len);//左下
    dg(n-1,x+2*len,y+2*len);//右下
}
int main()
{
    while(cin>>n && n!=-1)
    {
        memset(a,0,sizeof(a));
        dg(n,1,1);
        for(int i=1;i<=power(3,n-1);i++)
        {
            for(int j=1;j<=power(3,n-1);j++)
                if (a[i][j])
                    cout<<'X';
                else
                    cout<<' ';
            cout<<endl;
        }
        cout<<"-"<<endl;
    }
    return 0;
}

分治

平面最近点对

题目链接

解题思路：
详细的题解

代码：

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath> // 计算距离时需要用到 sqrt 函数

using namespace std;

const int N = 200005;
const double INF = 1e15;
const double eps = 1e-6;

int n;
double mind;
struct point // 结构体存所有点
{
    double x, y;                           // 存每个点的坐标
    bool type;                             // 存每个点的类型
    bool operator < (const point &t) const // 用于将所有点按 x 坐标从小到大排序
    {
        return x < t.x;
    }
} points[N], tmp[N];  // points 存输入的每个点，tmp 存分治时对于每个点要处理的点

double get_dist(point a, point b)            // 返回点 a 和点 b 的直径距离
{
    if (a.type == b.type) return mind ;      // 如果这两个点的类型不同，返回当前最优答案即可。
    double dx = a.x - b.x, dy = a.y - b.y;   // 计算出这两个点横纵坐标的差值
    return sqrt(dx * dx + dy * dy);          // 返回这两个点的平面距离
}

double dfs(int l, int r)
{
    if (l == r) return INF ;                 // 如果剩下区域只有一个点，那么为了避免更新答案，返回正无穷
    int mid = l + r >> 1;                    // 找到剩下区域内中间的点的位置。
    double mid_x = points[mid].x;            // 取出该点的 x 坐标，与该坐标距离超过 ans 的点不计入考虑。
    double ans = min(dfs(l, mid), dfs(mid + 1, r)); // 分治计算出上述未被更新的 ans

    // 先将 points 中的 [l, mid] 和 [mid + 1, r] 两段进行按 y 轴坐标进行按序归并
    // 注意这里一定要归并，后面对于每个点我们才能快速找出对应的（至多） 6 个点，以保证总时间复杂度是 O(n log n)
    int i = l, j = mid + 1, cnt = 0;
    while (i <= mid && j <= r)
        if (points[i].y < points[j].y) tmp[cnt ++ ] = points[i ++ ];
        else    tmp[cnt ++ ] = points[j ++ ];
    while (i <= mid) tmp[cnt ++ ] = points[i ++ ];
    while (j <= r) tmp[cnt ++ ] = points[j ++ ];
    for (i = l; i <= r; i ++ ) points[i] = tmp[i - l];

    // 找到所有在 [mid_x - ans, mid_x + ans] 中的点，存入 tmp
    cnt = 0;
    for (i = l; i <= r; i ++ )
        if (points[i].x >= mid_x - ans && points[i].x <= mid_x + ans) // 如果说该点距离 mid_x 的距离小于 ans，那么需要考虑该点
            tmp[cnt ++ ] = points[i];
    // 下面第二层循环中，有 tmp[i].y - tmp[j].y <= ans 这个判断，才能保证我们对于每个点最多只考虑六个点
    // 这样在每层递归中，就可以保证时间复杂度是线性的，否则时间复杂度是平方级别的
    for (i = 0; i < cnt; i ++ ) // 处理所有 tmp 中的点
        for (j = i - 1; ~j && tmp[i].y - tmp[j].y + eps <= ans; j -- )
            ans = min(ans, get_dist(tmp[i], tmp[j])); // 更新 ans
    mind = min(mind, ans);
    return ans;
}

int main()
{
    int T;
    scanf("%d", &T);
    while (T -- )
    {
        scanf("%d", &n);
        for (int i = 0; i < n; i ++ )
        {
            scanf("%lf %lf", &points[i].x, &points[i].y); // 输入所有核电站的坐标
            points[i].type = false;                       // 核电站的 type 制成 false
        }
        for (int i = n; i < n << 1; i ++ )
        {
            scanf("%lf %lf", &points[i].x, &points[i].y); // 读入所有特工的坐标
            points[i].type = true;                        // 特工的 type 制成 true
        }
        mind = get_dist(points[0], points[(n << 1) - 1]);
        sort(points, points + (n << 1));                  // 将所有点按 x 坐标排序
        printf("%.3lf\n", dfs(0, (n << 1) - 1));          // 分治函数的返回值即为答案
    }
    return 0;
}

二分

防线

题目链接

题目简译：给定n个等差数列，每个等差数列的起点为s，终点为e，差为d。整个序列中至多有一个位置所占数字是奇数。判断奇数位是否存在，如果不存在输出"There’s no weakness."，如果存在输出位置与大小。

详细题解

个人理解：

我们是利用前缀和的思想找到个数为奇数的位置，因为我们知道一个序列里边有一个奇数，其余全是偶数那么其和一定为奇数,那么我们找的位置满足其前边的和为偶数，其后边的和为奇数，这就符合了二分答案意思了。

技巧：

因为我们是二分位置，假设该位置为x，那么我们需要求出从开始节点到这个区间中点的数量。有公式此区间包含此数列的个数是 ⌊ ( m i n ( e , x ) − s ) / d ⌋ + 1 。此区间包含此数列的个数是⌊(min(e,x)−s)/d⌋+1。此区间包含此数列的个数是⌊(min(e,x)−s)/d⌋+1。

代码：

#include<stdio.h>
#include<algorithm>
#include<iostream>
using namespace std;

typedef long long  ll ;
const int N = 2E5 + 10;
int n;
struct seg{
    ll s,e,d;
}segs[N];

ll get_sum(ll x){
    ll ans = 0;
    for(int i = 0;i< n;++i)
        if(segs[i].s <= x)
            ans += (min(segs[i].e,x) - segs[i].s)/ segs[i].d + 1;
            
    return ans;
}

int main(){
    int T ;
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        ll l = 0 , r = 0;
        for(int i = 0;i<n;++i)
           { 
               scanf("%d%d%d",&segs[i].s,&segs[i].e,&segs[i].d);
               r = max(r,segs[i].e);
           }
        while(l < r){
            int mid = (l + r) >> 1;
            // 如果为奇数那么该位置在前一个区间上
            if(get_sum(mid) & 1) r = mid;
            else l = mid + 1;
        } 
        auto ans = get_sum(l) - get_sum(l - 1);
        if(ans % 2 )
        printf("%d %lld\n",r,ans);
        else 
            puts("There's no weakness.");
        }
        return 0;
    }

赶牛入圈

题目链接

解题思路：

首先为为什么可以二分答案呢(矩形的边长)，因为如果有最优解的话，那么在这个最优解的左边是不符合题意的，右边是符合题意的但不是最优的。
那为什么要离散化呢？因为如果我们暴力检测一个边长是否合法的话是可以通过二维前缀和枚举每一个坐标来检测的，但这题坐标个数最大为10000，这样的话最坏是n方的。而题目告诉我们N 单位，其中N < 500.也就是说很都坐标都是重复的因此我们可以对其进行离散化。

离散化

1、数组

//离散化
void discreate(){
	sort(a+1,a+1+n);
	for(int i = 1;i<=n;++i)
	{
		if(i == 1 || a[i]  != a[i-1])
			b[m++] = a[i];
	}
}
// 查询
int query(int x){
	return lower_bound(b+1,b+1+m,x) - b;
}

2.vector

//离散化
void discreate(){
	sort(numbers.begin(),numbers.end());
    numbers.erase(unique(numbers.begin(),numbers.end()) , numbers.end());
}
// 查询
int query(int x){
	return lower_bound(numbers.begin(),numbers.end(),x) - numbers.begin();
}

在这里插入图片描述
代码：

#include<stdio.h>
#include<algorithm>
#include<vector>

using namespace std;
typedef pair<int,int> PII;
const int N = 1110;

int n,C;
PII points[N];
int sum[N][N];
vector<int> numbers;

int get(int x){
    return lower_bound(numbers.begin(),numbers.end(),x) - numbers.begin();
}

// 边长为len
bool check(int len){
    int size = numbers.size();
    //在离散之后就变成了一维直线上的包含问题了，
    for(int x1 = 0 ,x2 = 1 ; x2 < size;++x2){
        while(numbers[x2] - numbers[x1+1] + 1 > len) x1++;
        for(int y1 = 0 , y2 = 1 ; y2 < size; ++y2){
            while(numbers[y2] - numbers[y1+1] +1 > len) y1 ++ ;
            if((sum[x2][y2] - sum[x1][y2] - sum[x2][y1] + sum[x1][y1]) >= C)
                return true;
        }
    }
    return false;
}

int main(){
    scanf("%d%d",&C,&n);
    numbers.push_back(0);
    for(int i = 0 , x, y ;i < n ;++i){
        scanf("%d%d",&x,&y);
        points[i] = {x,y};
        numbers.push_back(x);
        numbers.push_back(y);
    }
    sort(numbers.begin(),numbers.end());
    numbers.erase(unique(numbers.begin(),numbers.end()) , numbers.end());
    // 初始化前缀和
    // 相当于如果x,y 坐标重复的话 sum[x][y] 会得到累加
        for(int i = 0 ;i<n;++i){
            int x = get(points[i].first) , y = get(points[i].second);
            sum[x][y] ++;
        }
        for(int i = 1;i<numbers.size();++i)
            for(int j = 1;j<numbers.size();++j)
                sum[i][j] +=  sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1];
        // 二分答案
        int l = 1 , r = 10000;
        while( l < r){
            int mid = l + r >> 1;
            if(check(mid)) r = mid;
            else l = mid + 1;
        }
        printf("%d\n",r);
    
    return 0;
}

中位数

糖果传递【环形纸牌均分问题】

题目链接

解题思路：

在这里插入图片描述

由上面的式子我们就可以将问题转化为给定数轴上的n个点，找出一个到他们的距离之和尽量小的点，而这个点就是这些数中的中位数。重要的是如何得到c[i]数组，我们由上图得到 c[1] = -b + a1 ,c[2] = -2b + a1 + a2 = c[1] + a2 - b,… , 我们就可以通过迭代一遍算出 c了。同时要注意的是 c[n] = 0 ；

代码：

#include<stdio.h>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long ll ;
const int N = 1e6 + 10;
int   a[N], n ;
ll c[N], sum,avg;

int main(){
    sum = 0;
    scanf("%d",&n);
    for(int i = 0; i< n;++i)
        {
            scanf("%d",&a[i]);
            sum += a[i];
        }
     avg = sum / n;
    // c[1] = -b + a1 ,c[2] = -2b + a1 + a2 = c[1] + a2 - b
    for(int i = 1 ;i<= n;++i)
        c[i] = c[i-1] + a[i] - avg;
    c[n] = 0; // 最后一项特判以下为是为0
    sort(c+1,c+n+1);
    long long ans = 0;
    for(int i = 1;i<=n;++i)
        ans += abs (c[i] - c[(n>>1) +1]);
    
    printf("%lld\n",ans);
    return 0;
}

士兵

题目链接

解题思路：

该问题是求x与y移动距离之和最小，而x与y是独立的。对于y轴我们可以看成是货仓问题了，只要排个序累加每一个点到中位数的距离即可。对于x轴因为要保证x坐标相邻且不重复，那么对于最优的次数有一个性质是x坐标的相对位置不会改变，即你在我之前的，在移动后你应该任然在我前边，
设最左边的士兵走到x1=a处,那么由题意,第2个走到x2=a+1处,第i个走到xi=a+i−1处.那么,第i个士兵要走|xi−(a+i−1)|=|xi−(i−1)−a||xi−(a+i−1)|=|xi−(i−1)−a|单位距离.
将xi−(i−1)看成一个整体,问题就又转化为”货仓选址”问题了,排序,取中位数即可.

在这里插入图片描述
这里a是未知的x是已知的。

注意：

如果下标从0开始，那么中位数对应的下标应该是 n/2 ,当下标从1开始，则是(n+1) / 2.

代码；

#include<stdio.h>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long ll;

const int N = 1E4 + 10;

int x[N] , y[N];
int n;

int main(){
    scanf("%d",&n);
    for(int i = 0;i<n;++i)
        scanf("%d%d",&x[i],&y[i]);
    // 要先对x坐标排个序
    sort(x,x+n);
    for(int i = 0;i<n;++i)
        x[i] -= i;
    sort(x,x+n),sort(y,y+n);
    ll ans = 0;
    for(int i = 0;i<n;++i)
    {
        ans += abs( y[i] - y[n /2]);
        ans += abs( x[i] - x[n/2]);
    }
    printf("%lld\n",ans);
    return 0;
}

贪心

耍杂技的牛

题目链接

解题思路
我们考虑相邻的第 i 头牛与第 i+1 头牛
在这里插入图片描述
其他牛的危险值显然不变，所以分析交换前后这两头牛中最大的危险值即可。

我们为了让交换前最优，那么要有交换前的最大值小于交换后的最大值。明显 w i − s i + 1 > − s i + 1 w_i - s_{i+1} > -s_{i+1} wi−si+1>−si+1，所以我们只要 w i − s i + 1 < w i + 1 − s i w_i - s_{i+1} <w_{i+1} -s_{i} wi−si+1<wi+1−si既可以，整理一下得到 w i + s i < w i + 1 − s i + 1 w_i + s_{i} < w_{i+1} -s_{i+1} wi+si<wi+1−si+1

代码：

#include<stdio.h>
#include<algorithm>

using namespace std;

typedef long long ll;

const int N = 5E4+10;

int n;
struct cow{
    ll w,s;
}cows[N];


//从小到大排序，小的放到顶部
bool cmp(cow a,cow b){
    return a.w + a.s < b.w + b.s;
}

int main(){
    scanf("%d",&n);
    for(int i = 0;i<n;++i)
        scanf("%lld%lld",&cows[i].w,&cows[i].s);
    sort(cows,cows + n,cmp);
    ll sum = 0 , ans =- 98765421;
    for(int i = 0;i<n;++i)
    {
        ll temp =  sum - cows[i].s;
        ans = max(ans,temp);
        sum += cows[i].w;
    }

    printf("%lld\n",ans);
    return 0;
}

任务

题目链接

解题四路：

我门发现这题 x 是主导收益的，所依只要x大我们就不用考虑y，因此我们以x为第一关键字，y为第二关键字进行降序排列（升序也可以，遍历的时候反着遍历即可）。将x，y放到坐标轴上，我们可以知道能满足任务的机器一定在任务点的右上方，然后我们考虑对于x大于任务的机器，我们把y从小到大排序，从中选出一个最次的不过能符合的机器进行操作。

代码：

#include<stdio.h>
#include<set>
#include<algorithm>

using namespace std;

typedef pair<int ,int >PII;
typedef long long ll;
const int N = 1E5 + 10;
int n,m;
PII machs[N],tasks[N];

int main(){
    while(~scanf("%d%d",&n,&m)){
        for(int i = 0;i<n;++i)scanf("%d%d",&machs[i].first,&machs[i].second);
        for(int i = 0;i<m;++i)scanf("%d%d",&tasks[i].first,&tasks[i].second);
        //PII 默认以第一个为第一关键字，第二个为第二关键字，升序排列
        sort(machs,machs + n);
        sort(tasks,tasks + m);
        multiset<int>ys;
        ll cnt = 0 ,res = 0;
        // 所以是从后往前遍历
        for(int i = m-1,j = n-1;i>=0;i--){
            int x = tasks[i].first , y = tasks[i].second;
            // 将符合条件的机器加进去，因为set会对里边的元素默认 从小到大排序
            while(j>= 0 && machs[j].first >= x) ys.insert( machs[j--].second);
            auto it = ys.lower_bound(y); // 找到一个符合的bug是最次的
            if(it != ys.end()){
                cnt ++ ;
                res += 500 * x + 2* y;
                ys.erase(it);
            }
        }
        printf("%lld %lld\n",cnt,res);
    }
    
    return  0;
}

前缀和

最大子矩阵的和(二维列前缀和）

题目链接

解题思路：

我们回想一下一维的时候我们求最大连续区间和的做法，我们的做法是动态规划，其中 d p [ i ] 的含义是 i 的最大连续区间的和， d p [ i ] = m i x ( 0 , d p [ i − 1 ] ) + a [ i ] dp[i] 的含义是i的最大连续区间的和，dp[i] = mix(0,dp[i-1]) + a[i] dp[i]的含义是i的最大连续区间的和，dp[i]=mix(0,dp[i−1])+a[i] 因此在这里我们可以采用这种思路将这题变为一个 O （ n 3 ） O（n^3） O（n3）的做法。如下图

所以思路是两重循环遍历矩阵的上下边界，注意可以是直线，然后将这个边界的所有列的和看成一个数就变成了最大连续区间和。而快速求出所有列的和我们可以利用前缀和优化就可以了，

代码：

#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
#include<limits.h>
using namespace std;
const int N = 110;

int g[N][N];
int n;

int main(){
    scanf("%d",&n);
    for(int i = 1 ;i<= n ;++i)
        for(int j = 1;j<=n;++j)
        {
            scanf("%d",&g[i][j]);
            g[i][j] += g[i-1][j]; //每一列进行前缀和
        }
    int res = INT_MIN;
    for(int i = 1;i<=n;++i)
        for(int j = i;j<=n;++j){
            int last = 0;
            for(int k = 1;k<=n;++k){
                // g[j][k] - g[i-1][k] 就是 第k列 i ~j 行的所有数的和
                last = max(0,last) + g[j][k] - g[i-1][k];
                res = max(res,last);
            }
        }
        printf("%d\n",res);
    
    return 0;
}

这篇关于基本算法总结篇的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！

Java教程

基本算法总结篇

基本算法总结篇

位运算

飞行员兄弟

解题思路：

技巧

递归

分形

分治

平面最近点对

二分

防线

赶牛入圈

离散化

中位数

糖果传递【环形纸牌均分问题】

士兵

贪心

耍杂技的牛

任务

前缀和

最大子矩阵的和(二维列前缀和）

前端开发

后端开发

移动端开发

数据库

服务器运维

人工智能

区块链

游戏开发

网站运营

大数据/云计算

软件工程

软件/开发工具使用

资讯