第十四届蓝桥杯题解：平方差 ，更小的数，买瓜，网络稳定性（货车运输）

目录

平方差

 更小的数

买瓜

网络稳定性（货车运输）

货车运输

---

        

        

平方差

这道题就是数论的题，不难想到一个数m可以拆成(a-b)(a+b)，其实(a-b)和(a+b)就是m的一对因子，不妨设为x和y。

则有：

a+b=x;

a-b=y;

x*y=m;

联立求解：a=(x+y)/2，b=(x-y)/2；

也就是对于一个数m，只要存在一对因数x,y就必然存在一对a,b，又因为a和b必须为整数。

所以x+y和x-y必须为偶数。

不难发现

偶数+偶数=偶数，偶数-偶数=偶数

奇数+奇数=奇数，奇数-奇数=奇数

得出x+y和x-y必须同时为偶数或者奇数。

也就是m必须存在一对同时为偶数或者为奇数的因数 

那么这句话等价于m是4的倍数，或者是一个奇数

#include <bits/stdc++.h>
using namespace std;
int main(){
	int ans=0,l,r;cin>>l>>r;
	for(int i=l;i<=r;i++){
		if(i%4==0||i%2!=0)ans++;
	}
	cout<<ans;
}

        

        

 更小的数

很明显，要在O(n^2)内完成本题，但是判断每种方案是否满足又是一件头疼的事情，只能在O(n)内完成。

 
那么可以定义dp[i][j]表示从i下标到j下标的方案是否合法，主要就是为了快速求dp[i][j]

当我们在判断dp[i][j]是否合法时，完全可以借助之前的结果

 
如果字符s[i]>s[j]  则dp[i][j]=1（合法）
如果s[i]==s[j] 则dp[i][j]=dp[i+1][j-1]（里面的字符串是合法的则外面的也合法，否之不合法）

#include <bits/stdc++.h>
using namespace std;
int ans,n;
bool f[5005][5005];
string s;
int main(){
	cin>>s;n=s.size();
	for(int k=2;k<=n;k++)
	for(int i=0;i+k<=n;i++){
		int j=i+k-1;
		if(s[i]>s[j])f[i][j]=1,ans++;
		else if(s[i]==s[j])ans+=f[i+1][j-1],f[i][j]=f[i+1][j-1];
	}
	cout<<ans;
	return 0;
}

        

        

买瓜

这个题就是考察优化，3^30次方一定是满分不了的，如果想拿满分一定要优化。

首先是拿瓜：如果已经拿多了就放弃此方案

后面的瓜就算全拿也不够也放弃此方案

找到当前最优的刀数后只要比此更大的刀数一律放弃

然后就是数组倒序来加速找到答案。

总之一道非常好的dfs优化题

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
long long m,suf[35];
int n,ans,a[35];
void dfs(int x,int y, ll z){
	if(z==m){ans=min(ans,y);return ;}
	if((suf[x]+z<m)||y>=ans||x>n||z>m)return ;//3个主优化：找到最佳答案后抛弃当下答案，后面的数全部加起来也不行就放弃，数组倒序
	dfs(x+1,y+1,z+a[x]/2);//拿到瓜过多了就放弃，遍历完就返回。基本提高好几个数量级的速度
	dfs(x+1,y,z+a[x]);
	dfs(x+1,y,z);
}
int main(){
	cin>>n>>m;ans=60;m*=2;
	for(int i=1;i<=n;i++)cin>>a[i],a[i]*=2;
	sort(a+1,a+1+n);reverse(a+1,a+1+n);
	for(int i=n;i>=1;i--)suf[i]=suf[i+1]+a[i];//排序后再写缀合数组
	dfs(1,0,0);
	if(ans==60)cout<<-1;
	else cout<<ans;
	return 0;
}

        

        

网络稳定性（货车运输）

这个题是一道照抄过来的题，原题是“货车运输” 

就是这个题：

货车运输

一模一样，就拿这道做过的题来说把：

题意是要路径上最小的权值链路最大，如果是单源问题还是可以dijkstra的。

但是这个题是多源问题，就要kruskal+lca。

首先解释一下为什么要用kruskal：

那么不妨假设求u到v的路径，我们要所有由u通往v的路径中最小边权中最大的路径，那么如果我们按照最大生成树去建图，是不是图中任意两点间建立的路径都是最大路径？因为那些更小的边我们都没用上。可以设想一下如果u到v还有别的额外的路径，那么这些路径之所有没有没用上，不就是因为有的边权太小了。

然后是lca：

我们在建完树后，为什么就会想到lca呢？

首先这个时候我们要求两个点的路径，其实已经变得唯一了，而且必须找到最近公共祖先，所以需要用到lca

其次我们要求u到v的最小边权，那么这个最小边权如果一个一个的跑不就又变成n^n了吗，怎么办？这时候可以想到离线求极值的方法：倍增，线段树。

说到树上倍增，你最快的是不是想到lca

所以我们可以设置w[i][j]表示从i开始向上走2^j到长度对应的小的权值。然后从i开始走2^j长度路径上的最小权值。

同样设置：f[i][j]表示从i开始向上走2^j到的节点

这样就可以在逼近的时候一遍使用w来更新答案，一边使用f找公共祖先

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10,M=3e5+5,inf=1e9;
int tot,n,m,q,head[N],deep[N],f[N][21],w[N][21],fa[N];
//f[i][j]表示从i开始向上走2^j到的节点，w[i][j]表示从i开始向上走2^j到长度对应的小的权值
bool vis[N];
struct edge1{int u,v,w;}e1[M];
struct edge2{int v,w,next;}e2[N];
int find(int x){
	if(x!=fa[x])fa[x]=find(fa[x]);return fa[x];
}
void add(int u,int v,int w){e2[++tot]=(edge2){v,w,head[u]};head[u]=tot;}
bool cmp(edge1 a,edge1 b){return a.w>b.w;}
void kruskal(){
	for(int i=1;i<=n;i++) fa[i]=i;//初始化并查集
	sort(e1+1,e1+1+m,cmp);//建立最大生成树
	for(int i=1;i<=m;i++){ 
		int u=e1[i].u,v=e1[i].v,w=e1[i].w;
		int f1=find(u),f2=find(v);
		if(f1!=f2){ //建立重构树
			fa[f1]=f2;//合并并查集
			add(u,v,w);add(v,u,w);
		}
	}
}
void dfs(int u,int faa){//初始化每个点的deep[v]，f[v][0]，w[v][0]
	vis[u]=1;
	for(int i=head[u];i;i=e2[i].next){
		int v=e2[i].v;
		if(v==faa)continue;
		deep[v]=deep[u]+1;
		f[v][0]=u;
		w[v][0]=e2[i].w;
		dfs(v,u);//先更新自己再更新孩子
	}
}
int lca(int x,int y){
	if(find(x)!=find(y))return -1;
	int ans=inf;
	if(deep[x]>deep[y])swap(x,y);//让左边y向右边x靠近
	for(int i=20;i>=0;i--){//达到相同深度
		if(deep[f[y][i]]>=deep[x]){
			ans=min(ans,w[y][i]); y=f[y][i];//每上升一次就要更新此距离上的最小值。修改y位置
		}
	}
	if(x==y)return ans;//第一次返回
	for(int i=20;i>=0;i--){//一起上升到没有公共祖先为止
		if(f[x][i]!=f[y][i]){
			ans=min(ans,min(w[x][i],w[y][i]));//每上升一次就要更新两段距离上的最小值。
			x=f[x][i];y=f[y][i];
		}
	}
	ans=min(ans,min(w[x][0],w[y][0]));//此时再往上一格就是lca，所以再更新一次
	return ans;
}
int main(){
	cin>>n>>m>>q;
	for(int i=1;i<=m;i++){
		cin>>e1[i].u>>e1[i].v>>e1[i].w;
	}
	kruskal();
	for(int i=1;i<=n;i++){
		if(vis[i])continue;
		deep[i]=1;dfs(i,0);
		f[i][0]=i;w[i][0]=inf;//初始化根的信息
	}
	for(int i=1;i<=20;i++){//初始化倍增表
		for(int j=1;j<=n;j++){
			f[j][i]=f[f[j][i-1]][i-1];//距离倍增表
			w[j][i]=min(w[j][i-1],w[f[j][i-1]][i-1]);//极值倍增表
		}
	}
	int x,y;
	for(int i=1;i<=q;i++){
		cin>>x>>y;
		cout<<lca(x,y)<<'\n';
	}
	return 0;
	
}

当然如果你只是骗分，那么直接floyd就可以。

设置dp[i][j]表示i到j路径上的存在的最小边权，

根据： dp[i][j]=max(dp[i][j],min(dp[i][k],dp[k][j]))进行转移

当然前提是i能到k，k能到j 。然后至少能拿小半分了。

 memset(dp,-1,sizeof(dp));
    cin>>n>>m>>q;
    while(m--){
        int u,v,x;
        cin>>u>>v>>x;
        dp[u][v]=max(dp[u][v],x);   //如果有重边，选稳定性最大的一条路
        dp[v][u]=max(dp[v][u],x);
    }
    for(int k=1;k<=n;k++){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                if(i!=j&&j!=k&&i!=k){   //用K中转的路径 更新dp[i][j]
                    dp[i][j]=max(dp[i][j],min(dp[i][k],dp[k][j]));
                }
            }
        }
    }
    while(q--){
        int x,y;
        cin>>x>>y;
        cout<<dp[x][y]<<endl;
    }