7月6日测试题题解

第一题：

　　FBI树

　　洛谷同题：https://www.luogu.com.cn/problem/P1087

　　分析：

　　题目要求我们根据一个01串构建树。

　　01串的长度为2^n，所以我们可以按照类似于线段树建树的方法建一棵满二叉树。由此观之，每一个节点p的儿子为p<<1,p<<1|1（p*2,p*2+1）。

　　代码如下：

#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
int read()
{
    int f=0,k=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-') k=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){f=(f<<1)+(f<<3)+(ch^48);ch=getchar();}
    return f*k;
}
const int MAXN=1050;
char a[MAXN],t[MAXN<<2];
void pushup(int p)//向上传递
{
    if(t[p<<1]==t[p<<1|1]) t[p]=t[p<<1];//如果两个儿子的字符相等，那当前节点也肯定的儿子相等
    else t[p]='F';//如果不等说明既有0又有1，则为F
}
void build(int p,int l,int r)//建树
{
    if(l==r)//叶子
    {
        if(a[l]=='0') t[p]='B';//0为B
        if(a[l]=='1') t[p]='I';//1为I
        return ;
    }
    int m=(l+r)>>1;
    build(p<<1,l,m);//递归左儿子(l,m)
    build(p<<1|1,m+1,r);//递归右儿子(m+1,r)
    pushup(p);//向上传递
}
void dfs(int p,int l,int r)//输出后序遍历
{
    if(l==r)
    {
        putchar(t[p]);
        return ;
    }
    int m=(l+r)>>1;
    dfs(p<<1,l,m);
    dfs(p<<1|1,m+1,r);
    putchar(t[p]);
}
int main()
{
    int n=read();
    n=1<<n;
    for(int i=1;i<=n;i++) cin>>a[i];输入
    build(1,1,n);
    dfs(1,1,n);
    printf("/n");
    return 0;
}

第二题：

　　搭配购买

　　题目描述

　　商店里有 件商品，编号为： 1~n，每件商品有一个价值 和价钱。商店老板有个奇怪的规定，如果要买某件商品，则与这件商品相搭配的都必须买。

　　你的钱有限，所以你想用你现有的钱买到的商品价值越大越好。

　　输入格式

　　第一行有三个正整数，n，m，w，分别表示商店里有n件商品，共有n种搭配关系，你有w的钱。

　　接下来行n，每行两个整数vi,ci表示第i件商品的价钱和价值。　　

　　接下来行，每行两个整数，i，j表示要买i商品 ，必须买j商品 ，同理，如果买j必须买i 。

　　输出格式

　　一行，表示可以获得的最大价值。

　　

　　分析：

　　应为买i就要买j，直接把i，j合并，再做背包问题。

#include<cstdio>
#include<algorithm>
using namespace std;
int read()
{
    int f=0,k=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-') k=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){f=(f<<1)+(f<<3)+(ch^48);ch=getchar();}
    return f*k;
}
const int MAXN=1e4+10;
int fa[MAXN],f[MAXN];
int n,m,w,v[MAXN],c[MAXN];
int getfa(int x)
{
    if(fa[x]==x) return x;
    else return fa[x]=getfa(fa[x]);
}
int main()
{
    n=read(),m=read(),w=read();
    for(int i=1;i<=n;i++) fa[i]=i;//并查集初始化
    for(int i=1;i<=n;i++)
        c[i]=read(),v[i]=read()
    for(int i=1;i<=m;i++)
    {
        int x=read(),y=read();
        x=getfa(x);y=getfa(y);
        if(x==y) continue;
        fa[y]=x;//把y合并到x
        c[x]+=c[y];
        v[x]+=v[y];
    }
    for(int i=1;i<=n;i++)
        if(fa[i]==i){//fa[i]==i表示i是合并的根
        for(int j=w;j>=c[i];j--)//01背包，反向dp
        {
            f[j]=max(f[j],f[j-c[i]]+v[i]);
        }
    }
    printf("%d/n",f[w]);
    return 0;
}

第三题：

　　洛谷：https://www.luogu.com.cn/problem/P4826

　　可以维护一个并查集，把所有的比赛按比赛得分降序排序。从1到tot遍历，对于每一场比赛，两个队伍i，j，如果i和j的根节点不相同，则合并，把比赛结果加再ans上，相反，则跳过。

　　仔细看，发现上述方法就是最小生成树kruskal算法的最大生成树版本。

#include<cstdio>
#include<algorithm>
using namespace std;
long long read()
{
    long long f=0,k=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-') k=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){f=(f<<1)+(f<<3)+(ch^48);ch=getchar();}
    return f*k;
}
const int MAXN=2e3+10,MAXM=2e6+10;
struct Edge{
    int x,y;
    long long w;
}e[MAXM];
bool operator <(Edge a,Edge b){//重载运算符以排序
    return a.w>b.w;
}
int n,cnt,tot,fa[MAXN];
long long ans,a[MAXN];
int getfa(int x)
{
    if(fa[x]==x) return x;
    else return fa[x]=getfa(fa[x]);
}
int main()
{
    n=read();
    for(int i=1;i<=n;i++) fa[i]=i;
    for(int i=1;i<=n;i++)
    {
        a[i]=read();
        for(int j=1;j<i;j++) e[++tot]=(Edge){j,i,a[i]^a[j]};//储存比赛
    }
    sort(e+1,e+tot+1);对比赛排序
    for(int i=1;i<=tot&&cnt<n-1;i++)
    {
        int x=getfa(e[i].x),y=getfa(e[i].y);
        if(x==y) continue;//在同一个集合里跳过 
        fa[x]=y;//否则合并
        ans+=e[i].w;//加在总得分上
        cnt++;//记录比赛个数优化时间
    }
    printf("%lld/n",ans);
    return 0;
}

第四题：

　　AcWing同题：https://www.acwing.com/problem/content/1127/

　　首先根据输入建图，应为节点数很少，用邻接矩阵储存，方便floyd求最短路。

　　除了求最短路外，应为可能不止两个牧场，可以用并查集记录各个牧场有那些牧区。

　　对于每个节点，我们可以记录下从当前节点维起点的最长距离。

　　在修建道路时，把两端点的距离加上两点记录下的最长距离走位新的直径。

　　注意，新的直径也不一定是直径，我们还需要求出所有牧场中的直径，与新求出的直径进行比较。

#include<cstdio>
#include<algorithm>
#include<cmath>
#include<iostream>
using namespace std;
int read()
{
    int f=0,k=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-') k=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){f=(f<<1)+(f<<3)+(ch^48);ch=getchar();}
    return f*k;
}
const int MAXN=150+10;
const double INF=1e9+10;
int n,xx[MAXN],yy[MAXN],fa[MAXN];
double f[MAXN][MAXN],dis[MAXN],ans=INF,maxn=0;//定义与初始化，ans记录新建道路后的距离，maxn记录没有新建道路时的最长直径
int getfa(int x)
{
    if(fa[x]==x) return x;
    else return fa[x]=getfa(fa[x]);
}
double ask_dis(int a,int b){return sqrt(pow((double)(xx[a]-xx[b]),2)+pow((double)(yy[a]-yy[b]),2));}//求两点间距离
int main()
{
    char ch;
    n=read();
    for(int i=1;i<=n;i++) fa[i]=i;
    for(int i=1;i<=n;i++) xx[i]=read(),yy[i]=read();
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            cin>>ch;
            if(ch=='1')
            {
                f[i][j]=ask_dis(i,j);
                int x=getfa(i),y=getfa(j);//合并牧区
                if(x!=y) fa[x]=y;
            }
            else f[i][j]=INF;//没有连接则赋最大值
        }
        f[i][i]=0;//自己到自己的距离为0
    }
    for(int k=1;k<=n;k++)//flody板子
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++){
        f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(f[i][j]!=INF){
        dis[i]=max(dis[i],f[i][j]);//记录从每个顶点出发的最大距离
        maxn=max(maxn,f[i][j]);//记录最长的距离及求最长直径
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++){
        if(getfa(i)==getfa(j)) continue;//在同一个牧场内则跳过
        ans=min(ans,ask_dis(i,j)+dis[i]+dis[j]);//不在同一个牧场内则求出两端点的距离加上两点记录下的最长距离之和作为最长直径
    }
    printf("%.6lf/n",max(maxn,ans));//与未连接之前的最长直径作比较
    return 0;
}

　　完。

　　致谢。