平均分组
输出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);
}
};
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.