未优化，当成多重背包做。

#include <iostream>
#include <stdio.h>
using namespace std;
int v[1005],w[1005],s[1005],dp[1005];
int main(){
	freopen("P1776_4.in","r",stdin);
	int N,V;
	cin>>N>>V;
	for(int i=1;i<=N;i++){
		cin>>w[i]>>v[i]>>s[i];
	}
	for(int i=1;i<=N;i++){
		for(int k=V;k>=1;k--){
			for(int l=0;l<=s[i]&&l*v[i]<=k;l++){
				cout<<k<<' '<<k-l*v[i]<<' ';
				dp[k]=max(dp[k],dp[k-l*v[i]]+l*w[i]);
			}
		}
	}
	cout<<dp[V];
	return 0;
}

二进制优化后（节省了大量空间）

#include <iostream>
#include <stdio.h>
using namespace std;
const int maxx=1e7+5;
int N,V;
int v[12005],w[12006],dp[maxx];
int main(){
//	freopen("P1776_4.in","r",stdin);
	cin>>N>>V;
	int count=0;
	//分成2^0(1),2^1(2),2^2(4),2^3(8)...余数组。
	//O(n^3)->O(n^2logS）
	for(int i=1;i<=N;++i){
		int z,x,c;
		cin>>z>>x>>c;
		for(int k=1;k<=c;k*=2){
			count++;
			v[count]=x*k;//fu gai.?
			w[count]=z*k;
			c-=k;
		}
		if(c>0){
			count++;
			v[count]=x*c;
			w[count]=z*c;
		}
	}
	//拿1024次苹果或者拿10次。（7次？
	for(int i=1;i<=count;++i){
		for(int k=V;k>=1;k--){
			if(k>=v[i])
			dp[k]=max(dp[k],dp[k-v[i]]+w[i]);
		}
	}
	cout<<dp[V];
	return 0;
}

T2 尴尬的数字（P1555）

#include <iostream>
using namespace std;
string a,b;
int cvs(string x){
	int yu,temp=0;
	for(int i=0;i<x.length();i++){
		yu=x[i]-'0';
		temp*=10;
		temp+=yu;
	}
	return temp;
}//转换数据类型
string er_shi(string x){
	int len=x.length(),baka;
	int i=0;
	if(x[i]!='0')
		baka=x[0]-'0';
	else{
		baka=x[1]-'0';
		i++;
	}
	i++;
	for(;i<len;i++){
		baka*=2;
		baka+=x[i]-'0';
	}
	string back;
	char temp;
	while(baka){
		temp=(baka%10)+'0';
		back=temp+back;
		baka/=10;
	}
	return back;
}//二进制转十进制
string shi_san(string x){
	string back;
	int num=cvs(x);//
	int yu;
	char temp;
	while(num){
		yu=num%3;
		temp=yu+'0';
		back=temp+back;
		num/=3;
	}
	return back;
}//十进制转三进制
bool cmp(string x){
	if(x.length()!=b.length())
		return false;
	int cnt=0;
	for(int i=0;i<b.length();i++){
		if(x[i]!=b[i])
			cnt++;
	}
	if(cnt==1) return true;
	return false;
}//判断函数
void change(int x){
	if(a[x]=='1') a[x]='0';
	else a[x]='1';
}
int main(){
	cin>>a>>b;
	for(int i=0;i<a.length();i++){
		if(i==0){
			change(i);
		}
		else{
			change(i-1);
			change(i);
		}//更换数字
		//此时是二进制字符串
		int ans=-1;
		ans=cvs(er_shi(a));//保存答案
		if(cmp(shi_san(er_shi(a)))){
			cout<<ans;
			return 0;
		}
		else continue;
	}
	return 0;
}

T3 小卡和质数（P8845）

#include <iostream>
int main(){
	int t,a,b;
	std::cin>>t;
	while(t--){
		std::cin>>a>>b;
		if((a==1&&b==2)||(a==2&&b==1)) std::cout<<"Yes"<<std::endl;
		else std::cout<<"No"<<std::endl;
	}
	return 0;
}

#include <iostream>
using namespace std;
const int inf=1e9+5;
int n,t,ans;
int c[105][105][105],dp[105][105],planet[105];
//c(i,j,k)表示从等级为i编号为j的星球走到等级为i+1编号为k星球的代价
//dp(i,j)表示走到等级为i编号为j的星球的代价
//状态转移方程：dp(i,j)=min(dp(i-1,l)+c,dp(i,j))
void init(){
	for(int i=1;i<=103;i++)
	for(int l=1;l<=103;l++)
	dp[i][l]=inf;
	for(int i=1;i<=103;i++)
	for(int l=1;l<=103;l++)
	for(int k=1;k<=103;k++)
	c[i][l][k]=inf;
	planet[0]=1;
}
int main(){
	init();
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>t;
		planet[i]=t;
		int cnt=1;
		while(t--){
			int st,v,z;
			cin>>st>>v>>z;
			c[i-1][st][cnt]=v;
			while(z!=0){
				st=z;
				cin>>v>>z;
				if(c[i-1][st][cnt]>v)//你妈的有重边
				c[i-1][st][cnt]=v;
			}
			cnt++;//到达的等级为i的星球编号
		}
	}
	dp[0][1]=0;
	for(int i=1;i<=n;i++){
		for(int l=1;l<=planet[i];l++){
			for(int k=1;k<=planet[i-1];k++){
				if(c[i-1][k][l]==inf) continue;
				dp[i][l]=min(dp[i][l],dp[i-1][k]+c[i-1][k][l]);
			}
		}
	}
	ans=inf;
	for(int i=1;i<=planet[n];i++)
	ans=min(ans,dp[n][i]);
	cout<<ans;
	return 0;
}

T2 跑步（P1806）

#include<iostream>
using namespace std;
long long int n,ans,dp[505][505];
void init(){
	for(int i=1;i<3;i++)
	for(int l=1;l<=500;l++)
	dp[i][l]=0;
}
long long int sum_(int row,int x){
	long long int sum=0;
	for(int k=x;k<=500;k++)
	sum+=dp[row][k];
	return sum;
}
int main(){
	cin>>n;
	for(int i=1;i<=500;i++){
		for(int l=1;l<=500;l++){
			if((i%2!=0&&l>i/2)||(i%2==0&&l>=i/2)) break;
			dp[i][l]=sum_(i-l,l+1)+1;
		}
	}
	for(int i=1;i<=500;i++)
	ans+=dp[n][i];
	cout<<ans;
	return 0;
}

T3 砝码称重(P8742)

#include <iostream>
#include <cmath>
using namespace std;
int n,w[105],max_,ans;
bool dp[105][300005];
void prework(){
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>w[i];
		max_=max_+w[i];
	}
	dp[0][0]=1;
}
void solve(){
	for(int i=1;i<=n;i++){
		for(int l=1;l<=max_;l++){
			dp[i][l]=dp[i-1][l];
			if(w[i]==l) 
			dp[i][l]=1;
			else if(dp[i-1][l+w[i]]==1)
			dp[i][l]=1;
			else if(dp[i-1][abs(l-w[i])]==1)
			dp[i][l]=1;
			if(dp[n][l]==1) ans++;
		}
	}
	cout<<ans;
}
int main(){
	prework();
	solve();
	return 0;
}

T4 遗址（P1959）

#include <iostream>
#include <cmath>
using namespace std;
struct edge{
	int x,y;
}a[3005];
int n,ans;
bool vis[5005][5005];
void check(int x1,int y1,int x2,int y2){
	int yy=abs(y1-y2);
	int xx=abs(x1-x2);
	int x3=x2+yy;
	int y3=y2+xx;
	int x4=x1+yy;
	int y4=y1+xx;
	if(x3<=5000&&y3<=5000&&x4<=5000&&y4<=5000&&vis[x3][y3]&&vis[x4][y4]){
		int temp=xx*xx+yy*yy;
		if(temp>ans) ans=temp;
	}
	x3=x2-yy;
	y3=y2-xx;
	x4=x1-yy;
	y4=y1-xx;
	if(x3>=0&&y3>=0&&x4>=0&&y4>=0&&vis[x3][y3]&&vis[x4][y4]){
		int temp=xx*xx+yy*yy;
		if(temp>ans) ans=temp;
	}
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		int xx,yy;
		cin>>xx>>yy;
		vis[xx][yy]=true;
		a[i].x=xx;
		a[i].y=yy;
	}//读入数据
	for(int i=1;i<=n;i++){
		for(int j=1;j<i;j++){
			check(a[i].x,a[i].y,a[j].x,a[j].y);
		}
	}
	cout<<ans;
	return 0;
}

T5 环境治理（P8794）

#include <iostream>
using namespace std;
int n,q,max,cnt;
int map[105][105],work[105][105];
int lmt[105][105];
bool checklmt(){
	for(int i=0;i<n;i++)
	for(int l=0;l<n;l++)
	work[i][l]=lmt[i][l];
	for(int k=0;k<n;k++)
		for(int i=0;i<n;i++)
			for(int l=0;l<n;l++){
				if(i==l) continue;
				if(work[i][l]>work[k][l]+work[i][k])
				work[i][l]=work[k][l]+work[i][k];
				}
	int sum_=0;
	for(int i=0;i<n;i++)
	for(int l=0;l<n;l++)
	sum_+=work[i][l];
	if(sum_<=q) return true;
	return false;
}
void init(){
	for(int i=0;i<n;i++)
	for(int l=0;l<n;l++)
	work[i][l]=map[i][l];
}
int sum(){
	int ans=0;//加和前初始化
	for(int i=0;i<n;i++)
		for(int l=0;l<n;l++)
		ans+=work[i][l];
		return ans;
}
void prework(){
	cin>>n>>q;
	for(int i=0;i<n;i++)
		for(int l=0;l<n;l++)
			cin>>map[i][l];
	for(int i=0;i<n;i++)
		for(int l=0;l<n;l++)
			cin>>lmt[i][l];
}
bool floyd(){
	init();//初始化
	for(int k=0;k<n;k++)
		for(int i=0;i<n;i++)
			for(int l=0;l<n;l++){
				if(i==l) continue;
				if(work[i][l]>work[k][l]+work[i][k])
				work[i][l]=work[k][l]+work[i][k];
			}
			if(sum()<=q) return false;
			return true;
}
void solve(){
	while(floyd()){
		int row=cnt%n;
		for(int i=0;i<n;i++){
			if(map[row][i]>lmt[row][i])
			map[row][i]--;
		}
		cnt++;
	}
	cout<<cnt;
}
int main(){
	prework();
	if(!checklmt()){
		cout<<"-1";
		return 0;
	}
	solve();
	return 0;
}

是一题（一笔画）欧拉路的模板。欧拉路 是指若从起点到终点的路径恰经过图中每条边一次，则该路径成为欧拉路。存在欧拉路的条件是：图是联通的，且有0个或2个奇点（出入度为奇数的点）。欧拉路一定是从一个奇点开始，到另一个奇点结束，所以有两个奇点的时候能一笔画完。

若每多出两个奇点，画的次数就会+1，所以答案就是 奇点的个数 / 2。

//当一个无向图的奇点数为0或者2的时候
//可以不重边的走完所有点
//奇点为度为奇数的点
//所以一幅图要（奇点数/2）笔画完
#include <iostream>
using namespace std;
int du[1005];//统计一个点的度数
int main(){
	int n,m; cin>>n>>m;
	for(int i=1;i<=m;i++){
		int s,e;
		cin>>s>>e;
		du[s]++;
		du[e]++;
		//无向图，所以出入度相等
	}
	int ans=0;
	for(int i=1;i<=n;i++)
		if(du[i]%2)
		ans++;
		if(ans==0) cout<<"1";//小特判
		else cout<<ans/2;
		return 0;
}

T2 合根植物（并查集）

是一道并查集的板子题，需要路径压缩。

#include <iostream>
using namespace std;
int n,m,k;
int f[1000005];
void init(){
	for(int i=1;i<=1000000;i++)
	f[i]=i;
	return;
}//初始化是必须的
int getf(int v){
	if(f[v]==v)
	return v;//查找根节点
	else{
		f[v]=getf(f[v]);
		return f[v];//路径压缩
	}
}//查找
void merge(int a,int b){
	int b1,b2;
	b1=getf(a);
	b2=getf(b);
	if(b1!=b2){
		f[b2]=b1;
		//左靠原则
	}
	return;
}//合并
int main(){
	cin>>n>>m>>k;
	//n为行数，m为列数
	init();
	for(int i=1;i<=k;i++){
		int x,y;
		cin>>x>>y;
		merge(x,y);
	}
	int sum=0;
	int tot=n*m;
	for(int i=1;i<=tot;i++){
		if(f[i]==i)
		sum++;
	}
	cout<<sum;
	return 0;
}

T3 奶酪

题目可以用dfs进行n^2的遍历，通过两点球心距离和两球半径之和的孰大孰小判断两球是相交，相切还是相离。

#include <iostream>
#include <cmath>
#include <cstring>
#include <stdio.h>
using namespace std;
long long int t,n,h,r;
bool vis[1005],found;
struct ball{
	int x,y,z;
}p[1004];
bool link(ball a,ball b){
	long long int dis=(pow(a.x-b.x,2)+pow(a.y-b.y,2)+pow(a.z-b.z,2));
	//两点距离的平方与2r的平方对比
	if(dis>4*r*r) 
		return false;
	else return true;//如果相交
}
void dfs(int a){
	if(found==true) return;
	if(p[a].z+r>=h){
		found=true;
		return;
	}
	for(int i=1;i<=n;i++){
		if(vis[i]==true) continue;
		else{
			if(link(p[a],p[i])){
				vis[i]=true;
				dfs(i);
			}//如果相交
		}
	}
}
int main(){
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	cin>>t;
	while(t--){
		found = false;
		memset(vis,false,sizeof(vis));
		//初始化
		cin>>n>>h>>r;
		for(int i=1;i<=n;i++){
			cin>>p[i].x>>p[i].y>>p[i].z;
		}
		for(int i=1;i<=n;i++){
			if(p[i].z<=r){
				dfs(i);
				//如果和底边相交或相切
			}
		}
		if(found==true) cout<<"Yes"<<endl;
		else cout<<"No"<<endl;
	}
	return 0;
}

T4 灾后重建（最短路）

用了动态规划的思想，是一道很好的练习floyd的题。

#include <iostream>
#include <stdio.h>
using namespace std;
const int inf=1e9+5;
int map[205][205];
int n,m,q,t[205];
int st,ed,v;//临时变量
void init(){
	for(int i=0;i<n;i++)
		for(int l=0;l<n;l++){
		map[i][l]=inf;
	}
	for(int i=0;i<n;i++) map[i][i]=0;
}//初始化
void updata(int x){
	for(int i=0;i<n;i++){
		for(int l=0;l<n;l++){
			map[i][l]=min(map[i][l], map[i][x]+map[x][l]);
		}
	}
}
int main(){
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	cin>>n>>m;
	init();
	for(int i=0;i<n;i++) cin>>t[i];
	for(int i=0;i<m;i++){
		cin>>st>>ed>>v;
		map[st][ed]=v;
		map[ed][st]=v;
		//存图
	}
	cin>>q;
	int cur=0;
	while(q--){
		cin>>st>>ed>>v;
		while(t[cur]<=v&&cur<n){
			updata(cur);
			cur++;//时间是逐渐变大的，所以已经做过中转的村庄不会再用到
		}
		if(t[st]>v||t[ed]>v||map[st][ed]==inf) cout<<"-1"<<endl;
		else cout<<map[st][ed]<<endl;
	}
	return 0;
}

T5 聪明的猴子

生成树的模板题。

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
struct edge{
	int s,e;
	long long int v;
}p[1000005];
int f[1005];
int x[1005],y[1005];
int M,mk[505],n;
int ans;
int cnt;
int getf(int x){
	if(f[x]==x) return x;
	else{
		f[x]=getf(f[x]);
		return f[x];
	}
}
bool merge(int x,int y){
	int x1,y1;
	x1=getf(x);
	y1=getf(y);
	if(x1!=y1){
		f[x1]=y1;
		return true;
	}
	return false;//已经联通
}
void init(){
	for(int i=1;i<=n;i++){
		f[i]=i;
	}
	return;
}
long long int len(int x1,int y1,int x2,int y2){
	return (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);//返回距离的平方
}
bool cmp(edge a,edge b){
	return a.v<b.v;
}
int main(){
	cin>>M;
	for(int i=1;i<=M;i++){
		int aa; cin>>aa;
		mk[i]=aa*aa;
	}
	sort(mk+1,mk+1+M);
	cin>>n;
	init();
	for(int i=1;i<=n;i++){
		cin>>x[i]>>y[i];
	}//读入数据
	for(int i=1;i<=n;i++){
		for(int l=i+1;l<=n;l++){
			long long int lens;
			lens=len(x[i],y[i],x[l],y[l]);
			cnt++;
			p[cnt].s=i;
			p[cnt].e=l;
			p[cnt].v=lens;
			//读入所有边
		}
	}
	int time=n*(n-1)/2;
	sort(p+1,p+1+time,cmp);//对time条边进行排序
	cnt=0;
	long long int max=0;
	for(int i=1;i<=time;i++){
		if(merge(p[i].s,p[i].e)){
			cnt++;
			max=p[i].v;
		}
		if(cnt==time-1) break;
	}
	for(int i=M;i>=1;i--){
		if(mk[i]>=max) ans++;
		else break;
	}
	cout<<ans;
	return 0;
}

下附代码：

#include <bits/stdc++.h>
using namespace std;
const int maxx=1e6+5;
int n,m;
int vis[maxx];
vector<int> book[maxx];
queue<int> b;
void dfs(int x){
	if(vis[x]==1) return;
	vis[x]=1;
	cout<<x<<' ';
	for(int i=0;i<book[x].size();++i){
		dfs(book[x][i]);
	}
}
void bfs(){
	b.push(1);
	while(!b.empty()){
		int x=b.front();
		b.pop();
		cout<<x<<' ';
		vis[x]=1;
		for(int i=0;i<book[x].size();++i){
			int next=book[x][i];
			if(vis[next]==1) continue;
			else{
				b.push(next);
				vis[next]=1;
			}
		}
	}
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int f,e;
		cin>>f>>e;
		book[f].push_back(e);
	}
	for(int i=1;i<=n;i++){
		sort(book[i].begin(),book[i].end());
	}//排序n种资料
	dfs(1);
	cout<<endl;
	memset(vis,0,sizeof(vis));
	bfs();
	return 0;
}

T2 Floyd（最短路n^3模板题）

floyd比较短，本质上是一种dp算法。时间复杂度为 n^3，n<10^3内的数据可以用。floyd适用性也很高，遍历所有点所以可以做到一些生成树算法的功能。

下附代码：

#include <iostream>
#include <cstring>
using namespace std;
const long long int mod = 998244354;
const long long int INF=25e13+500;
int n,m;
long long int ans;
long long int map[505][505];
int main(){
	for(int i=1;i<=503;i++)
	for(int l=1;l<=503;l++){
		if(i==l) map[i][l]=0;
		else map[i][l]=INF;
	}
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int s,e,v;
		cin>>s>>e>>v;
		if(map[s][e]!=0&&map[s][e]>v){
			map[s][e]=v;
			map[e][s]=v;
		}
		//无向图。
	}
	for(int k=1;k<=n;k++){
		for(int i=1;i<=n;i++){
			for(int l=1;l<=n;l++){
				if(i==l) continue;
				if(map[k][l]<INF&&map[i][k]<INF&&map[i][l]>(map[k][l]+map[i][k]))
				map[i][l]=(map[k][l]+map[i][k]);
			}
		}
	}
	for(int i=1;i<=n;i++){
		ans=0;
		for(int l=1;l<=n;l++){
			ans+=map[i][l];
			ans%=mod;
		}
		cout<<ans%mod<<endl;
	}
	return 0;
}

T3 单源最短路径（标准版）

用dijkstra时要用堆来优化缩边过程的选点步骤，可以用优先队列来存放到各点的估计值。

各种存图方式，代码用了vector数组进行存图

下附代码：

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
const int inf=2e9+5;
struct point{
	int end,len;
	bool operator < (const point a) const{
		return len < a.len;
	}//重载运算符
	bool operator > (const point a) const{
		return len > a.len;
	}
};
int n,m,st,cnt,now;
bool book[100005];
vector <point> a[100005];//最多1e5个点
priority_queue <point, vector<point>,greater<point> > dis;
int ans[100005];//存答案的数组。
int main(){
	cin>>n>>m>>st;
	for(int i=1;i<=100005;i++){
		ans[i]=inf;
	}
	ans[st]=0;
	for(int i=1;i<=m;i++){
		int s,e,v;
		cin>>s>>e>>v;
		a[s].push_back({e,v});
	}//vector存图
	dis.push({st,0});//存入起点
	while(!dis.empty()){
		point temp=dis.top();
		dis.pop();
		now=temp.end;
		//因为确定值不能重复更新（优先队列内仍可能存在
		//所以要加一个判断。
		if(!book[now]){
			book[now]=true;
			for(int i=0;i<a[now].size();i++){
				//遍历所有边 vector下标从0开始
				point x=a[now][i];
				int to=x.end;
				int v=x.len;
				//dijkstra核心代码
				if(ans[to]>ans[now]+v){
					ans[to]=ans[now]+v;
				//dijkstra核心代码
					if(!book[to]){
						//减少判断次数，去掉不影响算法正确性。
						dis.push({to,ans[to]});
					}
				}
			}
		}
	}
	for(int i=1;i<=n;i++){
		cout<<ans[i]<<' ';
	}
	return 0;
}

太典了。

大家闭着眼睛都能敲出来。（？）

#include <iostream>
using namespace std;
int T,M;
int t[1005],v[1005],dp[1005];
int main(){
	cin>>T>>M;
	for(int i=1;i<=M;i++){
		cin>>t[i]>>v[i];
	}
	
	for(int i=1;i<=M;i++){
		for(int p=T;p>=1;p--){
			if(p>=t[i]){
				dp[p]=max(dp[p],dp[p-t[i]]+v[i]);
			}
		}
	}
	cout<<dp[T];
}

T2 最长上升子序列

题目：

逆向防御导弹？）

#include <iostream>
using namespace std;
const int N=1e6+5;
int n;
int num[5005];
int dp[5005];
int ans=1;
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>num[i];
		for(int j=i-1;j>=1;j--){
			if(num[j]<num[i]&&dp[i]<dp[j]+1){
				dp[i]=dp[j]+1;
			}
		}
		if(dp[i]==0)
		dp[i]=1;
		if(dp[i]>ans) ans=dp[i];
	}
	cout<<ans;
	return 0;
}

T3 最大序列和

题目：

更新的式子同样很好找到。

要注意的只是判断的条件而已。

#include <iostream>
using namespace std;
int n,ans=-999999;
int num[200005],dp[200005];
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>num[i];
		dp[i]=num[i];
		if(i!=1&&dp[i-1]>=0){
			dp[i]=dp[i]+dp[i-1];
		}
		if(dp[i]>ans) ans=dp[i];
	}
	cout<<ans;
	return 0;
}

T4 LCS

太典了，啧啧啧。

也是大家闭着眼睛也能敲出来的东西（？）

#include <bits/stdc++.h>
using namespace std;
int dp[3005][3005];
int max_,a1,b1;
string ans;
int main(){
	string a,b;
	getline(cin,a);
	getline(cin,b);
	int len1=a.length();
	int len2=b.length();
	//矩阵边边要从0开始，下标0为dp中的1.
	for(int i=0;i<len1;i++){
		for(int l=0;l<len2;l++){
			if(a[i]==b[l]) dp[i+1][l+1]=dp[i][l]+1;
			else dp[i+1][l+1]=max(dp[i][l+1],dp[i+1][l]);
			if(dp[i+1][l+1]>max_){
				max_=dp[i+1][l+1];
				a1=i+1;
				b1=l+1;
			}
		}	
	}
	while(a1>0&&b1>0){
		if(a[a1-1]==b[b1-1]){
			ans=a[a1-1]+ans;
			a1-=1;
			b1-=1;
		}
		else{
			if(dp[a1-1][b1]>dp[a1][b1-1])
			a1-=1;
			else
			b1-=1;
		}
	}
	cout<<ans;
}

题目：

是经典的01背包问题，在博客另一处有介绍，推出 状态转移方程即可。

代码如下。

#include <iostream>
using namespace std;
long long int T,n;
long long int t[10005],w[10005];
long long int dp[10000005];
int main(){
	cin>>T>>n;
	for(int i=1;i<=n;i++) 
	cin>>t[i]>>w[i];
	for(int i=1;i<=n;i++){
		for(int l=1;l<=T;l++){
			if(l>=t[i])
			dp[l]=max(dp[l],dp[l-t[i]]+w[i]);
		}
	}
	cout<<dp[T];
	return 0;
}

T2 摆花

题目：

计数dp

用填表法的思想可以得出更新dp数组的式子。

#include <iostream>
using namespace std;
const long long int x=1000007;
long long int n,m,a[104],dp[105][105];
//dp[i][j]记录有i种花，要摆j盆时的摆法。
int main(){
	dp[0][0]=1;//一种花都没有的话是一种情况。
	cin>>n>>m;
	for(long long int i=1;i<=n;i++)
	cin>>a[i];
	for(long long int i=1;i<=n;i++){
		for(long long int l=0;l<=m;l++){
			for(long long int p=0;p<=min(l,a[i]);p++){
				dp[i][l]=(dp[i][l]+dp[i-1][l-p])%x;//每次都取模。
			}
		}
	}
	cout<<dp[n][m];
	return 0;
}

T3 樱花

题目：

看题可以知道有些美学值是可以拿很多甚至无限次的，所以这是一个多重背包问题，可以用二进制优化将复杂度由O（n^3）优化至O（n^2 logn）

可以把没有次数限制的美学值次数设成一个比较大的数。

代码如下。

#include <bits/stdc++.h>
using namespace std;
int N,V;
int v[100000005],w[100000006],dp[100000005];
long long int hs,ms,he,me;
int main(){
	scanf("%lld:%lld %lld:%lld %lld",&hs,&ms,&he,&me,&N);
	he-=hs;
	if(me-ms<0)
	me=me-ms+60,he--,me+=he*60;
	else me = me - ms + he * 60;
	V=me;
	int count=0;
	//分成2^0(1),2^1(2),2^2(4),2^3(8)...余数组。
	//O(n^3)->O(n^2logS）
	for(int i=1;i<=N;++i){
		int z,x,c;
		cin>>z>>x>>c;
		if(c==0) c=9999999;
		for(int k=1;k<=c;k*=2){
			count++;
			v[count]=z*k;
			w[count]=x*k;
			c-=k;
		}
		if(c>0){
			count++;
			v[count]=z*c;
			w[count]=x*c;
		}
	}
	for(int i=1;i<=count;++i){
		for(int k=V;k>=0;k--){
			if(k>=v[i])
			dp[k]=max(dp[k],dp[k-v[i]]+w[i]);
		}
	}
	cout<<dp[V];
	return 0;
}

T4 金明的预算方案

题目：

这题存附件数据技巧是开二维数组cost[x][y],x为第x件物品，当y为0时为这件物品本身，y为1时为第x件物品的附件1，y为2时为第x件物品的附件2。

然后每次选择有五种情况，

①只买主件
②买主件+附件1
③买主件+附件2
④买主件+附件1+附件2
⑤不买主件。

除了1和5冲突外，其他四个都能判断后更新新的dp值，顺序任意，枚举这五种情况，填表即可。

代码如下。

#include <iostream>
#include <cstring>
using namespace std;
int m,n;
int dp[70][40000];
int cost[70][5],imp[70][5];
int main(){
	cin>>m>>n;
	int c,im,f;
	for(int i=1;i<=n;i++){
		cin>>c>>im>>f;
		if(!f){
			cost[i][0]=c;
			imp[i][0]=im;
		}
		else{
			if(!cost[f][1]){
				cost[f][1]=c;
				imp[f][1]=im;
			}
			else{
				cost[f][2]=c;
				imp[f][2]=im;
			}
		}
	}
	memset(dp,0,sizeof(dp));
	for(int i=1;i<=n;i++){
		for(int l=1;l<=m;l++){
			if(l-cost[i][0]>=0){
				dp[i][l]=max(dp[i-1][l],dp[i-1][l-cost[i][0]]+cost[i][0]*imp[i][0]);
				if(l-cost[i][0]-cost[i][1]>=0){
				dp[i][l]=max(dp[i][l],dp[i-1][l-cost[i][0]-cost[i][1]]+cost[i][0]*imp[i][0]+cost[i][1]*imp[i][1]);
				}
				if(l-cost[i][0]-cost[i][2]>=0){
				dp[i][l]=max(dp[i][l],dp[i-1][l-cost[i][0]-cost[i][2]]+cost[i][0]*imp[i][0]+cost[i][2]*imp[i][2]);
				}
				if(l-cost[i][0]-cost[i][1]-cost[i][2]>=0){
					dp[i][l]=max(dp[i][l],dp[i-1][l-cost[i][0]-cost[i][1]-cost[i][2]]+cost[i][0]*imp[i][0]+cost[i][1]*imp[i][1]+cost[i][2]*imp[i][2]);
				}
			}
			else
			dp[i][l]=dp[i-1][l];
		}
	}
	cout<<dp[n][m];
	return 0;
}

总结：

记忆化搜索>dp？）。
代码写的好丑呀。（不是什么大问题就是）

每次选择都不可能选中最大默契值的武将，所以从1号到最后一号武将找与他默契值第二大的武将，并一直更新答案。

代码如下。

#include <iostream>
#include <algorithm>
using namespace std;
int g[505][505];
int main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		for(int j=i+1;j<=n;j++){
			cin>>g[i][j];
			g[j][i]=g[i][j];
		}
	}
	for(int i=1;i<=n;i++){
		sort(g[i]+1,g[i]+n+1);
	}
	int ans=0;
	for(int i=1;i<=n;i++){
		if(g[i][n-1]>ans)
		ans=g[i][n-1];
	}
	cout<<"1"<<endl<<ans;
	return 0;
}

T2 独木桥

是summer camp的一道题目。

两个士兵相遇调头可以视作穿了过去。

#include <iostream>
using namespace std;
const int N=5e3+5;
int num[N];
int maxs,mins;
int l,r;
int len,n;
int main(){
	cin>>len>>n;
	for(int i=1;i<=n;i++){
		cin>>num[i];
		l=num[i];
		r=len-num[i]+1;
		if(l<r){
			if(l>mins) mins=l;
			if(r>maxs) maxs=r;
		}
		else{
			if(r>mins) mins=r;
			if(l>maxs) maxs=l;
		}
	}
	cout<<mins<<' '<<maxs;
	return 0;
}

T3 排队接水

贪心的入门题？

代码如下。

#include <bits/stdc++.h>
using namespace std;
struct p{
	int x;
	int t;
};
int n;
double sum;
bool cmp(p a,p b){
	return a.t<b.t;
}
p a[1005];
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i].t;
		a[i].x=i;
	}
	sort(a+1,a+1+n,cmp);
	for(int i=1;i<=n;i++){
		sum+=(a[i].t*(n-i));
		cout<<a[i].x<<' ';
	}
	double ans = sum / n;
	printf("\n%.2f",ans);
}

T4 合并果子

要用到优先队列 priority_queue。(stl是个好东西。

要包含头文件 queue。

头为小元素的声明方式。

贪心策略是每次合并最小的两堆果子。

priority_queue< long long int , vector< long long int > , greater<long long int > 

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
priority_queue< long long int , vector< long long int > , greater<long long int > >num;
long long int n,t,temp,ans;
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>t;
		num.push(t);
	}
	while(!num.empty()){
		temp=num.top();
		num.pop();
		if(num.empty()){
			break;
		}
		temp+=num.top();
		num.pop();
		ans+=temp;
		num.push(temp);
	}
	cout<<ans;
	return 0;
}

不足：

优先队列是个啥东西。

看了非常多题解。

搜索本质上是一种遍历，是对每一种情况操作一遍。

T1 迷宫（dfs）

是好题，一道用dfs的好题。

#include <iostream>
#include <cstring>
using namespace std;
int n,m,t;
int movex[5]={0,1,0,-1,0};//右 上
int movey[5]={0,0,-1,0,1};//左 下
int world[15][15];//图
int vis[15][15];//标记
int sx,sy,fx,fy;//起点 终点
int cnt;//计数。
void dfs(int x,int y){
	if(x==fx&&y==fy){
		cnt++;
		return;
	}
	for(int i=1;i<=4;i++){

		int nx=x+movex[i];
		int ny=y+movey[i];
		if(world[nx][ny]==1&&vis[nx][ny]==0){//可以走到。

			vis[nx][ny]=1;
			dfs(nx,ny);
			vis[nx][ny]=0;
		}
	}
}
int main(){
	memset(vis,0,sizeof(vis));
	memset(world,0x3f,sizeof(world));//默认不能走。
	cin>>n>>m>>t;
	for(int i=1;i<=n;i++){
		for(int l=1;l<=m;l++){
			world[i][l]=1;//可以走的。
		}
	}
	cin>>sx>>sy>>fx>>fy;
	for(int i=1;i<=t;i++){
		int x1,y1;
		cin>>x1>>y1;
		world[x1][y1]=0x3f;//障碍。
	}
	vis[sx][sy]=1;
	dfs(sx,sy);
	cout<<cnt;
	return 0;
}

T2 马的遍历

是好题，一道用bfs的好题。

非常愚笨的手写队列。

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=2e5;
struct note{
	int x;//横坐标。
	int y;//纵坐标。
	int step;//步数。
};
note point[N];
int movex[9]={0,2, 2, 1, 1,-1,-1,-2,-2};
int movey[9]={0,1,-1, 2,-2, 2,-2, 1,-1};
int world[405][405];
int step[405][405];
bool vis[405][405];
int n,m;
int mx,my;
int main(){
	memset(world,0x3f,sizeof(world));//
	memset(step,0,sizeof(step));//特判
	cin>>n>>m;//输入N M。
	cin>>mx>>my;//输入起点。
	for(int i=1;i<=n;i++){
		for(int l=1;l<=m;l++){
			world[i][l]=1;//能走的点。
		}
	}
	//step前+1 = step后。
	int head=1,tail=1;
	point[head].x = mx;
	point[head].y = my;//起点？？
	vis[mx][my]=true;
	tail++;
	while(head<tail){
                        for(int i=1;i<=8;i++){
			int cur_x=point[head].x+movex[i];//移动后的横坐标。
			int cur_y=point[head].y+movey[i];//移动后的纵坐标。

			if(cur_x<=0||cur_y<=0) continue;//防止数组越界。
			if(world[cur_x][cur_y]==1&&vis[cur_x][cur_y]==false){//可以走 且 没走过。

				point[tail].x=cur_x;//记录横坐标。
				point[tail].y=cur_y;//记录纵坐标。
				vis[cur_x][cur_y]=true;//这个点已经走过了。
				step[cur_x][cur_y]=step[point[head].x][point[head].y]+1;//从开始遍历八个方向的点的STEP+1。
				tail++;//记录 入列。
//cout<<"step head: "<<step[point[head].x][point[head].y]<<endl;
//cout<<"step cur : "<<step[cur_x][cur_y]<<endl<<endl;
			}
		}
		head++;//遍历完成。
	}
	for(int i=1;i<=n;i++){
		for(int l=1;l<=m;l++){
			if(step[i][l]==0){
				step[i][l]=-1;//仍然为0的点。
			}
		}
	}
	step[mx][my]=0;//起点为0。
	
	for(int i=1;i<=n;i++){
		for(int l=1;l<=m;l++){
			cout<<step[i][l]<<"    ";
		}
		cout<<endl;
	}
	return 0;
}

待续…………。

T1 队列安排

要用手写一种很新的东西存数据。
每个同学自带左手和右手，于是用链表完成对队列的操作。

代码如下。

#include <iostream>
using namespace std;
const int N=1e6+5;
struct hand{
	int l,r;
};//同学的左手和右手。
hand stu[N]={0};
void add(int i,int j,int f){//把j同学插入。
	if(f==0){//j是插入的同学 j i x的情况。j在i左边。
		stu[j].r=i;
		stu[j].l=stu[i].l;
		stu[stu[i].l].r=j;
		stu[i].l=j;
	}
	else{// i j x的情况。j在i右边。
		stu[j].l=i;
		stu[j].r=stu[i].r;
		stu[stu[i].r].l=j;
		stu[i].r=j;
	}
}
void del(int x){//删除编号为x的同学。
	if(stu[x].l==0&&stu[x].r==0) return;//没有这个同学。
	else{
		stu[stu[x].l].r=stu[x].r;
		stu[stu[x].r].l=stu[x].l;
		stu[x].l=0,stu[x].r=0;//删掉。
	}
}
int main(){
	int n; cin>>n;//n个同学。
	//非常重要。
	stu[0].l=0,stu[0].r=0;//设第零个同学自己抱住自己。
	add(0,1,1);//先把第一个同学插入。
	int num,op;//指有num个同学，op是操作类型（0/1）
	for(int i=2;i<=n;i++){
		cin>>num>>op;
		add(num,i,op);//进行插入操作。 
	}
	//删除操作。
	int cnt; cin>>cnt;//进行cnt次删除操作。。
	for(int i=1;i<=cnt;i++){
		int ds; cin>>ds;
		del(ds);
	}
	for(int i=stu[0].r;i;i=stu[i].r){//遇到0同学的时候就停止了。
		cout<<i<<' ';
	}
	cout<<endl;//行末换行。
	return 0;
}

当然也可以用标记的方式决定输不输出这个同学，（要是换了一道题有要求的还是得乖乖写hh。

T2 括号匹配

在发现字符串长度不超过100后。

#include <bits/stdc++.h>
using namespace std;
bool vis[105]={false};
int main(){
	string a; cin>>a;
	for(int i=0;i<a.length();i++){
		if(a[i]==')'||a[i]==']'){//如果遇到了右括号。
			for(int l=i-1;l>=0;l--){//查找右括号左边的左括号。
				if((a[l]=='('||a[l]=='[')&&vis[l]==false){//找到最近的没被查找过的左括号。
					if((a[l]=='('&&a[i]==')')||(a[l]=='['&&a[i]==']')){
						vis[i]=true,vis[l]=true;
						break;//配对成功。
					}
					else break;//配对失败。
				}
			}
		}
	}
	for(int i=0;i<a.length();i++){
		if(vis[i]==true){
			cout<<a[i];
		}
		else{
			if(a[i]=='('||a[i]==')') cout<<"()";
			if(a[i]=='['||a[i]==']') cout<<"[]";
		}
	}
	return 0;
}

其实这道题是试图让我们用栈解吧。））

T3 后缀表达式

是一道好题 用栈存数据的好题。

#include <iostream>
#include <stack>
#include <string>
using namespace std;
int main(){
	stack<int> num;//存数字。
	stack<char> op;//存运算符。
	char a;
	int x=0;
	while(cin>>a&&a!='@'){
		if(a=='.'){//遇到 . 时。
			num.push(x);//把数字存入栈中。
			x=0;//重新初始化x。
		}//遇到点吧数字压入栈中。
		if(a>='0'&&a<='9'){
			x*=10; x+=a-'0';
		}//读取数字
		//加减乘除————。（感觉写的好笨）
		if(a=='+'){
			int x1,x2;
			x1=num.top();
			num.pop();
			x2=num.top();
			num.pop();
			x1+=x2;
			num.push(x1);
		}
		else if(a=='-'){
			int x1,x2;
			x1=num.top();
			num.pop();
			x2=num.top();
			num.pop();
			x2-=x1;
			num.push(x2);
		}
		else if(a=='*'){
			int x1,x2;
			x1=num.top();
			num.pop();
			x2=num.top();
			num.pop();
			x2*=x1;
			num.push(x2);
		}
		else if(a=='/'){
			int x1,x2;
			x1=num.top();
			num.pop();
			x2=num.top();
			num.pop();
			x2/=x1;
			num.push(x2);
		}
	}
	cout<<num.top();//最后的一枚数字就是经过n次运算后的答案了。
	return 0;
}

T4 寄包柜

这题柜子里还有格子，如果用二维数组的话会M，如果搜索的话会T。传统的连续顺序表在这里用起来非常尴尬。

于是（看题解后）去学了强大的Map。
Map存储的数据类型是pair，可以存很多pair。
Pair是<key，value>的键值对，是存储一个键与键映射的一个值的数据类型，其中key和value可以是自带的任意一种数据类型，也可以是自定义的结构体，其中key的值会用const修饰，也就是说他是不可更变的值。

Map常用的函数有：

① .insert()
用法：map变量名.insert（{key,value}）；
② .erase()
用法：map变量名.erase（key）；
会删除map中键为key的pair

在经过一些map的小实验后，过此题简直如有神助。）

#include <iostream>
#include <map>//要包含头文件map！
using namespace std;
int main(){
	map<pair<int,int>,int> m;
	//定义一个map容器。
	//key为柜子和格子，value为物品。
	int n,q;//有n个柜子，q次操作。
	cin>>n>>q;
	for(int i=1;i<=q;i++){
		int op;
		cin>>op;
		//存入操作。
		if(op==1){
			int x1,x2,x3;
			cin>>x1>>x2>>x3;
			if(x3!=0)
			m.insert({{x1,x2},x3});
			else//坑点：物品为0时要拿出来。。
			m.erase({x1,x2});
		}
		//访问操作。
		else{
			int x1,x2;
			cin>>x1>>x2;
			cout<<m[{x1,x2}]<<endl;
			//访问的时候要 m[key]。
		}
	}
	return 0;
}

可以说是非常简单（bu）；

但是关于map的认识也只停留在过 T4 的程度。

其他的函数，我还没用过（之后会学的！）
如
.find()
.begin() / .rbegin()
.end() / .rend()
.empty()
.clear()
.size()
.swap()
.count() //不能声明count为变量名的元凶？）

总结：

总结是

①链表啊栈啊Map啊很好用 但是对使用条件适用范围不是非常熟练。

②我是不是看太多题解了？）（反正学到了新东西诶嘿。）

• 2024 年 10 月
• 2024 年 9 月
• 2024 年 8 月
• 2024 年 7 月
• 2024 年 6 月
• 2024 年 5 月
• 2024 年 4 月
• 2024 年 2 月
• 2024 年 1 月
• 2023 年 11 月
• 2023 年 10 月
• 2023 年 5 月
• 2022 年 12 月
• 2022 年 11 月
• 2022 年 10 月

二分查找有个很重要的特点，就是不会查找数列的全部元素，而查找的数据量其实正好符合元素的对数，正常情况下每次查找的元素都在一半一半地减少。在最坏的情况和一般情况下都比顺序查找要快。

使用二分查找的条件：
查找的序列必须要是单调的。

（假如考拉猫搬着刚借的1e5本书走出图书馆，两侧的门突然响了（bushi）

T1 二分查找

Tag：基础 二分查找。

（思路呢）
代码如下。

#include <iostream>
using namespace std;
int n,n_q;
long long int q;
int main(){
	cin>>n>>n_q;
	long long int num[n+5];
	for(int i=1;i<=n;i++) cin>>num[i];//输入数据。
	while(n_q--){
		cin>>q;//输入询问的数。
		long long int l=0,r=n+1,mid;
		while(l+1!=r){//左边界是询问数的编号-1
			mid=(l+r)/2;//更新数据。
			if(num[mid]>=q){
				r=mid;
			}
			else{
				l=mid;
			}
		}//找边界。
		if(num[l+1]==q){
				cout<<l+1<<' ';
		}//如果找到了 输出左边界加一l+1。
		else cout<<"-1 ";
		//找不到 输出-1。
	}
	return 0;
}

有时候会遇到 最大值的最小 或者 最小值的最大 问题，直接去做不好做，但是检查一个答案可不可行是比较简单的。然后用二分的思想 不断缩小答案的区间，最后获得可行答案的最大值。

T2 进击的奶牛

tag：二分答案 可行最大值。

用二分答案的思想去做，需要写检查函数。对于这道题，要将牛从左到右进行安置，直到所有牛棚被安排完或者所有牛被安置完。

代码如下。

#include <iostream>
#include <algorithm>
using namespace std;
int N,C;//N是牛棚的数量，C是牛的数量。
long long int x[100005];//是牛棚的坐标。
bool check(long long int ans){//检查函数将牛从左至右安置。
	long long int start=x[1],end,cow=C-1;
	for(int i=2;i<=N&&cow!=0;i++){
		end=x[i];
		//如果两个牛棚间隔大于答案的值,安置好了一头牛。
		if(end-start>=ans){
			start = end;//更新左边的牛棚。
			cow--;//需要安置的牛-1。
		}
	}
	if(cow<=0) return true;//如果所有的牛都安置好了,这个答案可行。
	else return false;
}
int main(){
	cin>>N>>C;//输入数据。
	for(int i=1;i<=N;i++){
		cin>>x[i];
	}
	sort(x+1,x+N+1);//不要忘记排序。
	//开始写二分搜索答案。
	long long int l=0,r=1e10+5,mid;
	while(l<=r){
		mid=(l+r)/2;
		//如果答案可行，把左边界的值右移。
		if(check(mid)){
			l=mid+1;
		}
		else
		r=mid-1;
	}
	cout<<l-1;//输出答案。
	return 0;
}

坑点是不要忘记排序，还有检查函数循环的结束条件。

T3 一元三次仿鲿求解。

tag：二分答案 简单 枚举。

这题注意到根的范围比较小，且根于根之差的绝对值大于等于1，所以可以枚举两百个点找根。
活用题面与提示，找够三个点后退出循环，然后输出答案。

获得精确到小数点后两位的答案，有两种方法
①一种是L,R作差的值精确到0.001时返回答案。
②一种是限定次数的浮点二分。（机宝hso）

代码如下。

#include <iostream>
#include <cmath>
using namespace std;
double a,b,c,d;
double temp;
double ans[4];//记录答案的数组（其实可以不要）
int cnt=1;
double f(double x){
	return (a*pow(x,3)+b*pow(x,2)+c*x+d);
}//计算函数值的函数。
bool root(double l,double r){
	if(f(l)*f(r)<0) return true;
	else return false;
}//非常简单的检查函数。
int main(){
	cin>>a>>b>>c>>d;
	for(int i=-100;i<100;i++){//枚举200个点。
		if(cnt==4) break;//存够答案就可以了。
		if(f(i)==0){
			ans[cnt++]=i;
			continue;
		}
		if(root(i,i+1)){//初步判断有没有根。
			double l=i,r=i+1,mid;
			int tot=1;//计数器。
			while(++tot<60){//限定次数的浮点二分。
				mid = (l+r)/2;
				if(root(l,mid)){
					r=mid;
				}
				else l=mid;
				temp=mid;
			}
			ans[cnt++]=temp;
		}
	}
	printf("%.2f %.2f %.2f",ans[1],ans[2],ans[3]);
	return 0;
}

T4 锯树

tag：二分答案 可行最大值

代码如下。

#include <iostream>
using namespace std;
const int N=1e6+5;
int n;//n为树木的数量。
long long int tree[N],need;//数的高度 和 需要的木头长度。
bool check(long long int x){
	long long int sum=0;//砍下的木材长度计数。
	for(int i=1;i<=n;i++)
	if(x<tree[i]){//如果木头能锯到树。
		sum+=tree[i]-x;//长度-锯子高度。
	}
	if(sum>=need) return true;//如果锯够了。
	return false;
}
int main(){
	cin>>n>>need;
	for(int i=1;i<=n;i++){
		cin>>tree[i];
	}//输入数据。
	long long int l=0,r=2e9+5,mid;
	//要求锯最少的树满足条件。（即求满足条件的最大值。
	while(l<=r){
		mid=(l+r)/2;
		if(check(mid)){//如果答案可行,找更高的值。
			l=mid+1;
		}
		else r=mid-1;
	}
	cout<<l-1;
	return 0;
}

T5 跳石头

tag：二分答案 边界最大值。

坑点：有可能要把第一颗或者最后一颗石头移走的情况，所以起点要设置成0，然后要把终点存入rock数组中，这样才能对最后一颗石头进行判定。

#include <iostream>
using namespace std;
const int N=5e5+5;
int l,n,m;// l是长度，n是岩石个数，m是可移走的石头数。
int rock[N];//记录石头 距离起点的 长度。
bool check(int x){
	int cnt=0,start=0,end;
	for(int i=1;i<=n+1;i++){
		end=rock[i];//更新下一个石头的值。
		if(end-start<x){//如果两个石头距离小于检查的距离。
			cnt++;//说明要移走一个石头。
		}
		else //否则更新上一个石头的值。
		start=end;
	}
	if(cnt<=m) return true;
	return false;
}
int main(){
	cin>>l>>n>>m;
	for(int i=1;i<=n;i++)
	cin>>rock[i];
	rock[n+1]=l;//坑点 最后一个石头也要进行判断。
	//所以要把他存入rock数组里。
	int l=0,r=1e9+5,mid;//二分。
	while(l<=r){
		mid=(l+r)/2;
		if(check(mid)){//如果答案可行。
			l=mid+1;//更新左边界的值。
		}
		else r=mid-1;//不可行更新右边界的值。
	}
	cout<<r;//输出r。
	return 0;
}

T6 三分法。

tag：三分模板。

这道题听说是典型的三分模板，用小学思维求导二分也行，但对于一些复杂函数求导并不是那么的方便。

这道题的思路是：在[L，R]上取两个三等分点记为 x=i 和 x=j ，肯定是f（x）更大的的数更靠近拐点。
所以为了让范围更接近拐点，可以让没那么接近的那个点为新的边界，不断缩小范围直到满足精确度
的条件。

坑点：三等分点不是（l+r）*（1/3）呜呜。

代码如下。

#include <iostream>
#include <cmath>//需要用到指数运算。
using namespace std;
int n;//函数有n+1项。
double l,r,ll,rr,cut;//ll，rr为左右三等分点
//cut为[L,R]三等分后每一段的长度。
//函数次数为6到13，所以定义一个数组存各项系数。
double a[20];
//计算并返回函数值的函数。
double f(double x){
	double sum=0;
	for(int i=0;i<=n;i++)
	sum+=a[i]*pow(x,i);
	return sum;
}
int main(){
	cin>>n>>l>>r;
	//注意是从次数大的系数开始输入。
	for(int i=n;i>=0;i--) cin>>a[i];
	while(abs(l-r)>0.00001){
		cut = (r-l)/3.0;
		ll=l+cut;//加三分之一长度。
		rr=r-cut;//减三分之一长度。
		if(f(ll)>=f(rr))//如果左边的点更靠近。
			r=rr;//更新右边界。
		else l=ll;//否则更新左边界。
	}
	printf("%.5lf",(l+r)/2.0);
	return 0;
}

大概就是这样？
好难哦。

存在的问题：

①二分答案的题写少了，检查函数写的很慢。
②其实对答案该怎么保存还是不太熟悉的（基本都是在调试的时候直接输出边界附近的数）

好累啊我要玩东方去了（摆。

• 2024 年 10 月
• 2024 年 9 月
• 2024 年 8 月
• 2024 年 7 月
• 2024 年 6 月
• 2024 年 5 月
• 2024 年 4 月
• 2024 年 2 月
• 2024 年 1 月
• 2023 年 11 月
• 2023 年 10 月
• 2023 年 5 月
• 2022 年 12 月
• 2022 年 11 月
• 2022 年 10 月