平均分组

输出n个数,以回车结束输入,把这些数分成两组,使得两组的差值c(c>=0)最小,输出这个差值

输入示例1

3 2 6

输出示例1

1

输入示例2

4 6 7 9

输出示例2

0

思路:前缀和

设第一组的数之和为x,第二组数之和为y,所有数之和为sum

则有 x+y=sum

设c为最小的差值,则c=|x-y|,设x>=y,则c=x-y

则联立两个式子可得 c=sum-2*y

则通过前缀和遍历获取y的值,并求出最小值

前缀和:

设数组sum是数组a的前缀和,即sum[i]为a[0]加到a[i-1]的和,且sum[0]=0,sum和a的下标都从1开始。

则有a[l]+…+a[r]=sum[r]-sum[l-1];

#include<iostream>
#include<numeric>
#include<sstream>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
    ////读入数据流中的数字
    vector<int> vec(1);
    string a;
    getline(cin, a);
    istringstream i(a);
    string s;
    while (i >> s)
    {
        vec.push_back(stoi(s));
    }
	//////

    int sum = accumulate(vec.begin(), vec.end(), 0);	
    int minv = INT_MAX, n = 0;

    vector<int> sumvec(vec.size() + 1);
    ///////////构造前缀和
    int d = 0;
    sumvec[0] = 0;
    for (int i = 1; i < vec.size(); i++)
    {
        d += vec[i];
        sumvec[i] = d;
    }
	/////////////////
    
    ///////////////遍历前缀和获取最小差值   
    for (int i = 0; i < sumvec.size(); i++)
    {
        for (int j = 1; j < sumvec.size(); j++)
        {
            for (int k = 0; k < j; k++)
            {
                int x = sumvec[j] - sumvec[k];
                minv = min(minv, abs(sum - 2 * x));
            }
        }
    }
    cout << minv;
}

spfa算法

适用范围:存在负权边求最短路

给定一个 n 个点 m 条边的有向图,图中可能存在重边和自环, 边权可能为负数。

请你求出 1 号点到 n 号点的最短距离,如果无法从 1 号点走到 n 号点,则输出 impossible。

数据保证不存在负权回路。

输入格式
第一行包含整数 n 和 m。

接下来 m 行每行包含三个整数 x,y,z,表示存在一条从点 x 到点 y 的有向边,边长为 z。

输出格式
输出一个整数,表示 1 号点到 n 号点的最短距离。

如果路径不存在,则输出 impossible。

数据范围
1≤n,m≤10^5,
图中涉及边长绝对值均不超过 10000。

输入样例:
3 3
1 2 5
2 3 -3
1 3 4
输出样例:
2

邻接矩阵

#include <iostream>
#include <cstring>
#include <algorithm>
#include<queue>
using namespace std;

const int N = 1e4;
int a[N][N], d[N];
int n, m;
bool v[N];
queue<int> q;

int spfa()
{
    memset(d, 0x3f3f3f3f, sizeof(d));
    d[1] = 0;
    q.push(1);
    while (!q.empty())
    {
        int t = q.front();
        q.pop();
        for (int i = 1; i <= n; i++)
            if (a[t][i] && d[i] > d[t] + a[t][i])
            {
                d[i] = d[t] + a[t][i];
                q.push(i);
            }
    }
    if (d[n] == 0x3f3f3f3f) return -1;
    return d[n];
}

int main()
{
    cin >> n >> m;
    while (m--)
    {
        int x, y, z;
        cin >> x >> y >> z;
        a[x][y] = z;
    }

    if (spfa() == -1) cout << "impossible" << endl;
    else cout << spfa() << endl;
}

邻接表

#include <iostream>
#include <cstring>
#include <algorithm>
#include<queue>
using namespace std;

const int N = 100100,M=100100;
int  d[N];
int n, m;
bool v[N];
queue<int> q;
int head[N],to[M],w[M],nxt[M],idx=0;  //head大小为点数,其他的大小为边数

void add(int a,int b,int c)
{
    to[idx]=b;
    w[idx]=c;
    nxt[idx]=head[a];
    head[a]=idx++;
}

int spfa()	
{
    memset(d, 0x3f, sizeof(d));
    d[1] = 0;
    q.push(1);
    v[1]=true;
    while (!q.empty())
    {
        int t = q.front();
        q.pop();
        v[t]=false;
        for(int i=head[t];i!=-1;i=nxt[i])
        {
            int j=to[i];
            if(d[j]>d[t]+w[i])
            {
                d[j]=d[t]+w[i];
                if(!v[j])
                {
                    q.push(j);
                    v[j]=true;
                }
            }
        }
    }
    if (d[n] > 0x3f3f3f3f/2) return -1;
    return d[n];
}

int main()
{
    cin >> n >> m;
    
    memset(head,-1,sizeof(head));
    
    while (m -- )
    {
        int x,y,z;
        cin>>x>>y>>z;
        add(x,y,z);
    }

    if (spfa() == -1) cout << "impossible" << endl;
    else cout << spfa() << endl;
}
  • spfa函数无参数是默认d[i]表示点i到点1的最短距离
  • spfa(int a) 有参数是,d[i]表示点i到点a的最短距离

Floyd算法

适用条件:求多源最短路,即求任意两个点之间的最短路问题


给定一个 n 个点 m 条边的有向图,图中可能存在重边和自环,边权可能为负数。

再给定 k 个询问,每个询问包含两个整数 x 和 y,表示查询从点 x 到点 y 的最短距离,如果路径不存在,则输出 impossible。

数据保证图中不存在负权回路。

输入格式
第一行包含三个整数 n,m,k。

接下来 m 行,每行包含三个整数 x,y,z,表示存在一条从点 x 到点 y 的有向边,边长为 z。

接下来 k 行,每行包含两个整数 x,y,表示询问点 x 到点 y 的最短距离。

输出格式
共 k 行,每行输出一个整数,表示询问的结果,若询问两点间不存在路径,则输出 impossible。

数据范围
1≤n≤200,
1≤k≤n2
1≤m≤20000,
图中涉及边长绝对值均不超过 10000。

输入样例:
3 3 2
1 2 1
2 3 2
1 3 1
2 1
1 3
输出样例:
impossible
1

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

const int N = 300;
int a[N][N];
int n,m,k;

int floyd()
{
    for(int k=1;k<=n;k++)
    {
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                a[i][j]=min(a[i][j],a[i][k]+a[k][j]);
            }
        }
    }
}

int main()
{
    cin>>n>>m>>k;
    
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(i==j) a[i][j]=0;
            else a[i][j]=0x3f3f3f3f;
        }
    }
    
    while (m -- )
    {
        int x,y,z;
        cin>>x>>y>>z;
        a[x][y]=min(a[x][y],z);
    }
    
    floyd();
    
    while(k--)
    {
        int x,y;
        cin>>x>>y;
        if(a[x][y]>0x3f3f3f3f/2) cout<<"impossible"<<endl;
        else cout<<a[x][y]<<endl;
    }
}

300. 最长递增子序列

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        vector<int> vec(nums.size()+1);
        vec[1]=nums[0];
        int len=1;
        for(int i=1;i<nums.size();i++)
        {
            if(nums[i]>vec[len])
            {
                vec[++len]=nums[i];
            }
            else
            {
                int l=1,r=len,p=0;
                while(l<=r)
                {
                    int mid=l+((r-l)>>1);
                    if(vec[mid]<nums[i])
                    {
                        l=mid+1;
                        p=mid;
                    }
                    else
                    {
                        r=mid-1;
                    }
                }
                vec[p+1]=nums[i];
            }
        }
        return len;
    }
};
  • 贪心+二分
  • vec[len]表示长度为len的序列的最小值
  • 如果nums[i]大于vec[len],则添加到vec中,否则在vec中二分查找第一个比nums[i]小的数,把nums[i]添加到他的后面

151. 颠倒字符串中的单词

class Solution {
public:
    string reverseWords(string s) {
        istringstream i(s);
        string t;
        string ans,a;
        while(i>>t)
        {
            t+=" ";
            a=t;
            a+=ans;
            ans=a;
        }       
        return ans.substr(0,ans.size()-1);
    }
};

##1143. 最长公共子序列

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        vector<vector<int>> dp(text1.size()+1,vector<int>(text2.size()+1));
        for(int i=1;i<=text1.size();i++)
        {
            for(int j=1;j<=text2.size();j++)
            {
                if(text1[i-1]==text2[j-1])
                {
                    dp[i][j]=dp[i-1][j-1]+1;
                }
                else
                {
                    dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
                }
            }
        }
        return dp[text1.size()][text2.size()]
    }
};

93. 复原 IP 地址

class Solution {
public:
    vector<string> vec;    
    vector<string> restoreIpAddresses(string s) {
        string str ="";
        backtrace(s,0,0,str);
        return vec;

    }
    
    void backtrace(string& s,int n,int index,string& str){
        if(n==4||index==s.size())
        {
            if(n==4&&index==s.size())
            {
                vec.push_back(str.substr(0,str.size()-1));
            }
            return;
        }
        for(int i=1;i<=3;i++){
            if(index+i>s.size()) return;
            if(s[index]=='0'&&i!=1) return;
            if(i==3&&s.substr(index,i)>"255") return;
            str+=s.substr(index,i);
            str+='.';
            backtrace(s, n+1, index+i, str);
            str=str.substr(0,str.size()-1-i);
        }
    }
};

01背包问题

有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。

第 i 件物品的体积是 vi,价值是 wi。

求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。
输出最大价值。

输入格式
第一行两个整数,N,V,用空格隔开,分别表示物品数量和背包容积。

接下来有 N 行,每行两个整数 vi,wi,用空格隔开,分别表示第 i 件物品的体积和价值。

输出格式
输出一个整数,表示最大价值。

数据范围
0<N,V≤1000
0<vi,wi≤1000
输入样例
4 5
1 2
2 4
3 4
4 5
输出样例:
8


二维dp

#include<iostream>
using namespace std;

const int N = 1020;
int dp[N][N];
int v[N],w[N];
int n,m;

int main()
{
    cin>>n>>m;
 
    for(int i=1;i<=n;i++)
    {
        cin>>v[i]>>w[i];
    }
    
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=m;j++)
        {
            dp[i][j]=dp[i-1][j];
            if(j>=v[i]) dp[i][j]=max(dp[i][j],dp[i-1][j-v[i]]+w[i]);
        }
    }
    cout<< dp[n][m];
}

一维dp

#include<iostream>
using namespace std;

const int N = 1020;
int dp[N];
int v[N],w[N];
int n,m;

int main()
{
    cin>>n>>m;
 
    for(int i=1;i<=n;i++)
    {
        cin>>v[i]>>w[i];
    }
    
    for(int i=1;i<=n;i++)
    {
        for(int j=m;j>=v[i];j--)
        {
            dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
        }
    }
    cout<< dp[m];
}

完全背包问题

有 N 种物品和一个容量是 V 的背包,每种物品都有无限件可用。

第 i 种物品的体积是 vi,价值是 wi。

求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。
输出最大价值。

输入格式
第一行两个整数,N,V,用空格隔开,分别表示物品种数和背包容积。

接下来有 N 行,每行两个整数 vi,wi,用空格隔开,分别表示第 i 种物品的体积和价值。

输出格式
输出一个整数,表示最大价值。

数据范围
0<N,V≤1000
0<vi,wi≤1000
输入样例
4 5
1 2
2 4
3 4
4 5
输出样例:
10


二维dp

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

const int N = 1030;
int n,m;
int dp[N][N],v[N],w[N];

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>v[i]>>w[i];
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=m;j++)
        {
            dp[i][j]=dp[i-1][j];
            if(j>=v[i]) dp[i][j]=max(dp[i-1][j],dp[i][j-v[i]]+w[i]);
        }
    }
    cout<<dp[n][m];
}

一维dp

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

const int N = 1030;
int n,m;
int dp[N],v[N],w[N];

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>v[i]>>w[i];
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=v[i];j<=m;j++)
        {
            dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
        }
    }
    cout<<dp[m];
}

多重背包问题I

有 N 种物品和一个容量是 V 的背包。

第 i 种物品最多有 si 件,每件体积是 vi,价值是 wi。

求解将哪些物品装入背包,可使物品体积总和不超过背包容量,且价值总和最大。
输出最大价值。

输入格式
第一行两个整数,N,V,用空格隔开,分别表示物品种数和背包容积。

接下来有 N 行,每行三个整数 vi,wi,si,用空格隔开,分别表示第 i 种物品的体积、价值和数量。

输出格式
输出一个整数,表示最大价值。

数据范围
0<N,V≤100
0<vi,wi,si≤100
输入样例
4 5
1 2 3
2 4 1
3 4 3
4 5 2
输出样例:
10

#include <bits/stdc++.h>
using namespace std;
int dp[1005],n,m,v,w,s;

int main()
{
    cin>>n>>m;
    while (n -- )
    {
        cin>>v>>w>>s;
        for(int i=1;i<=s;i++)
        {
            for(int j=m;j>=v;j--)
            {
                dp[j]=max(dp[j],dp[j-v]+w);
            }
        }
    }
    cout<<dp[m];
}

Q.E.D.