算法（一）基础算法

基础算法
算法基础课
发布日期:   2023-03-28
更新日期:   2023-05-28
文章字数:   9.3k
阅读时长:   54 分
阅读次数:  

算法（一）基础算法

基础课

1、快速排序

分治

  1. 确定分界点
  2. 调整范围（重点）
  3. 递归处理左右两段

模板：

void quick_sort(int q[],int l,int r)
{
	if(l >= r) return;
	int x = q[l+r>>1] , i = l-1, j = r+1;
	while(i<j)
	{
		do i++ ; while(q[i]<x);
		do j-- ; while(q[j]>x);
		if(i<j) swap(q[i],q[j]);
	}
	quick_sort(q,l,j);
	quick_sort(q,j+1,r);
}
public static void quick_sort(int[] q,int l,int r) 
{
    if(l >= r) return ;
    int x = q[l+r>>1], i = l - 1, j = r + 1;
    while(i < j)
    {
        do i++ ; while(q[i] < x);
        do j-- ; while(q[j] > x);
        if(i<j){
            int temp = q[i];
            q[i] = q[j];
            q[j] = temp;
        } 
    }
    quick_sort(q,l,j);
    quick_sort(q,j+1,r);
}

原题链接：快速排序

#include<iostream>
using namespace std;

const int N = 1e6+10;

int n;
int q[N];

void quick_sort(int q[],int l,int r)
{
	if(l >= r) return;
	int x = q[l] , i = l-1, j = r+1;
	while(i<j)
	{
		do i++ ; while(q[i]<x);
		do j-- ; while(q[j]>x);
		if(i<j) swap(q[i],q[j]);
	}
	quick_sort(q,l,j);
	quick_sort(q,j+1,r);
}

int main()
{
	scanf("%d",&n);
	for(int i=0;i<n;i++) scanf("%d",&q[i]);
	quick_sort(q,0,n-1);
	for(int i=0;i<n;i++) printf("%d ",q[i]);
	return 0;
}
import java.util.*;
import java.io.*;

public class Main{
    public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    public static StreamTokenizer in = new StreamTokenizer(new InputStreamReader(System.in));
    public static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
    
    public static int nextInt() throws Exception{
        in.nextToken();
        return (int)in.nval;
    }
    
    public static double nextDouble() throws Exception{
        in.nextToken();
        return in.nval;
    }
    
    public static int N = 1000010;
    public static int n;
    public static int q[] = new int[N];
    
    public static void quick_sort(int[] q,int l,int r) 
    {
        if(l >= r) return ;
        int x = q[l+r>>1], i = l - 1, j = r + 1;
        while(i < j)
        {
            do i++ ; while(q[i] < x);
            do j-- ; while(q[j] > x);
            if(i<j){
                int temp = q[i];
                q[i] = q[j];
                q[j] = temp;
            } 
        }
        quick_sort(q,l,j);
        quick_sort(q,j+1,r);
    }
    
    public static void main(String[] args) throws Exception{
        n = nextInt();
        for(int i = 0 ; i < n ; i ++ )
        {
            q[i] = nextInt();
        }
        quick_sort(q,0,n-1);
        for(int i = 0 ; i < n ; i ++ )
        {
            out.print(q[i] + " ");
        }
        out.flush();
    }
}

2、归并排序

分治

  1. 确定分界点mid=(1+r)/2
  2. 递归排序左边和右边
  3. 归并-合二为一（重点）

算法的稳定性：若原序列中相同数值的数排序后前后位置不发生变化，则称算法是稳定的，反之则是不稳定的

快排不稳定，归排稳定

模板

void merge_sort(int q[n],int l,int r)
{
	if (l>=r )return;
	int mid= l+r >> 1; //(l+r)/2
	merge_sort(q,l,mid);merge_sort(q,mid+1,r);
	int k =0 ,i = l,j = mid +1;
	while(i<=mid && j<=r)
		if(q[i] <= q[j]) tmp[k++] = q[i++];
		else tmp[k++] = q[j++];
	while(i<=mid) tmp[k++] = q[i++];
	while(j<=r) tmp[k++] = q[j++];
	for(i = 1,j=0;i<=r;i++,j++) q[i] = tmp[j]; 
}
public static void merge_sort(int[] q,int l,int r){
    if(l >= r) return ;
    int mid = l + r >> 1;
    merge_sort(q,l,mid); merge_sort(q,mid+1,r);
    int k = 0, i = l, j = mid + 1;
    while(i <= mid && j <= r)
    {
        if(q[i] <= q[j]) temp[k++] = q[i++];
        else temp[k++] = q[j++];
    }
    while(i <= mid) temp[k++] = q[i++];
    while(j <= r) temp[k++] = q[j++];
    for(i = l,j = 0; i <= r;i ++ , j ++ ) q[i] = temp[j];
}

原题链接：归并排序

#include<iostream>

using namespace std;
const int N = 1000010;
int n;
int q[N],tmp[N];

void merge_sort(int q[n],int l,int r)
{
	if (l>=r )return;
	int mid= l+r >> 1; //(l+r)/2
	merge_sort(q,l,mid);merge_sort(q,mid+1,r);
	int k =0 ,i = l,j = mid +1;
	while(i<=mid && j<=r)
		if(q[i] <= q[j]) tmp[k++] = q[i++];
		else tmp[k++] = q[j++];
	while(i<=mid) tmp[k++] = q[i++];
	while(j<=r) tmp[k++] = q[j++];
	for(i = l,j=0;i<=r;i++,j++) q[i] = tmp[j]; 
}
	
int main()
{
	scanf("%d",&n);
	for (int i = 0;i<n;i++) scanf("%d",&q[i]);
	merge_sort(q,0,n-1);
	for (int i = 0;i<n;i++) printf("%d ",q[i]);
	return 0;
}
import java.io.*;
import java.util.*;

public class Main{
    public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    public static StreamTokenizer in = new StreamTokenizer(new InputStreamReader(System.in));
    public static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
    
    public static int nextInt() throws Exception{
        in.nextToken();
        return (int)in.nval;
    }
    
    public static double nextDouble() throws Exception{
        in.nextToken();
        return in.nval;
    }
    
    public static int N = 100010;
    public static int n;
    public static int q[] = new int[N];
    public static int temp[] = new int[N];
    
    public static void merge_sort(int[] q,int l,int r){
        if(l >= r) return ;
        int mid = l + r >> 1;
        merge_sort(q,l,mid); merge_sort(q,mid+1,r);
        int k = 0, i = l, j = mid + 1;
        while(i <= mid && j <= r)
        {
            if(q[i] <= q[j]) temp[k++] = q[i++];
            else temp[k++] = q[j++];
        }
        while(i <= mid) temp[k++] = q[i++];
        while(j <= r) temp[k++] = q[j++];
        for(i = l,j = 0; i <= r;i ++ , j ++ ) q[i] = temp[j];
    }
    
    public static void main(String[] args) throws Exception{
        n = nextInt();
        for(int i = 0 ; i < n ; i ++ ) q[i] = nextInt();
        merge_sort(q,0,n-1);
        for(int i = 0 ; i < n ; i ++ ) out.print(q[i] +" ");
        out.flush();
    }
}

3、二分

整数

  1. mid=(l+r+1)/2
  2. check(mid):true->[mid,r],l=mid;false->[l,mid-1],r=mid-1
  3. mid=(l+r)/2
  4. check(mid):true->[l,mid];false->[mid+1,r]

模板

bool check(int x) {/* ... */} // 检查x是否满足某种性质

// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用：
int bsearch_1(int l, int r)
{
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;    // check()判断mid是否满足性质
        else l = mid + 1;
    }
    return l;
}
// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用：
int bsearch_2(int l, int r)
{
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}

原题链接：数的范围

#include<iostream>

using namespace std;
const int N = 100010;
int n,m;
int q[N];
int mian()
{
    scanf("%d%d",&n,&m);
    for(int i =0;i<n;i++) scanf("%d",&q[i]);
    while(m--)
    {
        int x;
        scanf("%d",&x);
        
        int l =0,r=n-1;
        while(l<r)
        {
            int mid = l+r>>1;
            if(q[mid]>=x) r=mid;
            else l =mid+1;
        }
        if(q[l] != x) cout<<"-1 -1"<<endl;
        else{
            cout <<l<<' ';
            int l =0,r=n-1;
        	while(l<r)
        	{
            	int mid = l+r+1>>1;
            	if(q[mid]<=x) l=mid;
            	else r =mid-1;
        	}
            cout<<l<<endl
        }
    }
    return 0;
}
import java.io.*;
import java.util.*;

public class Main{
    public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    public static StreamTokenizer in = new StreamTokenizer(new InputStreamReader(System.in));
    public static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
    
    public static int nextInt() throws Exception{
        in.nextToken();
        return (int)in.nval;
    }
    
    public static int N = 100010;
    public static int n,m;
    public static int q[] = new int[N];
    public static void main(String[] args)throws Exception{
        n = nextInt();
        m = nextInt();
        for(int i = 0; i < n ; i ++ ) q[i] = nextInt();
        while(m>0)
        {
            int x;
            x = nextInt();
            int l = 0, r = n - 1;
            while(l < r)
            {
                int mid = l + r >> 1;
                if(q[mid] >= x) r = mid;
                else l = mid + 1;
            }
            if(q[l] != x) out.println("-1 -1");
            else {
                out.print(l + " ");
                l = 0;
                r = n - 1;
                while(l < r)
                {
                    int mid = l + r + 1 >> 1;
                    if(q[mid] <= x) l = mid;
                    else r = mid - 1;
                }
                out.println(l);
            }
            m--;
        }
        out.flush();
    }
}

浮点数二分算法

模板

bool check(double x) {/* ... */} // 检查x是否满足某种性质

double bsearch_3(double l, double r)
{
    const double eps = 1e-6;   // eps 表示精度，取决于题目对精度的要求
    while (r - l > eps)
    {
        double mid = (l + r) / 2;
        if (check(mid)) r = mid;
        else l = mid;
    }
    return l;
}

4、高精度运算

Java

Java中有两个类可以来处理高精度的计算，分别是处理整数的BigInteger和处理小数的BigDecimal

BigInteger

构造方法

BigInteger(byte[] val) 
将包含BigInteger的二进制补码二进制表达式的字节数组转换为BigInteger 
BigInteger(int numBits, Random rnd) 
构造一个随机生成的BigInteger，均匀分布在0到（2 numBits - 1）的范围内。  
BigInteger(String val) 
将BigInteger的十进制字符串表示形式转换为BigInteger。

加法add()

import java.math.BigInteger;
import java.io.*;

public class Main {

    public static void main(String[] args) throws IOException{
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        BigInteger a = new BigInteger(reader.readLine());
        BigInteger b = new BigInteger(reader.readLine());
        System.out.println(a.add(b));
        reader.close();
    }
}

减法substract()

import java.io.*;
import java.math.BigInteger;

public class Main {

    public static void main(String[] args) throws IOException{
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        BigInteger a = new BigInteger(reader.readLine());
        BigInteger b = new BigInteger(reader.readLine());
        System.out.println(a.subtract(b));
        reader.close();
    }
}

乘法multiply()

import java.io.*;
import java.math.BigInteger;

public class Main {

    public static void main(String[] args) throws IOException{
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        BigInteger a = new BigInteger(reader.readLine());
        BigInteger b = new BigInteger(reader.readLine());
        System.out.println(a.multiply(b));
        reader.close();
    }
}

除法divideAndRemainder()

import java.io.*;
import java.math.BigInteger;

public class Main {

    public static void main(String[] args) throws IOException{
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        BigInteger a = new BigInteger(reader.readLine());
        BigInteger b = new BigInteger(reader.readLine());
        //divide 返回值为 a/b
        BigInteger[] c = a.divideAndRemainder(b); //返回值为数组，分别为a/b和a%b
        System.out.println(c[0]);
        System.out.println(c[1]);
        reader.close();
    }
}

取余mod()

import java.io.*;
import java.math.BigInteger;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        BigInteger a = new BigInteger(reader.readLine());
        BigInteger b = new BigInteger(reader.readLine());
        System.out.println(a.mod(b));
        reader.close();
    }
}

BigDecimal处理浮点数运算
构造方法

BigDecimal(char[] in) 
一个转换的字符数组表示 BigDecimal成 BigDecimal ，接受字符作为的相同序列 BigDecimal(String)构造。  
BigDecimal(char[] in, int offset, int len) 
一个转换的字符数组表示 BigDecimal成 BigDecimal ，接受字符作为的相同序列 BigDecimal(String)构造，同时允许一个子阵列被指定。    
BigDecimal(double val) 
将 double转换为 BigDecimal ，这是 double的二进制浮点值的精确十进制表示 
BigDecimal(int val)
将 int成 BigDecimal
BigDecimal(long val) 
将 long成 BigDecimal
BigDecimal(String val)

加法add()

import java.io.*;
import java.math.BigDecimal;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        BigDecimal a = new BigDecimal(reader.readLine());
        BigDecimal b = new BigDecimal(reader.readLine());
        System.out.println(a.add(b));
        reader.close();
    }
}

取余remainder()

import java.io.*;
import java.math.BigDecimal;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        BigDecimal a = new BigDecimal(reader.readLine());
        BigDecimal b = new BigDecimal(reader.readLine());
        System.out.println(a.remainder(b));
        reader.close();
    }
}

除法divide()

import java.io.*;
import java.math.BigDecimal;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        BigDecimal a = new BigDecimal(reader.readLine());
        BigDecimal b = new BigDecimal(reader.readLine());
        System.out.println(a.divide(b));
        reader.close();
    }
}

高精度加法

  1. 大整数存储（数组0位存个位，依此类推）
  2. 代码模拟加法的过程

模板：

// C = A + B, A >= 0, B >= 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;
}

原题链接：高精度加法

#include<iostream>
#include<vector>
using namespace std
const int N=1e6+10;
vector<int> add(vector<int> &A,vector<int> &B)
{
    vector<int> C;
    int t = 0;
    for(int i=0;i<A.size()||i<B.size();i++)
    {
        if(i<A.size()) 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;
}
int main()
{
	string a,b;
	vector<int> A,B;
	
	cin>>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');
	auto C=add(A,b); //auto意思是编译器自动推断返回值是什么类型
	for(int i=C.size()-1;i>=0;i--) printf("%d",C[i]);
	return 0;
}

高精度减法

模板：

bool cmp(vector<int> &A,vector<int> &B)
{
    if(A.size() != B.size()) return A.size() > B.size();
    for(int i = A.size() - 1; i >= 0 ; i -- ){
        if(A[i] != B[i]){
            return A[i] > B[i];
        }
    }
    return true;
}
vector<int> sub(vector<int> &A,vector<int> &B)
{
    vector<int> C;
    int t = 0;
    for(int i = 0 ; i < A.size() ; i ++ )
    {
        t = A[i] - t;
        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;
}

原题链接：高精度减法

#include<iostream>
#include<vector>
using namespace std;
bool cmp(vector<int> &A,vector<int> &B)
{
    if(A.size()!=B.size()) return A.size() > B.size();
    for(int i = A.size() - 1 ; i >= 0  ; i -- ) {
        if(A[i]!=B[i]) return A[i] > B[i];
    }
    return true;
}
vector<int> sub(vector<int> &A,vector<int> &B)
{
    vector<int> C;
    int t = 0;
    for(int i = 0 ; i < A.size() ; i ++ ){
        t = A[i] - t;
        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;
}
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');
    vector<int> C;
    if(cmp(A,B)) {
        C = sub(A,B);
        for(int i = C.size() - 1 ; i >= 0 ; i -- ) printf("%d",C[i]);
    }else {
        C = sub(B,A);
        printf("-");
        for(int i = C.size() - 1 ; i >= 0 ; i -- ) printf("%d",C[i]);
    }
    return 0;
}

高精度乘低精度

// C = A * b, A >= 0, b >= 0
vector<int> mul(vector<int> &A, int b)
{
    vector<int> C;

    int t = 0;
    for (int i = 0; i < A.size() || t; i ++ )
    {
        if (i < A.size()) t += A[i] * b;
        C.push_back(t % 10);
        t /= 10;
    }

    while (C.size() > 1 && C.back() == 0) C.pop_back();

    return C;
}

原题链接：高精度乘法

#include<iostream>
#include<vector>
using namespace std;
vector<int> mul(vector<int>&A,int b)
{
    vector<int> C;
    int t = 0;
    for(int i = 0 ; i < A.size() || t ; i ++ )
    {
        if(i < A.size()) t += A[i] * b;
        C.push_back(t%10);
        t/=10;
    }
    while(C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}
int main()
{
    string a;
    int b;
    cin >> a ;
    cin >> b ;
    vector<int> A;
    for(int i = a.size() - 1 ; i >= 0 ; i -- ) A.push_back(a[i]-'0');
    vector<int> C;
    C = mul(A,b);
    for(int i = C.size() - 1 ; i >= 0 ; i -- ) printf("%d",C[i]);
    return 0;
}

高精度除以低精度

// A / b = C ... r, A >= 0, b > 0
vector<int> div(vector<int> &A, int b, int &r)
{
    vector<int> C;
    r = 0;
    for (int i = A.size() - 1; i >= 0; i -- )
    {
        r = r * 10 + A[i];
        C.push_back(r / b);//push_back即在数组后添加某数
        r %= b;
    }
    reverse(C.begin(), C.end());
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

原题链接：高精度除法

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
vector<int> div(vector<int>& A,int b ,int& r)
{
    vector<int> C;
    r = 0;
    for(int i = A.size()- 1 ; i >= 0 ; i -- )
    {
        r = r * 10 + A[i];
        C.push_back(r/b);
        r %= b;
    }
    reverse(C.begin(),C.end());
    while(C.size()> 1 && C.back() == 0) C.pop_back();
    return C;
}
int main()
{
    string a;
    int b;
    cin >> a ;
    cin >> b ;
    vector<int> A;
    for(int i = a.size() - 1 ; i >= 0 ; i -- ) A.push_back(a[i]-'0');
    vector<int> C;
    int r;
    C = div(A,b,r);
    for(int i = C.size() - 1 ; i >= 0 ; i -- ) printf("%d",C[i]);
    printf("\n%d",r);
    return 0;
}

5、前缀和与差分

一维前缀和

原数组：a1,a2,a3,a4….an

前缀和：Si=a1+a2+…ai

  1. 如何求Si：S[i]=S[i-1]+a[i]
  2. 作用：快速求出原数组中的一段数的和 al+…+ar=S[r]-S[l-1]

模板：

S[i] = a[1] + a[2] + ... a[i]
a[l] + ... + a[r] = S[r] - S[l - 1]

原题链接：前缀和

#include<iostream>
using namespace std;
const int N = 100010;
int n,m;
int a[N],s[N];
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)s[i]=s[i-1]+a[i];
    while(m--)
    {
        int l,r;
        scanf("%d%d",&l,&r);
        printf("%d\n",s[r]-s[l - 1]);
    }  
    return 0;
}
import java.io.*;
import java.util.*;

public class Main{
    public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    public static StreamTokenizer in = new StreamTokenizer(new InputStreamReader(System.in));
    public static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
    
    public static int nextInt() throws Exception{
        in.nextToken();
        return (int)in.nval;
    }
    public static int N = 100010;
    public static int n,m;
    public static int a[] = new int[N];
    public static int s[] = new int[N];
    
    public static void main(String[] args)throws Exception{
        n=nextInt();
        m=nextInt();
        for(int i = 1 ;i <= n ; i ++ ) a[i] = nextInt();
        for(int i = 1 ;i <= n ; i ++ ) s[i] = s[i-1] + a[i];
        int l,r;
        for(int i = 0 ; i < m ; i ++ )
        {
            l = nextInt();
            r = nextInt();
            out.println(s[r] - s[l-1]);            
        }
        out.flush();
    }
}

二维前缀和

模板

S[i, j] = 第i行j列格子左上部分所有元素的和
以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵的和为：
S[x2, y2] - S[x1 - 1, y2] - S[x2, y1 - 1] + S[x1 - 1, y1 - 1]

初始化：s[i][j] = s[i][j-1] + s[i-1][j] - s[i-1][j-1] + q[i][j];
前缀和：s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[x1 - 1][y1 - 1]

原题链接：子矩阵的和

#include<iostream>
using namespace std;
const int N = 1010;
int n,m,k,q[N][N],s[N][N];
int main()
{
    scanf("%d%d%d",&n,&m,&k);
    for(int i = 1 ; i <= n ; i ++ )
        for(int j = 1 ; j <= m ; j ++ )
            scanf("%d",&q[i][j]);
            
    for(int i = 1 ; i <= n ; i ++ )
        for(int j = 1 ; j <= m ; j ++ )
            s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + q[i][j];
    while(k--)
    {
        int x1,y1,x2,y2;
        scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
        printf("%d\n",s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[x1-1][y1-1]);
    }
    return 0;
}
import java.io.*;
import java.util.*;

public class Main{
    public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    public static StreamTokenizer in = new StreamTokenizer(new InputStreamReader(System.in));
    public static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
    
    public static int nextInt() throws Exception{
        in.nextToken();
        return (int)in.nval;
    }
    
    public static int N = 1010;
    public static int n,m,q;
    public static int a[][] = new int[N][N];
    public static int s[][] = new int[N][N];
    
    public static void main(String[] args) throws Exception{
        n = nextInt();
        m = nextInt();
        q = nextInt();
        for(int i = 1 ; i <= n ; i ++ )
        {
            for(int j = 1 ; j <= m ; j ++ )
            {
                a[i][j] = nextInt();
            }
        }
        
        for(int i = 1 ; i <= n ; i ++ )
        {
            for(int j = 1 ; j <= m ; j ++ )
            {
                s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + a[i][j];
            }
        }
        
        while(q-- > 0)
        {
            int x1, y1, x2, y2;
            x1 = nextInt();
            y1 = nextInt();
            x2 = nextInt();
            y2 = nextInt();
            out.println(s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[x1-1][y1-1]);
        }
        
        out.flush();
    }
}

一维差分

原数组：a1,a2,a3,a4….an

构造b1,b2…bn

使得ai=b1+b2+…bi

即b1=a1;b2=a2-a1;b3=a3-a2

模板

给区间[l, r]中的每个数加上c：B[l] += c, B[r + 1] -= c

原题链接：差分

#include<iostream>
using namespace std;
const int N = 100010;
int n,m;
int a[N],b[N];
void insert(int l,int r,int c)
{
    b[l]+=c;
    b[r+1]-=c;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= n;i++) scanf("%d",&a[i]);
    for(int i = 1;i <= n;i++) insert(i, i, a[i]);
    while(m--)
    {
        int l,r,c;
        scanf("%d%d%d",&l,&r,&c);
        insert(l,r,c);
    }
    for(int i =1;i<=n;i++) b[i] += b[i-1];
    for(int i =1;i<=n;i++) printf("%d ",b[i]);
    return 0;
}
import java.io.*;
import java.util.*;

public class Main{
    public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    public static StreamTokenizer in = new StreamTokenizer(new InputStreamReader(System.in));
    public static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
    
    public static int nextInt() throws Exception{
        in.nextToken();
        return (int)in.nval;
    }
    public static int N = 100010;
    public static int n,m;
    public static int b[] = new int[N];
    public static int a[] = new int[N];
    public static void insert(int l,int r,int c){
        b[l] += c;
        b[r+1] -= c;
    }
    
    public static void main(String[] args)throws Exception{
        n = nextInt();
        m = nextInt();
        for(int i = 1 ; i <= n ; i ++ ) a[i] = nextInt();
        for(int i = 1 ; i <= n ; i ++ ) insert(i, i, a[i]);
        while(m-- > 0){
            int l, r , c;
            l = nextInt();
            r = nextInt();
            c = nextInt();
            insert(l,r,c);
        }
        for(int i = 1 ; i <= n ; i ++ ) b[i] += b[i-1];
        for(int i = 1 ; i <= n ; i ++ ) out.print(b[i] + " ");
        out.flush();
    }
}

二维差分

模板：

给以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵中的所有元素加上c：
S[x1, y1] += c, S[x2 + 1, y1] -= c, S[x1, y2 + 1] -= c, S[x2 + 1, y2 + 1] += c

原题链接：差分矩阵

#include<iostream>
using namespace std;
const int N = 1010;
int n,m,k,q[N][N],b[N][N];
void insert(int x1,int y1,int x2,int y2,int c)
{
    b[x1][y1] += c;
    b[x1][y2+1] -=c;
    b[x2+1][y1] -=c;
    b[x2+1][y2+1] += c;
    
}
int main()
{
    scanf("%d%d%d",&n,&m,&k);
    for(int i = 1 ; i <= n ; i++ ) 
        for(int j = 1 ; j <= m ; j ++ ) 
            scanf("%d",&q[i][j]);
            
    for(int i = 1 ; i <= n ; i ++ )
        for(int j = 1 ; j <= m ; j ++ )
            insert(i,j,i,j,q[i][j]);
    while(k--)
    {
        int x1,y1,x2,y2,c;
        scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&c);
        insert(x1,y1,x2,y2,c);
    }
    for(int i = 1 ; i <= n ; i ++ )
        for(int j = 1 ; j <= m ; j ++)
            q[i][j] = q[i-1][j] + q[i][j-1] - q[i-1][j-1] + b[i][j] ;
    for(int i = 1 ; i <= n ; i ++ )
    {
        for(int j = 1 ; j <= m ; j ++ )
            printf("%d ",q[i][j]);
        puts("");
    }
    return 0;
}
import java.io.*;
import java.util.*;

public class Main{
    public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    public static StreamTokenizer in = new StreamTokenizer(new InputStreamReader(System.in));
    public static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        public static int nextInt() throws Exception{
        in.nextToken();
        return (int)in.nval;
    }
    
    public static int N = 1010;
    public static int n,m,q;
    public static int b[][] = new int[N][N];
    public static int a[][] = new int[N][N];
    
    public static void insert(int x1,int y1,int x2,int y2,int c){
        b[x1][y1] += c;
        b[x1][y2+1] -= c;
        b[x2+1][y1] -= c;
        b[x2+1][y2+1] += c;
    }
    
    public static void main(String[] args) throws Exception{
        n = nextInt();
        m = nextInt();
        q = nextInt();
        for(int i = 1 ; i <= n ; i ++ )
        {
            for(int j = 1 ; j <= m ; j ++ )
            {
                a[i][j] = nextInt();
            }
        }
        
        for(int i = 1 ; i <= n ; i ++ )
        {
            for(int j = 1 ; j <= m ; j ++ )
            {
                insert(i,j,i,j,a[i][j]);
            }
        }
        
        while(q-- > 0)
        {
            int x1,y1,x2,y2,c;
            x1 = nextInt();
            y1 = nextInt();
            x2 = nextInt();
            y2 = nextInt();
            c = nextInt();
            insert(x1, y1, x2, y2, c);
        }
        
        for(int i = 1 ; i <= n ; i ++ )
        {
            for(int j = 1 ; j <= m ; j ++ )
            {
                a[i][j] = a[i-1][j] + a[i][j-1] - a[i-1][j-1] + b[i][j];
            }
        }
        
        for(int i = 1 ; i <= n ; i ++ )
        {
            for(int j = 1 ; j <= m ; j ++ )
            {
                out.print(a[i][j] + " ");
            }
            out.println();
        }
        
        out.flush();
    }
}

6、位运算

n的二进制表示中第k位是几

  1. 先把第k位移到最后一位 n>>k
  2. 看个位是几

模板：

求n的第k位数字: n >> k & 1 //&1的意思是&000...01
返回n的最后一位1：lowbit(n) = n & -n
//即若n=1010则lowbit(n)=10
//在c++里，-n为n的补码操作

原题链接：二进制中1的个数

#include<iostream>
using namespace std;
int lowbit(int x)
{
    return x & -x;
}
int main()
{
    int n;
    cin >> n;
    while(n -- ){
        int x;
        cin >> x;
        int res = 0;
        while(x) x-=lowbit(x),res++; //每次减去x的最后一位1
        cout<<res<<' ';
        
    }
    return 0;
}
import java.io.*;
import java.util.*;

public class Main{
    public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    public static StreamTokenizer in = new StreamTokenizer(new InputStreamReader(System.in));
    public static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        public static int nextInt() throws Exception{
        in.nextToken();
        return (int)in.nval;
    }
    
    public static int lowbit(int x){
        return x & -x;
    }
    
    public static int n;
    public static void main(String[] args)throws Exception{
        n = nextInt();
        while(n-- > 0){
            int x;
            x = nextInt();
            int res = 0;
            while(x > 0){
                x -= lowbit(x);
                res ++ ;
            } 
            out.print(res + " ");
        }
        out.flush();
    }
}

7、双指针算法

模板

for (int i = 0, j = 0; i < n; i ++ )
{
    while (j < i && check(i, j)) j ++ ;

    // 具体问题的逻辑
}
常见问题分类：
    (1) 对于一个序列，用两个指针维护一段区间
    (2) 对于两个序列，维护某种次序，比如归并排序中合并两个有序序列的操作

原题链接：最长连续不重复子序列

#include<iostream>

using namespace std;

const int N = 100010;
int a[N] , s[N] , n;

int main()
{
    cin >> n;
    for(int i = 0 ; i < n ; i ++ ) cin >> a[i];
    int res = 0;
    for(int i = 0 , j = 0 ; i < n ; i ++ )
    {
        s[a[i]] ++ ;
        while(s[a[i]] > 1)
        {
            s[a[j]] -- ;
            j ++;
        }
        res = max(res, i - j + 1);
    }
    cout << res << endl;
    return 0;
}
import java.io.*;
import java.util.*;

public class Main{
    public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    public static StreamTokenizer in = new StreamTokenizer(new InputStreamReader(System.in));
    public static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        public static int nextInt() throws Exception{
        in.nextToken();
        return (int)in.nval;
    }
    
    public static int N = 100010;
    public static int n;
    public static int a[] = new int[N];
    public static int s[] = new int[N];
    
    public static void main(String[] args)throws Exception{
        n = nextInt();
        for(int i = 0 ; i < n ; i ++ ) a[i] = nextInt();
        int res = 0 ;
        for(int l = 0, r = 0; r < n; r ++ ){
            s[a[r]] ++;
            while(s[a[r]] > 1)
            {
                s[a[l]] -- ;
                l ++ ;
            }
            res = Math.max(res, r - l + 1);
        }
        
        out.print(res);
        out.flush();
    }
}

原题链接：数组元素的目标和

#include<iostream>
using namespace std;
const int N = 100010;
int n,m,x;
int a[N],b[N];

int main()
{
    cin >> n >> m >> x;
    for(int i = 0 ;i < n ; i ++ ) cin >> a[i];
    for(int i = 0 ;i < m ; i ++ ) cin >> b[i];
    
    for(int i = 0 , j = m - 1 ; i < n ; i ++ ){
        while(j >= 0 && a[i] + b[j] > x) j -- ;
        if(j >= 0 && a[i] + b[j] == x) cout << i << ' ' << j << endl;
    }
    return 0;
}
import java.io.*;
import java.util.*;

public class Main{
    public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    public static StreamTokenizer in = new StreamTokenizer(new InputStreamReader(System.in));
    public static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        public static int nextInt() throws Exception{
        in.nextToken();
        return (int)in.nval;
    }
    
    public static int N = 100010;
    public static int n,m,x;
    public static int a[] = new int[N];
    public static int b[] = new int[N];
    
    public static void main(String[] args)throws Exception{
        n = nextInt();
        m = nextInt();
        x = nextInt();
        for(int i = 0 ; i < n ; i ++ ) a[i] = nextInt();
        for(int i = 0 ; i < m ; i ++ ) b[i] = nextInt();
        
        //和暴力算法的区别在于：j不会回退
        for(int i = 0 , j = m - 1; i < n ; i ++ ){
            while(j >= 0 && a[i] + b[j] > x) j -- ;
            if(j >= 0 && a[i] + b[j] == x) out.print(i + " " + j);
        }
        
        out.flush();
    }
}

原题链接：判断子序列

#include<iostream>
using namespace std;
const int N = 100010;
int n,m;
int a[N],b[N];

int main()
{
    cin >> n >> m;
    for(int i = 0 ; i < n ; i ++ ) cin >> a[i];
    for(int i = 0 ; i < m ; i ++ ) cin >> b[i];
    
    int i = 0;
    for(int j = 0 ; j < m ; j ++ )
    {
        if(i < n && a[i] == b[j]) i ++ ;
    }
    
    if(i == n) cout << "Yes" << endl;
    else cout << "No" << endl;
}
import java.io.*;
import java.util.*;

public class Main{
    public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    public static StreamTokenizer in = new StreamTokenizer(new InputStreamReader(System.in));
    public static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        public static int nextInt() throws Exception{
        in.nextToken();
        return (int)in.nval;
    }
    
    public static int N = 100010;
    public static int n,m,x;
    public static int a[] = new int[N];
    public static int b[] = new int[N];
    
    public static void main(String[] args)throws Exception{
        n = nextInt();
        m = nextInt();
        for(int i = 0 ; i < n ; i ++ ) a[i] = nextInt();
        for(int i = 0 ; i < m ; i ++ ) b[i] = nextInt();
        
        int i = 0;
        for(int j = 0; j < m ; j ++ ){
            if(i < n && a[i] == b[j]) i ++ ;
        }
        
        if(i == n) out.print("Yes");
        else out.print("No");
        
        out.flush();
    }
}

8、离散化

模板

//将一个值域特别大的数组有序的映射到一个值域较小的数组
vector<int> alls; // 存储所有待离散化的值
sort(alls.begin(), alls.end()); // 将所有值排序
alls.erase(unique(alls.begin(), alls.end()), alls.end());   // 去掉重复元素

// 二分求出x对应的离散化的值
int find(int x) // 找到第一个大于等于x的位置
{
    int l = 0, r = alls.size() - 1;
    while (l < r)
    {
        int mid = l + r >> 1;
        if (alls[mid] >= x) r = mid;
        else l = mid + 1;
    }
    return r + 1; // 映射到1, 2, ...n
}

public static ArrayList<Pairs> add = new ArrayList<>(); //n次操作
public static ArrayList<Pairs> query = new ArrayList<>(); //m次询问
public static ArrayList<Integer> alls = new ArrayList<>(); //存储待离散化的值
public static int unique(ArrayList<Integer> list) {
    int j = 0;
    for (int i = 0; i < list.size(); i++) {
        if (i == 0 || list.get(i) != list.get(i - 1)) {
            list.set(j, list.get(i));
            j++;
        }  
    }
    return j;		
}
// 二分求出x对应的离散化的值
public static int find(int x, List<Integer> list) {// 找到第一个大于等于x的位置
    int l = 0;
    int r = list.size() - 1;
    while (l < r) {
        int mid = l + r >> 1;
        if (list.get(mid) >= x) r = mid;
        else l = mid + 1;
    }
    return l + 1; //因为要考虑到前缀和，映射到1, 2, ...n
}
class Pairs {
    int first;
    int second;
    public Pairs(int first, int second) {
        this.first = first;
        this.second = second;
    }
}

原题链接：区间和

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
const int N = 300010 ;
int n, m;
vector<PII> add, query;
vector<int> alls; //存储所有待离散化的值
int a[N], s[N];
//二分查找,目的就是取出x的坐标
int find(int x)
{
    int l = 0 , r = alls.size() - 1;
    while(l<r)
    {
        int mid = l + r >> 1;
        if(alls[mid] >= x) r = mid;
        else l = mid + 1;
    }
    return r + 1; //+1是因为前缀和是从1开始求的
}

int main()
{
    cin >> n  >> m;
    for(int i = 0 ; i < n ; i ++ )
    {
        int x , c;
        cin >> x >> c;
        add.push_back({x,c});
        alls.push_back(x);
    }
    for(int i = 0 ; i < m ; i ++ )
    {
        int l , r ;
        cin >> l >> r;
        query.push_back({l,r});
        alls.push_back(l);
        alls.push_back(r);
    }
    sort(alls.begin(),alls.end());
    alls.erase(unique(alls.begin(),alls.end()),alls.end()); //去掉重复元素
    
    for(auto it : add)
    {
        int x = find(it.first);
        a[x] += it.second;
    }
    
    for(int i = 1 ; i <= alls.size() ; i ++ ) s[i] = s[i-1] + a[i];
    for(auto it : query)
    {
        int l = find(it.first) , r = find(it.second);
        cout << s[r] - s[l-1] << endl;
    }
    
}
import java.io.*;
import java.util.*;

public class Main {
	public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	public static StreamTokenizer in = new StreamTokenizer(new InputStreamReader(System.in));
	public static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));

	public static int nextInt() throws Exception {
		in.nextToken();
		return (int) in.nval;
	}

	public static int N = 300010;
	public static int n,m ;
	public static ArrayList<Pairs> add = new ArrayList<>(); //n次操作
	public static ArrayList<Pairs> query = new ArrayList<>(); //m次询问
	public static ArrayList<Integer> alls = new ArrayList<>(); //存储待离散化的值
	public static int a[] = new int[N];
	public static int s[] = new int[N];
	public static int unique(ArrayList<Integer> list) {
        int j = 0;
        for (int i = 0; i < list.size(); i++) {
            if (i == 0 || list.get(i) != list.get(i - 1)) {
                list.set(j, list.get(i));
                j++;
            }  
        }
        return j;		
	}
    public static int find(int x, List<Integer> list) {
        int l = 0;
        int r = list.size() - 1;
        while (l < r) {
            int mid = l + r >> 1;
            if (list.get(mid) >= x) r = mid;
            else l = mid + 1;
        }
        return l + 1; //因为要考虑到前缀和
    }
	
	public static void main(String[] args) throws Exception {

		int n = nextInt(), m = nextInt();
		for (int i = 0; i < n; i++) {
			int x = nextInt(), c = nextInt();
			add.add(new Pairs(x,c));
			alls.add(x);
		}
		
		for(int i = 0; i < m; i ++ ) {
			int l = nextInt(), r = nextInt();
			query.add(new Pairs(l, r));
			alls.add(l);
			alls.add(r);
		}
		
		Collections.sort(alls);
		int unique = unique(alls);
		List<Integer> subList = alls.subList(0, unique); //将去重后的List保存下来
        for (Pairs item:add) {
            int index = find(item.first, subList);
            a[index] += item.second;
        }

        //求前缀和
        for (int i = 1; i <= subList.size(); i++) s[i] = s[i - 1] + a[i];

        for (Pairs item:query) {
            int l = find(item.first, subList);
            int r = find(item.second, subList);
            System.out.println(s[r] - s[l - 1]);
        }
        
		out.flush();
	}
}

class Pairs {
    int first;
    int second;
    public Pairs(int first, int second) {
        this.first = first;
        this.second = second;
    }
}

9、区间合并

  1. 按区间左端点排序
  2. 扫描整个区间，过程中将所可能合并的区间合并

模板

// 将所有存在交集的区间合并
void merge(vector<PII> &segs)
{
    vector<PII> res;

    sort(segs.begin(), segs.end());

    int st = -2e9, ed = -2e9;
    for (auto seg : segs)
        if (ed < seg.first)
        {
            if (st != -2e9) res.push_back({st, ed});
            st = seg.first, ed = seg.second;
        }
        else ed = max(ed, seg.second);

    if (st != -2e9) res.push_back({st, ed});

    segs = res;
}
public static ArrayList<Pairs> segs = new ArrayList<>(); 

public static ArrayList<Pairs> merge(ArrayList<Pairs> segs){
    ArrayList<Pairs> res = new ArrayList<>();

    Collections.sort(segs);
    int st = Integer.MIN_VALUE, ed = Integer.MIN_VALUE;
    for(Pairs seg: segs) {
        if(ed < seg.first) {
            if(st != Integer.MIN_VALUE) res.add(new Pairs(st, ed));
            st = seg.first;
            ed = seg.second;
        }
        else ed = Math.max(ed, seg.second);
    }
    if(st != Integer.MIN_VALUE) res.add(new Pairs(st, ed));
    return res;
}
class Pairs implements Comparable<Pairs>{
    int first;
    int second;
    public Pairs(int first, int second) {
        this.first = first;
        this.second = second;
    }
    
    @Override
    public int compareTo(Pairs p) {
    	if(this.first != p.first) {
    		return this.first - p.first;
    	}else {
    		return this.second - p.second;
    	}
    }
}

原题链接：区间合并

#include<iostream>
#include<algorithm>
#include<vector>

using namespce std;
typedef pair<int,int> PII;
const int N=100010;
int n;
vector<PII> segs;

void merge(vector<PII> &segs)
{
    vector<PII> res;
    
    sort(segs.begin(),segs.end()); //按左端点排序
    
    int st = -2e9,ed= -2e9; //预先设定边界值，即负无穷
    for(auto seg :segs)
        if(ed < seg.first) //若区间没有交叉，则跳转到下一个区间
        {
            if (st != -2e9) res.push_back({st,ed});
            st = seg.first,ed = seg.second;
        }
    	else ed = max(ed, seg.second); //若有交叉则更新右边界
    if(st!= -2e9) res.push_back({st,ed}); //将最后一个区间添加到结果中，判断条件是防止输入区为空
    segs = res;
}

int main()
{
    cin >> n;
    for(int i=0;i<n;i++)
    {
        int l,r;
        cin >> l >> r;
        segs.push_back({l,r});
    }
    merge(segs);
    cout << segs.size() << endl;
    return 0;
}
import java.io.*;
import java.util.*;

public class Main {
	public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	public static StreamTokenizer in = new StreamTokenizer(new InputStreamReader(System.in));
	public static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));

	public static int nextInt() throws Exception {
		in.nextToken();
		return (int) in.nval;
	}

	public static int N = 100010;
	public static int n;
	public static ArrayList<Pairs> segs = new ArrayList<>(); //n次操作

    public static ArrayList<Pairs> merge(ArrayList<Pairs> segs){
        ArrayList<Pairs> res = new ArrayList<>();
        
        Collections.sort(segs);
        int st = Integer.MIN_VALUE, ed = Integer.MIN_VALUE;
        for(Pairs seg: segs) {
        	if(ed < seg.first) {
        		if(st != Integer.MIN_VALUE) res.add(new Pairs(st, ed));
        		st = seg.first;
        		ed = seg.second;
        	}
        	else ed = Math.max(ed, seg.second);
        }
        if(st != Integer.MIN_VALUE) res.add(new Pairs(st, ed));
        return res;
    }
    
	public static void main(String[] args) throws Exception {

		int n = nextInt();
		for (int i = 0; i < n; i++) {
			int l = nextInt(), r = nextInt();
			segs.add(new Pairs(l,r));
		}
		ArrayList<Pairs> res = merge(segs);
        out.print(res.size());
		out.flush();
	}
}

class Pairs implements Comparable<Pairs>{
    int first;
    int second;
    public Pairs(int first, int second) {
        this.first = first;
        this.second = second;
    }
    
    @Override
    public int compareTo(Pairs p) {
    	if(this.first != p.first) {
    		return this.first - p.first;
    	}else {
    		return this.second - p.second;
    	}
    }
}

提高课

前缀和与差分

激光炸弹

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;
const int N = 5010;

int s[N][N];

int main()
{
    int n, R;
    cin >> n >> R;
    R = min(R, 5001);
    for(int i = 0 ; i < n ; i ++ ){
        int x, y, w;
        cin >> x >> y >> w;
        x ++, y ++ ;
        s[x][y] += w;
    }
    
    for(int i = 1 ; i <= 5001 ; i ++ ){
        for(int j = 1 ; j <= 5001 ; j ++ ){
            s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
        }
    }
    int res = 0;
    for(int i = R ; i <= 5001 ; i ++ ){
        for(int j = R ; j <= 5001 ; j ++ ){
            res = max(res, s[i][j] - s[i - R][j] - s[i][j - R] + s[i - R][j - R]);
        }
    }
    cout << res << endl;
    return 0;
}

增减序列

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;
typedef long long ll;
const int N = 100010;

int n;
ll a[N], b[N];

int main()
{
    cin >> n ;
    for(int i = 1 ; i <= n ; i ++ ) cin >> a[i];
    for(int i = 1 ; i <= n ; i ++ ) b[i] = a[i] - a[i - 1];
    
    ll p = 0 , q = 0;
    for(int i = 2 ; i <= n ; i ++ ) 
    {
        if(b[i] > 0 ) p += b[i];
        else q -= b[i];
    }
    
    cout << max(p, q) << endl;
    cout << abs(p - q) + 1 << endl;
    return 0;
}

最佳牛围栏

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;
const int N = 100010;

int n, F;
double a[N], s[N];

bool check(double avg)
{
    for(int i = 1; i <= n ; i ++ ) s[i] = s[i - 1] + a[i] - avg;
    
    double mins = 0 ;
    for(int k = F ; k <= n ; k ++ ){
        mins = min(mins, s[k - F]);
        if(s[k] >= mins) return true;
    }
    
    return false;
}

int main()
{
    cin >> n >> F;
    double l = 0 , r = 0 ;
    for(int i = 1 ; i < n ; i ++ ){
        cin >> a[i];
        r = max(r, a[i]);
    } 
    
    while(r - l > 1e-5){
        double mid = (l + r) / 2;
        if(check(mid)) l = mid;
        else r = mid;
    }
    
    cout << (int)(r * 1000) << endl;
    return 0;
    
}

特殊排序

// 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> res ;
        res.push_back(1);
        for(int i = 2; i <= N ; i ++)
        {
            int l = 0, r = res.size() - 1;
            while(l < r)
            {
                int mid = l + r + 1>> 1;
                if(compare(res[mid], i)) l = mid;
                else r = mid - 1;
            }
            
            res.push_back(i);
            for(int j = res.size() - 2; j > r ; j -- ) swap(res[j], res[j + 1]);
            if(compare(i, res[r])) swap(res[r], res[r + 1]);
        }
        
        return res;
    }
};
文章作者: wck
文章链接: http://example.com/2023/03289396.html
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 wck !
基础算法
赏
评论
  目录