[数据结构与算法]20220407模拟赛总结

A.子串

题目大意：两个字符串$S,T$，改变$S$中的若干字符，使得$T$成为$S$的子串。其中$S,T$的长度不超过$1000$.

思路：$S,T$的长度不超过$1000$，暴力$O(|S||T|)$即可

B.数对乘积之和

题目大意：给出$N$个整数$A_1...A_n$，问两两数对相乘的总和为多少。答案$\mathrm{m}\mathrm{o}\mathrm{d}1e9+7$，其中$0<A_i<10^9,1\le N\le 10^6$

思路：求解$A$前缀和,根据乘法分配律求得。

错因：乘法是可以直接取模的，只有除法不能直接去模

//code B
#include<cstdio>
#include<iostream>
using namespace std;
typedef long long LL;
const int Mod=1e9+7;
const int N=2e5+5;
LL n,a[N],qzh[N],ans;
int main(){
    scanf("%lld",&n);
    for(int i=1;i<=n;i++) scanf("%lld",a+i),qzh[i]=qzh[i-1]+a[i];
    for(int i=1;i<=n;i++) ans=(ans+(a[i]*((qzh[n]-qzh[i])%Mod)))%Mod;
    printf("%lld",ans);
    return 0;
}

C.朋友

题目大意：有$N$个人，编号为$1,2.3...N$给你$M$个结论，诸如$A_i$和$B_i$是好朋友之类。相同的结论也许会给出多次。 如果$X$和$Y$是朋友，$Y$和$Z$是朋友，那么$X$和$Z$也是朋友。 现在请把这些人分成若干组，使得每一组没有两人是朋友。 最少能够分出来多少个这样的组。

数据范围：$2\le N\le 10^5,0\le M\le 2\times 10^5$

思路：关系拼凑成不同的集合，并查集求出最大集合即可

D.互质

题目大意：
有一个数组，有$N$个整数，分别为$A_1,A_2,A_3...A_n$. 如果对于任意的$i$和$j$,都满足$A_i$与$A_j$互质，则称数组A具有成对互质属性；
如果不满足成对互质属性，且 ,则称数组具有集合互质属性。
求给出的数组是具有哪一种属性? 如果是成对互质属性，输出“pairwise coprime”，否则如果是集合互质属性，输出“setwise coprime”，如果都不具备，输出“not coprime”。

数据范围：$2\le N\le 10^6,1\le A_i\le 10^6$

思路：
首先“not coprime”在输入时判断就好.

寒假集训讲过，与质数相关的题目一般两种，一种是$N$小$A$大从$N$入手的，另一种是$N$大$A$小从$A$入手的。
这里我们会发现，如果用第一种方法来做：

先用埃筛$O(\max A_i\log \max A_i)$求出所有质因数，再$O(170)$将每一个$A_i$分解小于1000质因数，留下最多一个超过1000的质因数，$N$个数之间不重复出现质因子即为“pairwise coprime”.

这样时间复杂度为$O(170N)$，过不了.

于是思考第二种方法：
同样使用埃筛，但在埃筛的过程中可以加一些操作：因为若$A_i$为此质数倍数时一定会被扫描到，
所以可以在筛一个质数的倍数时，可以统计扫描到了多少$A$数组中的数（这里的扫描要从该质数开始，不然$A_i$为质数的情况扫不到 例如数据$N=3$,$2$ $6$ $3$答案不为pair，我就是这么错的）大于1则不为pair.

然后时间复杂度就只有一个埃筛$O(\max A_i\log \max A_i)$了.

很不错。

//code D
#include<cstdio>
#include<cmath>
#include<iostream>
using namespace std;
const int N=1e6+5;
int n,sp,mxa,a[N],b[N],pri[N];
int gcd(int x,int y){return x%y==0?y:gcd(y,x%y);}
void prime(){
    for(int i=2;i<=mxa;i++){
        int cnt=0;
        if(!pri[i]){
            for(int j=1;i*j<=mxa;j++){
                pri[i*j]=1;
                if(b[i*j]) cnt+=b[i*j];
            }
            if(cnt>1){puts("setwise coprime");return ;}
        }
    }
    puts("pairwise coprime");
    return ;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",a+i);
        if(i==1) sp=a[i];
        else sp=gcd(sp,a[i]);
        mxa=max(mxa,a[i]);
        b[a[i]]++;
    }
    if(sp!=1) return puts("not coprime")&0;
    prime();
    return 0;
}

《新程序员》：云原生和全面数字化实践

50位技术专家共同创作，文字、视频、音频交互阅读