蓝桥杯练习系统题解

转于：http://www.cnblogs.com/cshhr/p/3550014.html



蓝桥杯官网练习系统题解(非VIP)


BEGIN-4(Fibonacci数列)

有递推公式，大家都知道用递推公式求，仅仅要记得在递推的时候同一时候取模求好

这里给一份另类代码，用矩阵高速幂求，事实上还有循环节

复制代码
/*
    (1 1) * (Fn-1) = ( Fn )//矩阵相乘，将就着看吧
    (1 0)   (Fn-2)   (Fn-1)

    (1 1) * (1 1) * (Fn-2) = ( Fn )
    (1 0)   (1 0)   (Fn-3)   (Fn-1)

    F1=1,F0=0...

    (1 1) * ... * (1 1) * (1) = ( Fn )//共n-1个(1 1)
    (1 0)         (1 0)   (0)   (Fn-1)         (1 0)
*/ 
#include<cstdio>
const int Mod=10007;
int Z[2][2];
void Matrix_Multiply(int X[][2],int Y[][2]){
    for(int i=0;i<2;i++){
        for(int j=0;j<2;j++){
            Z[i][j]=0;
            for(int k=0;k<2;k++)
                Z[i][j]+=X[i][k]*Y[k][j];
        }
    }
}
void Matrix_Copy(int *C){
    for(int i=0;i<2*2;i++)
        C[i]=Z[i/2][i%2]%Mod;
}
int Fast(int n){//高速求幂
    int B[2][2]={1,0,0,1,},A[2][2]={1,1,1,0};//B为单位矩阵
    while(n){
        if(n&1){
            Matrix_Multiply(B,A);
            Matrix_Copy(&B[0][0]);
        }
        n>>=1;
        Matrix_Multiply(A,A);
        Matrix_Copy(&A[0][0]);
    }
    return B[0][0];//B[0][0]*f1+B[0][1]*f0 (f1=1,f0=0)
}
int main()
{
    int n;
    scanf("%d",&n);
    n=(n-1)%20016+1;//实验发现循环节为20016，事实上在使用高速幂的情况下这个优化快不了多少
    printf("%d
",Fast(n-1));
    return 0;
}
复制代码

 

BASIC-1(闰年推断)

复制代码
#include<cstdio>
bool Is(int y){
    if(y%4)return false;
    if(y%100)return true;
    if(y%400)return false;
    return true;
}
int main()
{
    int y;
    scanf("%d",&y);
    printf("%s
",Is(y)?
"yes":"no");
    return 0;
}
复制代码


BASIC-2(01字串)

回溯就好

复制代码
#include<cstdio>
#define MAXN 5
int ans[MAXN];
void Print_ans(int k){
    for(int i=0;i<k;i++)printf("%d",ans[i]);printf("
");
}
void Set_01(int k){
    if(k==MAXN){
        Print_ans(k);
        return;
    }
    for(int i=0;i<2;i++){
        ans[k]=i;
        Set_01(k+1);
    }
}
int main()
{
    Set_01(0);
    return 0;
}
复制代码

BASIC-3(字母图形)

复制代码
#include<cstdio>
int main()
{
    char ans[26][26];
    for(int i=0;i<26;i++){//这样把最大图案存好就不会错了，黑黑 
        ans[i][i]='A';
        for(int j=i+1;j<26;j++)
            ans[i][j]=ans[j][i]='A'+j-i;
    }
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++)
            printf("%c",ans[i][j]);
        printf("
");
    }
    return 0;
}
复制代码

BASIC-4(数列特征)

懒得思考了。最大最小值 直接存下标了

复制代码
int main()
{
    int minid,maxid,sum,n,a[10010];
    minid=maxid=sum=0;
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d",&a[i]);
        if(a[i]>a[maxid])maxid=i;
        if(a[i]<a[minid])minid=i;
        sum+=a[i];
    }
    printf("%d
%d
%d
",a[maxid],a[minid],sum);
    return 0;
}
复制代码

BASIC-5(查找整数)

每一个数都不大于10000，可在输入时储存每一个数字第一次出现的位置，后面的查找就变成了O(1)

复制代码
#include<cstdio>
int a[10010];
int main()
{
    int n,c;
    scanf("%d",&n);
    for(int i=1;i<=n+1;i++){
        scanf("%d",&c);
        if(a[c]==0)a[c]=i;
    }
    printf("%d
",a[c]>n?
-1:a[c]);//这里a[c]>n表示c仅仅在最后输入查询值时出现过 
    return 0;
}
复制代码

BASIC-6(杨辉三角形)

不多说了。注意格式就好

复制代码
#include<cstdio>
int main()
{
    int n,f[35][35];
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        f[i][0]=f[i][i]=1;
        for(int j=1;j<i;j++)
            f[i][j]=f[i-1][j-1]+f[i-1][j];
        for(int j=0;j<i;j++)printf("%d ",f[i][j]);printf("%d
",f[i][i]);
    }
    return 0;
}
复制代码

BASIC-7(特殊的数字)

是不是非常逗

#include<cstdio>
int main()
{
    printf("153
370
371
407
");
    return 0;
}

BASIC-8(回文数)

还去写什么推断语句真是弱爆了

复制代码
#include<cstdio>
int main()
{
    for(int i=1;i<10;i++)
        for(int j=0;j<10;j++)
            printf("%d%d%d%d
",i,j,j,i);
    return 0;
}
复制代码

BASIC-9(特殊回文数)

两份代码。后者比前者快

复制代码
#include<cstdio>
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<10;i++)
        for(int j=0;j<10;j++){
            int k=n-i*2-j*2;
            if(k>=0 && k<10)
            printf("%d%d%d%d%d
",i,j,k,j,i);}
    if(n%2==0){
        n/=2;
        for(int i=1;i<10;i++)
            for(int j=0;j<10;j++){
                int k=n-i-j;
                if(k>=0 && k<10)
                printf("%d%d%d%d%d%d
",i,j,k,k,j,i);}
    }
    return 0;
}
复制代码
复制代码
#include<cstdio>
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n/2&&i<10;i++)
        for(int j=0;j<=n/2-i&&j<10;j++){
            int k=n-i*2-j*2;
            if(k<10)
            printf("%d%d%d%d%d
",i,j,k,j,i);}
    if(n%2==0){
        n/=2;
        for(int i=1;i<=n&&i<10;i++)
            for(int j=0;j<=n-i&&j<10;j++){
                int k=n-i-j;
                if(k<10)
                printf("%d%d%d%d%d%d
",i,j,k,k,j,i);}
    }
    return 0;
}
复制代码

BASIC-10(十进制转十六进制)

复制代码
#include<cstdio>
int main()
{
    int n;
    scanf("%d",&n);
    printf("%X
",n);//注意X
    return 0;
}
复制代码

BASIC-11(十六进制转十进制)

复制代码
#include<cstdio>
int main()
{
    long long n;
    scanf("%I64X",&n);
    printf("%I64d
",n);
    return 0;
}
复制代码

BASIC-12(十六进制转八进制)

一位16进制相应四位2进制，一位8进制相应三位2进制，三位16进制相应四位8进制(也能够六位相应八位....)

复制代码
#include<cstdio>
#include<cstring>
int getnu(char c){
    if(c>='0' && c<='9')return c-'0';
    return c-'A'+10;
}
void putans(char *s){
    int ans=0;
    for(int i=0;i<3;i++)
        ans=ans*16+getnu(s[i]);
    printf("%04o",ans);
}
int main()
{
    int n;
    char a[100010];
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%s",a);
        int len=strlen(a);
        int flen=(len-1)%3+1;
        int ans=0;
        for(int i=0;i<flen;i++)
            ans=ans*16+getnu(a[i]);
        printf("%o",ans);
        for(int j=flen;j<len;j+=3)putans(a+j);
        printf("
");
    }
    return 0;
}
复制代码

BASIC-13(数列排序)

你们老师有没有教sort()，我们老师没有

复制代码
#include<cstdio>
#include<algorithm>
using namespace std;
int main()
{
    int a[210],n;
    scanf("%d",&n);
    for(int i=0;i<n;i++)scanf("%d",&a[i]);
    sort(a,a+n);
    for(int i=0;i<n-1;i++)printf("%d ",a[i]);printf("%d
",a[n-1]);
    return 0;
}
复制代码

 ALGO-1(区间k大数查询)

排序啊 排序

 View Code

ALGO-2(最大最小公倍数)

不纠结。题目数据有问题

顺带提：此题是丽洁桑高中时在CF上出的题146A

复制代码
#include<cstdio>
//1-n中取三个数
int main()
{
    long long n,ans;
    scanf("%I64d",&n);
    if(n<3)ans=n;
    else{
        if(n&1)ans=n*(n-1)*(n-2);
        else{
            if(n%6==0)ans=(n-1)*(n-2)*(n-3);
            else ans=n*(n-1)*(n-3);
        }
    }
    printf("%I64d
",ans);
    return 0;
}
复制代码

ALGO-3(K好数)

DP 先存下第n-1位为0-(k-1)分别的个数,依据第n-1位为0-(k-1)的个数推出第n位为0-(k-1)的个数,最后对第L位的0-(k-1)分别的个数求和

复制代码
#include<cstdio>
#include<cmath>
using namespace std;
const int Mod=1000000007; 
int main()
{
    int k,l,dp[110][110]={0},ans=0;
    scanf("%d%d",&k,&l);
    if(l<2)ans=k*l;//我认为这里的k不应该减一。可是题目中这里的k须要减掉1才干过掉第一组数据（好坑） 
    else{
        dp[0][1]=0;
        for(int i=1;i<k;i++)dp[i][1]=1;
        for(int j=2;j<=l;j++){
            for(int i=0;i<k;i++){
                for(int h=0;h<k;h++){
                    if(abs(h-i)!=1)dp[i][j]=(dp[i][j]+dp[h][j-1])%Mod;//abs()=1时表示是相邻的数字 
                }
            }
        }
        for(int i=0;i<k;i++){
            ans=(ans+dp[i][l])%Mod;
        }
    }
    printf("%d
",ans);
    return 0;
}
复制代码

ALGO-4(节点选择)

树形DP 从图中任选一点作为根节点，得到生成树,再在生成树上从叶子节点向上DP

复制代码
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define MAXN 100010
int Head[MAXN],Head0[MAXN],n,V[MAXN],D[MAXN],Son[MAXN],GSon[MAXN],mk=0;
bool f[MAXN];
struct EdgeNode{
    int to,next;
}Edges[MAXN],Edges0[MAXN<<1];
void DFS(int s){//递归 
    int k=Head[s];
    D[s]=V[s];
    while(k>=0){
        if(D[Edges[k].to]<0)DFS(Edges[k].to);
        Son[s]+=D[Edges[k].to];
        GSon[s]+=Son[Edges[k].to];
        k=Edges[k].next;
    }
    D[s]=max(D[s]+GSon[s],Son[s]);
}
void GtoT(int u){//生成树
    int k=Head0[u];
    while(k>=0){
        if(!f[Edges0[k].to]){
            f[Edges0[k].to]=true;
            Edges[mk].to=Edges0[k].to;
            Edges[mk].next=Head[u];
            Head[u]=mk;
            mk++;
            GtoT(Edges0[k].to); 
        }
        k=Edges0[k].next;
    }
}
void Swap(int &a,int &b){
    int c=a;
    a=b;
    b=c;
}
int main()
{
    int u,v;
    scanf("%d",&n);
    memset(Head,-1,sizeof(Head));
    memset(Head0,-1,sizeof(Head0));
    memset(D,-1,sizeof(D));
    memset(Son,0,sizeof(Son));
    memset(GSon,0,sizeof(GSon));
    for(int i=1;i<=n;i++)scanf("%d",&V[i]);
    for(int i=0;i<2*n-2;i++){//生成图。双向 
        scanf("%d%d",&u,&v);
        Edges0[i].to=v;
        Edges0[i].next=Head0[u];
        Head0[u]=i++;
        Swap(u,v);
        Edges0[i].to=v;
        Edges0[i].next=Head0[u];
        Head0[u]=i;
    }
    memset(f,false,sizeof(f));
    f[1]=true;//图中任选一点。这里选结点1 
    GtoT(1); 
    DFS(1);
    printf("%d
",D[1]);
    return 0;
}
复制代码

ALGO-5(最短路)

存在负边所以不能用Dijkstra,SPFA比Bellman-Ford快,赤裸裸的套模版

复制代码
#include<cstdio>
#include<cstring>
#define MAXN 20010
#define MAXM 200010
#define INF 200000
int Head[MAXN],n,m,Dist[MAXN];
struct EdgeNode{
    int to,w,next;
}Edges[MAXM];
void SPFA(int s){//题目说不存在负环，所以没实现推断负环存在功能 
    int Que[MAXN],Iq=0;
    bool Visit[MAXN];
    for(int i=0;i<=n;i++)Dist[i]=INF;
    memset(Visit,false,sizeof(Visit));
    Dist[s]=0;
    Visit[s]=true;
    Que[Iq++]=s;
    int Id=0;
    while(Id!=Iq){
        int top=Que[Id];
        Visit[top]=false;
        int k=Head[top];
        while(k>=0){
            if(Dist[Edges[k].to]>Edges[k].w+Dist[top]){
                Dist[Edges[k].to]=Edges[k].w+Dist[top];
                if(!Visit[Edges[k].to]){
                    Que[Iq++]=Edges[k].to;
                    Visit[Edges[k].to]=true;
                }
            }
            k=Edges[k].next;
        }
        Id++;
    }
}
int main()
{
    int u,v,l;
    scanf("%d%d",&n,&m);
    memset(Head,-1,sizeof(Head));
    for(int i=0;i<m;i++){//链式前向星建图 
        scanf("%d%d%d",&u,&v,&l);
        Edges[i].to=v;
        Edges[i].w=l;
        Edges[i].next=Head[u];
        Head[u]=i;
    }
    SPFA(1);
    for(int i=2;i<=n;i++)printf("%d
",Dist[i]);
    return 0;
}
复制代码

ALGO-6(安慰奶牛)

题目关键在于怎样转换成构建最小生成树的形式
假如如今我们已经生成了最小生成树，不难发现：
1.一个节点有几个度。就须要訪问该节点(牧场)的奶牛几次+訪问一次过夜牧场的奶牛
2.每条边(路)都要走两次
如此便可进行转换：
每条边的权可改为:走该条路须要的时间*2+路两端的奶牛交谈须要的时间
即：Li*2+C[Si]+C[Ei]
然后执行一遍最小生成树
过夜牧场自然选择与奶牛交谈时间最少的

复制代码
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXM=100010;
const int MAXN=10010;
int f[MAXN];
int find(int x){
    if(f[x]==x)return x;
    return find(f[x]);
}
void Merge(int x,int y){
    f[y]=x;
}
struct Edge{
    int a,b,v;
}e[MAXM];
bool cmp(Edge a,Edge b){
    return a.v<b.v;
}
int main()
{
    int ans=0,k=1,N,P,C[MAXN];
    scanf("%d%d",&N,&P);
    for(int i=1;i<=N;i++){
        scanf("%d",&C[i]);
        if(C[i]<C[k])k=i;//选择过夜牧场 
    }
    ans+=C[k];
    for(int i=0;i<P;i++){
        scanf("%d%d%d",&e[i].a,&e[i].b,&e[i].v);
        e[i].v<<=1;//边权重构
        e[i].v+=C[e[i].a]+C[e[i].b];
    }
    sort(e,e+P,cmp);
    k=0;
    for(int i=1;i<=N;i++)f[i]=i;
    for(int i=0;i<P;i++){//Kruskal 
        int x=find(e[i].a);//并查集 
        int y=find(e[i].b);
        if(x!=y){
            k++;
            ans+=e[i].v;
            Merge(x,y);
        }
        if(k==N-1)break;
    }
    printf("%d
",ans);
    return 0;
}
复制代码

ALGO-7(逆序对)

平衡树。SBT;外加一些分治。回溯思想，一顿胡搞。

先求同一颗树下两颗子树分别的逆序对数。然后求两颗子树交换前后两者间的逆序对数。取小值，递归求和。

先上未整理的杂乱代码

复制代码
#include<cstdio>
#include<algorithm>
using namespace std;
#define MAXN 200005
int n,m;
long long ans;
//SBT,Size Blance Tree
int S[MAXN],Left[MAXN],Right[MAXN];
unsigned int Key[MAXN];
int Left_Rotate(int rt){
    int k=Right[rt];
    Right[rt]=Left[k];
    Left[k]=rt;
    S[k]=S[rt];
    S[rt]=S[Left[rt]]+S[Right[rt]]+1;
    return rt=k;
}
int Right_Rotate(int rt){
    int k=Left[rt];
    Left[rt]=Right[k];
    Right[k]=rt;
    S[k]=S[rt];
    S[rt]=S[Left[rt]]+S[Right[rt]]+1;
    return rt=k;
}
int Maintain(int rt,bool flag){
    if(flag){
        if(S[Left[Right[rt]]]>S[Left[rt]] || S[Right[Right[rt]]]>S[Left[rt]]){
            if(S[Left[Right[rt]]]>S[Left[rt]])Right[rt]=Right_Rotate(Right[rt]);
            return Left_Rotate(rt);
        }
    }
    else{
        if(S[Right[Left[rt]]]>S[Right[rt]] || S[Left[Left[rt]]]>S[Right[rt]]){
            if(S[Right[Left[rt]]]>S[Right[rt]])Left[rt]=Left_Rotate(Left[rt]);
            return Right_Rotate(rt);
        }
    }
    return rt;
}
int Insert(int rt,int RT){
    S[rt]+=1;
    if(Key[RT]>Key[rt]){
        if(Right[rt]>0)Right[rt]=Insert(Right[rt],RT);
        else{
            Right[rt]=RT;
        }
    }
    else{
        if(Left[rt]>0)Left[rt]=Insert(Left[rt],RT);
        else{
            Left[rt]=RT;
        }
    }
    return rt=Maintain(rt,Key[RT]>Key[rt]);
}
int Rank(int rt,int v){
    if(v>Key[rt]){
        if(Right[rt]==0)return S[rt];
        return S[rt]-S[Right[rt]]+Rank(Right[rt],v);
    }
    if(Left[rt]==0)return 0;
    return Rank(Left[rt],v);
}
int Merge(int rt,int Start,int End){
    long long lans=0,rans=0;
    for(int i=Start;i<=End;i++){
        lans+=Rank(rt,Key[i]);
        rans+=S[rt]-Rank(rt,Key[i]+1);
    }
    for(int i=Start;i<=End;i++){
        S[i]=1;
        Left[i]=Right[i]=0;
        rt=Insert(rt,i);
    }
    ans+=min(lans,rans);
    return rt;
}
int Init(){
    int v;
    scanf("%d",&v);
    if(v){
        Key[++m]=v;
        S[m]=1;
        Left[m]=Right[m]=0;
        return m;
    }
    int TL,TR,Ls,Le,Rs,Re;
    Ls=m+1;
    TL=Init();
    Le=m;
    Rs=m+1;
    TR=Init();
    Re=m;
    if(S[TL]<S[TR])return Merge(TR,Ls,Le);
    return Merge(TL,Rs,Re);
}
int main()
{
    scanf("%d",&n);
    Init();
    printf("%I64d
",ans);
    return 0;
}
复制代码

用红黑树拓展一下应该过也没问题

ALGO-8(操作格子)

线段树（实现区间最大值查询O(logn)）+树状数组（实现区间求和查询O(logn)）

复制代码
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define MAXN 100001
int s=1,n,Seg[MAXN<<2],BIT[MAXN];
void Seg_RefUp(int i,int c){//线段树更新O(logn)
    Seg[i]=c;
    while(i>1){
        i>>=1;
        int e=Seg[i];
        Seg[i]=max(Seg[i<<1],Seg[i<<1|1]);
        if(e==Seg[i])return;
    }
}
void BIT_RefUp(int k,int c){//树状数组更新O(logn)
        while(k<=n){
            BIT[k]+=c;
            k+=k&-k;
        }
}
void BuildSegAndBIT(){//建线段树和树状数组(时间复杂度和空间复杂度实际上都是O(n))
    memset(Seg,0,sizeof(Seg));
    memset(BIT,0,sizeof(BIT));
    while(s<n)
        s<<=1;
    s--;
    int c;
    for(int i=1;i<=n;i++){
        scanf("%d",&c);
        Seg_RefUp(s+i,c);
        BIT_RefUp(i,c);
    }
}
int BIT_Query(int a,int b){//树状数组查询O(logn)
    int ans=0;
    while(b>0){
        ans+=BIT[b];
        b-=b&-b;
    }
    a--;
    while(a>0){
        ans-=BIT[a];
        a-=a&-a;
    }
    return ans;
}
int Seg_Query(int a,int b,int k,int l,int r){//线段数查询O(logn)
    if(a<=l && b>=r)return Seg[k];
    if(a>r || b<l)return 0;
    return max(Seg_Query(a,b,k<<1,l,(l+r)>>1),Seg_Query(a,b,(k<<1)+1,((l+r)>>1)+1,r));
}
int main()
{
    int m,p,x,y;
    scanf("%d%d",&n,&m);
    BuildSegAndBIT();
    for(int i=0;i<m;i++){
        scanf("%d%d%d",&p,&x,&y);
        if(p==1){
            BIT_RefUp(x,y-Seg[s+x]);
            Seg_RefUp(s+x,y);
        }
        if(p==2)
            printf("%d
",BIT_Query(x,y));
        if(p==3)
            printf("%d
",Seg_Query(x,y,1,1,s+1));
    }
    return 0;
}
复制代码

ADV-1(两条直线)

对全部坐标按(x+y,x-y)排序,反过来排也行。然后用O(n)时间求前i个坐标的最大最小x-y和后i个坐标的最大最小x-y

然后二分搜索最小答案，在推断二分出的值是否满足正确性时，依据(x+y)的递增性能够再应用一次二分

复制代码
#include<cstdio>
#include<algorithm>
using namespace std;
#define MAXN 100010
int n;
double lmin[MAXN],lmax[MAXN],rmin[MAXN],rmax[MAXN];//lmin[i],lmax[i]分别存前i个x-y的最大最小值。对应的rmin[],rmax[]你们懂
struct hmd{
    int aa,bb;
    double a,b;
}e[MAXN];
bool cmp(hmd p,hmd q){
    if(p.aa!=q.aa)
        return p.aa<q.aa;
    return p.bb<q.bb;
}
bool Is(double ans){
    for(int i=0;i<n;i++){
        int l=i+1,j=n;
        while(l<j){//二分搜索第一个j使e[j].a-e[i].a>ans*2
            int m=(l+j)/2;
            if(e[m].a-e[i].a>ans*2)j=m;
            else l=m+1;
        }
        int d=0;
        double Min=0,Max=0;
        if(i>0){
            Min=lmin[i-1];
            Max=lmax[i-1];
            d=1;
        }
        if(j<n){
            if(d){
                Min=min(Min,rmin[j]);
                Max=max(Max,rmax[j]);
            }else{
                Min=rmin[j];
                Max=rmax[j];
            }
        }
        if(Max-Min<=ans*2)return true;
    }
    return false;
}
int main()
{
    int x,y;
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d%d",&x,&y);
        e[i].aa=x+y;
        e[i].a=e[i].aa;
        e[i].bb=x-y;
        e[i].b=e[i].bb;
    }
    sort(e,e+n,cmp);
    lmin[0]=lmax[0]=e[0].b;
    for(int i=1;i<n;i++){
        lmin[i]=min(lmin[i-1],e[i].b);
        lmax[i]=max(lmax[i-1],e[i].b);
    }
    rmin[n-1]=rmax[n-1]=e[n-1].b;
    for(int i=n-2;i>=0;i--){
        rmin[i]=min(rmin[i+1],e[i].b);
        rmax[i]=max(rmax[i+1],e[i].b);
    }
    double L=0,R=1e9;
    while(R-L>1e-2){//二分搜索最小的最大曼哈顿距离的值
        double M=(L+R)/2;
        if(Is(M))R=M;
        else L=M;
    }
    printf("%.1lf
",L);
    return 0;
}
复制代码

ADV-2

无

ADV-3(金属採集)

以S为根节点向下深搜。回溯向上DP
dp[x][i]表示在以x为根节点的子树上用i个机器人採集时的最小花费
jqr[x]存当前以x为根节点的子树上最多能够jqr[x]个机器人
当两颗子树a,b汇到同一父亲c节点上时
dp[c][i]=min(dp[a][j]+dp[b][k]+k*(c节点到b节点的距离))（c节点到a节点的距离为0；j+k=i；j<=jqr[a],k<=jqr[b]）
dp[c][0]=以c为根节点的子树上的全部边的边权*2的和

复制代码
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
#define MAXN 100010
int head[MAXN],dp[MAXN][11],du[MAXN],jqr[MAXN],n,s,k,m;
bool vis[MAXN];
struct Edge{
    int to,next,w;
}e[MAXN<<1];
void add_edge(int u,int v,int c){
    e[m].to=v;
    e[m].w=c;
    e[m].next=head[u];
    head[u]=m++;
}
void dfs(int x,int w){
    vis[x]=true;
    if(du[x]==1 && x!=s){//为了方便推断叶子节点，这里用到了节点的度 (一课树上度为1的是叶子节点，根节点除外)
        jqr[x]=1;//叶子节点初始化一个不工作的机器人 
        dp[x][0]+=w*2;// dfs()最后一行解释 
        return;
    }
    int d=head[x];
    while(d>=0){
        int y=e[d].to;
        if(!vis[y]){
            dfs(y,e[d].w);
            for(int i=min(k,jqr[x]+jqr[y]);i>0;i--){
                int xf,count=0;
                for(int a=min(i,jqr[y]);a>=0;a--){
                    int b=i-a;
                    if(b>jqr[x])break;//x是x的一颗距离为0的子树 
                    if(count>0)xf=min(xf,dp[x][b]+dp[y][a]+e[d].w*a);
                    else{
                        xf=dp[x][b]+dp[y][a]+e[d].w*a;
                        count++;
                    }
                }
                dp[x][i]=xf;
            }
            dp[x][0]+=dp[y][0];
            jqr[x]+=jqr[y];
        }
        d=e[d].next;
    }
    dp[x][0]+=w*2;//为了方便写转移方程。将父亲节点到其某一子树根节点的距离累加到子树上，这样到该子树上的距离为0 
}
void work(){
    dfs(s,0);
    int ans=dp[s][0];
    for(int i=1;i<=k && dp[s][i]>0;i++)if(dp[s][i]<ans)ans=dp[s][i];
    printf("%d
",ans);
}
void init(){
    scanf("%d%d%d",&n,&s,&k);
    int x,y,w;
    memset(head,-1,sizeof(head));
    for(int i=1;i<n;i++){
        scanf("%d%d%d",&x,&y,&w);
        du[x]++;
        du[y]++;
        add_edge(x,y,w);
        add_edge(y,x,w);
    }
}
int main()
{
    init();
    work();
    return 0;
}
复制代码

ADV-4(道路和航路)

有道路连接的点都属于强连通块
并查集储存强连通块
航路是强连通块间的有向道路
航路指向的强连通块入度加1
依次求入度为0的强连通块内点的最短路，然后更新该块发出的航路的连接点，接着去掉该航路(对应入度减1)
并查集+链式前向星存图
优先队列+Dijkstra求最短路

复制代码
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
const int MAXN=25010;
const int MAXE=150010;
int head[MAXN],size,HEAD[MAXN],SIZE;

struct Edge{
    int to,next,w;
}edge[MAXE],EDGE[50010];
void edge_Add(int u,int v,int l){
    edge[size].to=v;
    edge[size].w=l;
    edge[size].next=head[u];
    head[u]=size++;
}
void EDGE_Add(int u,int v){
    EDGE[SIZE].to=v;
    EDGE[SIZE].next=HEAD[u];
    HEAD[u]=SIZE++;
}
int par[MAXN],rank[MAXN];
int find(int x){
    if(x==par[x])return x;
    return par[x]=find(par[x]);
}
void merge(int x,int y){
    x=find(x);
    y=find(y);
    if(x==y)return;
    if(rank[x] < rank[y])par[x]=y;
    else{
        par[y]=x;
        if(rank[x]==rank[y])rank[y]++;
    }
}
bool isvis[MAXN];
void DFS_isvis(int s){
    isvis[s]=true;
    for(int k=head[s];k>=0;k=edge[k].next)if(!isvis[edge[k].to])DFS_isvis(edge[k].to);
}
int indegree[MAXN],dist[MAXN];
bool p[MAXN];
void Dijkstra(int s){
    queue<int> degree0;
    priority_queue<pair<int,int> > heap;
    dist[s]=0;
    heap.push(make_pair(0,s));
    while(!heap.empty() || !degree0.empty()){
        if(heap.empty()){
            int u=degree0.front();
            degree0.pop();
            for(int k=HEAD[u];k>=0;k=EDGE[k].next){
                int v=EDGE[k].to;
                heap.push(make_pair(-dist[v],v));
            }
        }else{
            int u=heap.top().second;
            heap.pop();
            if(p[u])continue;
            p[u]=true;
            for(int k=head[u];k>=0;k=edge[k].next){
                int v=edge[k].to;
                if(!p[v] && dist[v]>dist[u]+edge[k].w){
                    dist[v]=dist[u]+edge[k].w;
                    if(find(u)==find(v))heap.push(make_pair(-dist[v],v));
                }
                if(find(u)!=find(v)){
                    indegree[find(v)]--;
                    if(indegree[find(v)]==0)degree0.push(find(v));
                }
            }
        }
    }
}
int main()
{
    int n,r,p,s,a,b,c,d=0,U[50010],V[50010];
    scanf("%d%d%d%d",&n,&r,&p,&s);
    for(int i=1;i<=n;i++){
        par[i]=i;
        rank[i]=0;
        head[i]=HEAD[i]=-1;
    }
    for(int i=0;i<r;i++){
        scanf("%d%d%d",&a,&b,&c);
        edge_Add(a,b,c);
        edge_Add(b,a,c);
        merge(a,b);
    }
    for(int i=0;i<p;i++){
        scanf("%d%d%d",&a,&b,&c);
        U[d]=a;
        V[d++]=b;
        edge_Add(a,b,c);
    }
    DFS_isvis(s);
    for(int i=0;i<p;i++)if(isvis[U[i]]){
        indegree[find(V[i])]++;
        EDGE_Add(find(V[i]),V[i]);
    }
    for(int i=1;i<=n;i++)dist[i]=2000000000;
    Dijkstra(s);
    for(int i=1;i<=n;i++)if(isvis[i])printf("%d
",dist[i]);else puts("NO PATH");
    return 0;
}
复制代码

ADV-5(最小方差生成树)

不纠结，题目数据有问题(求VIP给的)，目測第4到第6组也有问题，第2到第3组肯定有问题

一份粗糙代码

复制代码
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
#define MAXN 55
#define MAXM 1010
int n,m,U[MAXM],V[MAXM],f[MAXN],Case;
double W[MAXM],Min,Max,cw[MAXN];
struct edge{
    int id;
    double wf;
}e[MAXM];
bool cmp(edge a,edge b){
    return a.wf<b.wf;
}
void merge(int x,int y){
    int c=f[y];
    for(int i=1;i<=n;i++)if(f[i]==c)f[i]=f[x];
}
double MST(){
    int k=n;
    double sum=0,fcz=0;
    for(int i=1;i<=n;i++)f[i]=i;
    for(int i=0;i<m;i++){
        if(k==1)break;
        int Id=e[i].id;
        if(f[U[Id]]!=f[V[Id]]){
            merge(U[Id],V[Id]);
            cw[--k]=W[Id];
            sum+=cw[k];
        }
    }
    sum/=(n-1);
    for(int i=1;i<n;i++){
        fcz+=(sum-cw[i])*(sum-cw[i]);
    }
    return fcz/(n-1);
}
void work(){
    double ans=10000;
    for(double pw=Min;pw<=Max;pw+=0.25){
        for(int i=0;i<m;i++){
            e[i].id=i;
            e[i].wf=abs(W[i]-pw);
        }
        sort(e,e+m,cmp);
        ans=min(ans,MST());
    }
    printf("Case %d: %.2lf
",++Case,ans);
}
void init(){
    Min=50;
    Max=0;
    for(int i=0;i<m;i++){
        scanf("%d%d%lf",&U[i],&V[i],&W[i]);
        if(W[i]>Max)Max=W[i];
        if(W[i]<Min)Min=W[i];
    }
}
int main()
{
    while(scanf("%d%d",&n,&m),n){
        init();
        if(n==1){
            printf("0
");
            continue;
        }
        work();
    }
    return 0;
}
复制代码

PREV-1(核桃的数量)

复制代码
#include<cstdio>
int gcd(int x,int y){//求x,y两者的最大公约数
    int z;
    while(y){
        z=x%y;
        x=y;
        y=z;
    }
    return x;
}
int main()
{
    int a,b,c,ans;
    scanf("%d%d%d",&a,&b,&c);
    ans=a*b/gcd(a,b);//a,b,c<30
    ans=ans*c/gcd(ans,c);
    printf("%d
",ans); 
    return 0;
}
复制代码

PREV-2(打印十字图)

没什么好说的，渣渣填充二维数组

复制代码
#include<cstdio>
#define MAX 125
int main()
{
    char g[MAX][MAX],a='$',b='.';
    int n,center=63;
    for(int i=0;i<MAX;i++)for(int j=0;j<MAX;j++)g[i][j]=b;
    scanf("%d",&n);n++;
    for(int k=1;k<=n;k++){
        int s=center-k*2,e=center+k*2;
        for(int i=s+2;i<=e-2;i++)g[i][s]=g[i][e]=g[s][i]=g[e][i]=a;
        s++;e--;
        int ss=s+1,ee=e-1;
        g[s][ss]=g[s][ee]=g[ss][s]=g[ss][e]=g[ee][s]=g[ee][e]=g[e][ss]=g[e][ee]=g[ss][ss]=g[ss][ee]=g[ee][ss]=g[ee][ee]=a;
    }
    n<<=1;
    for(int i=center-n;i<=center+n;i++){
        for(int j=center-n;j<=center+n;j++)printf("%c",g[i][j]);printf("
");
    }
    return 0;
}
复制代码

PREV-3(带分数)

具体解释：

http://www.cnblogs.com/cshhr/p/3584271.html

PREV-4

不多说，我是弱渣做不出，尽管我过了

PREV-5(错误票据)

看了数据范围(不大于100000)。果断定义数组，不用排序。不用比較。速度妥妥的

sstream是老师教的

复制代码
#include<cstdio>
#include<sstream>
#include<string>
#include<iostream>
using namespace std;
int f[100010];
int main()
{
    int n,max=0,min=100010,c;
    string s;
    scanf("%d",&n);
    getline(cin,s);
    for(int i=0;i<n;i++){
        getline(cin,s);
        istringstream ss(s);
        while(ss>>c){
            f[c]++;
            if(c<min)min=c;
            if(c>max)max=c;
        }
    }
    for(int i=min;i<max;i++){
        if(f[i]==0)n=i;
        if(f[i]==2)c=i;
    }
    printf("%d %d
",n,c);
    return 0;
}
复制代码

PREV-6(翻硬币)

贪心，字符从头到尾一个个推断，不一样就翻

复制代码
#include<cstdio>
#include<cstring>
int main()
{
    int ans=0;
    char a[1010],b[1010];
    scanf("%s%s",&a,&b);
    for(int i=0;i<strlen(a)-1;i++)if(a[i]!=b[i]){
        ans++;
        if(b[i+1]=='o')b[i+1]='*';else b[i+1]='o';
    }
    printf("%d
",ans);
    return 0;
}
复制代码

PREV-7(连号区间数)

n<=50000,推断每一个区间[l,r]先求最大最小值，再求差，时间复杂度为O(3*(r-l)),区间[l,r]能够从[l,r-1]递推上路推断。所以总的时间复杂度为O(n^2)

本以为会有几组数据超时，结果全过了。弱渣想不到并查集怎样运用T>.<T

复制代码
#include<cstdio>
#define MAXN 50010
int main()
{
    int n,ans=0,a[MAXN],max,min;
    scanf("%d",&n);
    for(int i=0;i<n;i++)scanf("%d",&a[i]);
    ans+=n;
    for(int i=0;i<n;i++){
        max=min=a[i];
        for(int j=i+1;j<n;j++){
            if(a[j]>max)max=a[j];
            if(a[j]<min)min=a[j];
            if(j-i==max-min)ans++;
        }
    }
    printf("%d
",ans);
    return 0;
}
复制代码

看了锦囊，这比用并查集还快？

PREV-8(买不到的数目)

a*b-a-b望大神贡献证明过程

复制代码
#include<cstdio>
int main()
{
    int a,b;
    scanf("%d%d",&a,&b);
    printf("%d
",a*b-a-b);
    return 0;
}
复制代码

PREV-9(大臣的旅费)

具体解释：

http://www.cnblogs.com/cshhr/p/3584271.html

PREV-10(幸运数)

模拟取幸运数过程
现初始化取出全部奇数(题目中，第二个位置的数被两次作为选数基数)
每次剔除非幸运数时，未被剔除的数的当前位置应及时减去前面的被剔除个数
由于依照规律，两幸运数相隔应该不是非常大，
所以查询一个数的不大于她的一个近期幸运数的位置应该非常easy

复制代码
#include<cstdio>
#define MAXN 1000010
bool flag[MAXN];
int m,n,a[MAXN],s[MAXN],size=0;//a[i]存储幸运数i的位置(幸运数列中的) 
int fa(int k){
    if(flag[k])return a[k];
    return fa(k-1);
}
int main()
{
    scanf("%d%d",&m,&n);
    for(int i=1;i<=n;i+=2){
        s[++size]=i;//s[]存储幸运数列 
        flag[i]=true;//f[i]存储i是否为幸运数 
        a[i]=size;
    }
    for(int i=2;i<=size;i++){
        int Mod=s[i],d=s[i]-1;
        if(Mod>size)break;
        for(int p=1,j=Mod;j<=size;j+=Mod,p++){
            flag[s[j]]=false;
            for(int k=1;k<Mod&&k+j<=size;k++){
                s[++d]=s[j+k];
                a[s[j+k]]-=p;
            }
        }
        size=d;
    }
    printf("%d
",fa(n-1)-fa(m));
    return 0;
}
复制代码

弱渣想问，用堆怎样来做
PREV-11(横向打印二叉树)

普通二分搜索树的建立，打印的格式要注意的地方是每一个数的字符串形式的长度

复制代码
#include<cstdio>
#include<sstream>
#include<string>
#include<iostream>
using namespace std;
#define MAXN 110
#define MAXM 710
struct Node{
    int left,right,left_s,right_s,v,id,ak;
    char a[10];
}Nodes[MAXN];
char map[MAXN][MAXN],a='.',b='-',c='|',d='';
void BinaryTree_set(int rt,int k){
    if(Nodes[k].v>Nodes[rt].v){
        Nodes[rt].right_s++;
        if(Nodes[rt].right!=-1)BinaryTree_set(Nodes[rt].right,k);
        else Nodes[rt].right=k;
    }
    else{
        Nodes[rt].left_s++;
        if(Nodes[rt].left!=-1)BinaryTree_set(Nodes[rt].left,k);
        else Nodes[rt].left=k;
    }
}
void Id_set(int rid,int k){
    Nodes[k].id=rid+Nodes[k].right_s+1;
    if(Nodes[k].right!=-1)Id_set(rid,Nodes[k].right);
    if(Nodes[k].left!=-1)Id_set(Nodes[k].id,Nodes[k].left);
}
void Map_set(int k,int index){
    for(int i=0;i<Nodes[k].ak;i++)map[Nodes[k].id][index+i]=Nodes[k].a[Nodes[k].ak-1-i];
    index+=Nodes[k].ak;
    if(Nodes[k].left!=-1 || Nodes[k].right!=-1){
        map[Nodes[k].id][index++]=b;
        int max,min;
        max=min=Nodes[k].id;
        if(Nodes[k].left!=-1){
            max=Nodes[Nodes[k].left].id;
            map[Nodes[Nodes[k].left].id][index+1]=b;
            Map_set(Nodes[k].left,index+2);
        }
        if(Nodes[k].right!=-1){
            min=Nodes[Nodes[k].right].id;
            map[Nodes[Nodes[k].right].id][index+1]=b;
            Map_set(Nodes[k].right,index+2);
        }
        for(int i=min;i<=max;i++)map[i][index]=c;
        map[Nodes[k].id][index+1]=d;
    }
    else{
        map[Nodes[k].id][index]=d;
        return;
    }
}
int main()
{
    int n=0,e,A[MAXN];
    string s;
    getline(cin,s);
    istringstream ss(s);
    while(ss>>e)A[n++]=e;
    for(int i=0;i<n;i++){
        e=A[i];
        Nodes[i].left=Nodes[i].right=-1;
        Nodes[i].left_s=Nodes[i].right_s=0;
        Nodes[i].ak=0;
        Nodes[i].v=e;
        while(e){
            Nodes[i].a[Nodes[i].ak++]=e%10+'0';
            e/=10;
        }
    }
    for(int i=1;i<n;i++)BinaryTree_set(0,i);
    Id_set(0,0);
    for(int i=1;i<=n;i++)for(int j=0;j<MAXM;j++)map[i][j]=a;
    Map_set(0,0);
    for(int i=1;i<=n;i++)printf("%s
",map[i]);
    return 0;
}
复制代码

PREV-12(危急系数)

枚举除x,y外的n-2个点，除去枚举点所连的全部边。对除枚举点外全部的点生成树

复制代码
#include<cstdio>
#define MAXN 1010
#define MAXM 2010
int E[MAXN],U[MAXM],V[MAXM],n,m,x,y,ans=-1;
void Merge(int a,int b){
    int c=E[b];
    for(int i=1;i<=n;i++)if(E[i]==c)E[i]=E[a];
}
void MinSpanTree(int t){
    for(int i=0;i<m;i++){
        if(U[i]==t || V[i]==t)continue;
        if(E[U[i]]!=E[V[i]])Merge(U[i],V[i]);
        if(E[x]==E[y])break;
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;i++)scanf("%d%d",&U[i],&V[i]);
    scanf("%d%d",&x,&y);
    for(int j=1;j<=n;j++)E[j]=j;
    MinSpanTree(0);
    if(E[x]==E[y])ans++;//推断两点是否连通 
    if(ans!=-1)for(int i=1;i<=n;i++){
        if(i==x || i==y)continue;
        for(int j=1;j<=n;j++)E[j]=j;
        MinSpanTree(i);
        if(E[x]!=E[y])ans++;//推断出去i点后，两点是否连通 
    }
    printf("%d
",ans);
    return 0;
}
复制代码

PREV-13(网络寻路)

枚举每条边作为两转发点的联通路径
枚举的边的两点的其它度相乘 便是以该两点作为转发点全部路径数，记得通信是双向的

复制代码
#include<cstdio>
#include<cstring>
#define MAXN 10010
#define MAXM 100010
int Du[MAXN],U[MAXM],V[MAXM];
int main()
{
    int n,m;
    long long ans=0;
    scanf("%d%d",&n,&m);
    memset(Du,0,sizeof(Du));
    for(int i=0;i<m;i++){
        scanf("%d%d",&U[i],&V[i]);
        Du[U[i]]++;
        Du[V[i]]++;
    }
    for(int i=0;i<m;i++)if(Du[U[i]]>1&&Du[V[i]]>1)ans+=(Du[U[i]]-1)*(Du[V[i]]-1)*2;//我在想，这里的Du是不是也应该定义成long long型(特例好像会溢出，但測试数据中没有) 
    printf("%I64d
",ans);
    return 0;
}
复制代码

PREV-14(高僧斗法)

博弈（hdu1850能够去看看）

复制代码
#include<cstdio>
#include<string>
#include<sstream>
#include<iostream>
using namespace std;
#define MAXN 110
int a[MAXN],b[MAXN],n,t;
int main()
{
    string s;
    getline(cin,s);
    istringstream ss(s);
    while(ss>>t)a[n++]=t;
    for(int i=0;i<n-1;i++)b[i]=a[i+1]-a[i]-1;
    int sss=0;
    for(int i=0;i<n-1;i+=2)sss^=b[i];
    if(sss==0){
        printf("-1
");
        return 0;
    }
    for(int i=0;i<n-1;i++){
        if(i&1){
            if(b[i]>=(sss^b[i-1])-b[i-1]){
                printf("%d %d
",a[i],a[i]+(sss^b[i-1])-b[i-1]);
                return 0;
            }
        }
        else{
            if(b[i]>(sss^b[i])){
                printf("%d %d
",a[i],a[i]+(b[i]-(sss^b[i])));
                return 0;
            }
        }
    }
    printf("-1
");
    return 0;
}
复制代码

PREV-15(格子刷油漆)

DP

复制代码
/*
    当n>1时，刷油漆能够分为5个状态
    顺序为a->b->c->d
    或a->b->...->c->d(状态3)
状态1)(可由状态1,2得来)
..ac    ..ab
..db    ..dc
状态2)(可由状态2,3,4,5得来)
..bc    ..bd    ..ad    ..ac
..ad    ..ac    ..bc    ..bd
状态3)(可由状态3得来)
..ba    ..ca
..cd    ..bd
状态4)(可由状态2得来)
..ba    ..dc
..dc    ..ba
状态5)(可由状态2得来)
..ad    ..cb
..cb    ..ad

*/
#include<cstdio>
#define MAXN 1010
#define MOD 1000000007
int main()
{
    long long DP[5][MAXN],ans=2;
    int n;
    scanf("%d",&n);
    if(n>1){
        DP[0][2]=DP[2][2]=DP[3][2]=DP[4][2]=4;
        DP[1][2]=8;
        for(int i=3;i<=n;i++){
            DP[0][i]=(DP[0][i-1]*2+DP[1][i-1]*2)%MOD;
            DP[1][i]=(DP[1][i-1]*2+DP[2][i-1]*4+DP[3][i-1]*2+DP[4][i-1]*2)%MOD;
            DP[2][i]=DP[2][i-1]*2%MOD;
            DP[3][i]=DP[1][i-1];
            DP[4][i]=DP[1][i-1];
        }
        ans=0;
        for(int i=0;i<5;i++)ans+=DP[i][n];
        ans%=MOD;
    }
    printf("%I64d
",ans);
    return 0;
}
复制代码

PREV-16

无

PREV-17(约数倍数卡片)

dfs深搜，目測最后一组数据有错...

PREV-18

无

PREV-19(九宫重排)

bfs广搜，把九宫中的'.'换成'9'。这样每种状态就能够转换成一个9位整数表示，共9^9种状态，

用平衡树set容器维护已搜索的状态 队列维护已搜索到但未进行下一步搜索的状态

从初始状态開始广搜，每次遇到一种新状态时，把新状态存入平衡树set容器中。并增加到队列队尾

每次搜到一种状态推断是否已存在，假设存在无论它。继续搜索下一个状态

假设搜索到的状态是目标状态，停止搜索，假设队列为空，停止搜索

不难看出，每种状态最多搜索一次，时间复杂度最大为O(9!*lg(9!))

复制代码
#include<cstdio>
#include<set>
#include<queue>
using namespace std;
int Start,End,g[3][3],bfsnum[5],k,dx[]={0,0,-1,1},dy[]={-1,1,0,0};
char s[10];
set<int> Set;
queue<pair<int,int> > Que;
void bfs(int num){
    int x,y;
    for(int i=2;i>=0;i--){
        for(int j=2;j>=0;j--){
            g[i][j]=num%10;
            num/=10;
            if(g[i][j]==9){
                x=i;
                y=j;
            }
        }
    }
    k=0;
    for(int i=0;i<4;i++){
        int xx=x+dx[i],yy=y+dy[i];
        if(xx>=0 && xx<3 && yy>=0 && yy<3){
            int exc=g[xx][yy];
            g[xx][yy]=g[x][y];
            g[x][y]=exc;
            exc=0;
            for(int j=0;j<3;j++){
                for(int h=0;h<3;h++)
                    exc=exc*10+g[j][h];
            }
            bfsnum[k++]=exc;
            exc=g[xx][yy];
            g[xx][yy]=g[x][y];
            g[x][y]=exc;
        }
    }
}
int StoI(){
    int num=0;
    for(int i=0;i<9;i++)
        if(s[i]=='.')s[i]='9';
    for(int i=0;i<9;i++)num=num*10+s[i]-'0';
    return num;
}
int main()
{
    scanf("%s",&s);
    Start=StoI();
    scanf("%s",&s);
    End=StoI();
    if(Start==End){
        puts("0");
        return 0;
    }
    Set.insert(Start);
    Que.push(make_pair(0,Start));
    int ans=-1;
    while(!Que.empty()){
        int num=Que.front().second;
        int count=Que.front().first;
        Que.pop();
        bfs(num);
        for(int i=0;i<k;i++){
            if(bfsnum[i]==End){
                ans=count+1;
                break;
            }
            int cc=Set.count(bfsnum[i]);
            if(cc>0)continue;
            Set.insert(bfsnum[i]);
            Que.push(make_pair(count+1,bfsnum[i]));
        }
        if(ans>0)break;
    }
    printf("%d
",ans);
    return 0;
}
复制代码

PREV-20

无

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/wgwyanfs/p/6808310.html