蓝桥杯练习（三）

青旅半醒 2023-05-28 06:45 2阅读 0赞

### 蓝桥杯练习（三） ###

*   *   *  芯片测试
         *  分解质因数
         *  矩阵乘法
         *  矩阵乘方
         *  找零钱
         *  审美课
         *  参考博客

### 芯片测试 ###

**问题描述**  
　　有n（2≤n≤20）块芯片，有好有坏，已知好芯片比坏芯片多。  
　　每个芯片都能用来测试其他芯片。用好芯片测试其他芯片时，能正确给出被测试芯片是好还是坏。而用坏芯片测试其他芯片时，会随机给出好或是坏的测试结果（即此结果与被测试芯片实际的好坏无关）。  
　　给出所有芯片的测试结果，问哪些芯片是好芯片。  
**输入格式**  
　　输入数据第一行为一个整数n，表示芯片个数。  
　　第二行到第n+1行为n\*n的一张表，每行n个数据。表中的每个数据为0或1，在这n行中的第i行第j列（1≤i, j≤n）的数据表示用第i块芯片测试第j块芯片时得到的测试结果，1表示好，0表示坏，i=j时一律为1（并不表示该芯片对本身的测试结果。芯片不能对本身进行测试）。

#include<bits/stdc++.h>
    using namespace std;
    const int MAXN = 22;
    int g[MAXN][MAXN];
    int a[MAXN];
    
    
    int main(){ 
        int n;
        scanf("%d",&n);
        for(int i=0;i<n;++i){ 
            for(int j=0;j<n;++j)scanf("%d",&g[i][j]);
        }
        int t = 1<<n;//利用2进制可以进行子集选择
        int cnt = 0;//统计1的个数
        bool flag = false;//标记该方法的可行性
        for(int i=1;i<t;++i){ 
            for(int j=0;j<n;++j)a[j]=(i>>j)&1;
            cnt=0;
            for(int j=0;j<n;++j)if(a[j])cnt++;
            if(cnt<=n-cnt)continue;//好的比坏的多才满足题意
            flag = true;//默认可行
            for(int j=0;j<n;++j){ 
                if(!a[j])continue;//坏的没参考性
                for(int t=0;t<n;++t)if(g[j][t]!=a[t]){ flag=false;break;}
                if(!flag)break;
            }
            if(flag){ 
                int cntt=1;
                for(int j=0;j<n;++j){ 
                    if(a[j]){ 
                        if(cntt<cnt)printf("%d ",j+1);
                        else printf("%d",j+1);
                        cntt++;
                    }
                }
                break;
            }
        }
        return 0;
    }

### 分解质因数 ###

**问题描述**  
　　求出区间\[a,b\]中所有整数的质因数分解。  
**输入格式**  
　　输入两个整数a，b。  
**样例输入**  
3 10  
**样例输出**  
3=3  
4=2\*2  
5=5  
6=2\*3  
7=7  
8=2\*2\*2  
9=3\*3  
10=2\*5

#include<bits/stdc++.h>
    using namespace std;
    const int MAXN = 105;
    bool vis[MAXN];
    int  prime[MAXN],_index=0;
    void EuerPrime(){ 
        for (int i=2; i<MAXN; i++)
        { 
            if (!vis[i]) prime[_index++]=i;
            for(int j=0; j<_index&&prime[j]*i<MAXN; j++)
            { 
                vis[prime[j]*i]=1;
                if(i%prime[j]==0)break;
            }
        }
    }//欧拉筛法
    
    int main(){ 
        EuerPrime();
        int a,b,d,j,cnt;
        scanf("%d%d",&a,&b);
        for(int i=a;i<=b;++i){ 
            d = i;
            cnt = 0;
            printf("%d=",d);
            for(j=0;j<_index;++j){ 
                if(d<=prime[j])break;
                if(d%prime[j])continue;
                while(d%prime[j]==0){ 
                    if(cnt)printf("*");
                    printf("%d",prime[j]);
                    cnt++;
                    d/=prime[j];
                }
            }
            if(cnt&&d!=1)printf("*");
            if(d!=1)printf("%d",d);
            printf("\n");
        }
    }

### 矩阵乘法 ###

**问题描述**  
　　给定一个N阶矩阵A，输出A的M次幂（M是非负整数）  
　　例如：  
　　A =  
　　1 2  
　　3 4  
　　A的2次幂  
　　7 10  
　　15 22  
**输入格式**  
　　第一行是一个正整数N、M（1<=N<=30, 0<=M<=5），表示矩阵A的阶数和要求的幂数  
　　接下来N行，每行N个绝对值不超过10的非负整数，描述矩阵A的值

#include <bits/stdc++.h>
    using  namespace std;
    typedef long long ll;
    const int MAXN = 32;
    int tmp[MAXN][MAXN]={ 0};//用来暂存结果
    void matrixcopy(int a[][MAXN],int b[][MAXN],int n){ 
    		for(int i=0;i<n;i++)
    		for(int j=0;j<n;j++)a[i][j]=b[i][j];
    }//将矩阵B的内容赋值给矩阵A
    
    // 矩阵A(n*n)*矩阵B(n*n),并且结果保留在矩阵A中
    void mul(int a[][MAXN],int b[][MAXN],int n){ 
        int tmp[MAXN][MAXN]={ 0};//用来暂存结果
    	for(int i=0;i<n;i++)
    		for(int j=0;j<n;j++)
    			for(int k=0;k<n;k++)
    				tmp[i][j]+=a[i][k]*b[k][j];
    	matrixcopy(a,tmp,n);
    }
    
    void matrixquickpow(int a[][MAXN],int b,int n){ 
        int ans[MAXN][MAXN]={ 0};
    	for(int i=0;i<n;i++)ans[i][i]=1;//形成单位矩阵
    	while (b)
    	{ 
    		if(b&1)mul(ans,a,n);
    		mul(a,a,n);
    		b>>=1;
    	}
    	matrixcopy(a,ans,n);
    }//矩阵快速幂
    int t[MAXN][MAXN];
    int main(){ 
        int n,m;
        scanf("%d%d",&n,&m);
        for(int i=0;i<n;++i){ 
            for(int j=0;j<n;++j)scanf("%d",&t[i][j]);
        }
        matrixquickpow(t,m,n);
        for(int i=0;i<n;++i){ 
            for(int j=0;j<n-1;++j)printf("%d ",t[i][j]);
            printf("%d\n",t[i][n-1]);
        }
    }

### 矩阵乘方 ###

**问题描述**  
　　给定一个矩阵A,一个非负整数b和一个正整数m，求A的b次方除m的余数。  
　　其中一个nxn的矩阵除m的余数得到的仍是一个nxn的矩阵，这个矩阵的每一个元素是原矩阵对应位置上的数除m的余数。  
　　要计算这个问题，可以将A连乘b次，每次都对m求余，但这种方法特别慢，当b较大时无法使用。下面给出一种较快的算法(用A^b表示A的b次方)：  
　　若b=0，则A^b%m=I%m。其中I表示单位矩阵。  
　　若b为偶数，则Ab%m=(A(b/2)%m)^2%m，即先把A乘b/2次方对m求余，然后再平方后对m求余。  
　　若b为奇数，则Ab%m=(A(b-1)%m)\*a%m，即先求A乘b-1次方对m求余，然后再乘A后对m求余。  
　　这种方法速度较快，请使用这种方法计算A^b%m，其中A是一个2x2的矩阵，m不大于10000。  
**输入格式**  
　　输入第一行包含两个整数b, m，第二行和第三行每行两个整数，为矩阵A。

#include <bits/stdc++.h>
    using  namespace std;
    typedef long long ll;
    const int MAXN = 32;
    int tmp[MAXN][MAXN]={ 0};//用来暂存结果
    void matrixcopy(int a[][MAXN],int b[][MAXN],int n){ 
    		for(int i=0;i<n;i++)
    		for(int j=0;j<n;j++)a[i][j]=b[i][j];
    }//将矩阵B的内容赋值给矩阵A
    
    // 矩阵A(n*n)*矩阵B(n*n),并且结果保留在矩阵A中
    void mul(int a[][MAXN],int b[][MAXN],int n,int m){ 
        int tmp[MAXN][MAXN]={ 0};//用来暂存结果
    	for(int i=0;i<n;i++)
    		for(int j=0;j<n;j++)
    			for(int k=0;k<n;k++)
    				tmp[i][j]=(tmp[i][j]+a[i][k]*b[k][j])%m;
    	matrixcopy(a,tmp,n);
    }
    
    void matrixquickpow(int a[][MAXN],int b,int n,int m){ 
        int ans[MAXN][MAXN]={ 0};
    	for(int i=0;i<n;i++)ans[i][i]=1;//形成单位矩阵
    	while (b)
    	{ 
    		if(b&1)mul(ans,a,n,m);
    		mul(a,a,n,m);
    		b>>=1;
    	}
    	matrixcopy(a,ans,n);
        for(int i=0;i<n;++i){ 
            for(int j=0;j<n;++j)a[i][j]%=m;//当b=0
        }
    }//矩阵快速幂
    int t[MAXN][MAXN];
    int main(){ 
        int n=2,b,m;
        scanf("%d%d",&b,&m);
        for(int i=0;i<n;++i){ 
            for(int j=0;j<n;++j)scanf("%d",&t[i][j]);
        }
        matrixquickpow(t,b,n,m);
        for(int i=0;i<n;++i){ 
            for(int j=0;j<n-1;++j)printf("%d ",t[i][j]);
            printf("%d\n",t[i][n-1]);
        }
    }

### 找零钱 ###

**问题描述**  
　　有n个人正在饭堂排队买海北鸡饭。每份海北鸡饭要25元。奇怪的是，每个人手里只有一张钞票（每张钞票的面值为25、50、100元），而且饭堂阿姨一开始没有任何零钱。请问饭堂阿姨能否给所有人找零（假设饭堂阿姨足够聪明）  
**输入格式**  
　　第一行一个整数n，表示排队的人数。  
　　接下来n个整数a\[1\],a\[2\],…,a\[n\]。a\[i\]表示第i位学生手里钞票的价值（i越小，在队伍里越靠前）  
**输出格式**  
　　输出YES或者NO

#include <bits/stdc++.h>
    using  namespace std;
    
    int main(){ 
        int n,a=0,b=0,d;//总数，25，50
        scanf("%d",&n);
        for(int i=0;i<n;++i){ 
            scanf("%d",&d);
            if(d==25)a++;
            else if(d==50){ 
                a--;
                if(a<0){ 
                    printf("NO");
                    return 0;
                }
                b++;
            }else{ 
                if(b==0){ 
                    a-=2;
                }else { 
                    a--;
                    b--;
                }
                if(a<0){ 
                    printf("NO");
                    return 0;
                }
            }
        }
        printf("YES");
        return 0;
    }

### 审美课 ###

**问题描述**  
　　《审美的历程》课上有n位学生，帅老师展示了m幅画，其中有些是梵高的作品，另外的都出自五岁小朋友之手。老师请同学们分辨哪些画的作者是梵高，但是老师自己并没有答案，因为这些画看上去都像是小朋友画的……老师只想知道，有多少对同学给出的答案完全相反，这样他就可以用这个数据去揭穿披着皇帝新衣的抽象艺术了（支持帅老师\_）。  
　　答案完全相反是指对每一幅画的判断都相反。  
**输入格式**  
　　第一行两个数n和m，表示学生数和图画数；  
　　接下来是一个n\*m的01矩阵A：  
　　如果aij=0，表示学生i觉得第j幅画是小朋友画的；  
　　如果aij=1，表示学生i觉得第j幅画是梵高画的。

#include <bits/stdc++.h>
    using namespace std;
    int x[1<<20];
    int main()//利用2进制
    { 
        int n,m,d,ans=0;
        scanf("%d%d",&n,&m); 
        const int N =(1<<m)-1;
        for(int i=0;i<n;++i){ 
            int sum1=0,sum2=0;
            for(int j=0;j<m;++j){ 
                scanf("%d",&d);
                sum1=(sum1<<1)+d;//注意优先级
            }
            x[sum1]++;
            ans+=x[sum1^N];
        }
       printf("%d\n",ans);
    }

### 参考博客 ###

*  [蓝桥杯练习（一）][Link 1]
 *  [蓝桥杯练习（二）][Link 2]

[Link 1]: https://blog.csdn.net/qq_41146650/article/details/103479737
[Link 2]: https://blog.csdn.net/qq_41146650/article/details/105148589