牛客练习赛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;
}