蓝桥杯练习（三）-蒲公英云

蓝桥杯练习（三）

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

芯片测试

问题描述
　　有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);
}