目录
平方差
更小的数
买瓜
网络稳定性（货车运输）
货车运输
平方差
这道题就是数论的题，不难想到一个数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;
}
