首页 > 编程语言 >基础算法

基础算法

时间：2023-08-03 14:44:45浏览次数：38  
标签：return int 基础 mid 算法 vector include size

复健\(Day3\)

一些基础的算法（模板）

\(1.\)位运算

进行状压\(DP\)时常用到位运算

\(64\)位整数乘法

https://www.acwing.com/problem/content/92/

#include<iostream>
#include<cstdio>
#define LL long long 
using namespace std;

int main()
{
    LL a,b,p;
    cin>>a>>b>>p;
    LL res=0;
    while(b)
    {
        if(b&1) res=(res+a)%p;
        a=(a<<1)%p;
        b>>=1;
    }
    printf("%lld\n",res);
    return 0;
}

快速幂

https://www.acwing.com/problem/content/91/

#include<iostream>
#include<cstdio>
#include<cstring>
#define LL long long
using namespace std;

int main()
{
    LL a,b,p;
    cin>>a>>b>>p;
    LL res=1%p;
    while(b)
    {
        if(b&1) res=res%p*a%p;
        a=a*a%p;
        b>>=1;
    }
    return res;
    printf("%lld\n",res);
    return 0;
}

最短\(Hamiton\)路径

https://www.acwing.com/problem/content/93/

#include<iostream>
#include<cstdio>
#include<cstring>
#define N 20
using namespace std;

int dis[N][N];
int dp[1<<N][N];

int main()
{
    memset(dp,0x3f,sizeof(dp));
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            cin>>dis[i][j];
        }
    }
    dp[1][0]=0;
    for(int i=0;i<(1<<n);i++)//注意枚举顺序，最外层枚举为走过的状态
    {
        for(int j=0;j<n;j++)
        {
            if(i&(1<<j))
            {
                for(int k=0;k<n;k++)
                {
                    if(j!=k)
                    {
                        dp[i][j]=min(dp[i][j],dp[i^(1<<j)][k]+dis[k][j]);
                    }
                }
            }
        }
    }
    printf("%d\n",dp[(1<<n)-1][n-1]);
    return 0;
}

\(2.\)二分

https://www.acwing.com/blog/content/2112/

image-20230418204900992

对于左边红色区间的情况为

while(l<r)
{
	int mid=(l+r+1)>>1;
	if(check(mid)) l=mid;
	else r=mid-1;
}

对于右边绿色区间的情况为

while(l<r)
{
	int mid=(l+r)>>1;
	if(check(mid)) r=mid;
	else l=mid+1;
}

题目

\(1.Acwing102\)

https://www.acwing.com/problem/content/104/

向下取整函数\(floor\)，\(double\) \(floor\)\((double\) \(arg)\)，向上取整函数\(ceil\)，用法与\(floor\)相同

#include<iostream>
#include<cstdio>
#include<cmath>
#define EPS 1e-5
#define maxn 100010
using namespace std;

int n,F;
int s[maxn];
double sum[maxn];

int Min(int a,int b)
{
	return a>b?b:a;
}

int Max(int a,int b) 
{
	return a>b?a:b;
}

bool check(double ans)//双指针做法 
{
	for(int i=1;i<=n;i++)
	{
		sum[i]=sum[i-1]+s[i]-ans;
	}
	double minv=0;
	for(int i=0,j=F;j<=n;i++,j++)
	{
		minv=min(minv,sum[i]);
		if(sum[j]-minv>=0) return true;
	}
	return false;
}

int main()
{
	cin>>n>>F;
	double l=2000.0,r=1.0;
	for(int i=1;i<=n;i++)
	{
		cin>>s[i];
		l=Min(l,s[i]);
		r=Max(r,s[i]);
	}
	while(r-l>EPS)
	{
		double mid=(l+r)/2.0;
		if(check(mid)) l=mid;
		else r=mid;
	}
	printf("%d\n",int(r*1000));
	return 0;
}

这道题要求我们找到一段长度大于等于\(F\)的区间，这段区间里牛的平均数要使得其最大

首先我们可以考虑到采用二重循环，枚举区间长度（大于等于F）以及起点，这样的时间复杂度是略小于\(O(n\ ^2)\)（在前缀和预处理的情况下）

我们思考要如何优化，在前缀和上考虑进行处理。平均数有一个很明显的性质，某个数减去平均数如果大于\(0\)，那么它本身就是大于平均数的，若小于\(0\)就是小于平均数的。因此我们用\(sum[i]\)记录\(s[1]-avg+s[2]-avg+s[3]-avg+...+s[i]-avg\)。

然后我们用两个指针\(i\)和\(j\)，我们初始化\(i=0,j=F\)，然后每次循环都\(i++,j++\)这样我们就可以保证\(i\)和\(j\)之间的距离始终保持为\(F\).

\(sum[j]-sum[i]\geqslant0\)时显然这一段的数减去平均大于等于\(0\)，也即满足平均值大于等与该二分的答案，这样是考虑了长度为\(F\)的区间，而对于大于\(F\)的区间，我们又用一个\(minv\)记录从\(1\)至\(i\)的过程中\(sum[i]\)的最小值，这是最优的一个最小值，当我们\(sum[j]-minv\geqslant0\)时，那么我们的平均值就满足条件了并且保证了区间长度大于等于\(F\)了

这样\(check\)函数就优化成了\(O(n)\)的复杂度了

\(2.Acwing113\)

https://www.acwing.com/problem/content/115/

关于交互式问题

// Forward declaration of compare API.
// bool compare(int a, int b);
// return bool means whether a is less than b.

class Solution {
public:
    vector<int> specialSort(int N) {
        vector<int> v;
        v.push_back(1);//将1装入v中，便于比较
        for(int i=2;i<=N;i++)
        {
            int l=0,r=v.size()-1;
            while(l<r)//找到第一个小于i的位置r
            {
                int mid=(l+r+1)>>1;//这里注意是l+r+1>>1
                if(compare(v[mid],i)) l=mid;//v[mid]<i
                else r=mid-1;
            }
            v.push_back(i);//把i放在v的最后一个位置
            for(int j=v.size()-2;j>r;j--)//将i放在r+1的位置，然后把原本在r+1以及以后的数都往后移一位
            {
                swap(v[j],v[j+1]);
            }
            if(compare(i,v[r])) swap(v[r],v[r+1]);//i可能是最小的元素，v[r]仍然大于i，故这个时候我们做一个特殊判断
        }
        return v;
    }
};

注意到我们这里的二分部分给的边界条件是\(l<r\)，然后\(mid\)的计算式\((l+r+1)>>1\)

\(3.[USACO\) \(2009\) \(Dec\) \(S]Music\) \(Notes\)

https://ac.nowcoder.com/acm/contest/22353/A

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define maxn 50010
using namespace std;

int n,q,b[maxn];
int T[maxn];//记录开始时间

int query(int t)
{
	int l=1,r=n;
	while(l<r)
	{
		int mid=(l+r+1)>>1;
		if(T[mid]>t) r=mid-1;
		else l=mid;
	}
	return l;
}

int main()
{
	cin>>n>>q;
	for(int i=1;i<=n;i++)
	{
		cin>>b[i];
		T[i]=T[i-1]+b[i-1];
	}
	while(q--)
	{
		int t;
		cin>>t;
		printf("%d\n",query(t));
	}
	return 0;
}

这道题需分清楚是我们二分里的哪种情况，因为T记录起始时间，所以当某个编号的起始时间大于\(t\)的时候\(mid\)一定不是最后的答案，故\(r\)为\(mid\)往前移一位

实际上我们的二分有很多种写法，也不必拘泥于这两种

\(3.\)排序

https://www.acwing.com/problem/content/description/109/

超快速排序

\(4.\)高精度

\(substr\)截取函数的用法：\(string\)型变量\(a\)的\(a.substr(n)\)指从\(a[1]\)一直截取至最后

高精度加减法模板

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;

int compare(vector<int>& A,vector<int>& B)
{
	if(A.size()<B.size()) return -1;
	if(A.size()>B.size()) return 1;
	
	for(int i=A.size()-1;i>=0;i--)
	{
		if(A[i]>B[i]) return 1;
		else if(A[i]<B[i]) return -1;
	}
	return 0;
}

vector<int> add(vector<int>& A,vector<int>& B)
{
	if(A.size()<B.size()) return add(B,A);
	vector<int> C;
	int t=0;
	for(int i=0;i<A.size();i++)
	{
		t+=A[i];
		if(i<B.size()) t+=B[i];
		C.push_back(t%10);
		t/=10;
	}
	if(t) C.push_back(t);
	return C;
}

vector<int> sub(vector<int>& A,vector<int>& B)
{
	if(compare(A,B)<0)
	{
		printf("-");
		return sub(B,A);
	}
	vector<int> C;
	int t=0;
	for(int i=0;i<A.size();i++)
	{
		t+=A[i];
		if(i<B.size()) t-=B[i];
		C.push_back((t+10)%10);
		if(t<0) t=-1;
		else t=0;
	}
	while(C.size()>1&&C.back()==0) C.pop_back();
	return C;
}

void print(vector<int> A)
{
	for(int i=A.size()-1;i>=0;i--) printf("%d",A[i]);
	printf("\n");
}

int main()
{
	string a,b;
	cin>>a>>b;
	vector<int> A,B;
	for(int i=a.size()-1;i>=0;i--) A.push_back(a[i]-'0');
	for(int i=b.size()-1;i>=0;i--) B.push_back(b[i]-'0');
	print(add(A,B));
	print(sub(A,B));
	return 0;
}

高精度乘法模板

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;

vector<int> mul(vector<int>& A,vector<int>& B)
{
	vector<int> C(A.size()+B.size());
	for(int i=0;i<A.size();i++)
		for(int j=0;j<B.size();j++)
			C[i+j]+=A[i]*B[j];
	int t=0;
	for(int i=0;i<C.size();i++)
	{
		t+=C[i];
		C[i]=t%10;
		t/=10;
	}
	
	while(C.size()>1&&C.back()==0) C.pop_back();
	return C;
}

void print(vector<int> A)
{
	for(int i=A.size()-1;i>=0;i--) printf("%d",A[i]);
}

int main()
{
	string a,b;
	cin>>a>>b;
	
	vector<int> A,B;
	for(int i=a.size()-1;i>=0;i--) A.push_back(a[i]-'0');
	for(int i=b.size()-1;i>=0;i--) B.push_back(b[i]-'0');
	print(mul(A,B));
	return 0;
}

标签：return,int,基础,mid,算法,vector,include,size
From： https://www.cnblogs.com/iwillenter-top1/p/17603293.html

相关文章

  • 《Kali渗透基础》12. 无线渗透（二）
    @目录1：无线协议栈1.1：ifconfig1.2：iwconfig1.3：iw1.4：iwlist2：无线网卡配置2.1：查看无线网卡2.2：查看信道频率2.3：扫描附近AP2.4：侦听接口添加与删除3：RADIOTAP头部4：MPDU4.1：基本知识4.2：MPDU介绍4.3：Header4.3.1：FrameControl4.3.1.1：Type/SubType4.3.1.2：ToDS/FromDS4.3.2：Duration/I......
  • 为什么倒排索引不采用zlib这样的字典压缩算法——因为没法直接使用啊
    看了下压缩算法的发展历史，根据倒排索引的数据结构特点，个人认为zstd不适合做倒排索引压缩，举例说明下：假设有一份文档倒排列表为：[300,302,303,332]，对于这组倒排数据，是没法***直接***采用zstd这类字典压缩算法的，因为里面没有重复数据（字典压缩通常重复数据较多，例如一个重复单词较多的......
  • 简单解压缩算法
    题目描述现需要实现一种算法，能将一组压缩字符串还原成原始字符串，还原规则如下:字符后面加数字表示重复字符次。例如：压缩内容为，表示原始字符串为花括号中的字符串加数字表示花括号中的字符重复次。例如压缩内容为表示原始字符串为字符加和花括号后面加，支持任意的嵌套，包括互相嵌......
  • 算法-18-希尔排序
         ......
  • 算法笔记（二）—— 认识N（logN）的排序算法
    递归行为的时间复杂度估算整个递归过程是一棵多叉树，递归过程相当于利用栈做了一次后序遍历。对于master公式，T(N)表明母问题的规模为N，T(N/b)表明每次子问题的规模，a为调用次数，加号后面表明，除去调用之外，剩余语句的复杂度是多少，算出d。根据上次三个判断公式进行算法时间复杂度计算......
  • 算法-15-归并排序
       ......
  • 【python_4】基础语法：字面量和注释！
    1.字面量的含义字面量：在代码中，被写下来的固定的值，称之为字面量。2.常见的字面量类型类型描述说明数字Number支持：整数int浮点数float复数complex布尔bool整数int，如10，-10浮点数float，如13.14，-13.14复数complex，如4+3j布尔bool，表达现实生活中的逻辑，即真和假，True表示真，False表示假。True......
  • C/C++ 数据结构五大核心算法之动态规划算法-给你一根长度为 n 的金条，请把金条剪成 m
    动态规划也是一种分治思想，但与分治算法不同的是，分治算法是把原问题分解为若干子问题，自顶向下，求解各子问题，合并子问题的解从而得到原问题的解。动态规划也是自顶向下把原问题分解为若干子问题，不同的是，然后自底向上，先求解最小的子问题，把结果存储在表格中，在求解大的子问题时，直接从表......
  • Qt+GDAL开发笔记（二）：在windows系统msvc207x64编译GDAL库、搭建开发环境和基础Demo
    前言  上一篇使用mingw32版本的gdal，过程曲折，为更好的更方便搭建环境，在windows上msvc方式对于库比较友好。<br>大地坐标简介概述  大地坐标（Geodeticcoordinate）是大地测量中以参考椭球面为基准面的坐标，地面点P的位置用大地经度L、大地纬度B和大地高H表示。原理  当点在......
  • JavaScript学习 -- RSA算法应用实例及公钥私钥的生成方法
    正文：RSA算法是一种非对称加密算法，用于加密、解密和数字签名等场景。本文将介绍如何在JavaScript中使用RSA算法，并提供一个实际的案例，同时也会说明如何生成公钥和私钥。首先，确保您已经引入了jsencrypt库。以下是一个使用RSA算法进行加密和解密的示例，同时也包含了公钥和私钥的生成方法......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99