2014年蓝桥杯省赛个人题解

r囧r小猫 2023-07-10 15:37 25阅读 0赞

### 2014年蓝桥杯省赛个人题解 ###

*   *   *  神奇算式
         *   *  源代码
         *  蚂蚁感冒
         *  地宫取宝

请你写出：小明的较小的妹妹的年龄。

注意：只写一个人的年龄数字，请通过浏览器提交答案。不要书写任何多余的内容。

### 神奇算式 ###

> 由4个不同的数字，组成的一个乘法算式，它们的乘积仍然由这4个数字组成。  
> 比如：  
> 210 x 6 = 1260  
> 8 x 473 = 3784  
> 27 x 81 = 2187  
> 都符合要求。  
> 如果满足乘法交换律的算式算作同一种情况，那么，包含上边已列出的3种情况，一共有多少种满足要求的算式。  
> 请填写该数字，通过浏览器提交答案，不要填写多余内容（例如：列出所有算式）。

#### 源代码 ####

#include<bits/stdc++.h>
    using namespace std;
    
    bool check(int i1,int i2,int i3,int i4 ,int c){ 
        int a[10]={ 0};
        a[i1]++;
        a[i2]++;
        a[i3]++;
        a[i4]++;
        while(c){ 
            a[c%10]++;
            c/=10;
        }
        int ans=0;
        for(int i=0;i<10;++i)if(a[i]==2)ans++;
        return ans == 4;
    }
    
    int main(){ 
        int cns=0;
        for(int i1=1;i1<10;++i1){ 
            for(int i2=0;i2<10;++i2){ 
                if(i1==i2)continue;
                for(int i3=0;i3<10;++i3){ 
                    if(i2==i3||i1==i3)continue;
                    for(int i4=0;i4<10;++i4){ 
                        if(i1==i4||i2==i4||i3==i4)continue;
                        if(i2!=0&&check(i1,i2,i3,i4,i1*(i2*100+i3*10+i4))){ 
                            //cout<<i1<<"*"<<(i2*100+i3*10+i4)<<"="<<i1*(i2*100+i3*10+i4)<<endl;
                            cns++;
                        }
                        if(i3!=0&&check(i1,i2,i3,i4,(i1*10+i2)*(i3*10+i4))){ 
                            //cout<<(i1*10+i2)<<"*"<<(i3*10+i4)<<"="<<(i1*10+i2)*(i3*10+i4)<<endl;
                            cns++;
                        } 
                        if(i4!=0&&check(i1,i2,i3,i4,(i1*100+i2*10+i3)*i4)){ 
                            //cout<<(i1*100+i2*10+i3)<<"*"<<i4<<"="<<(i1*100+i2*10+i3)*i4<<endl;
                            cns++;
                        } 
                    }
                }
            }
        }
        cout<<ans/2<<endl;//A*B 和B*A 等价 
        //12
    }

### 蚂蚁感冒 ###

#include<bits/stdc++.h>
    using namespace std;
    
    struct Ant{ 
        int pos;//位置
        int v;//方向，1 正，-1 负
        bool flag;//是否感冒
        Ant(){ flag=false;}
        void set(int a,int b){ 
            pos=a;
            v=b;
        }
    };
    
    Ant ant[50]; 
    
    bool cmp(const Ant &a,const Ant &b){ 
        return a.pos<b.pos;
    }
    
    int main(){ 
        int n,d;
        scanf("%d",&n);
        for(int i=0;i<n;++i){ 
            scanf("%d",&d);
            d*=2;//由于移速为1，点是随机，蚂蚁相遇不一定在整数点，把坐标扩大2倍，易证蚂蚁在整数点相遇
            if(d>0)ant[i].set(d,1);
            else ant[i].set(-d,-1);
        }
        ant[0].flag=true;
        sort(ant,ant+n,cmp);//排序
        ///for(int i=0;i<n;++i)printf("%d %d\n",ant[i].pos,ant[i].v);
        int ans=0,cnt=0,left=0,right=n;
        while(left<right){ 
            cnt = 0;
            for(int i=left;i<right;++i){ 
                if(ant[i].pos==0||ant[i].pos==200)continue;
                cnt ++;
                ant[i].pos+=ant[i].v;
            }
            for(int i=1;i<right;++i){ 
                if(ant[i].pos==0||ant[i].pos==200)continue;
                if(ant[i].pos==ant[i-1].pos){ 
                    ant[i].v*=-1;
                    ant[i-1].v*=-1;
                    ant[i].flag=ant[i].flag||ant[i-1].flag;
                    ant[i-1].flag=ant[i].flag||ant[i-1].flag;
                }
            }
            if(ant[left].v==-1)ant[left++].pos=0;
            if(ant[right].v==1)ant[--right].pos=200;
            if(cnt==0)break;
        }
        for(int i=0;i<n;++i){ 
            if(ant[i].flag)ans++;
        }   
        printf("%d",ans);
    }

### 地宫取宝 ###

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    /* X 国王有一个地宫宝库。是 n x m 个格子的矩阵。每个格子放一件宝贝。每个宝贝贴着价值标签。 　　地宫的入口在左上角，出口在右下角。 　　小明被带到地宫的入口，国王要求他只能向右或向下行走。 　　走过某个格子时，如果那个格子中的宝贝价值比小明手中任意宝贝价值都大，小明就可以拿起它（当然，也可以不拿）。 　　当小明走到出口时，如果他手中的宝贝恰好是k件，则这些宝贝就可以送给小明。 　　请你帮小明算一算，在给定的局面下，他有多少种不同的行动方案能获得这k件宝贝。 　输入一行3个整数，用空格分开：n m k (1<=n,m<=50, 1<=k<=12) 　　接下来有 n 行数据，每行有 m 个整数 Ci (0<=Ci<=12)代表这个格子上的宝物的价值 */
    
    int n,m,k;
    int g[50][50];
    ll mem[50][50][12][14];
    const int mod = 1000000007 ;
    
    ll dfs(int i,int j,int v,int maxv){ 
        if(i>=n||j>=m||v>k) return 0;
        if(mem[i][j][v][maxv+1]!=-1)return mem[i][j][v][maxv+1];
        if(i==n-1&&j==m-1&&(v==k||(v==k-1&&g[i][j]>maxv)))return mem[i][j][v][maxv+1]=1;
        int t=0;
        if(g[i][j]>maxv)t=dfs(i+1,j,v+1,g[i][j])%mod+dfs(i,j+1,v+1,g[i][j])%mod;
        return mem[i][j][v][maxv+1]=(t%mod+dfs(i+1,j,v,maxv)%mod+dfs(i,j+1,v,maxv)%mod)%mod;
    }
    
    int main(){ 
        scanf("%d%d%d",&n,&m,&k);
        for(int i=0;i<n;++i){ 
            for(int j=0;j<m;++j){ 
                scanf("%d",&g[i][j]);
            }
        }
        memset(mem,-1,sizeof(mem));
        printf("%d",dfs(0,0,0,-1));
        return 0;
    }