牛客练习赛8

A.约数个数的和

我一眼看，还以为是用欧拉筛的方法线性求每个数的约数个数。

后来看了数据范围，好大1e8，又T又MLE怎么办。

换个方向，换个思路，发现考虑每个数作为因子对答案的贡献就可以轻易做出来了

时间复杂度O(n)

#include<bits/stdc++.h>
using namespace std;
int n,ans;
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)ans=ans+n/i;
    cout<<ans;
    return 0;
}

B. 储物点的距离

思维难度不高，但代码实现较难。

记几个前缀和数组。sum1=sigema(a[i]) , sum2=sigema(dis[i]) , sum3=sigema(a[i]*dis[i])

对于每个l和r，如果，

如果 ,

如果 ,这个情况就要复杂一点，

时间复杂度:O(n)

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=1000000007;
const int N=200005;
int n,m,x,l,r,a[N],dis[N],sum1[N],sum2[N],sum3[N];
signed main()
{
    scanf("%lld%lld",&n,&m);
    for(int i=2;i<=n;i++)
    {
        scanf("%lld",&dis[i]);
        dis[i]%=mod;
    }
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
        a[i]%=mod;
    }
    for(int i=1;i<=n;i++)
    {
        sum1[i]=(sum1[i-1]+a[i])%mod;
        sum2[i]=(sum2[i-1]+dis[i])%mod;
        sum3[i]=(sum3[i-1]+a[i]*sum2[i]%mod)%mod;
    }
    while(m--)
    {
        scanf("%lld%lld%lld",&x,&l,&r);
        if(x<=l)printf("%lld\n",((sum3[r]-sum3[l-1]-(sum1[r]-sum1[l-1])*sum2[x]%mod)%mod+mod)%mod);
        else if(x>=r)printf("%lld\n",(((sum1[r]-sum1[l-1])%mod*sum2[x]-(sum3[r]-sum3[l-1]))%mod+mod)%mod);
        else{
            int ans=0;
            ans+=(sum3[r]-sum3[x-1])-(sum1[r]-sum1[x-1])*sum2[x]%mod;
            ans+=-(sum3[x]-sum3[l-1])+(sum1[x]-sum1[l-1])*sum2[x]%mod;
            printf("%lld\n",(ans%mod+mod)%mod);
        }
    }
    return 0;
}

D. 加边的无向图

水题，答案就是联通块个数-1，就是把每一个联通块都连起来(边数就是联通块个数-1)。

维护联通块可以用并查集。

时间复杂度O(nlog(n)) (并查集有只log)

#include<bits/stdc++.h>
using namespace std;
const int N=100005;
int n,m,x,y,ans,fa[N],b[N];
int find(int x)
{
    if(fa[x]==x)return x;
    fa[x]=find(fa[x]);
    return fa[x];
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)fa[i]=i;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        int xx=find(x),yy=find(y);
        fa[xx]=yy;
    }
    for(int i=1;i<=n;i++)
        b[find(i)]=true;
    for(int i=1;i<=n;i++)
        if(b[i])ans++;
    cout<<ans-1;
    return 0;
}

E. 集合中的质数

一道容斥基础题(重复计数问题 )。

答案就是一个数的所有倍数-两个数的所有倍数+三个数的所有倍数......

时间复杂度O(2^n)

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,ans,a[25];
void dfs(int x,int gs,int sum)
{
    if(x==n+1)
    {
        if(gs==0)return;
        if(gs%2==1)ans+=m/sum;
        else ans-=m/sum;
        return;
    }
    dfs(x+1,gs+1,sum*a[x]);
    dfs(x+1,gs,sum);
}
signed main()
{
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
    dfs(1,0,1);
    cout<<ans;
    return 0;
}

F.重排的回文串

难题。我们先发现了一个性质：一个串能重排后成为回文串，仅当一个串每个元素异或起来后只剩一个元素。

我们可以用莫队来做，把那些能组成回文串的连边，维护以某个点为端点的答案。

每次左右端点移动，答案就加或减移动的那个点的答案。

时间复杂度:n根号n

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=60005;
struct node{
    int l,r,id;
}q[N];
int n,m,len,b[N],c[N],d[N],pos[N],num[N];
char s[N];
vectorf[N];
ll res,ans[N];
int cmp(node a,node b)
{
    return (a.l/len!=b.l/len)?a.lb.r;
}
void add(int x)
{
    res+=num[d[x]];
    for(int i=0;i<f[x].size();i++)res+=num[f[x][i]];
    num[d[x]]++;
}
void del(int x)
{
    num[d[x]]--;
    res-=num[d[x]];
    for(int i=0;i<f[x].size();i++)res-=num[f[x][i]];
}
int main()
{
    scanf("%d%d",&n,&m);
    len=sqrt(n);
    scanf("%s",s+1);
    for(int i=1;i<=n;i++)
    {
        s[i]-='a';
        c[i]=c[i-1]^(1<<s[i]);
        b[i]=c[i];
    }
    b[0]=0;
    sort(b,b+n+1);
    int Len=unique(b,b+n+1)-b;
    for(int i=1;i<=n;i++)d[i]=lower_bound(b,b+Len,c[i])-b;
    for(int i=0;i<=n;i++)
        for(int j=0;j<26;j++)
        {
            int pos=lower_bound(b,b+Len,c[i]^(1<<j))-b;
            if(pos<Len&&b[pos]==(c[i]^(1<<j)))f[i].push_back(pos);
        }
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&q[i].l,&q[i].r);
        q[i].l--;
        q[i].id=i;
    }
    sort(q+1,q+m+1,cmp);
    res=0;
    int l=1,r=0;
    for(int i=1;i<=m;i++)
    {     
        while(l<q[i].l)del(l++);
        while(l>q[i].l)add(--l);
        while(r<q[i].r)add(++r);
        while(r>q[i].r)del(r--);
        ans[q[i].id]=res;
    }
    for(int i=1;i<=m;i++)printf("%lld\n",ans[i]);
    return 0;
}